Safe State

• A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock.
• More formally, a system is in a safe state only if there exists a safe sequence.
  • A sequence of processes $< P_1,P_2,\ldots,P_n>$ is a safe sequence for the current allocation state if, for each $P_i$ the resource requests that $P_i$ can still make can be satisfied by the currently available resources plus the resources held by all $P_j$, with $j < i$.
  • In this situation, if the resources that $P_i$ needs are not immediately available, then $P_i$ can wait until all $P_j$ have finished.
  • When they have finished, $P_i$ can obtain all of its needed resources, complete its designated task, return its allocated resources, and terminate.
  • When $P_i$ terminates, $P_{i+1}$ can obtain its needed resources, and so on.
  • If no such sequence exists, then the system state is said to be unsafe.
• A safe state is not a deadlocked state. Conversely, a deadlocked state is an unsafe state. Not all unsafe states are deadlocks, however (see Fig. 9).

  Figure 9: Safe, unsafe, and deadlock state spaces.

  
• An unsafe state may lead to a deadlock.
  • As long as the state is safe, the OS can avoid unsafe (and deadlocked) states.
  • In an unsafe state, the OS cannot prevent processes from requesting resources such that a deadlock occurs: The behavior of the processes controls unsafe states.
  • 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.
• To illustrate, we consider a system with 12 magnetic tape drives and three processes: $P_0, P_1$, and $P_2$ .
  • Process $P_0$ requires 10 tape drives, and holds 5 tape drives
  • Process $P_1$ may need as many as 4 tape drives, and holds 2 tape drive
  • Process $P_2$ may need up to 9 tape drives, and holds 2 tape drives
  • Thus, there are 3 free tape drives.

  $P_i$	Maximum Needs	Current Needs
  $P_0$	10	5
  $P_1$	4	2
  $P_2$	9	2

• At time $t_0$, the system is in a safe state. The sequence $< P_1,P_0,P_2 >$ satisfies the safety condition.
• A system can go from a safe state to an unsafe state. Suppose that, at time $t_1$, process $P_2$ requests and is allocated one more tape drive. The system is no longer in a safe state.
  • At this point, only process $P_1$ can be allocated all its tape drives.
  • When it returns them, the system will have only 4 available tape drives.
  • Since process $P_0$ is allocated 5 tape drives but has a maximum of 10, it may request 5 more tape drives. Since they are unavailable, process $P_0$ must wait.
  • Similarly, process $P_2$ may request an additional 6 tape drives and have to wait, resulting in a deadlock.
• Our mistake was in granting the request from process $P_2$ for one more tape drive.
• In Fig. 10 we have a state in which
  • A total of 10 instances of the resource exist, so with 7 resources already allocated, there are 3 still free.
  • $A$ has 3 instances of the resource but may need as many as 9 eventually.
  • $B$ currently has 2 and may need 4 altogether, later.
  • Similarly, $C$ also has 2 but may need an additional 5.
  • The state of Fig. 10upper is safe because there exists a sequence of allocations that allows all processes to complete. By careful scheduling, can avoid deadlock.
  • Now suppose, this time $A$ requests and gets another resource, giving Fig. 10lower. Eventually, $B$ completes. 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. $A$'s request should not have been granted.
  • But, an unsafe state is not a deadlocked state. It is possible that $A$ might release a resource before asking for any more, allowing $C$ to complete and avoiding deadlock altogether.

  Figure 10: Demonstration that the state in is safe (Upper), is not safe (Lower).

  

  
• Given the concept of a safe state, we can define avoidance algorithms that ensure that the system will never deadlock.
  • The idea is simply to ensure that the system will always remain in a safe state.
  • Initially, the system is in a safe state.
  • Whenever a process requests a resource that is currently available, the system must decide whether the resource can be allocated immediately or whether the process must wait.
  • The request is granted only if the allocation leaves the system in a safe state.
• In this scheme, if a process requests a resource that is currently available, it may still have to wait. Thus, resource utilization may be lower than it would otherwise be.