中正大學，資工系，作業系統實驗室 陽春副教授 羅習五 shiwulo@gmail.com deadlock 中正大學，資工系，作業系統實驗室 陽春副教授 羅習五 shiwulo@gmail.com

前言： 版本：0.1 假如你想收到最新的作業系統資訊，請填寫底下表格，這份投影片每半年到一年會有一 次大更新，我會將更新資訊寄給您 https://goo.gl/GzqoXo 台灣的資訊教育較為特別，幾乎所有資工系的學生都要「考」研究所，因此無法直接使 用國外的教材 目前網路上看到大部分的教材都是pdf形式，無法修改，授課老師無法依照學生的需求， 增減資料 我希望能用幾年的時間，完成沒有版權問題，涵蓋恐龍本基本觀念，並以Linux為基礎的 作業系統簡介投影片 作業系統非常龐大，很多地方是我沒接觸過的、沒研究過的，因此投影片當中可能會有 不少錯誤

前言： 這份投影片對讀者（學生）的設定如下 由於計算機結構是研究所的內容，因此相關的部分會在投影片內交代清楚 （大學部只修過計算機組織） 略懂資料結構、演算法 「真的」會寫程式 約略看懂組合語言 了解Linux system programming，例如基本的fork、pipe、signal等等 由於計算機結構是研究所的內容，因此相關的部分會在投影片內交代清楚 （大學部只修過計算機組織） 恐龍本中涵蓋，但不重要的部分我放在投影片最後面的「補充的名詞解釋」 這份投影片依然以介紹概念為主，與恐龍本不同的是以Linux為例介紹概念

接下來的規劃 橋接恐龍書和Linux上，讓到業界的新鮮人可以透過這份投影片 快速了解整個Linux架構 更加模組化，教師可以選擇自己喜歡的部分，組成一個章節 每個章節都提供一個夠有代表性的實作 每個章節提供一系列的課後問題 提供更進階的部分

什麼是deadlock 一群task，彼此等待 考慮這個例子，系統中有二個task分別是A、B，他們個別需要 鎖定x和y A先鎖定x再鎖y，B先鎖定y再鎖定x。 如下表，1~4分別代表時間，在這樣的情況下A握有x等y，B握有y等x。 換句話說A等B，B等A。造成deadlock task A和task B不一定每次執行都會造成deadlock task A task B lock(x) lock(y)

deadlock的圖形表示 X X⇒A 表示X分配給A task A task B A⇒Y 表示Ｘ需要鎖定Ｙ Y

deadlock的圖形表示 （resource allocation graph） X X⇒A 表示X分配給A 如果resource X、Y各自只有1個instance，畫出「分配需求圖」以後，如果有loop表示系統存在deadlock task A task B A⇒Y 表示Ｘ需要鎖定Ｙ Y

相似的名詞：livelock 一群task彼此等待，但這群task不斷的改變自身的狀態，但卻無 法讓行程的有任何實質的進展 例如： 二個人在狹路上相遇，互讓，但這其中一個人讓出右邊時，另一個人剛 好讓左邊。 雖然二個人不斷的互讓，但還是無法「前進」

相似的名詞：starvation starvation（飢餓）問題：來自於某種資源分配方式，讓特定的 某些task幾乎拿不到任何的resource 例如：按照優先權分配resource，優先權最低的task有可能永遠 拿不到resource

發生deadlock必備的四條件 Mutual exclusion：資源無法共用 Hold and wait or resource holding：握有一些資源等待另一些 No preemption：OS無法隨意的將分配出去的資源再重新分配 Circular wait：resource allocation graph中至少有一個等待回 圈 These four conditions are known as the Coffman conditions from their first description in a 1971 article by Edward G. Coffman, Jr.

deadlock prevention mutual exclusion mutual exclusion是critical section的主要功能 mutual exclusion通常也是resource的本身特性，例如：印表機 不可能讓二個process在同一個時間列印 有時候可以改寫演算法，讓resource可以lock-free，例如：上 一個章節介紹的lock-free concurrent queue

