Operating Systems: Concurrent and Distributed Software Design

18.2. Deadlock

A simple example of deadlock was given in Section 17.5. In that case, process P had locked object A for exclusive use and went on to request object B. Process Q had already locked object B. Deadlock occurs when process Q proceeds to request object A.

Figure 18.1 illustrates this problem. It shows the progress of processes P and Q when they are scheduled to run on a single processor, that is, only one at a time can run. Their behaviour is that each acquires one object and, while still holding it, requests the other. Paths i, j, k, l, m, n illustrate different possible dynamic behaviours of the two processes. In i and j, process P acquires both A and B before process Q requests B. In k and l, process Q acquires both B and A before ...