Deadlocks

Question 1

Give an example of a deadlock taken from politics.

Answer 1

In the U.S., consider a presidential election in which three or more candidates are trying for the
nomination of some party. After all the primary elections are finished, when the delegates
arrive at the party convention, it could happen that no candidate has a majority and that no
delegate is willing to change his or her vote. This is a deadlock. Each candidate has some
resources (votes) but needs more to get the job done. In countries with multiple political parties
in the parliament, it could happen that each party supports a different version of the annual
budget and that it is impossible to assemble a majority to pass the budget. This is also a
deadlock.

Question 2

Students working at individual PCs in a computer laboratory send their files to be printed
by a server that spools the files on its hard disk. Under what conditions may a deadlock occur
if the disk space for the print spool is limited? How may the deadlock be avoided?

Answer 2

Disk space on the spooling partition is a finite resource. Every block that comes in de facto
claims a resource and every new one arriving wants more resources. If the spooling space is,
say, 10 MB and the first half of ten 2-MB jobs arrive, the disk will be full and no more blocks can
be stored so we have a deadlock. The deadlock can be avoided by allowing a job to start printing
before it is fully spooled and reserving the space thus released for the rest of that job. In this
way, one job will actually print to completion, then the next one can do the same thing. If jobs
cannot start printing until they are fully spooled, deadlock is possible.

Question 3

In the preceding question (Students working at individual PCs in a computer laboratory send their files to be printed by a server that spools the files on its hard disk.), which resources are preemptable and which are
nonpreemptable?

Answer 3

The printer is nonpreemptable; the system cannot start printing another job until the previous
one is complete. The spool disk is preemptable; you can delete an incomplete file that is
growing too large and have the user send it later, assuming the protocol allows that.

Question 4

