Deadlock Prevention, Deadlock Avoidance | Deadlock Detection

What is DeadLock?

• Deadlock is a situation where two or more processes are unable to proceed because each is waiting for the other to release a resource.
• To understand deadlocks, it's essential to first establish the system model, which includes key components such as:

1. Resources

• Resources can be hardware (e.g., printers, CPU) or software (e.g., files, semaphores).
• Each resource is categorized into various types, and multiple instances of each type might exist.

2. Processes

3. Allocation Matrix

4. Request Matrix

Deadlock Characterization

1. Mutual Exclusion

• At least one resource must be held in a non-shareable mode, meaning only one process can use it at a time.
• Example: Consider a printer as a non-shareable resource. Only one process can print at a time.
• If process A is printing, process B cannot access the printer until process A is done.

2. Hold and Wait

• Processes must hold a resource while waiting for another resource, which can result in circular waiting.
• Example: Suppose a process holds a printer and then requests access to a scanner.
• While waiting for the scanner, it retains its hold on the printer.
• This waiting with resources held is the "hold and wait" condition.

3. No Preemption

• Resources cannot be preempted from a process.
• If a process is using a resource and needs another one, it must release the current resource and request a new one.
• Example: If a process has obtained a resource (e.g., a file or a CPU), that resource cannot be taken away from the process.
• The process must willingly release it.

4. Circular Wait

• A set of processes must be waiting for resources in a circular chain.
• Each process in the chain is waiting for a resource held by the next process.
• Example: Consider three processes, L, M, and N. L is waiting for a resource held by M,
• M is waiting for a resource held by N, and N is waiting for a resource held by L.
• This forms a circular chain of dependencies, satisfying the "circular wait" condition.

Methods for Handling Deadlocks

Deadlock Prevention

Resource Allocation Graph (RAG)

• In a Resource Allocation Graph, nodes represent processes and resources, while edges indicate resource requests and allocations.
• A cycle in this graph implies a deadlock. By avoiding circular dependencies in the RAG, deadlocks can be prevented.
• Example: Consider two processes (P1 and P2) and two resources (R1 and R2). P1 holds R1 and requests R2, while P2 holds R2 and requests R1.
• This situation forms a cycle in the RAG, indicating a potential deadlock.

Eliminate Mutual Exclusion

• This approach involves making resources shareable instead of exclusive.
• By allowing multiple processes to share resources simultaneously, you eliminate the mutual exclusion condition.
• However, this may not always be feasible, especially for certain types of resources.

Solve Hold and Wait

• In this strategy, processes are required to request all the resources they need at the beginning of their execution.
• They will only begin execution once all requested resources are available.
• This way, processes won't hold resources while waiting for others, breaking the hold and wait condition.
• However, it can lead to resource underutilization.

Deadlock Avoidance

Banker's Algorithm

• The Banker's algorithm is a method for deadlock avoidance.
• It allocates resources to processes only if the system remains in a safe state.
• It checks if resource requests can be granted without causing a deadlock.
• Example: Imagine a bank with a fixed amount of money (resources) and multiple customers (processes) making withdrawal requests.
• The bank ensures that it always has enough resources to satisfy customer demands without causing insolvency (deadlock).

a. Allow Preemption:

• Preemption involves forcibly taking resources away from processes.
• When a high-priority process requests a resource currently held by a lower-priority process, the lower-priority process may be preempted to release the resource.
• This helps avoid circular waiting by allowing resources to be reallocated to processes with higher priority.

b. Circular Wait Solution:

• Implement a resource allocation strategy that ensures that resource requests do not create circular waiting.
• For example, using a resource allocation graph or the Banker's algorithm to determine whether a resource allocation will lead to a safe state, avoiding potential circular waits.
• These strategies aim to address the four necessary conditions for deadlock, ensuring that resources are allocated and released in a way that minimizes the risk of deadlock formation.
• Each approach has its advantages and drawbacks, and the choice of strategy depends on the specific requirements and constraints of the system.

Deadlock Detection

• (i) Wait Die
• (ii) Wound Wait
• (iii) Banker's Algorithm
• (iv) Resource allocation Graph

Wait-Die Scheme

• In Wait-Die: Younger processes are allowed to wait,
• but if a younger process requests a resource held by an older process,
• the younger process is aborted (dies). Older processes continue.

Wound-Wait

• In Wound-Wait: Older processes are allowed to wait,
• while younger processes are allowed to wait.
• if they request a resource held by an older process.

Recovery from Deadlock

• Process Termination
• Process Rollback
• Wait-die Scheme
• Wound Wait Scheme
• Allow Preemption

Process Termination

• Processes involved in a deadlock can be terminated, releasing their held resources.
• Example: If processes P1, P2, and P3 are deadlocked, the system can choose to terminate one or more of them, breaking the deadlock.

Process Rollback

• In some cases, it may be possible to roll back the state of a process to a previously defined checkpoint to release resources and resolve the deadlock.
• Example: A database system might roll back a transaction to a consistent state to break a deadlock in a multi-transaction scenario.

Conclusion

• Deadlocks are a challenging problem in computer systems, and they can be managed using prevention, avoidance, detection, and recovery methods.
• Certainly, deadlock can arise if the following four necessary conditions hold simultaneously: