---
# System prepended metadata

title: 'Operating System #7'
tags: [note]

---

# Operating System #7

## The Deadlock Problem

* 其實前面已經提過，所謂的死結就是一群processes以循環的方式等候彼此的資源。
* 一個簡單的例子：
    * ![](https://i.imgur.com/EHjbbJg.png)
---
* 死結出現必須有以下四個條件同時符合：
    1.  Mutual exclusion
        * 一次一個process執行。
    2.  Hold and wait
        * process必須至少擁有一個資源，且正等候另一個資源。 
    3.  No preemption
        * 要得到資源時必須等候該資源的擁有者結束，不可強制取得並執行。 
    4.  Circular wait
        * 環狀結構的等待。 

## Resource-Allocation Graph

* 圓形代表process，方框裡面的點代表資源。
    * ![](https://i.imgur.com/NARvIyY.png)
* 圓形指向方框代表正在要求資源，方框指向圓形代表process正在占用該資源。
* 基礎概念：
    * 沒有環狀出現：一定沒有死結。
    * 有環狀出現：可能有可能沒有。

## Methods for Handling Deadlocks

* 確保系統不會有死結出現，通常有兩種方法：
    * Prevention: 確保上面說過的四種條件其中一種不會發生。
    * Avoidance: OS透過各種資訊去判斷該請求是否造成死結，進而決定是否執行或是要延後。
* 其他方案：
    * 允許系統進入死結，但是可以修正該狀態。
    * 無視該問題，將死結的發生視為程式設計師的問題。EX: UNIX。

## Deadlock Avoidance

* 藉由processes給予的資訊去判斷狀態是否會進入unsafe，如果請求的process會進入unsafe就拒絕掉。
    * unsafe不代表一定會發生死結，只是有可能。
    * ![](https://i.imgur.com/0wzInjJ.png)
* 題目正常會給予**總資源數量**、**每個process的需求**和**每個process目前擁有的資源**，要求你判斷現在是否會發生死結。
* 以下範例，總資源為`12`：

|| Max needs | Current holding | Will need |
|---| -------- | -------- | -------- |
|A| 10    | 5     | 5     |
|B| 4     | 2     | 2     |
|C| 9     | 2     | 7     |

* 只要用B,A,C就不會產生死結。(正常只要由需求最少一路往上推即可)

## Banker’s Algorithm

* 上面那種問題的延伸，在資源也有多個的情況下的演算法。
* 演算法寫個很複雜，其實步驟就是：
    1. Loop檢查每個未執行的process是否擁有資源執行
    2. 如果有，執行process，回收它的資源，回到第一步
    3. Loop結束，如果都執行完畢就沒有死結，反之亦然。

## Deadlock Detection

* 如果一個系統既沒有Deadlock Prevention也沒有Deadlock Avoidance，那它就需要：
    * deadlock detection algorithm去檢查系統狀態是否發生死結。
        * 使用Deadlock Avoidance的方法去偵測。
    * recovery algorithm去修復它。
        * 中斷process或是資源搶占

###### tags: `note`