Chapter 5, Process Management, Ida A. Flynn and Ann McIver McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Company (1993)

Lesson A: Deadlock, Race, Conditions for Deadlock, Starvation
Deadlocks: File Requests, Device Allocation, Multiple Device Allocation, Spooling, Disk Sharing, Network
Race: In Databases

Problem 1.  What are the major differences between deadlock, starvation, and race?

Deadlock and starvation are problems of scheduling of scarce resources.  Race is a problem of synchronizing processes even when the resource is not scarce. 

Deadlock occurs

• when a group of processes,
• which refuse to share,
• own a portion of what they want,
• the remainder of what they want is owned by another process in the group,
• and they refuse to make progress until they get what they want. 

Starvation occurs when the resource allocation rules consistently exclude a needy process from limited resources because higher priority processes continue to be granted resource requests first.

Race is the problem of uncoordinated use of a common resource by multiple processes resulting in unintended consequences. 

http://www-aml.cs.umass.edu/~cs377/

http://cs.millersv.edu/cs382.dir/overhead.html

a. Deadlock: Peter Freeman, Software Systems Principles: A Survey, Science Research Associates, Inc. (1975), pg. 122.  Two processes are deadlocked if neither process can continue until the other continues.  A system deadlock occurs when all processes in the system are deadlocked.  

http://webopedia.internet.com/TERM/d/deadlock.html

http://www-ec.njit.edu/~acc9804/deadlock.html

http://www.cag.lcs.mit.edu/~rinard/osnotes/h4.html

b. Starvation:  The state of indefinite postponement of execution of a process because it is waiting for resources that never become available.

c. Race:  A problem of the state of a resource depending on the order in which processes use that resource when that order is not synchronized.  A race is not a deadlock.

Problem 2.  Give some "real life" examples (not related to a computer system environment) of deadlock, starvation, and race.

a.  Deadlock:  Traffic gridlock illustrated on page 101 is an often cited example.  Another example might be a savings and loan institution in a dying community.  People need additional capital to modernize factories to bring the community back to life.  The savings and loan needs profitable factories to deposit money so that the savings and loan can have capital to loan.

b.  Starvation:  The example of an even number of hungry students, with a platter of roast beef in the center, and alternating knife and fork at the place settings is a variation of Dijkstra's Dining Philosopher's problem.  (This, of course, would never happen because students would order pizza... most analogies break down when pushed to their limits :-)  )

c.  Race:  Two junior high school girls working together to mix dough for cookies for a surprise party, without identifying what ingredients the other has started to add.  They only check off a task when it is completed.  The race condition is a result of girl (call her Lucy) observes the last check mark on the recipie and sees that salt is needed next.  Lucy gets a spoon full of salt and proceeds to add it to the mix.  The other girl (call her Henrietta) finishes with her task and looks at the recipie, notes the last check mark on the recipie, and sees that salt is needed next.   Henrietta gets a spoon of salt.  Lucy, having finished adding salt, goes back to the recipie, checks off "add salt", and takes a break.  Because the next item is "add sugar", Lucy is unconcerned about the white stuff in Henrietta's spoon.  Henrietta, in a rush to catch the last scene in the popular soap opera, adds the salt, and dutifully checks off the next list item without looking closely at the item.   The cookies are well preserved, and surely a surprise.

Problem 3.  Select one example of deadlock from Exercise 2 and list the four necessary conditions needed for the deadlock.

The four conditions are:  (1) Mutual Exclusion, (2) Resource Holding, (3) No Preemption, and (4) Circular Wait.  Reference: Coffman, Elphick and Shoshani, "System Deadlocks", Computing Surveys, pages 67 - 78 (June 1971).

Condition 1:  Mutual Exclusion.  Definition: "Each resource is assigned to exactly 1 process, or is available."

• Each intersection in the 4-intersection block is assigned to one vehicle, or it is available.  Each space between the blocked intersections is assigned to one vehicle, or it is available.

Condition 2:  Resource Holding.  Definition: "Processes currently holding resources granted earlier can request new resources."

• Each vehicle in an intersection refuses to give up its position in its intersection and wants additional space to move into.

