Module 7: Deadlocks

Introduction

This module covers one chapter in your text – Chapter 6 on Deadlocks.

Deadlocks are caused by a process holding a resource while requesting another resource. Deadlocks
can occur in operating systems which support multiple processes (as most modern operating systems do
today). We will discuss the conditions that can cause deadlocks, how to identify them if they occur, and
most importantly how to avoid them in the first place. There are several classical methods discussed in
your reading.

Definition of Deadlock

Let's first summarize some of the essential elements from your reading. The definition of deadlock is on
page 444 of your text:

A set of processes is deadlocked if each process in the set is waiting for an event that only another
process in the set can cause.

This should be pretty clear — if all the processes are waiting (not running), then they cannot cause the
event that some other process is waiting for.

Next, you should recall the four conditions for deadlock (page 445):

• Mutual Exclusion
• Hold and wait
• No preemption
• Circular wait

Note that these four conditions are necessary for deadlock to occur, but they may not be sufficient. That
is, in a given situation, you may have all four of these conditions, but deadlock may not be present. On
the other hand, if in any situation, one of those conditions is not present, then there cannot be deadlock.
So, one approach to avoiding deadlock is assuring that all four of these conditions cannot be true at the
same time. (These conditions are sufficient for deadlock in the case that there is only one instance of a
resource in a system.)

It is interesting to note that in order to have ‘circular wait’, you do have to have a hold-and-wait condition –
so, there are really three necessary conditions, not four. But, the literature always asserts that these four
conditions are necessary. Why? Perhaps the answer lies in the fact that each of the four conditions,
although not independent, are needed for deadlock, so to prevent deadlock, you only need to prevent one
of the four. Preventing the hold and wait naturally prevents the circular wait, but you could prevent the
circular wait while still allowing the hold and wait. In other words, preventing hold-and-wait would be a
heavier-handed approach to preventing deadlock. Another observation is that the first three conditions
are ‘policy’ based, whereas the fourth condition is one that arises from a sequence of events.

So, mathematically, you can say only the three conditions need to be present, with ‘hold-and-wait’ being a
part of the definition for the circular wait. You can blame Coffman for the original way he laid it out:
(https://jhu.instructure.com/files/5999401/download?download_frd=1).
Resource Graphs

Resource graphs (I typically call these “resource allocation graphs) are discussed in section 6.4.3 of the
text. The supplied video in the course content takes a look at a few examples of these graphs and how
they can help identify deadlock.

The Banker's Algorithm

The Banker's Algorithm is first described for a single resource type. For example, if processes need
multiple storage devices such as tape drives to perform some task, then consider if a system has three
storage devices and three processes that each might require two storage devices to perform their task. If
each process gets one of the storage devices, and then has to wait for the other, there is a deadlock
situation, since all have one and are waiting for the other, but none can release the one they have until
they get one to complete their task. (Sounds similar the dining philosopher problem, which can
experience deadlock if all the philosophers get one fork at the same time.) The Banker's algorithm
prevents this deadlock situation by avoiding giving a resource that could otherwise be given if it puts the
system in an unsafe state where deadlock might occur.

Make sure you review the section in the text that describes this algorithm, and then view the video in the
course content area that walks through an example.

Once the Banker's algorithm for a single resource is understood, extending this to multiple resources (as
discussed on pp. 459–461 of your text) can be more easily understood. Be sure to read through it, and
maybe we will look at this your problem set.

Resource Trajectories

Another method to examine deadlock detection and avoidance is the use of Resource Trajectories. A
graph of resource trajectories is a method to examine resource usage by processes when two resources
are in play. The short video in the module content area discusses the example in your text on pages 456-
457 in a slightly different way.

Dealing with Deadlocks

For the most part, most modern operating systems do not see too many deadlocks. In the worst case, a
deadlock in the system might require some processes to be forcibly killed (essentially getting rid of the
"no preemption condition" required for deadlock) and in the worst case, the system might require a
reboot.

Tanenbaum discusses the "Ostrich Algorithm", which implies that most operating system designers
simply ignore the problem and will just hope it doesn't happen. Of course, insofar as a kernel developer
can, the developer will design the system so there are no deadlocks at least as far as the kernel
developer can control. But with externally developed device drivers that can be loaded dynamically, there
is not much a kernel developer can do to prevent deadlocks there. However, with the microkernel
approach, device drivers can be essentially system processes that can be easily rebooted (without
rebooting the entire system, so that helps).

Tanenbaum mentions contention for some of the finite resources in operating systems, such as process
slots, which is a problem I have seen first-hand as an instructor. In my System Development in the UNIX
Environment class, we learn about forking new processes, and occasionally a student might accidentally
create a program that forks indefinitely. This fills up the process table, and in some cases the only way to
fix this problem (since even an administrator cannot create a process to kill other processes if the process
table is full) is to reboot the system. Another way to deal with it is to set resource limits on a per-user
basis, so if a student deadlocks their account, at least they don't deadlock the system. And in this case,
an administrator could kill the user's process causing the deadlock to rectify the situation.

In addition to the "Ostrich Algorithm", what were the other two methods of dealing with deadlocks
discussed in the text? One method was detection and recovery — of which the aforementioned killing of
deadlocking processes is one example, at least of the recovery part. The other methods were of the
"Deadlock Prevention" variety, which were techniques described above: the Banker's Algorithm, and
Resource Trajectories.