- 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
is a safe sequence for the current allocation state if, for each the resource requests that can still make can be satisfied by the currently available resources plus the resources held by all , with .
- In this situation, if the resources that needs are not immediately available, then can wait until all have finished.
- When they have finished, can obtain all of its needed resources, complete its designated task, return its allocated resources, and terminate.
- When terminates, 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. 7.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: , and .
- Process requires 10 tape drives, and holds 5 tape drives
- Process may need as many as 4 tape drives, and holds 2 tape drive
- Process may need up to 9 tape drives, and holds 2 tape drives
- Thus, there are 3 free tape drives.
- At time , the system is in a safe state. The sequence
satisfies the safety condition.
- A system can go from a safe state to an unsafe state. Suppose that, at time , process requests and is allocated one more tape drive. The system is no longer in a safe state.
- At this point, only process can be allocated all its tape drives.
- When it returns them, the system will have only 4 available tape drives.
- Since process is allocated 5 tape drives but has a maximum of 10, it may request 5 more tape drives. Since they are unavailable, process must wait.
- Similarly, process may request an additional 6 tape drives and have to wait, resulting in a deadlock.
- Our mistake was in granting the request from process for one more tape drive.
- In Fig. 7.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.
- has 3 instances of the resource but may need as many as 9 eventually.
- currently has 2 and may need 4 altogether, later.
- Similarly, also has 2 but may need an additional 5.
- The state of Fig. 7.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 requests and gets another resource, giving Fig. 7.10lower. Eventually, 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. 's request should not have been granted.
- But, an unsafe state is not a deadlocked state. It is possible that might release a resource before asking for any more, allowing to complete and avoiding deadlock altogether.
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.