Deadlock Prevention

Deadlock prevention strategies focus on ensuring that at least one of the four conditions necessary for a deadlock to occur is systematically negated. Here's a breakdown of how each condition can be addressed:

Mutual Exclusion

  • Concept: Some resources inherently cannot be shared among multiple processes. This condition is necessary for deadlocks but cannot always be eliminated because certain resources, like a printer or a mutex lock, require exclusive access to function correctly.

  • Prevention: While mutual exclusion is essential for certain resources, making more resources shareable when possible can reduce the likelihood of deadlocks. For example, read-only files can be accessed by multiple processes simultaneously without leading to deadlock situations.

Hold and Wait

  • Concept: This condition occurs when a process holds onto resources while waiting for additional ones.

  • Prevention Strategies:

    1. All-or-Nothing: Require processes to request all the resources they will need upfront, before starting execution. This way, a process does not enter the system and hold onto resources while waiting for others.

    2. Incremental Allocation: Allow processes to request resources only when they hold none, forcing them to release any currently held resources before requesting new ones.

Both approaches aim to prevent processes from waiting for resources while holding others, but they come with their own sets of drawbacks:

  • Low Resource Utilization: Resources might be locked by a process long before they're actually needed, lying idle and thus reducing overall system efficiency.

  • Starvation: Processes requiring popular resources might end up waiting indefinitely if those resources are continually in use by others.

Example of Hold and Wait Prevention

Imagine a process that involves reading data from a DVD, storing it on a disk, sorting the data, and then printing it. Under the all-or-nothing approach, the process would have to lock down the DVD drive, disk space, and printer right from the start, even though the printer is only needed at the end of the process. This can lead to inefficient resource use. Alternatively, the incremental allocation method allows the process to initially request just the DVD drive and disk space, releasing them once the data transfer is complete, before requesting access to the disk file and printer for the final printing step. While more efficient, this approach also risks leaving the process without needed resources if they become unavailable during its operation.

No Preemption

  • Concept: This condition exists when resources allocated to a process cannot be taken away until the process voluntarily releases them.

  • Prevention: Introducing preemption where resources can be forcibly taken away from a process if it requests new resources but cannot be immediately granted. If a process holding resources requests another resource and must wait, its currently held resources are released and added to the list of resources it's waiting for. This strategy applies mainly to resources whose states can be easily saved and restored, such as CPU registers and memory.

Circular Wait

  • Concept: Circular wait occurs when there is a chain of processes where each process holds one resource and waits for another held by the next process in the chain, forming a circle.

  • Prevention: By imposing a total ordering on all resource types and requiring that each process requests resources in an increasing order based on this ordering, circular wait can be avoided. This method involves assigning a unique integer to each resource type, and a process can only request resources in ascending order of these integers. If a process needs multiple instances of a resource, it must request all of them at once. This approach prevents the formation of cycles because it disallows scenarios where a process holding a resource with a higher number waits for a resource with a lower number.

For example, consider resources like tape drives, disk drives, and printers assigned numbers 1, 5, and 12, respectively. A process must request these resources in ascending order of their assigned numbers. This method requires careful planning and adherence by application developers, who must ensure that their programs request resources following the defined order.