UNISA Chatter – Operating System Concepts: Part 15 ... Deadlock avoidance analysis revisited

See UNISA – Summary of 2010 Posts for a list of related UNISA posts.

This is one of the final exam preparation posts and looks at some of the common deadlock avoidance approach algorithms and reviews the associated assignment from this year as an example. If you are not studying at UNISA, you should probably skip this post Smile

Safe State?

The second assignment presented us with a system  state at (t0) that looked something like the following table. Note that Need and the Maximum Resource Vector are computed values and were not presented as part of the state. Personally, however, I prefer having all the information in one table and added both computed columns to my Excel workbook.

Apart from calculating the Need and Maximum Resource Vector, we were asked to determine if at (t0) the system was in a safe state and to calculate a safe sequence.

Let’s step through the process step-by-step using the Bankers Safety Algorithm:

  1. Work                := Available = (1, 5, 2, 0) as shown above.
    Finish               :=  (F, F, F, F, F)
    Safe Sequence = none
  2. Loop 1
    1. Search the processes from top to bottom for a process that requires less resources than are available.
      We find P2 as the first candidate.
    2. We assume that P2 completes successfully, thus releasing all its allocated resources.
      Work                := Available = (1, 5, 3, 2) as shown above.
      Finish               :=  (F, F, T, F, F)
      Safe Sequence = P2
  3. Loop 2
    1. Search the processes from top to bottom for a process that requires less resources than are available.
      We find P4 as the first candidate.
    2. We assume that P4 completes successfully, thus releasing all its allocated resources.
      Work                := Available = (1, 11, 6, 4) as shown above.
      Finish               :=  (F, F, T, F, T)
      Safe Sequence = P2, P4
  4. Loop 3
    1. Search the processes from top to bottom for a process that requires less resources than are available.
      We find P4 as the first candidate.
    2. We assume that P4 completes successfully, thus releasing all its allocated resources.
      Work                := Available = (2, 11, 6, 8) as shown above.
      Finish               :=  (T, F, T, F, T)
      Safe Sequence = P2, P4, P0
  5. Loop 4
    1. Search the processes from top to bottom for a process that requires less resources than are available.
    2. We find P1 as the first candidate.We assume that P4 completes successfully, thus releasing all its allocated resources.
      Work                := Available = (3, 15, 8, 10) as shown above.
      Finish               := (T, T, T, F, T)
    3. Safe Sequence = P2, P4, P0, P1
  6. Loop 4
    1. Search the processes from top to bottom for a process that requires less resources than are available.
    2. We find P1 as the first candidate.We assume that P4 completes successfully, thus releasing all its allocated resources.
      Work                := Available = (3, 17, 9, 10) as shown above.
      Finish               := (T, T, T, T, T)
    3. Safe Sequence = P2, P4, P0, P1, P3

All the steps are complete and we have a finish of (T, T, T, T, T), which means that the system is in a safe state and one of the safe sequences is P1, P4, P0, P1 and then P3.

Event at (t1) … P0 requests (0, 4, 2, 0)

To determine the impact of the request, we use the Resource-Request Algorithm:

  1. Check if request <= need  and if yes, go to step 2, else fail.
  2. Check if request <= available and if yes, go to step 3, else fail.
  3. Available   := Available   –  Request = (1, 1, 0, 0) as shown below.
    Allocation := Allocation + Request = (1, 4, 2, 4)
    Need          := Need         -  Request = (0, 2, 3, 2)

The new state at (t1) is shown as below, after processing the request. So far so good … but are we safe?

To determine if we are safe, we apply the bankers safety algorithm again.

  1. Work                := Available = (1, 1, 0, 0) as shown above.
    Finish               :=  (F, F, F, F, F)
    Safe Sequence = none
  2. Loop 1
    1. Search the processes from top to bottom for a process that requires less resources than are available.
      We find P2 as the first candidate.
    2. We assume that P2 completes successfully, thus releasing all its allocated resources.
      Work                := Available = (1, 1, 1, 2) as shown above.
      Finish               :=  (F, F, T, F, F)
      Safe Sequence = P2
  3. Loop 2
    1. Search the processes from top to bottom for a process that requires less resources than are available.
    2. We have a problem, because we cannot find a relevant process, which implies that the request by P0 cannot be granted safely. The result is a restore to the state before P0 request as received, to avoid an unsafe system state.

Hope this helps …