Deadlocks in Computing Systems

Deadlocks

• Deadlocks occur when a set of blocked processes each hold a resource and wait to acquire a resource held by another process in the set.
• A system with two tape drives, where process P₁ and P₂ each hold one tape drive and need another, is an example.
• Another example uses semaphores A and B, initialized to 1, with processes P₀ and P₁ exhibiting the following sequence of waits: P₀ waits for A, then B; P₁ waits for B, then A. This can lead to deadlock.
• A bridge crossing example illustrates a similar concept. Traffic only moves in one direction, and each segment of the bridge represents a resource. If a deadlock occurs, a car must back up to resolve the situation, potentially leading to the need for multiple cars to reverse course.
• Starvation, where processes are indefinitely delayed despite being able to proceed given sufficient resources, is possible with deadlocks.

System Model

• Resource types like CPU cycles, memory space, and I/O devices are categorized as R₁, R₂, ..., Rₘ.
• Each resource type, Rᵢ, has wᵢ instances.
• Processes utilize resources using the sequence: request, use, release.

Deadlock Characterization

• Deadlocks arise when four conditions hold simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait.
• Mutual exclusion states only one process can use a resource at a time.
• Hold and wait means a process holding at least one resource is waiting to acquire additional resources held by other processes.
• No preemption prevents a resource from being forcibly released by a process before its task is completed.
• Circular wait exists if a set of waiting processes is such that each process is waiting for a resource held by the next process in the set, ultimately waiting for the resource it initially requested.

Resource-Allocation Graph

• A resource-allocation graph model comprises vertices (V) and edges (E).
• Vertices are categorized as processes (P₁ , P₂, ...) and resources (R₁, R₂, ...).
• Request edges are directed from a process to a resource, indicating a resource request.
• Assignment edges are directed from a resource to a process, implying resource allocation.

Resource-Allocation Graph (Cont.)

• Processes are represented by circles.
• Resource types with multiple instances are represented by boxes containing the instances (e.g., 4 instances inside a box).
• Directed lines depict request edges or assignment edges. P₁ requests R; is indicated by a directed line from P₁ to Rᵢ. P₁ holding R₁ is indicated by a directed line from Rᵢ to P₁ .

Example of a Resource Allocation Graph

• A graphical representation demonstrates interconnected processes and resources.

Resource Allocation Graph with a Deadlock

• A specific graph example demonstrates a circular dependency amongst processes and resources, resulting in a deadlock state.

Resource Allocation Graph with a Cycle but No Deadlock

• Another example demonstrates a cycle within the graph, where the system may not be in a deadlock state.

Basic Facts

• An absence of cycles in a resource-allocation graph indicates no deadlock.
• If there is only one instance of each resource type, a cycle in the graph signifies a deadlock.
• If there are multiple instances of each resource type, a cycle may or may not indicate a deadlock.

Methods for Handling Deadlocks

• Ensuring the system never enters a deadlock state is one approach.
• Allowing the system to enter then recovering from deadlock is another approach.
• Ignoring the problem of deadlocks is the most common approach in operating systems like UNIX.

Deadlock Prevention

• Preventing deadlocks involves constraining how resource requests are made.
• Mutual exclusion is not always necessary for sharable resources but is crucial for nonsharable resources.
• Hold and wait requires that processes request all their resources before executing, or request resources only when holding no other resources.
• No preemption involves releasing all held resources if a process needs a resource that cannot be immediately allocated. Preempted resources are added to the process's waiting list for later allocation.
• Circular wait employs a total ordering of resource types, ensuring processes request resources in ascending order. Preventing circular wait prevents a chain of requests where resource order is violated.

Deadlock Avoidance

• Deadlock avoidance requires prior information about resource requests.
• Processes declare the maximum number of resources they might need.
• The deadlock-avoidance algorithm dynamically checks for potential circular waits by analyzing changes in resource availability.
• The resource-allocation state is described by the numbers of available and allocated resources and the maximum demands of all processes. A safe state is defined such that a safe sequence exists of process termination.

Resource-Allocation Graph Algorithm

• Claim edges (dashed lines) indicate potential future requests by processes for particular resources.
• Claim edges transition into request edges when resources are requested.
• Assignment edges revert to claim edges when resources are released.
• Resources are claimed prior to allocation.

Resource Allocation Graph for Deadlock Avoidance

• Specific situations are shown using resource graphs to demonstrate safe and unsafe states.

Unsafe State in A Resource Allocation Graph

• Illustrations depict an unsafe state, marked by a deadlock or possibility thereof

Banker's Algorithm

• Appropriate for systems with multiple instances of resource types.
• Each process must declare the maximum use of each resource type in advance.
• Processes may need to wait until resources become available.
• Processes must return resources when no longer required.

Data Structures for the Banker's Algorithm

• Data structures for the Banker's Algorithm are used to track available resources, maximum resource allocation, current allocations, and the resources still needed by the process.

Example of Banker's Algorithm

• Demonstrates how Banker's Algorithm operates to find a safe state for a specific instance of resource allocation.

Example (Cont.)

• Continues to depict the solution for the example resource allocation scenario using Banker's Algorithm.