Deadlock


# To-do
- [ ] update last recovery part


Deadlock problem -** A set **of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set


> - Has a set of processes
> - Has a set of resources
> - deadlocks can occur across machines (between I/O processes)
> Paradigm of resource usage by process →

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Feb2997df-06f0-4a58-a3ab-8a260766ca4c%2FUntitled.png?table=block&id=b09cf27f-fd2c-4fde-ac6b-6e47c6f16cad&cache=v2)



> ex. - semaphores A and B, initialized to 1
>  - P1 and P2 each hold one tape drive and each needs another one

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F295577a4-2317-41fe-a9f6-1189a2a6234b%2FUntitled.png?table=block&id=2c8323b5-ea0d-4f36-afe3-5e629c1ac5a5&cache=v2)

> Deadlock problem is important in special purpose OS


# Bridge Crossing
> - it can be resolved if one car backs up - preempt resources and rollback
> - Several cars may have to be backed up(kill process) if a deadlock occurs
> - Starvation is possible

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fb18b9b81-b9ab-4d66-b14c-c7d635c684c2%2FUntitled.png?table=block&id=a0e07da0-3140-4acf-9739-fcbee231f253&cache=v2)

> Kill process need restart process - Why?


# Resource Allocation Graph
> $$G = (V, E).$$
> Model tuple of the state of a computer system as a directed graph
> **Request edge** : process to resource (not to special one resource set itself)
> **Allocation edge **: resource to process
> 

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F0b47c6e3-caf9-44ec-822a-2bb25517d3e1%2FUntitled.png?table=block&id=bb437e11-4e02-4313-a5e3-a4af541a760e&cache=v2)




> ## Theorem 1
> **If a graph does not contain a cycle then no processes are deadlocked**

> ## Theorem 2
> **If there is only a “single” instance per resource type, then a set of processes are deadlocked if and only if the processes and resources form a cycle in the resource allocation graph**




## “Necessary” Conditions for a Deadlock
**Deadlock can arise if the following four conditions hold simultaneously - at the same time**

1. **Mutual exclusion** : only one process at a timfe can use a resource.
2. **Hold and wait** : a process holding at least one resource is waiting to acquire additional resources held by other processes.
3. **No preemption **: a resource can be released only voluntarily by the process holding it.
4. **Circular wait : **a cycle in the resource allocation graph



### So we will not make this conditions simultaneously by Handling Deadlocks
> theorem 2 is only enable sufficient condition


## Method 1: Deadlock Prevention
**Ensure that one of the four deadlock conditions never occur ← make one false among 4 (not about information, policy and data structure change)**
<details><summary>

1 →  make shareable share</summary>

make mutual exclusive available resources to not exclusively is impossible → Must hold for non-shareable resources
</details>

<details><summary>

2 → **No wait or No hold **(resources utilization become low, starvation possible)</summary>

Guarantee that whenever a process requests a resource, it does not hold any other resources
Require process to request and be allocated “all” its resources before it begins execution, or allow process to request resources only when the process has “none”.
</details>

<details><summary>

3 → become preemptive (stop while processing)</summary>

If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
Preempted resources are added to the list of available resources
Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting
Can be applied to resources whose state can be easily saved and restored later : e.g. CPU registers, memory, …
</details>

<details><summary>

4 → remove cycle (if no resources can be substituted → Theorem 2) **most used method**</summary>

Impose a total **ordering of all resource types**, and require that each process **requests resources in order **of enumeration
</details>


## Method 2: Deadlock Avoidance
**Avoid deadlock by run-time checking and allocation of resources - check before allocate (never enter an unsafe state)**
<details><summary>

**Requires** that the system has some additional a **priori information **and **algorithm**</summary>

Simplest and most useful model requires that each process declare the** maximum number of resources** of each type that it may need
**The deadlock-avoidance algorithm dynamically examines the “resource-allocation state” to ensure that there can never be a circular-wait condition**

</details>

- **Safe State** : System is in safe state if there exists a **safe sequence** of all processes
**requests resource → decide immediate allocation leaves the system in a “safe” state**

> **Resource-allocation state **is defined by the number of available and allocated resources, and the maximum demands of the processes



### Then How can we do that by what algorithm?
if resource is single instance → use resource allocation graph and check cycle
> **if resource is multiple instance →**

> 
> [Banker's algorithm](https://texonom.com/bankers-algorithm-a3e9530ac45b4c61806354379b55c593)
> 


## Method 3: Deadlock Detection and Recovery
**Let the system deadlock and then deal with it (No a priori information, algorithm exist)**
### **Detection Algorithm**
Request: an n x m matrix indicates the current request of each process (Replace Need with Request matrix) - it is safety algorithm in banker's algorithm
> usually each process is not assumed to have knowledge in its maximum use

**Then how often we will invoke algorithm - have no answer**

## Recovery from Deadlock
<details><summary>

**Methods of recovery**</summary>

</details>

5. Process terminate - lose all process, not easy to recover process done
6. resource preemption
> - Selecting a victim, rollback, starvation is an issue


> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F7bc1d018-01cc-425b-a17c-ec7615a6adb2%2FUntitled.png?table=block&id=60291423-d42a-4d02-a3e5-ed94f7618e42&cache=v2)
> **if resource is multiple instance → D**etection algorithm like banker's algorithm

> caution of starvation → aging
> need to kill cause process → re-deadlock
> Rollback - 최소한 싸이클이 없어질 만큼의 프로세스는 죽여야 한다.
> wait for 그래프는 어떤 프로세스가 어떤 리소스를 wait하고 있는가만 체크한다. 싸이클이 발생했으면 데드락이 발생 한 것이다.
> if resource is single instance → check wait-for graph 주깆거


### Method 4: No policy
Ignore the problem and pretend that deadlocks never occur in the system → just reboot
Used by most operating systems, including UNIX and Windows ← too much overhead




# Reference
- Refer Lock hierarchy
> [DeadLock](https://ozt88.tistory.com/35)





