In-depth Notes on Deadlocks in Operating Systems

Introduction to Deadlocks

In computer systems, a deadlock occurs when several processes are in a state of waiting for resources that other processes are holding. A system is in a deadlock state if every process in a set is waiting for an event that can only be triggered by another process in the set. For example, consider a system with two tape drives, where Process 1 (P1) holds one tape drive and needs the one held by Process 2 (P2), while P2 holds the other tape drive and needs the one held by P1.

System Model for Resource Allocation

In any deadlock scenario, resources are partitioned into several types, each consisting of identical instances. Resources can either be physical (like printers, tape drives) or logical (like files, semaphores). Resources may be:

• Preemptible: Can be taken away from a process without harming it (e.g. memory).

• Non-preemptible: Cannot be taken away once allocated, or it will fail the process (e.g. printers).

A process interacts with resources in three steps: 1) Requesting the resource, 2) Using the resource, and 3) Releasing the resource.

Necessary Conditions for Deadlock

According to Coffman et al., four conditions must simultaneously hold for a deadlock to occur:

1. Mutual Exclusion: Only one process can use a resource at any given time.

2. Hold and Wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.

3. No Pre-emption: Resources can only be released voluntarily by the process holding them.

4. Circular Wait: A set of processes exists such that each process is waiting for a resource held by the next process in the cycle.

Deadlock Modelling

A deadlock can be represented by a system resource-allocation graph. In this directed graph:

• V: set of nodes consisting of processes (P) and resource types (R).

• Request edge: A directed edge from Pi to Rj indicates that process Pi is requesting resource Rj.

• Assignment edge: A directed edge from Rj to Pi indicates that resource Rj is allocated to process Pi.

A cycle in this graph can indicate a deadlock. If there is no cycle, the system is guaranteed not to be in deadlock.

Deadlock Prevention Techniques

Deadlock prevention strategies aim to ensure that at least one of the necessary conditions cannot hold:

1. Deny Mutual Exclusion: This is not feasible for non-sharable resources, such as printers.

2. Deny Hold and Wait: Require processes to request all resources at once or release all resources before requesting more. However, this can lead to low resource utilization and starvation.

3. Allow Pre-emption: If a process holds resources and requests more that cannot be allocated, it must release all resources.

4. Deny Circular Wait: Impose a strict ordering on resource types so that resources are requested only in a predefined order.

Deadlock Avoidance Techniques

Deadlock avoidance requires prior information about how resources will be requested. The Banker's Algorithm is widely used for this purpose. It checks for safe states, where a sequence of resource allocation does not lead to a deadlock, by ensuring that processes can finish with the available resources.

Safe State

A system is in a safe state if there exists a sequence of processes such that each one can get the necessary resources to complete execution without leading to a deadlock. If the system transitions into an unsafe state, deadlocks can become possible.

Detection and Recovery from Deadlock

If a system does not implement prevention or avoidance, it may enter a deadlock. Hence, deadlock detection involves maintaining a wait-for graph that monitors processes and resource requests:

• If cycles are detected in this graph, the system is in deadlock.

• Recovery strategies can include terminating processes or preempting resources from processes to resolve a deadlock.

Combined Approach to Deadlock Handling

Ultimately, the most effective strategy for managing deadlocks combines multiple methods: prevention, avoidance, and detection. By partitioning resources into hierarchically ordered classes, the system can apply the most appropriate technique for handling deadlocks for each class of resources.