Q2Operating System

A deadlock is a situation where a set of processes are permanently blocked, each waiting for a resource held by another process in the same set. No process can proceed, none can release resources, and none can be awakened. This is a permanent blocking as opposed to a temporary wait.

Example: Process P1 holds Resource R1 and needs R2. Process P2 holds Resource R2 and needs R1. Neither can proceed — classic deadlock.

All four of the following conditions must hold simultaneously for a deadlock to occur:

• Mutual Exclusion: At least one resource must be held in a non-shareable mode. Only one process at a time can use the resource. If another process requests that resource, it must wait.
• Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently held by other processes.
• No Preemption: Resources cannot be preempted; a resource can be released only voluntarily by the process holding it after it has completed its task.
• Circular Wait: A set of processes {P0, P1, …, Pn} must exist such that P0 waits for a resource held by P1, P1 waits for a resource held by P2, …, Pn waits for a resource held by P0 — forming a circular chain.

Ensure that at least one of the four necessary conditions cannot hold. Strategies: Eliminate Mutual Exclusion (use sharable resources where possible), Eliminate Hold and Wait (request all resources at once or release all before new request), Allow Preemption (preempt resources from waiting processes), Eliminate Circular Wait (impose total ordering on resource types and require processes to request resources in increasing order).

The OS dynamically decides whether each resource request should be granted based on future possible states. Requires each process to declare its maximum resource needs a priori. The Banker's Algorithm checks if granting a request leads to a safe state. A safe state guarantees a safe sequence exists — all processes can eventually complete. If the resulting state is unsafe, the request is postponed.

Allow deadlocks to occur. Periodically run a detection algorithm: For single-instance resources, detect cycles in the Resource Allocation Graph (RAG). For multiple-instance resources, use an algorithm similar to the Banker's algorithm (maintaining Wait-For graph). Run periodically or when CPU utilization drops suspiciously low.

• Process Termination: Abort all deadlocked processes (drastic but simple). Or abort processes one at a time (by priority, resources held, time used) until deadlock is broken — re-run detection after each abort.
• Resource Preemption: Select a victim process, preempt its resources, rollback the victim to a safe state (or restart it), and continue. Must consider victim selection (minimize cost), rollback (safe state or total restart), and starvation prevention (limit the number of times a process is victim).