Illustrating deadlock

"When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone."
  -- early 20th century Kansas state statute

Just outside Dodge City they are still waiting.


The exercise for you to perform

Operate in an instance of the provided VirtualBox virtual machine. Log in a student, launch the graphical desktop, and open  a terminal window. Within it:

terminator  -f  &

Operate as root in a terminal window within your graphical environment. Create a working directory for this exercise:

cd
mkdir deadlock
cd deadlock

Obtain the programs, in the form of file deadlockers.zip. In the provided VirtualBox environment it can be found in the /home.public directory. Get a copy of it in your "deadlock" directory and unzip it there:

cp  /home/public/deadlockers.zip  ~/deadlock
unzip  deadlockers.zip

It contains 2 scripts, "deadlock" and "deadlock-prevented".

Run deadlock:

./deadlock

It complains. You need to tell it the name of one or more files which it must create before it gets to work. However, it will create such files only if they do not already exist. If one of the files it wants to create does exist, deadlock will just wait. And it will wait until the existing file disappears, so that it can then go ahead and create it. But if the file never disappears, deadlock will be waiting for... ever. It will be stuck; it will be deadlocked. Run it again, properly this time giving it the name of a file it must create. How about "a":

./deadlock  a

It does not have the problem described above, because no file named "a" exists already. So it creates "a", gets down to work, and when finished deletes "a" as a matter of clean-up. Try it with 3 files:

./deadlock  a  b  c

The problem of deadlock occurs when there are two agents both trying to do this sort of thing at the same time. So have terminator split its terminal window in two, horizontally. To do that, either right-click and follow the sub-menu or give the ctrl-shift-O keystroke. Now you have two terminal windows within which you can work. You can switch back and forth between them by clicking on the one you want, or toggle with the ctrl-Tab keystroke. In both windows, clear the screen and type the "deadlock" command without however hitting the enter key yet:

clear
./deadlock  a  b
   [but don't hit the enter key yet]

When this is set up in both windows you'll get them both running simultaneously by hitting the enter key in one, then switching quickly to the other and pressing enter over there too. Do it and watch what happens. Both of them will do their work, but the one that is launched second will wait before doing so until the one launched first finishes. That's because the first one created file "a" before the second one came along to do so. Remember, as stated above, "... it will create such files only if they do not already exist." When the second copy of the program ran, one or more of them do exist, because the first copy has created it/them. The second copy must wait for the first one to finish and get out of the way,  i.e., delete the file(s), before it is allowed to proceed.

So far, there is no deadlock here. But that arises when you ask the programs to create 2 files, if you tell them to do so in the opposite order. This time, in the first window:

clear
./deadlock  a  b
   [but don't hit the enter key yet]

and in the second window:

clear
./deadlock  b  a
   [but don't hit the enter key yet]

Now you will select the first window and hit enter, then quickly (within 3 seconds) switch to the second and do the same. It should be clear from the screen messages what has happened. Both programs were able to create their first file, but each program's first file was the other's second. When they got to creating their second file they found it created already, so entered a wait for that file to disappear. Both programs will make the files disappear, at the end, but now they neither of them will ever reach the end because they are forever waiting for the other to do so.. they are embraced in a deadlock. Neither ever "does work." But as long as they both ask for the files in the same order "a b c" versus "a b c" no deadlock will occur. Interrupt both programs with a ctrl-C keystroke. Then, in either window:

rm  a
rm  b

(either window works because both are dealing with the same fileset). This is necessary to give the programs a clean starting point if you wish to run them further. Experiment with different combinations and ordering of filenames given to the two programs and understand in what circumstances this program can enter deadlock.

A way this program could be improved, to avoid the deadlock we suffered above, would be to insert an up-front test that determines that none of the required files pre-exists. Only then, knowing the coast is clear, would the program embark on creating the files. The "deadlock-prevented" program does this. Run the same scenario in which you experienced deadlock above and observe the new behavior:

In the first window:

clear
./deadlock-prevented  a  b
   [but don't hit the enter key yet]

and in the second window:

clear
./deadlock-prevented  b  a
   [but don't hit the enter key yet]

Now do the doubletime-quick-start., boom boom. There's no deadlock this time. That's an improvement, but no solution. Try this:

clear
./deadlock-prevented  a  b  c
   [but don't hit the enter key yet]

and in the second window:

clear
./deadlock-prevented  c  b
   [but don't hit the enter key yet]

And quick start. The first program created "a" just fine but it took too long because but beyond that you have the programs going after "b-and-c" and "c-and-b" in those opposite orders. That's the original deadlock situation all over again! So there are timing issues. And other issues. This is a hard problem. Suppose even you could get this program perfect. Then it would never run afoul of another copy of itself. But a different program that might create files of these names, and not contain any special checks, could still stop our program in its tracks. So could you, manually, just by creating one of the strategically named files yourself.

This, at the level of an application, is representative of the kind of problem encountered by multiple copies of code contending for common resources. Backing into a deadlock, painting yourself into a corner, is something that a coder can easily and unexpectedly do. The real problem comes not within applications, but within operating systems. Multi-process, multi-user operating systems engage in such contention routinely and frequently. Deadlock was one of the problems that challenged early operating systems.


What to turn in

Defeat deadlock-prevented. Force it into a deadlock.by some combination of filename arguments that you give it. Once you have it in deadlock, the programs in both windows will be forever printing their "waiting for..." messages. First clear the screen, then give your deadlock-prevented commands at the prompt at the top of the screen, then after the programs are in deadlock for a minute or so interrupt them both with ctrl-C keystrokes. Your commands and the evidence of deadlock must be visible. Take a screenshot at that point and upload it.