Operating Systems - Deadlocks

Operating Systems - Deadlocks

• Deadlocks occur in multi-programming environments, where several threads compete for a finite number of resources.
• A thread requests resources; if they're unavailable, the thread enters a waiting state.
• Sometimes, a waiting thread can't change state because the requested resources are held by other waiting threads.
• A deadlock occurs when every process in a set of processes is waiting for an event that can only be caused by another process in the set.
• A set of threads is in a deadlocked state when each thread waits for an event caused by another thread in the set.

System Model

• Systems have a finite number of resources to be distributed among competing threads.
• Resource types are R1, R2, ..., Rm.
• Examples of resources include CPU cycles, memory, I/O devices.
• Synchronization tools (e.g., mutex locks, semaphores) are also resources.
• Each resource type (e.g., R₁) has a number of instances (e.g., W₁).
• Processes utilize resources in these steps:
  • Request: The thread asks for a resource.
  • If the request can't be granted immediately, the thread waits.
  • Use: The thread operates on the resource.
  • Release: The thread releases the resource after usage.

Deadlock Characterization

• Deadlocks arise when these four conditions hold simultaneously:
  • Mutual Exclusion: Only one process can use a resource at a time.
  • Hold and Wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
  • No Preemption: Resources cannot be taken away from a process holding them until the process releases them.
  • Circular Wait: There exists a cycle of waiting processes, where each process is waiting for a resource held by the next process in the cycle.

Deadlock Prevention

• Invalidate one of the four conditions to prevent deadlocks.

  • Mutual Exclusion: Break mutual exclusion for those resources that can be shared.
  • Hold and Wait: Require a process to request all its needed resources at once, preventing it holding some while waiting for others.
  • No Preemption: Allow the system to preempt resources from a process that's waiting and give them to a process that's requesting them.
  • Circular Wait: Impose a total ordering on all the resources. Requiring each process to seek resources in an increasing order prevents circular waits.

Deadlock Avoidance

• Systems must have a priori information about how resources are to be requested.
• Deadlock avoidance algorithms dynamically examine the resource allocation state to prevent circular waits.
• Resource allocation states use available and allocated resources and maximum demands of processes.

Safe State

• A system is in a safe state if there exists a safe sequence of all processes (e.g., P₁, P₂, ..., Pn).
• The resources needed by P₁ can be granted using current available resources and resources of processes with indices < i.
• If a process requests resources when they are unavailable in the safe state, the process can wait until the other processes have completed and can obtain the resources it requires in a safe order.

Unsafe State

• If a system is in an unsafe state, there is a possibility of deadlock.
• However, not all unsafe states lead to deadlocks.

Resource Allocation Graph

• Deadlocks can be analyzed using a system resource allocation graph, which consists of a set of vertices (V) and edges (E) representing threads (T) and resource instances (R).
• A request edge (T1 → R;) signifies that T1 has requested R₁ and is waiting.
• An assignment edge (R; → T1) indicates that R₁ has been allocated to T₁.
• Cycle in the graph might imply potential deadlock.
• If there are no cycles, then the system is in a safe state.