Condition 3:  No Preemption.  Definition: "Resources previously granted cannot be forcibly taken away from a process.  They must be explicitly released by the process holding them."

• The tow trucks cannot get to any intersection to remove a vehicle blocking traffic.

Condition 4:  Circular Wait.  Definition: "There must be a circular chain of 2 or more processes, each of which is waiting for a resource held by the next member of the chain."

• Each vehicle around the block needs space occupied by another vehicle.

Problem 4.  Suppose the narrow staircase (used as an example in the beginning of Chapter 5, page 99 - 100) has become a major source of aggravation.  Design an algorithm (see page 18) for using it so that both deadlock and starvation are not possible.

Strategy:  Permit travel Down to commence from Floor Landing A if and only if at least one between-floor landing space and Stairway X is available.  Once the between-floor landing is reached, permit travel Down to continue only when Stairway Z is available.  Similarly, permit travel Up to commence from Floor Landing B if and only if at least one between-floor landing space and Stairway Z is available.  Once the between-floor landing is reached, permit travel Up to continue only when Stairway X is available.

The controlling resource is Y.  If Y is occupied by two processes and one of them is going down, but without yet entering Stairway Z, you do not want to permit newcomer process at Landing B to grab Stairway Z.  If the downward process retains claim to Y until transiting Z, then Z cannot complete its probe to occupy Z until the downward process has finished its transit.  As long as only 2 processes can occupy the system simultaneously, you can prevent deadlock.  

This is not the maximum capacity use of the system, however.  If this were the fire escape, you would want to fill the system with 4 processes, all going down, until the building were cleared.  This would, however, block firemen from going up.  Starvation.

An algorithm.

For the downward traveler beginning at Floor Landing A.

For the upward traveler beginning at Floor Landing B.

The solution below uses the concept of a semaphore, introduced in Chapter 6.

Three semaphores are used in the pseudocode below: X, Y, and Z.  Initialize semaphores X and Z to permit only one occupant on stairs at a time.  Initialize semaphore Y to permit 2 occupants at a time.  I use Probe(*) for the operator P(s) or Proben(s), and Vacate(*) for the operator V(*) or Verhogen(s).  In the pseudocode for Probe, the letter S is a "dummy" semaphore.  Similarly, the letter T is a "dummy" semaphore in procedure Vacate.  When Probe(X) is issued in Procedure Down or Up, the S in Procedure Probe refers to X.  When Probe(Y) is issued in Procedure Down or Up, the S in Procedure Probe refers to Y.  Similarly, when Probe(Z) is issued, the S refers to Z.  When a procedure is called, the target procedure automatically records the location it was called from.  In this way, it will know where to return control.  If you take a programming course, you will see this concept of passing parameters when you study subprograms.

I added the direction of the traveler in the call to Probe and Vacate.  If the resource is occupied, this permits Probe to place the traveler's direction into a waiting queue.  When the resource scheduler later has to choose who will use the resource next, the scheduler can now consider the direction of the traveler.  When the resource is Vacated by "Down", the scheduler can look next for an "Up".  If no more "Up" travelers exist, then another "Down" can be scheduled.  Similarly, when the resource is Vacated by an "Up", the scheduler can look next for a "Down".  This helps prevent starvation.

I permit the semaphores to take on negative values.  A negative value indicates how many processes are waiting for the resource protected by its semaphore.  Remember that the semaphores are controlled by the operating system, not by the calling program.  When Probe(S) is called, control is not returned to the calling program until that program is cleared to proceed.

Problem 5.  The following figure shows a tunnel going through a mountain and two streets parallel to each other at each entrance/ exit of the tunnel.  Traffic lights are located at each end of the tunnel to control the crossflow of traffic through each intersection.