deadlock prevention hold and wait 方法一：所有的process必須一開始的時候，就鎖住所有「可能」 需要的資源（因此只有hold沒有wait） 缺點是：會造成resource的使用率偏低，例如：打開powerpoint，因為 powerpoint有可能會印出投影片，所以就鎖住印表機！？因為「有可能」 就讓其他人在這段時間無法使用印表機 其次：鎖定的時間拉長，從「需求開始到資源使用結束」變成「程式一 開始到資源使用結束」 方法二：如果要新的資源時，必須釋放掉手上所有已經鎖定的 資源（因此只有wait沒有hold） 缺點：換句話說，就是每次都要重新「一次性鎖定所有『目前需要』的 資源」，釋放資源之時，資源可能被其他process鎖定，可能造成 starvation

deadlock prevention No preemption No preemption幾乎也是resource天生的性質，如果讓不能 preempt的resource變成preemptable代價通常很大 例如：印表機原則上是不能preempt，因為需要緊急印資料給 客戶，將印表機「關掉，重開」。算是讓印表機「preemptable」 的方法之一 有些時候可以用rollback解決，例如：上一章節介紹的 sequential lock 有時候可以用multi-version解決，例如：上一章節介紹的RCU 也可以是沒辦法「立即」lock某個resource，該task就釋放掉手 上的所有resource

deadlock prevention circular wait 依照特定順序鎖定資源，例如：先鎖定a再鎖定b 「授課老師認為」這是最可行的方法，因為這個方法和資源本 身的特性無關，主要是和「程式碼的撰寫方式有關」 缺點：有時候鎖定的順序和使用的順序相法，這會造成資源使 用率偏低 缺點：必須確認所有的programmer都牢記這個順序

deadlock avoidance 與deadlock prevention不同，deadlock avoidance是不要讓系 統進入「可能」造成deadlock的狀態 我們首先定義「safe state」，表示現在絕對不會進入deadlock 狀態 當系統「可能」發生deadlock就稱之為unsafe 注意：就算是unsafe也不一定會造成deadlock deadlock prevention需要事先知道「所有process可能需要的 resource」 deadlock prevention方法是：不讓系統進入circular wait的狀態

著名的deadlock avoidance方法 priority celling protocol（PCP） 可以防止系統進入deadlock狀態 高優先權的task等低優先權「頂多等一次」 是非常有用、有名的real-time OS常用的方法 需要搭配rate-monotonic（RM）排程演算法使用 RM是real-time system中最常見的排程演算法 Stack Resource Policy (SRP)  特性上與PCP非常類似 可以搭配earliest deadline first（EDF）排程演算法使用

本節未介紹的方法 Single instance of a resource type. Use a resource-allocation graph Multiple instances of a resource type. Use the banker’s algorithm 請參閱2017年，OS投影片

deadlock detection algorithms 如果所有的resource都是single instance，那麼檢查系統是否存 在迴圈 基本上是「週期性」使用banker’s algorithm檢查系統是否 deadlock

如果系統進入dealock狀態 假設系統支援roll back機制，讓某些task roll back，並釋放出 resource再重新執行 直接殺掉某些task（例如：佔用系統資源特別多的task）

討論 是否可以撰寫一個自動化的鎖定機制，當系統可能進入 deadlock狀態時，提出警告？ 是否可以給某個resource一個獨一無二的id 每此鎖定的時候，只能由低id往高id鎖定呢？

如果能解決id問題 是否可以解決circular waiting問題？ 應該可以，使用resource的address當id，每個task紀錄目前鎖 定的所有resource中，哪一個resource的address最大，接下來 只能鎖定address更大的resource（注意：kernel space中，不 會有二個resource擁有相同的address）

如果能解決id問題 是否可以解決circular waiting問題？ 如果想要鎖定address較小的resource，kernel噴出訊息，告訴 programmer，必須改變鎖定順序（授課老師覺得這個方法較可 行） 如果想要鎖定address較小的resource，必須先放棄手上所有的 resource，再依照address從小鎖到大

如果能解決id問題 是否可以解決circular waiting問題？ 通常我們鎖定resource時，表示已經對這個resource進行操作， 作業系統很難讓一個task可以「放棄鎖」，這違背了mutual exclusion 除非這個process本身是可以roll back（就是undo所有做過的事 情，回到從前）

本章節結束