Deadlock Avoidance – Resource Trajectories

Lists of Questions Answers and Short Study Notes

  • (1) How Resource Trajectories can be helpful in avoiding the deadlock?
  • (2) Explain safe and unsafe states with example.

Question-1 How Resource Trajectories can be helpful in avoiding the deadlock?

Following example explains how Resource Trajectories can be helpful in avoiding the deadlock.

  • Consider a model for dealing with two processes and two resources, for example, a printer and a plotter.
  • The horizontal axis represents the number of instructions executed by process A.
  • The vertical axis represents the number of instructions executed by process B.
  • At I1 process A requests a printer; at I2 it needs a plotter.
  • The printer and plotter are released at I3 and I4, respectively.
  • Process B needs the plotter from I5 to I7 and the printer from I6 to I8.
  • Every point in the diagram represents a joint state of the two processes.
  • Initially, the state is at p, with neither process having executed any instructions.
  • If the scheduler chooses to run process A first, we get to the point q, in which process A has executed some number of instructions, but process B has executed none.
  • At point q the trajectory becomes vertical, indicating that the scheduler has chosen to run process B.
  • When process A crosses the I1 line on the path from r to s, it requests and is granted the printer.

resource trajectories

  • When process B reaches point t, it requests the plotter.
  • The regions that are shaded are especially interesting. The region with lines slanting from southwest to northeast represents both processes having the printer. The mutual exclusion rule makes it impossible to enter this region.
  • Similarly, the region shaded the other way represents both processes having the plotter, and is equally impossible.
  • If the system ever enters the box bounded by I1 and I2 on the sides and I5 and I6 top and bottom, it will eventually deadlock when it gets to the intersection of I2 and I6.
  • At this point process A is requesting the plotter and process B is requesting the printer, and both are already assigned.
  • The entire box is unsafe and must not be entered.
  • At point t the only safe thing to do is run process A until it gets to I4.
  • The important thing to see here is at point t process B is requesting a resource.
  • The system must decide whether to grant it or not.
  • If the grant is made, the system will enter an unsafe region and eventually deadlock.
  • To avoid the deadlock, B should be suspended until A has requested and released the plotter.

 

Question-2 Explain safe and unsafe states with example.

  • At any instant of time, there is a current state consisting of existing resource vector E,available resource vector A, current allocation matrix C, and request matrix R.
  • A state is said to be safe if it is not deadlocked and there is some scheduling order in which every process can run to completion even if all of them suddenly request their maximum number of resources immediately.
  • It is easiest to illustrate this concept by an example using one resource.
  • In Fig. below (a) we have a state in which process A has 3 instances of the resource but may need as many as 9 eventually.
  • Process B currently has 2 and may need 4 altogether, later.
  • Similarly, process C also has 2 but may need an additional 5.

safe state

  • A total of 10 instances of the resource exist, so with 7 resources already allocated, there are 3 still free.
  • The state of Fig. above (a) is safe because there exists a sequence of allocations that allows all processes to complete.
  • Namely, the scheduler could simply run B exclusively, until it asked for and got two more instances of the resource, leading to the state of Fig. above (b).
  • When B completes, we get the state of Fig. above (c).
  • Then the scheduler can run C leading eventually to Fig. above (d). When C completes, we get Fig. above (e).
  • Now A can get the six instances of the resource it needs and also complete.
  • Thus the state of Fig. above (a) is safe because the system, by careful scheduling, can avoid deadlock.
  • Now suppose we have the initial state shown in Fig. below (a), but this time A requests and gets another resource, giving Fig. below (b).
  • Can we find a sequence that is guaranteed to work? Let us try. The scheduler could run B until it asked for all its resources, as shown in Fig. below (c).
  • Eventually, B completes and we get the situation of Fig. below (d).
  • At this point we are stuck. We only have four instances of the resource free, and each of the active processes needs five. There is no sequence that guarantees completion.
  • Thus the allocation decision that moved the system from Fig. below (a) to Fig. below (b) results into an unsafe state.
  • It is worth noting that an unsafe state is not a deadlocked state.

The difference between a safe state and an unsafe state is that from a safe state the system can guarantee that all processes will finish; from an unsafe state, no such guarantee can be given.

unsafe state