deadlock (a brief introduction)

I just want to introduce you now to one of the problems with concurrency and waiting. We've talked about race conditions. Race conditions occur when two or more processes are unconstrained, and do not wait their turn when accessing some resource. A deadlock is the opposite problem. In the case of a deadlock, two or more processes are held up forever, waiting on each other.

As a very simple example, assume that two unshareable resources; two files say, are protected by semaphores. Two processes, A and B want to use both resources. Process A locks file 1, then locks file 2; process B tries to lock file 2, then lock file 1. As is the case with the race condition, if the two processes execute one after the other, there is no problem. If however, process B runs, just after process A has locked on of the files, process B will succeed in locking the other file, and be unable to lock the first file. Process A is unable to lock the second file too, since B has locked it.

Effectively, process A is locked, waiting for B, and B is locked, waiting for A. Sometimes known as 'the deadly embrace', it is now more commonly---and less glamorously known as deadlock. Kind of similar to gridlock.

We'll look at ways round the problem later on, but the best way around deadlock, is to design your system carefully.


last updated 13 February 1998