In Fig. 6-1 (https://imgur.com/a/jtqLB7X) the resources are returned in the reverse order of their acquisition. Would giving
them back in the other order be just as good?

Answer 4

Yes. It does not make any difference whatsoever.

Question 5

The four conditions (mutual exclusion, hold and wait, no preemption and circular wait) are
necessary for a resource deadlock to occur. Give an example to show that these conditions
are not sufficient for a resource deadlock to occur. When are these conditions sufficient for a
resource deadlock to occur?

Answer 5

Suppose that there are three processes, A, B and C, and two resource types, R and S. Further
assume that there are one instance of R and two instance of S. Consider the following execution
scenario: A requests R and gets it; B requests S and gets; C requests S and gets it (there are two
instances of S); B requests R and is blocked; A requests S and is blocked. At this stage all four
conditions hold. However, there is no deadlock. When C finishes, one instance of S is released
that is allocated to A. Now A can complete its execution and release R that can be allocated to
B, which can then complete its execution. These four conditions are enough if there is one
resource of each type.

Question 6

City streets are vulnerable to a circular blocking condition called gridlock, in which
intersections are blocked by cars that then block cars behind them that then block the cars
that are trying to enter the previous intersection, etc. All intersections around a city block are
filled with vehicles that block the oncoming traffic in a circular manner. Gridlock is a resource
deadlock and a problem in competition synchronization. New York City’s prevention
algorithm, called ‘don’t block the box,’ prohibits cars from entering an intersection unless the
space following the intersection is also available. Which prevention algorithm is this? Can you
provide any other prevention algorithms for gridlock?

Answer 6

“Don’t block the box” is a pre-allocation strategy, negating the hold and wait deadlock
precondition, since we assume that cars can enter the street space following the intersection,
thus freeing the intersection. Another strategy might allow cars to temporarily pull into garages
and release enough space to clear the gridlock. Some cities have a traffic control policy to shape
traffic; as city streets become more congested, traffic supervisors adjust the settings for red
lights in order to throttle traffic entering heavily congested areas. Lighter traffic ensures less
competition over resources and thus lowers the probability of gridlock occurring.

Question 7

Suppose four cars each approach an intersection from four different directions
simultaneously. Each corner of the intersection has a stop sign. Assume that traffic regulations
require that when two cars approach adjacent stop signs at the same time, the car on the left
must yield to the car on the right. Thus, as four cars each drive up to their individual stop
signs, each waits (indefinitely) for the car on the left to proceed. Is this anomaly a
communication deadlock? Is it a resource deadlock?

Answer 7

(FFE18)
The above anomaly is not a communication deadlock since these cars are independent of each
other and would drive through the intersection with a minimal delay if no competition occurred.
It is not a resource deadlock, since no car is holding a resource that is requested by another car.
Nor would the mechanisms of resource pre-allocation or of resource preemption assist in
controlling this anomaly. This anomaly is one of competition synchronization, however, in which
cars are waiting for resources in a circular chain and traffic throttling may be an effective
strategy for control. To distinguish from resource deadlock, this anomaly might be termed a
“scheduling deadlock”. A similar deadlock could occur following a law that required two trains
merging onto a shared railroad track to wait for the other to proceed. Note that a policeman
signaling one of the competing cars or trains to proceed (and not the others) can break this
dead state without rollback or any other overhead.

Question 8

Is it possible that a resource deadlock involves multiple units of one type and a single unit
of another? If so, give an example.

Answer 8

(TUT13)
It is possible that one process holds some or all of the units of one resource type and requests
another resource type, while another process holds the second resource while requesting the
available units of the first resource type. If no other process can release units of the first
resource type and the resource cannot be preempted or used concurrently, the system is
deadlocked. For example, two processes are both allocated memory cells in a real memory
system. (We assume that swapping of pages or processes is not supported, while dynamic
requests for memory are supported.) The first process locks another resource - perhaps a data
cell. The second process requests the locked data and is blocked. The first process needs more
memory in order to execute the code to release the data. Assuming that no other processes in
the system can complete and release memory cells, a deadlock exists in the system.

Question 9

Fig. 6-3 (https://imgur.com/a/zNOS9Js) shows the concept of a resource graph. Do illegal graphs exist, that is, graphs that
structurally violate the model we have used of resource usage? If so, give an example of one.

Answer 9

Yes, illegal graphs exist. We stated that a resource may only be held by a single process. An arc
from a resource square to a process circle indicates that the process owns the resource. Thus, a
square with arcs going from it to two or more processes means that all those processes hold the
resource, which violates the rules. Consequently, any graph in which multiple arcs leave a
square and end in different circles violates the rules unless there are multiple copies of the
resources. Arcs from squares to squares or from circles to circles also violate the rules.

Question 10

Consider Fig. 6-4 (https://imgur.com/a/NX5BFXM). Suppose that in step (o) C requested S instead of requesting R. Would
this lead to deadlock? Suppose that it requested both S and R.

Answer 10

Neither change leads to deadlock. There is no circular wait in either case.

Question 11

Suppose that there is a resource deadlock in a system. Give an example to show that the
set of processes deadlocked can include processes that are not in the circular chain in the
corresponding resource allocation graph.

Answer 11

Consider three processes, A, B and C and two resources R and S. Suppose A is waiting for I that is
held by B, B is waiting for S held by A, and C is waiting for R held by A. All three processes, A, B
and C are deadlocked. However, only A and B belong to the circular chain.

Question 12

In order to control traffic, a network router, A periodically sends a message to its
neighbor, B, telling it to increase or decrease the number of packets that it can handle. At
some point in time, Router A is flooded with traffic and sends B a message telling it to cease
sending traffic. It does this by specifying that the number of bytes B may send (A’s window
size) is 0. As traffic surges decrease, A sends a new message, telling B to restart transmission.
It does this by increasing the window size from 0 to a positive number. That message is lost.
As described, neither side will ever transmit. What type of deadlock is this?

Answer 12

This is a communication deadlock, and can be controlled by having A time out and retransmit its
enabling message (the one that increases the window size) after some period of time (a
heuristic). It is possible, however, that B has received both the original and the duplicate
message. No harm will occur if the update on the window size is given as an absolute value and
not as a differential. Sequence numbers on such messages are also effective to detect
duplicates.

Question 13

The discussion of the ostrich algorithm mentions the possibility of process-table slots or
other system tables filling up. Can you suggest a way to enable a system administrator to
recover from such a situation?

Answer 13

A portion of all such resources could be reserved for use only by processes owned by the
administrator, so he or she could always run a shell and programs needed to evaluate a
deadlock and make decisions about which processes to kill to make the system usable again.

Question 14

Consider the following state of a system with four processes, P1, P2, P3, and P4, and five
types of resources, RS1, RS2, RS3, RS4, and RS5:
(https://imgur.com/a/SYuSlhq)
Using the deadlock detection algorithm described in Section 6.4.2, show that there is a
deadlock in the system. Identify the processes that are deadlocked.

Answer 14

(TUT13)
First, the set of unmarked processes, P = (P1 P2 P3 P4)
● R1 is not less than or equal to A
● R2 is less than A; Mark P2; A = (0 2 0 3 1); P = (P1 P3 P4)
● R1 is not less than or equal to A
● R3 is equal to A; Mark P3; A = (0 2 0 3 2); P = (P1 P4)
● R1 is not less than or equal to A
● R4 is not less than or equal to A
Processes P1 and P4 remain unmarked that means they are deadlocked

Question 15

Consider the following state of a system with four processes, P1, P2, P3, and P4, and five
types of resources, RS1, RS2, RS3, RS4, and RS5:
(https://imgur.com/a/SYuSlhq)
Explain how the system can recover from the deadlock in this problem using
a) recovery through preemption.
b) recovery through rollback.
c) recovery through killing processes.

Answer 15

(TUT13)
Answer:
a) Recovery through preemption: After processes P2 and P3 complete, process P1 can be
forced to preempt 1 unit of RS3. This will make A = (0 2 1 3 2), and allow process P4 to
complete. Once P4 completes and release its resources P1 may complete.
b) Recovery through rollback: Rollback P1 to the state checkpointed before it acquired RS3.
Recovery through killing processes:
c) Kill P1.

