3. Using the narrow staircase example from the beginning of this chapter, create

Question

3. Using the narrow staircase example from the beginning of this chapter, create a list of actions or tasks that could be implemented by the building manager that would allow people to use the staircase without risking a deadlock or starvation.

Here is the staircase exmaple from the book:

A deadlock is most easily described with an example that we return to throughout the chapter—a narrow staircase in a building. The staircase was built as a fire escape route, but people working in the building often take the stairs instead of waiting for the slow elevators. Traffic on the staircase moves well unless two people, traveling in opposite directions, need to pass on the stairs—there’s room for only one person on each step. There’s a landing at each floor that is wide enough for two people to share, but the stairs are not—they can be allocated to only one person at a time. In this example, the staircase is the system and the steps and landings are the resources. Problems occur when someone going up the stairs meets someone coming down, and each refuses to retreat to a wider place. This creates a deadlock, which is the subject of much of our discussion on process synchronization.Similarly, if two people on a landing try to pass each other but cannot do so because as one steps to the right, the other steps to the left, and vice versa, then they will continue moving but neither will ever move forward. This is called livelock .On the other hand, if a few patient people wait on the landing for a break in the opposing traffic, and that break never comes, they could wait there forever. That results in starvation , an extreme case of indefinite postponement, and is discussed at the end of this chapter.

Explanation / Answer

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.

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

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.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.