Deadlock Prevention & Avoidance

### <style> html, body, .ui-content { background-color: #333; color: #ddd; } .markdown-body h1, .markdown-body h2, .markdown-body h3, .markdown-body h4, .markdown-body h5, .markdown-body h6 { color: #ddd; } .markdown-body h1, .markdown-body h2 { border-bottom-color: #ffffff69; } .markdown-body h1 .octicon-link, .markdown-body h2 .octicon-link, .markdown-body h3 .octicon-link, .markdown-body h4 .octicon-link, .markdown-body h5 .octicon-link, .markdown-body h6 .octicon-link { color: #fff; } .markdown-body img { background-color: transparent; } .ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a { color: white; border-left: 2px solid white; } .expand-toggle:hover, .expand-toggle:focus, .back-to-top:hover, .back-to-top:focus, .go-to-bottom:hover, .go-to-bottom:focus { color: white; } .ui-toc-dropdown { background-color: #333; } .ui-toc-label.btn { background-color: #191919; color: white; } .ui-toc-dropdown .nav>li>a:focus, .ui-toc-dropdown .nav>li>a:hover { color: white; border-left: 1px solid white; } .markdown-body blockquote { color: #bcbcbc; } .markdown-body table tr { background-color: #5f5f5f; } .markdown-body table tr:nth-child(2n) { background-color: #4f4f4f; } .markdown-body code, .markdown-body tt { color: #eee; background-color: rgba(230, 230, 230, 0.36); } a, .open-files-container li.selected a { color: #5EB7E0; } </style> # Deadlock Prevention & Avoidance ## Deadlock Prevention Recall the 4 necessary conditions for deadlock, see how can these conditions be canceled - **Mutual exclusion (ME)** : In order avoid it, do not require ME on shareable resources - Ex : There is no need to ensure ME on read-only files - However, some resources are not shareable (e.g. writer, critical section) - **Hold & wait** : In order avoid it, when a process requests a resource, it cannot hold any resource - Pre-allocate all resources before executing - Low resource utilization, and starvation is possible - **No preemption** : In order avoid it, all resource should be able to be preempted - Ex : P1 requests R1, which is allocate to P2, and P2 is waiting for R2 (P1 → R1 → P2 → P2) ⇒ R2 can be preempted and reallocated to P1 - Suitable for resources whose states can be easily saved and restored (e.g. CPU registers, memory) - Not suitable for resources such as mutex locks, semaphores, printers, tape drivers, etc. - **Circular wait** : - Impose a total ordering of all resources types - Let $R = \{R_1, R_2,..., R_N\}$ be the set of resource types - When request $R_k$, the process should release $R_{k+1},..., R_N$, i.e., when a process is requesting resource with index k, all resources with index larger than k that the process holds must be released - Example : - Tape drive = $R_1$, disk drive, $R_5$, printer = $R_{12}$ - A process must request tape and drive before printer - Proof : This policy can certainly avoid deadlocks - Let $P_0(R_0)$ → $R_1$ be $P_0$ is holding $R_0$ and waiting for $R_1$ - If circular wait holds, there must exist $P_{i_1}(R_{1})$ → $R_{2}$, $P_{i_2}(R_{2})$ → $R_{3}$,..., $P_{i_N}(R_{N})$ → $R_{1}$ relationship - $P_{i_N}(R_{N})$ → $R_{1}$ violates the the allocation policy above, so deadlocks will never occur ## Deadlock Avoidance - Every resource type has only single instance - **Resource-allocation graph (RAG) algorithm** based on circle detection - Every resource type has multiple instances - **Banker's algorithm** based on safe sequence detection ## Deadlock Avoidance for Single Instance per Resource Type ### Resource-Allocation Graph (RAG) Algorithm ![image](https://hackmd.io/_uploads/Hy4PohW8T.png) - Except for request edges and assignment edges, there are claim edges additionally - Pi → Rj : Pi may request Rj in the future - Claim edge transforms into request edge if the requests really happens - After the claim edge is transformed into request edge, it will further transform into assignment edge if the system decided to allocate resource to the requesting process Note that the **pointing direction will be reversed** - Assignment edge transforms back into claim edge if the process releases its holding resource. Here pointing direction will also be reversed - An example of formation of a deadlock ![image](https://hackmd.io/_uploads/BkAbEhWUp.png) - Before the process starts executing, all its claim edges must appear in the resource-allocation graph - The request can be **granted** only if the join of assignment edge that is transformed by Claim edge **will not form a cycle** - Check safety using a cycle-detection algorithm with $O(n^2)$ ## Deadlock Avoidance for Multiple Instances per Resource Type - **Safe state** : A system is in a safe state if there exists a sequence of allocations to satisfy requests by all processes - Such sequence of allocations is called **safe sequence** - Safe state ⇒ No deadlocks - Unsafe state ⇒ Possibility of deadlock - Ensure that the system will never enter unsafe state ⇒ Deadlock avoidance ### Safe State with Safe Sequence - Assume there are 12 tape drives (1 type of resource, 12 instances) - Assume at some time, there are three processes with their holding resources and max need resources : ![image](https://hackmd.io/_uploads/ryVeyWz86.png) - At this time, 9 resources is used ⇒ 3 resources are available - The worst scenario of this case is : - P0 needs at most 5 resources to execute next instruction - P1 needs at most 2 resources to execute next instruction - P2 needs at most 7 resources to execute next instruction - If we allocate resources to P1, P0, P2 sequentially : 1. By allocating all resources to P1, P1 can definitely finish its execution ![image](https://hackmd.io/_uploads/rJBalbG8a.png) 2. After P1 finishes its execution, it releases all resources it held ⇒ 5 resources are available By allocating all resources to P0, P0 can definitely finish its execution ![image](https://hackmd.io/_uploads/BkD5-bM8a.png) 3. After P0 finishes its execution, it releases all resources it held ⇒ 10 resources are available By allocating all resources to P2, P2 can definitely finish its execution ![image](https://hackmd.io/_uploads/SJ8a-ZMIp.png) - **\{P1, P0, P2\} is a safe sequence** ### UnSafe State with No Safe Sequence - Assuming at another time : ![image](https://hackmd.io/_uploads/SkJkXbz8T.png) - **No safe sequence exists** ⇒ The system has entered an unsafe state - A request is only granted if the **allocation leaves the system on a safe state** ### Banker's Algorithm - Use a **general safety algorithm** to pre-determine if any safe sequence exists after allocation - The allocation is allowed only if exists a safe sequence - Safety algorithm : 1. Assume processes exists a maximum amount of resources 2. Find a process that can be satisfied by free resources 3. Free the resource usage of the process 4. Repeat step 2. until all processes are satisfied ### Safety Algorithm Example 1 - Assume the total instances of each type of resources are : - A : 10 - B : 6 - C : 7 - The available instances are : - (A, B, C) = (3, 3, 2) ⇒ P1, P3 can be satisfied ⇒ Choose P1 ![image](https://hackmd.io/_uploads/SyVr8-f86.png) - The available instances becomes : - (A, B, C) = (5, 3, 2) ⇒ P3, P4 can be satisfied ⇒ Choose P3 ![image](https://hackmd.io/_uploads/HkPzv-MI6.png) - The available instances becomes : - (A, B, C) = (7, 4, 3) ⇒ All remain processes can be satisfied ⇒ Choose arbitrary process ![image](https://hackmd.io/_uploads/rkKRsWGIp.png) - One possible safe sequence = {P1, P3, P4, P2, P0} ### Safety Algorithm Example 2 - Assume the total instances of each type of resources are : - A : 10 - B : 5 - C : 7 - The available instances are : - (A, B, C) = (3, 3, 2) ![image](https://hackmd.io/_uploads/HkWM2Zz8a.png) - If request P1 = (1, 0, 2) arrives ⇒ If the request is permitted, allocation of P1 will become (3, 0, 2), need of P1 will become (0, 2, 0), available instances will become (2, 3, 0) ⇒ **Still exists a safe sequence {P1, P3, P4, P2, P0}** ⇒ The allocation request is permitted - If request P4 = (3, 3, 0) arrives ⇒ If the request is permitted, allocation of P4 will become (3, 3, 2), need of P4 will become (1, 0, 0), available instances will become (0, 0, 2) ⇒ **No safe sequence exists** ⇒ The allocation request is rejected