Question 16

Suppose that in Fig. 6-6 (https://imgur.com/a/fHXmMrJ) Cij + Rij > E j for some i. What implications does this have for the
system?

Answer 16

The process is asking for more resources than the system has. There is no conceivable way it can
get these resources, so it can never finish, even if no other processes want any resources at all.

Question 17

All the trajectories in Fig. 6-8 (https://imgur.com/a/JjHRXwh) are horizontal or vertical. Can you envision any circumstances in which diagonal trajectories are also possible?

Answer 17

If the system had two or more CPUs, two or more processes could run in parallel, leading to
diagonal trajectories.

Question 18

Can the resource trajectory scheme of Fig. 6-8 (https://imgur.com/a/JjHRXwh) also be used to illustrate the problem of
deadlocks with three processes and three resources? If so, how can this be done? If not, why
not?

Answer 18

Yes. Do the whole thing in three dimensions. The z-axis measures the number of instructions
executed by the third process.

Question 19

In theory, resource trajectory graphs could be used to avoid deadlocks. By clever
scheduling, the operating system could avoid unsafe regions. Is there a practical way of
actually doing this?

Answer 19

The method can only be used to guide the scheduling if the exact instant at which a resource is
going to be claimed is known in advance. In practice, this is rarely the case.

Question 20

Can a system be in a state that is neither deadlocked nor safe? If so, give an example. If
not, prove that all states are either deadlocked or safe.

Answer 20

There are states that are neither safe nor deadlocked, but which lead to deadlocked states. As
an example, suppose we have four resources: tapes, plotters, scanners, and CD-ROMs, as in the
text, and three processes competing for them. We could have the following situation:
https://imgur.com/a/FaznCfp
This state is not deadlocked because many actions can still occur, for example, A can still get
two printers. However, if each process asks for its remaining requirements, we have a deadlock.

Question 21

Take a careful look at Fig. 6-11(b) (https://imgur.com/a/WDUgN39). If D asks for one more unit, does this lead to a safe state
or an unsafe one? What if the request came from C instead of D?

Answer 21

A request from D is unsafe, but one from C is safe.

Question 22

A system has two processes and three identical resources. Each process needs a maximum
of two resources. Is deadlock possible? Explain your answer.

Answer 22

(TUT13)
The system is deadlock free. Suppose that each process has one resource. There is one resource
free. Either process can ask for it and get it, in which case it can finish and release both
resources. Consequently, deadlock is impossible.

Question 23

Consider the previous problem again (a system has two processes and three identical resources. Each process needs a maximum
of two resources), but now with p processes each needing a maximum
of m resources and a total of r resources available. What condition must hold to make the
system deadlock free?

Answer 23

(TUT13)
If a process has m resources it can finish and cannot be involved in a deadlock. The worst case is
where every process has m − 1 resources and needs another one. If there is one resource left
over, one process can finish and release all its resources, letting the rest finish too. The
condition for avoiding deadlock is r ≥ p(m − 1) + 1.

Question 24

Suppose that process A in Fig. 6-12 (https://imgur.com/a/vAcceqV) requests the last tape drive. Does this action lead to a deadlock?

Answer 24

No. D can still finish. When it finishes, it returns enough resources to allow E (or A) to finish, and
so on.

Question 25

The banker’s algorithm is being run in a system with m resource classes and n processes.
In the limit of large m and n, the number of operations that must be performed to check a
state for safety is proportional to mᵃnᵇ. What are the values of a and b?

Answer 25

(FE17) (TUT13)
Comparing a row in the matrix to the vector of available resources takes m operations. This step
must be repeated on the order of n times to find a process that can finish and be marked as
done. Thus, marking a process as done takes on the order of mn steps. Repeating the algorithm
for all n processes means that the number of steps is then O(mn²). Thus, a = 1 and b = 2.

Question 26

A system has four processes and five allocatable resources. The current allocation and
maximum needs are as follows:
https://imgur.com/a/5eIkR2d
What is the smallest value of x for which this is a safe state?

Answer 26

(TUT13)
The needs matrix is as follows:
0 1 0 0 2
0 2 1 0 0
1 0 3 0 0
0 0 1 1 1
If x is 0, we have a deadlock immediately. If x is 1, process D can run to completion. When it is
finished, the available vector is 1 1 2 2 1. Unfortunately we are now deadlocked. If x is 2, after D
runs, the available vector is 1 1 3 2 1 and C can run. After it finishes and returns its resources
the available vector is 2 2 3 3 1, which will allow B to run and complete, and then A to run and
complete. Therefore, the smallest value of x that avoids a deadlock is 2.

Question 27

One way to eliminate circular wait is to have rule saying that a process is entitled only to a
single resource at any moment. Give an example to show that this restriction is unacceptable
in many cases.

Answer 27

Consider a process that needs to copy a huge file from a tape to a printer. Because the amount
of memory is limited and the entire file cannot fit in this memory, the process will have to loop
through the following statements until the entire file has been printed:
Acquire tape drive
Copy the next portion of the file in memory (limited memory size)
Release tape drive
Acquire printer
Print file from memory
Release printer
This will lengthen the execution time of the process. Furthermore, since the printer is released
after every print step, there is no guarantee that all portions of the file will get printed on
continuous pages.

Question 28

Two processes, A and B, each need three records, 1, 2, and 3, in a database. If A asks for
them in the order 1, 2, 3, and B asks for them in the same order, deadlock is not possible.
However, if B asks for them in the order 3, 2, 1, then deadlock is possible. With three
resources, there are 3! or six possible combinations in which each process can request them.
What fraction of all the combinations is guaranteed to be deadlock free?

Answer 28

Suppose that process A requests the records in the order a, b, c. If process B also asks for a first,
one of them will get it and the other will block. This situation is always deadlock free since the
winner can now run to completion without interference. Of the four other combinations, some
may lead to deadlock and some are deadlock free. The six cases are as follows:
a b c deadlock free
a c b deadlock free
b a c possible deadlock
b c a possible deadlock
c a b possible deadlock
c b a possible deadlock
Since four of the six may lead to deadlock, there is a 1/3 chance of avoiding a deadlock and a
2/3 chance of getting one.

Question 29

A distributed system using mailboxes has two IPC primitives, send and receive. The latter
primitive specifies a process to receive from and blocks if no message from that process is
available, even though messages may be waiting from other processes. There are no shared
resources, but processes need to communicate frequently about other matters. Is deadlock
possible? Discuss.

Answer 29

Yes. Suppose that all the mailboxes are empty. Now A sends to B and waits for a reply, B sends
to C and waits for a reply, and C sends to A and waits for a reply. All the conditions for a
communications deadlock are now fulfilled.

Question 30

In an electronic funds transfer system, there are hundreds of identical processes that work
as follows. Each process reads an input line specifying an amount of money, the account to be
credited, and the account to be debited. Then it locks both accounts and transfers the money,
releasing the locks when done. With many processes running in parallel, there is a very real
danger that a process having locked account x will be unable to lock y because y has been
locked by a process now waiting for x. Devise a scheme that avoids deadlocks. Do not release
an account record until you have completed the transactions. (In other words, solutions that
lock one account and then release it immediately if the other is locked are not allowed.)

Answer 30

To avoid circular wait, number the resources (the accounts) with their account numbers. After
reading an input line, a process locks the lower-numbered account first, then when it gets the
lock (which may entail waiting), it locks the other one. Since no process ever waits for an
account lower than what it already has, there is never a circular wait, hence never a deadlock.

Question 31

One way to prevent deadlocks is to eliminate the hold-and-wait condition. In the text it
was proposed that before asking for a new resource, a process must first release whatever
resources it already holds (assuming that is possible). However, doing so introduces the
danger that it may get the new resource but lose some of the existing ones to competing
processes. Propose an improvement to this scheme.

Answer 31

Change the semantics of requesting a new resource as follows. If a process asks for a new
resource and it is available, it gets the resource and keeps what it already has. If the new
resource is not available, all existing resources are released. With this scenario, deadlock is
impossible and there is no danger that the new resource is acquired but existing ones lost. Of
course, the process only works if releasing a resource is possible (you can release a scanner
between pages or a CD recorder between CDs).

Question 32

A computer science student assigned to work on deadlocks thinks of the following brilliant
way to eliminate deadlocks. When a process requests a resource, it specifies a time limit. If
the process blocks because the resource is not available, a timer is started. If the time limit is
exceeded, the process is released and allowed to run again. If you were the professor, what
grade would you give this proposal and why?

Answer 32

I’d give it an F (failing) grade. What does the process do? Since it clearly needs the resource, it
just asks again and blocks again. This is no better than staying blocked. In fact, it may be worse
since the system may keep track of how long competing processes have been waiting and assign
a newly freed resource to the process that has been waiting longest. By periodically timing out
and trying again, a process loses its seniority.

Question 33

Main memory units are preempted in swapping and virtual memory systems. The
processor is preempted in time-sharing environments. Do you think that these preemption
methods were developed to handle resource deadlock or for other purposes? How high is
their overhead?

Answer 33

Both virtual memory and time-sharing systems were developed mainly to assist system users.
Virtualizing hardware shields users from the details of prestating needs, resource allocation, and
overlays, in addition to preventing deadlock. The cost of context switching and interrupt
handling, however, is considerable. Specialized registers, caches, and circuitry are required.
Probably this cost would not have been incurred for the purpose of deadlock prevention alone.

Question 34

Explain the differences between deadlock, livelock, and starvation.

Answer 34

(TUT13)
For all cases, bridge has an entry and an exit which can be considered as resources of different
types. A car will cross the bridge if and only if it takes both resources.
● Deadlock: Two cars are entering the bridge from different sides. Each car captures one
resource. If both car drivers are stubborn, no one will willingly free a resource that other
one needs. Consequently, we have a deadlock, since both cars will stuck forever.
● Livelock: Let’s assume that both drivers are polite and they decide to get back and let
other driver pass the bridge, than try entering the bridge again. If both follow the same
strategy, they will stuck forever. However, they will continue entering and leaving the
bridge, so this situation is not a deadlock since some activity still happens.
● Starvation: Consider the bridge with a sign that says that trucks have lower priority than
passenger cars and can cross the bridge if and only if there are no such cars at both ends.
In this case, theoretically, a truck might stuck for a long time (or forever) if passenger
cars constantly arrive at the bridge.

Question 35

Assume two processes are issuing a seek command to reposition the mechanism to access
the disk and enable a read command. Each process is interrupted before executing its read,
and discovers that the other has moved the disk arm. Each then reissues the seek command,
but is again interrupted by the other. This sequence continually repeats. Is this a resource
deadlock or a livelock? What methods would you recommend to handle the anomaly?

Answer 35

This dead state is an anomaly of competition synchronization and can be controlled by resource
pre-allocation. Processes, however, are not blocked from resources. In addition, resources are
already requested in a linear order. This anomaly is not a resource deadlock; it is a livelock.
Resource preallocation will prevent this anomaly. As a heuristic, processes may time-out and
release their resources if they do not complete within some interval of time, then go to sleep for
a random period and then try again.

Question 36

Local Area Networks utilize a media access method called CSMA/CD, in which stations
sharing a bus can sense the medium and detect transmissions as well as collisions. In the
Ethernet protocol, stations requesting the shared channel do not transmit frames if they
sense the medium is busy. When such transmission has terminated, waiting stations each
transmit their frames. Two frames that are transmitted at the same time will collide. If
stations immediately and repeatedly retransmit after collision detection, they will continue to
collide indefinitely.
a) Is this a resource deadlock or a livelock?
b) Can you suggest a solution to this anomaly?
c) Can starvation occur with this scenario?

Answer 36

(a) This is a competition synchronization anomaly. It is also a livelock. We might term it a
scheduling livelock. It is not a resource livelock or deadlock, since stations are not holding
resources that are requested by others and thus a circular chain of stations holding resources
while requesting others does not exist. It is not a communication deadlock, since stations are
executing independently and would complete transmission were scheduled sequentially.
(b) Ethernet and slotted Aloha require that stations that detect a collision of their transmission
must wait a random number of time slots before retransmitting. The interval within which the
time slot is chosen is doubled after each successive collision, dynamically adjusting to heavy
traffic loads. After sixteen successive retransmissions a frame is dropped.
(c) Because access to the channel is probabilistic, and because newly arriving stations can
compete and be allocated the channel before stations that have retransmitted some number of
times, starvation is enabled.

Question 37

A program contains an error in the order of cooperation and competition mechanisms,
resulting in a consumer process locking a mutex (mutual exclusion semaphore) before it blocks on an empty buffer. The producer process blocks on the mutex before it can place a
value in the empty buffer and awaken the consumer. Thus, both processes are blocked
forever, the producer waiting for the mutex to be unlocked and the consumer waiting for a
signal from the producer. Is this a resource deadlock or a communication deadlock? Suggest
methods for its control.

Answer 37

The anomaly is not a resource deadlock. Although processes are sharing a mutex, i.e., a
competition mechanism, resource pre-allocation and deadlock avoidance methods are all
ineffective for this dead state. Linearly ordering resources is also ineffective. Indeed one could
argue that linear orders may be the problem; executing a mutex should be the last step before
entering and the first after leaving a critical section. A circular dead state does exist in which
both processes wait for an event that can only be caused by the other process. This is a
communication deadlock. To make progress, a time-out will work to break this deadlock if it
preempts the consumer’s mutex. Writing careful code or using monitors for mutual exclusion
are better solutions.

Question 38

38. Cinderella and the Prince are getting divorced. To divide their property, they have agreed
    on the following algorithm. Every morning, each one may send a letter to the other’s lawyer
    requesting one item of property. Since it takes a day for letters to be delivered, they have
    agreed that if both discover that they have requested the same item on the same day, the
    next day they will send a letter canceling the request. Among their property is their dog,
    Woofer, Woofer’s doghouse, their canary, Tweeter, and Tweeter’s cage. The animals love
    their houses, so it has been agreed that any division of property separating an animal from its
    house is invalid, requiring the whole division to start over from scratch. Both Cinderella and
    the Prince desperately want Woofer. So that they can go on (separate) vacations, each spouse
    has programmed a personal computer to handle the negotiation. When they come back from
    vacation, the computers are still negotiating. Why? Is deadlock possible? Is starvation
    possible? Discuss your answer.

Answer 38

If both programs ask for Woofer first, the computers will starve with the endless sequence:
request Woofer, cancel request, request Woofer, cancel request, and so on. If one of them asks
for the doghouse and the other asks for the dog, we have a deadlock, which is detected by both
parties and then broken, but it is just repeated on the next cycle. Either way, if both computers
have been programmed to go after the dog or the doghouse first, either starvation or deadlock
ensues. There is not really much difference between the two here. In most deadlock problems,
starvation does not seem serious because introducing random delays will usually make it very
unlikely. That approach does not work here.