Chapter 5A

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

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).

Gridlock.gif (11281 bytes)

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

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

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."

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."

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.

1 If space exists in the Between Floor Landing, 
  then reserve the space and continue to the next step; 
  else wait.
2 If space exists in Stairway X, 
  then reserve the space and transit from Floor Landing A to Between Floor Landing.  Occupy the Between Floor Landing.  
  else, wait.
3 If space exists in Stairway Z,
  then reserve the space and transit from Between Floor Landing to Floor Landing B, and release claim on the Between Floor Landing;
  else, wait.

For the upward traveler beginning at Floor Landing B.

1 If space exists in the Between Floor Landing, 
  then reserve the space and continue to the next step; 
  else wait.
2 If space exists in Stairway Z, 
  then reserve the space and transit from Floor Landing B to Between Floor Landing.  Occupy the Between Floor Landing.  
  else, wait.
3 If space exists in Stairway X,
  then reserve the space and transit from Between Floor Landing to Floor Landing B, and release claim on the Between Floor Landing;
  else, wait.

 

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.

Main Program Down: Floor A to B Up: Floor B to A Proben Verhogen
Procedure Main
  Begin

/* Initialize semaphores */
    X = 1 
    Y = 2
    Z = 1

/* Process simultaneously */
    COBEGIN
      Repeat Down
      Repeat Up
    COEND

  End

Procedure Down
  Begin

    Probe(Y, Down)
    Probe(X, Down)
    Transit_X
    Occupy_Y
    Vacate(X, Down)

    Probe(Z, Down)
    Transit_Z
    Vacate(Y, Down)
    Vacate(Z, Down)

  End

Procedure Up
  Begin

    Probe(Y, Up)
    Probe(Z, Up)
    Transit_Z
    Occupy_Y
    Vacate(Z, Up)

    Probe(X, Up)
    Transit_X
    Vacate(Y, Up)
    Vacate(X, Up)

  End

Procedure Probe(S, Direction)
  Begin
    S = S - 1

    If S <= 0
      Then move the Caller Process (with its Direction) from the Run queue to the "Wait on S" Queue.
      Else permit the Caller Process to remain in the Run queue and return control to the Caller process.
      End If

  End

Procedure Vacate(T, Direction)
  Begin
    T = T + 1

    If T <= 0
      Then

        If Opposite_Direction is in the "Wait on T" Queue
          Then Move Opposite_Direction process from the "Wait on T" Queue to the Ready Queue
          Else Move Direction process from the "Wait on T" Queue to the Ready Queue
         End If

      End If

  End


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.

  1. 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.

 

1