Consider a pair of processes, in which each process attempts to receive a message from the other process and then send a message to the other proces

• Table of Contents

Principles of Deadlock

As we briefly covered last week, deadlock is the permanent blocking of a set of — two or more —processes that either compete for system resources or communicate with each other. We can spot a potential deadlock from occurring in quadrants a to d.

Figure 6.1 Illustration of deadlock.

Now let’s look at a depiction of deadlock involving processes and computer resources. Consider the following set of instructions by processes P and Q.

Figure 6.2 Execution of processes P and Q.

Here, we have two processes, who each needs an exclusive access to a resource A and B for a period of time. The joint progress diagram illustrates this progress of two processes competing for two resources.

Figure 6.1 Example of deadlock.

• Similar to the car analogy, we can spot a potential deadlock from occurring, given one of many execution paths. The numbered arrows depict six different execution paths.

<aside> <img src="/icons/map-pin_gray.svg" alt="/icons/map-pin_gray.svg" width="40px" /> Deadlock is only inevitable if the joint progress of the two processes creates a path that enters the fatal region.

</aside>

When process P tries to get B or process Q tries to get A, it will get blocked, because the other process is currently using it. To prevent potential deadlock, each process needs exclusive use of both resources for a certain period of time.

Figure 6.3 Example of no deadlock.

In cases where more than two processes may compete for the same resource, a higher dimensional diagram would be required, but the principles would remain the same. There are two general categories of resources can be distinguished: reusable and consumable.

Reusable Resource

A reusable resource is one that can be safely used by only one process at a time and is not depleted by that use. These are processors, I/O channels, main and secondary memory, devices, and data structures — e.g. semaphores.

Figure 6.4 Example of two processes competing for reusable resources.

<aside> <img src="/icons/map-pin_gray.svg" alt="/icons/map-pin_gray.svg" width="40px" /> In this context, Unlock() is like releasing the resource and Request() and Lock() means acquire the resource.

</aside>

Consider two processes that compete for exclusive access to a disk file D and a tape drive T. Deadlock occurs if each process holds one resource and requests the other.