SPRING 2002
DEADLOCK
Laura A. Weiland
(http:// compsci.snc.edu/cs460_2002/weilla/)
Part 1: Project Description (8-10 minutes)
A.
Definition and Requirements:
Project Description: Implement a module to the Train Operation System (TOS) that manages the deadlock problem for the Computer Controlled Railroad (CCR).
Inherited: Jeremy Vosters 2001 project (VOS) was the basis
from which I started where the problem was ignored. Dr. McVey had made some modifications to VOS that would not allow
trains to start in a blocked state, thus they could not start in deadlock.
Requirements:
·
Extend
or redesign the TOS that currently prevents collisions.
·
Detect
deadlock and report it.
·
Recover
from deadlock by removing processes (trains).
·
Recover
from deadlock by removing resources (track).
·
Avoid
a deadlock state when possible.
·
Prevent
deadlock from occurring.
·
All
solutions will create a log file recording the state of the system at each step
taken for recovery, avoidance, etc.
·
Modify
the TOS initialization module so that it will prevent a start-up that is
deadlocked, or identify that it is initially deadlocked.
B.
Solution(s):
·
Allow
for direction changes under batch processing.
·
Detection
and resolution to processes sliding past photocells.
·
Deadlock
is detected by hashing through an indexed array structure searching for a
circular pattern.
·
Deadlock
is recovered by moving a train with highest id number that is able to revert
back one instruction in its instruction sequence.
·
Deadlock
is avoided when possible using the yellow light method adopted from
train signaling today.
C.
Exceptions:
·
Recovery
from deadlock by removing processes (trains).
·
This
form of recovery was not explored due to its impracticality in a real-life
situation.
·
Prevent
deadlock from occurring.
·
Suggestion
– Given the current layout, it would take 6 trains to put the system into a
visually circular deadlock. Thus, to
prevent deadlock, never allow more than 5 trains to exist on the track AND only
allow traffic to flow in a single direction.
D.
Methodology:
·
Batch
Processing – Interactive processing allowed for various unknown variables
·
Deadlock
detection
·
Generated
a simulator that given the indexed array would detect deadlock
·
No
trains necessary for testing algorithm
·
Recovery
·
Trains
are released by increasing train id number, thus to recover using a train with
a low id number resulted in the two trains oscillating.
·
A
train needs to be checked for recovery potential before the recovery process is
put into motion. Failure to do so could
result in an infinite loop of deadlock.
·
Avoidance
·
Used
the yellow light method adopted from train signals practiced today.
·
The
section(s) of track directly proceeding the section you currently own are
marked with a yellow light to signify to another train that you might be
entering this section of track next.
Part 2: Demonstration (8-10 minutes)
·
Demonstration
showing two processes participating in deadlock. This will show the recovery method where there are no other
processes involved.
·
Demonstration
with three processes.
·
Two
processes in deadlock, the other process running.
·
Two
processes in deadlock, the other process blocked.
A.
Strategies:
I found I accomplished the most when I was away from
the computer. I was able to look at the
problem at a higher level, concentrating more on the overall algorithm rather
than the details of syntax. I also
found several answers to various problems in the log file that was
generated. The trains are only a
visual. The log file allowed me to see
where and why a sequence of events did not work.
B.
Knowledge:
The OS class was essential to understanding the problem and its developing solutions. I had also taken an independent study during my sophomore year where I was first exposed to CCR and worked alongside Jeremy Vosters to devise some of the basic OS ideas that he put into place for his senior capstone project.
C.
Extensions:
Artificial Intelligence (AI) – The train project lends way for various AI opportunities. Currently, the train with the largest id number not blocked by another train recovers the instance of deadlock. Although it may make the algorithm more track-specific, an order of operations for deadlock recovery could be devised to use the train with the smallest possibility of generating another instance of deadlock.
D.
Advice:
Plan ahead! It was helpful to break the overall problem into smaller, more manageable sections that can be assigned concrete deadlines. Once this is done, make sure to follow them! Test, test, and then test some more. Many problems do not show up on the first test, so test thoroughly. It is also important to learn the environment that you will be working with, but don’t get hung up on details of coding in the beginning.
E.
Overall
Experience:
I think it is important to evaluate what you have
learned with each new experience, and this one has taught me many things. It taught me organization, time management,
proper means of experimentation, analysis of results, and patients. I believe this style of evaluation brought
out the science in computer science.
It will also be nice to have had an experience such as this before I
enter graduate school and have to prepare a defense for my thesis.