Deadlock Prevention

3.1.1 Breaking Mutual Exclusion

Explanation:
Deadlock prevention aims to structurally eliminate one or more of the four necessary deadlock conditions. To break mutual exclusion, the OS attempts to make resources sharable wherever possible. Although many hardware resources must remain non-sharable, software-managed resources can often be redesigned to support concurrent access. This reduces the number of exclusive locks and minimizes the opportunity for circular dependencies to form.

Example:
Instead of exclusive file locks, the OS uses read-write locks allowing multiple readers concurrently, reducing mutual exclusion scenarios.

Use Cases:
• File systems allowing parallel read access
• Shared memory with atomic operations
• Replacing mutexes with lock-free data structures

3.1.2 Eliminating Hold & Wait

Explanation:
To eliminate Hold & Wait, processes must either request all required resources at the start or release held resources before requesting new ones. This ensures no process holds one resource while waiting for another. Although effective at preventing deadlocks, this approach often reduces system efficiency because resources may remain idle even when unused.

Example:
A print-and-save process must request both the printer and disk at the beginning. If unavailable, it waits without holding anything.

Use Cases:
• Batch processing systems
• Programs that execute predictable multi-step operations
• Real-time systems needing deterministic allocation

3.1.3 Allowing Preemption

Explanation:
Allowing preemption means the OS can forcibly take resources away from a process and reassign them when needed to avoid deadlock. Preemption works best for CPU time, memory pages, and logical locks but is not always applicable to hardware resources. The OS attempts to interrupt and roll back processes without compromising data integrity.

Example:
If P1 holds memory and waits for I/O, while P2 needs memory but holds the I/O device, the OS may preempt memory from P1, allowing P2 to proceed and later return memory to P1.

Table:

Use Cases:
• Paging systems
• Transaction rollback
• Memory-managed multi-tasking systems

3.1.4 Breaking Circular Wait

Explanation:
To break circular wait, the OS imposes a strict global ordering of resource acquisition. Every resource is assigned a number, and processes must request resources in ascending order. This prevents cyclic dependencies because no process can wait for a lower-numbered resource while holding a higher-numbered one.

Example:
Resource ordering: R1 < R2 < R3
Processes must request R1 before R2, and R2 before R3.

Table:

Use Cases:
• Operating system device allocation
• Database locking order policies
• Distributed transaction systems

3.2 Deadlock Avoidance

3.2.1 Safe State Concept

Explanation:
A safe state is a system state from which all processes can complete their execution without causing deadlock. The OS evaluates whether allocating a resource will still leave the system in a safe sequence. If not, the allocation is denied. Safe states are crucial in avoidance algorithms, especially Banker's Algorithm.

Example:
If the system finds a sequence P1 → P3 → P2 that allows all processes to complete, the state is safe.

Table:

Use Cases:
• Banker's Algorithm
• Resource-aware real-time systems
• Virtual machine scheduling

3.2.2 Unsafe State Concept

Explanation:
An unsafe state is not necessarily a deadlock but represents a condition where the OS cannot guarantee that all processes will complete. If resource allocation leads into an unsafe state, the system risks entering a deadlock. Avoidance algorithms reject or delay requests that push the system into unsafe states.

Example:
If no possible completion sequence exists after a resource allocation, the state becomes unsafe.

Use Cases:
• Preemptive resource schedulers
• Cloud environments allocating VMs
• Database management during transaction scheduling

3.2.3 Need, Allocation, Max Matrices

Explanation:
Deadlock avoidance depends on three matrices:
• Allocation Matrix – Resources currently allocated to each process
• Maximum Matrix – Maximum resources each process may request
• Need Matrix – Remaining resources required (Need = Max − Allocation)

These structures allow the OS to compute possible safe sequences and decide whether granting future resource requests is safe.

Example:
If Max = [7] and Allocation = [5], then Need = [2].

Table:

Use Cases:
• Banker's Algorithm safety checks
• OS kernel resource allocation policies
• Multi-resource transaction managers