owned this note
owned this note
Published
Linked with GitHub
---
## Deadlock Detection and Prevention
---
## What is a deadlock and how does it occur?
- A **deadlock** is a situation in which two or more processes are unable to proceed because each is waiting for the others to do something.
- Deadlocks occur in multi-process systems where processes compete for resources.
---
## Deadlock
```mermaid
graph TD
A[Process 1] -->|requests| R[Resource 1]
R -->|held by| B[Process 2]
B -->|requests| S[Resource 2]
S -->|held by| A
```
---
## What are the four necessary conditions for a deadlock to occur?
---
## Four Necessary Conditions for a Deadlock
1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait
---
## **Mutual Exclusion:**
Each resource can only be held by one process at a time.
```mermaid
graph TD
A[Process 1] -->|requests Resource| R[Resource]
B[Process 2] -->|requests Resource| R
style A fill:#ffcc66, stroke:#333,stroke-width:1px;
style B fill:#66ccff, stroke:#333,stroke-width:1px;
style R fill:#99ff99, stroke:#333,stroke-width:1px;
```
---
## **Hold and Wait:**
A process holding a resource is waiting to acquire additional resources held by other processes.
```mermaid
graph TD
A[Process 1] -->|requests Resource A| R1[Resource A]
A -->|holds Resource A, requests Resource B| R2[Resource B]
B[Process 2] -->|requests Resource B| R2
B -->|holds Resource B, requests Resource A| R1
style A fill:#ffcc66, stroke:#333,stroke-width:1px;
style B fill:#66ccff, stroke:#333,stroke-width:1px;
style R1 fill:#99ff99, stroke:#333,stroke-width:1px;
style R2 fill:#99ff99, stroke:#333,stroke-width:1px;
```
---
## **No Preemption:**
A resource cannot be forcibly removed from a process holding it.
```mermaid
graph TD
A[Process 1] -->|holds Resource| R[Resource]
B[Process 2] -->|requests Resource| R
C[Process 3] -->|requests Resource| R
style A fill:#ffcc66, stroke:#333,stroke-width:1px;
style B fill:#66ccff, stroke:#333,stroke-width:1px;
style C fill:#cc99ff, stroke:#333,stroke-width:1px;
style R fill:#99ff99, stroke:#333,stroke-width:1px;
```
---
## **Circular Wait:**
A set of processes is waiting for resources held by each other, forming a circular chain.
```mermaid
graph TD
A[Process 1] -->|holds Resource A, requests Resource B| R1[Resource A]
B[Process 2] -->|holds Resource B, requests Resource C| R2[Resource B]
C[Process 3] -->|holds Resource C, requests Resource A| R3[Resource C]
style A fill:#ffcc66, stroke:#333,stroke-width:1px;
style B fill:#66ccff, stroke:#333,stroke-width:1px;
style C fill:#cc99ff, stroke:#333,stroke-width:1px;
style R1 fill:#99ff99, stroke:#333,stroke-width:1px;
style R2 fill:#99ff99, stroke:#333,stroke-width:1px;
style R3 fill:#99ff99, stroke:#333,stroke-width:1px;
```
---
## How can a deadlock be prevented?
- Deadlocks can be prevented by removing any one of the four necessary conditions.
- Techniques for preventing deadlocks include:
- Resource Allocation Graph (RAG)
- Banker's Algorithm
- Time-Slicing
---
## Describe the technique of time-slicing as a method of preventing deadlocks.
- **Time-slicing** is a technique where resources are allocated to processes for a fixed amount of time, after which they are released.
- Processes are allowed to execute until their allocated time slice expires or they voluntarily release their resources.
- This prevents any single process from holding resources indefinitely, and ensures that other processes can eventually acquire the resources they need.
---
## How can a deadlock be identified in a system?
- Deadlocks can be identified by:
- Checking for circular wait conditions in the system.
- Using deadlock detection algorithms that periodically scan the system for deadlock conditions.
- One such algorithm is the Two-Phase Algorithm developed by HO Ramamurthy.
---
## What techniques can be used to resolve a deadlock?
- Deadlocks can be resolved by:
- Resource preemption: forcibly removing a resource from a process and allocating it to another.
- Process termination: aborting one or more processes to break the deadlock.
- Deadlock resolution algorithms are designed to select which processes or resources to preempt or terminate.
---
## Wait-Die Algorithm
```mermaid
graph TD
A[Process 1] -->|requests| R[Resource]
R -->|held by| B[Process 2]
style A fill:#ffcc66, stroke:#333,stroke-width:1px;
style B fill:#66ccff, stroke:#333,stroke-width:1px;
style R fill:#99ff99, stroke:#333,stroke-width:1px;
```
- Older process waits, younger process allowed to die
- Process 1 waits for Resource, while Process 2 proceeds
- If Process 2 requests the same resource, it is allowed to wait, while Process 1 proceeds
---
## Wound-Wait Algorithm
```mermaid
graph TD
A[Process 1] -->|requests| R[Resource]
R -->|held by| B[Process 2]
style A fill:#ffcc66, stroke:#333,stroke-width:1px;
style B fill:#66ccff, stroke:#333,stroke-width:1px;
style R fill:#99ff99, stroke:#333,stroke-width:1px;
```
---
## Wound Wait Algorithm
- Younger process waits, older process allowed to die
- Process 2 waits for Resource, while Process 1 proceeds
- If Process 1 requests the same resource, it is allowed to wait, while Process 2 proceeds
---
## Distributed Deadlock Detection HO Ramamurthy (Two-Phase Algorithm)
```mermaid
graph TD
A[Node] --> B(Take Local Snapshot)
B --> C{All Nodes Received Snapshot?}
C -- No --> B
C -- Yes --> D{Deadlock Detected?}
D -- No --> E(Algorithm Finishes)
D -- Yes --> F(Resolve Deadlock)
```
---
## Conclusion
- Deadlocks can be prevented by removing any one of the four necessary conditions.
- Techniques for preventing deadlocks include Resource Allocation Graph (RAG), Banker's Algorithm, and Time-Slicing.
- Deadlocks can be identified by checking for circular wait conditions or using deadlock detection algorithms.
- Deadlocks can be resolved by resource preemption or process termination.
- Distributed deadlock detection algorithms, such as the Two-Phase Algorithm, are used to detect and resolve deadlocks in distributed systems.
Google Drive
Gist
Clipboard
Sign in with Wallet
