Understanding Operating System Deadlocks
Deadlocks in Operating Systems
When a process requests resources that are unavailable, it enters a waiting state. A deadlock occurs when a waiting process can never change its state because the resources it needs are held by other waiting processes.
Methods for Handling Deadlocks
- Implement a protocol to prevent or avoid deadlocks, ensuring the system never enters a deadlocked state.
- Allow the system to enter a deadlocked state, then detect it, and recover.
- Ignore the problem altogether, pretending that deadlocks never occur in the system.
The third solution, ignoring the problem, is commonly used by most operating systems, including UNIX and Windows. In such cases, it is the application developer’s responsibility to write programs that can handle potential deadlocks.
Resource Request Protocols: An Illustration
To illustrate the difference between resource request protocols, consider a process that copies data from a DVD drive to a disk file, sorts the file, and then prints the results. If all resources must be requested at the beginning of the process, it would initially request the DVD drive, disk file, and printer.
This approach means the process would hold the printer for its entire execution, even though it only needs it at the very end.
An alternative method allows the process to initially request only the DVD drive and disk file. After copying data from the DVD drive to the disk, it releases both resources. The process then requests the disk file and the printer. Once the disk file is copied to the printer, these two resources are released, and the process terminates.
Deadlock Prevention Conditions
Mutual Exclusion
The mutual exclusion condition states that at least one resource must be held in a non-sharable mode. This means only one process at a time can use the resource. Sharable resources, such as read-only files, do not require mutually exclusive access and therefore cannot be involved in a deadlock. A process never needs to wait for a sharable resource. However, we generally cannot prevent deadlocks by denying the mutual-exclusion condition, as some resources are intrinsically non-sharable.
Hold and Wait
To prevent the hold and wait condition, the system must guarantee that whenever a process requests a resource, it does not hold any other resources. One protocol requires each process to request and be allocated all its resources before it begins execution. This can be implemented by requiring that system calls requesting resources for a process precede all other system calls.
An alternative protocol allows a process to request resources only when it holds none.
No Preemption
The no preemption condition states that resources cannot be forcibly taken away from a process once they have been allocated. To prevent this condition, a protocol can be used: If a process is holding resources and requests another resource that cannot be immediately allocated (meaning the process must wait), then all resources the process currently holds are preempted. These resources are implicitly released and added to the list of resources for which the process is waiting. The process will only be restarted when it can regain its old resources, along with the new ones it is requesting.