1. Can deadlock occur?  How and under what circumstances?

   The resources are the spaces in intersections A and B, which are controlled by lights.  Apply the tests for deadlock given in class.  

   (1)  Mutual Exclusion.  "Each resource (intersection) is assigned to exactly one process (vehicle), or is available."   Intersections A and B are either assigned to exactly one process or the intersection is available for assignment.  This condition is satisfied. 

   (2)  Resource Holding.  "Processes (vehicles) currently holding resources (intersections) granted earlier can request new resources."  A vehicle in intersection A continuing straight through the tunnel can request assignment of intersection B.  You could quibble that the request is not made until the vehicle is at the intersection.  I could respond by making the tunnel one foot wide (thin mountain ridge).  This condition is satisfied.

   (3)  No Preemption.  "Resources previously granted cannot be forcibly taken away from a process.  They must be explicitly released by the process holding them."  Except by extracting a vehicle from an intersection by helicopter, this condition is satisfied.

   (4)  Circular Wait.  "There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain."   In this problem, there is no circular chain.  This example therefore does not have the property of circular wait.  It therefore cannot be deadlocked.

   Note that this problem is very different from Problem 3.  In Problem 3, no traffic light controls imposed on the system could break the deadlock because there are vehicles occupying intersections that cannot be vacated regardless of traffic light conditions.  In Problem 5, a traffic light can control an intersection to cause it to become vacant, thus allowing vehicles in the tunnel to exit.

   It is possible to have starvation if the traffic lights do not operate properly.  This is different from deadlock.

    

2. How can deadlock be detected?

Consider the digraph for the Squirrel Mountain Tunnel.  Deadlock can be detected by applying the rules on page 115 of the text.  

Find a process that is currently using a resource and not waiting for one. This is the case of process 2.  It will eventually clear the intersection.  Process 2 is not contributing to the deadlock.  Remove P2 from the diagram and return resource B to the available list.

Find a process that is waiting only for resource classes that are not fully allocated.  P1 is waiting for resource B which now is not fully allocated.  Resource B can be allocated to process P1.  Therefore, P1 is not contributing to a deadlock.  Remove P1 from the diagram.

There are no processes in the system remaining that can be contributing to a deadlock.  The system both irreducible and has been completely reduced.  There is no deadlock.

A separate question:  How can starvation be detected?  Answer:  Place a motion detector in the tunnel.

3. Give a solution to prevent deadlock but watch out for starvation.

Deadlock does not exist, so there is no deadlock problem to solve.  There is a possible starvation problem if a traffic light fails.  The solution is to have the police station receive an alarm if there is no motion detected for 10 minutes during times when vehicles should be using the tunnel.  Send a policeman to control the intersection until the light is fixed.

Problem 12.  Suppose you are an operating system designer and have been approached by the operator to help solve the recurring deadlock problem in your installation's spooling system.  What features might you incorporate into the operating system so that deadlocks in the spooling system can be resolved without loss of work done by the processes involved?

Answers to a full spooler (including practical issues): 

1. Check if the printer is turned on.  If the printer is off, sound an alarm to alert the operator to turn the printer on.

2. Check to see if the printer has run out of paper.  Printers have an out-of-paper detector.  If the printer is out of paper, sound an alarm to alert the operator to put more paper into the printer.

3. Have the operating system collect performance data on the spooler.
   (a)  Determine if getting a faster printer would solve the problem.
   (b)  Determine if an additional printer is needed.

4. Require jobs producing output to declare a page limit.  Assume that a program attempting to exceed this limit has a mistake in it, and kill that process automatically.  This is routinely done on mainframe computers.

5. Permit multi-volume files.  When a spooling disk fills up, if this is not a case of a program gone wild, then bring another disk online as an overflow.

Problem 13.  A system in an unsafe state is not necessarily deadlocked. Explain why this is true. Give an example of a system in an unsafe state and show how all the processes could be completed without having deadlock occurring.

Using the banking analogy, extension of credit does not require that any of the customers request their maximum loan amount.

If jobs must request resources as part of the job submission procedure, that does not mandate that the jobs must actually request assignment of all declared resources during job execution.  For example, the use of resources may be data dependent.  If the data received by a job does not require use of all declared possible resources, then the job might be able to run to completion without starving or causing a deadlock.

In large transaction processing systems, it is common for programs that do polyphase sorting techniques to examine how many resources are available, and adjust the request for scratch (temporary) file space accordingly.  If fewer resources are available, the process takes more time.