OS筆記-Chapter 7: Deadlocks

tags: OS

---

目錄

• 總論
  Chapter 1: Introduction
  Chapter 2: Operating-System Structures
• 行程管理
  Chapter 3: Processes
  Chapter 4: Threads
  Chapter 5: CPU Scheduling
  Chapter 6: Process Synchronization
  Chapter 7: Deadlocks
• 記憶體管理
  Chapter 8: Main Memory
  Chapter 9: Virtual Memory
• 儲存裝置
  Chapter 10: File-System Interface
  Chapter 11: File System Implementation
  Chapter 12: Mass-Storage Systems
  Chapter 13: I/O Systems
• 保護和安全
  Chapter 14: Protection
  Chapter 15: Security

---

系統模型(System Model)

• 例證(instance):每種型式的資源含有數種相同的例證，當某行程要求某一型式的例證實，配置這型之任一例證均可滿足

  • 例如:一個系統有兩個CPU，則CPU這種型式有兩個例證

• 一個行程只能依據下列的順序來使用資源:

  • 要求:若此要求不能立即被認可，則行程必須等候以獲得此資源
  • 使用:行程能夠在此資源上運作
  • 釋放:行程釋放資源

• 作業系統應先確定此資源已被要求，才能分配這項資源給此行程使用

• 一個集合中的每一行程若是在等待這集合其他行程所產生的事件，則此集合中所有行程均為死結狀態

死結的特性(Deadlock Characterization)

• 下列狀況在系統中同時成立時，死結才有可能發生:

  • 互斥(Mutual exclusion):至少有一資源是不可共用
  • 佔用與等待(Hold and wait):必須存在一個行程至少已佔用一個資源，且此行程正等待其他行程已佔用的另外資源
  • 不可搶先(No preemption):資源不能被搶先
  • 循環式等候(Circular wait):集合{P₀,P₁,…,Pₙ}，P₀等待的資源被P₁占用，P₁等候的資源被P₂占用，以此類推，Pₙ₋₁等待的資源被Pₙ占用

• 系統資源配置圖(system resource-allocation graph)

  • 方塊:資源型式
  • 點:該資源型式的例證
  • 要求邊(request edge):行程P指向資源R
  • 分配邊(assignment edge):資源R指向行程P
    
  • 分配邊必須指向點，要求邊只需指向方塊
  • 若此圖中出現循環，則可能存在死結(若每個資源型式只有一個例證，則一定有死結)
    

處理死結的方法(Methods for Handling Deadlocks)

• 一般來說使用以下三種方法:
  • 使用某一協議，防止或避免死結
    • 預防死結(deadlock prevention):確保死結必要條件有一項不會發生
    • 避免死結(deadlock avoidance):要求作業系統能先取得行程將會要求的資源，作業系統可以決定行程的要求可以被滿足或必須延遲
  • 允許死結，偵測出來再想辦法恢復
    • 以一個演算法來檢查其狀態
    • 另一套演算發來恢復
  • 忽視此問題
    • 被大部分的作業系統採用，所以由應用程式開發人員寫處理死結的程式
    • 系統可能停止工作，必須重啟

預防死結(Deadlock Prevention)

• 產生死結時，四個必須條件必須成立，所以只要這些條件有一個不成立，就能預防死結
  • 互斥:我們不可能藉由排除此條件來預防死結
  • 占用與等候:保證行程在要求資源時，不佔用任何資源
    • 每一行程在執行之前必須先要求並取得所需的資源
    • 讓每一行程只有在未占用資源的狀況下才能要求資源
    • 缺點:
      • 資源使用率不佳
      • 飢餓問題
  • 不可搶先:
    • 目前所持有的資源應該可以由他人搶先使用(可搶先)
    • 通常適用於資源狀態能輕易被保存或稍後可恢復的情況
    • 不適用於互斥鎖和號誌
  • 循環式等候:
    • 對所有的資源型式強迫安排一個線性的順序，行程要求資源時必須依數字大小，遞增提出要求
    • 證明:如果是循環式等待則{P₀,P₁,…,Pₙ}，P₀等待P₁，Pₙ等待P₀，又P₀占用的資源R₀順序小於P₁占用的資源R₁，R₀<R₁<…<Rₙ<R₀，R₀<R₀矛盾，因此不會有循環式等待

避免死結(Deadlock Avoidance

• 要求每一個行程聲明其所需每種型式的資源之最大數量

• 安全狀態(Safe State):系通能以某種順序將其資源分配給各個行程，而且能避免死結者
  

• 系統必須決定是否立刻把資源分配給行程，或是該行程進入等待，因此資源利用率可能比沒避免死結的狀況更低

• 資源配置圖演算法

  • 申請邊(claim edge):表示行程P可能在未來須要求資源R
    
  • 若無循環此要求被允許
    
  • 若發生循環，則需使行程進入等待(P₁等待)

• 銀行家演算法(Banker’s Algorithm)

  • 資源配置圖演算法不適用於有多個例證的資源
  • 當一個使用者要求一組資源時，就必須決定系統是否會因為這些資源的佔用而脫離安全狀態
  • m為資源型式的數量，n為行程數
  • 可用的(Available):長度m的向量，表示每種類型可用的例證(Available[j]=k)
  • 最大值(Max):n*m之矩陣，表示行程最大需求資源(Max[i][j]=k，Pᵢ至多要求k個Rⱼ)
  • 占用(Allocation):n*m之矩陣，表示行程目前佔用的資源(Allocation[i][j]=k)
  • 需求(Need):n*m之矩陣，表示行程剩餘的需求量(Need[i][j]=k)
  • 安全演算法(Safety Algorithm):
    • Finish[n]=false表示行程是否能完成，Work=Available表示可用的資源
    • 尋找Finish[i]=false且Need<Work的行程
      • Work=Work + Allocation
      • Finish[i]=True
      • 重複尋找
    • 如果找不到符合條件的，則檢查Finish[n]是否全為True，則此系統為安全狀態
    • m*n²次運算
  • 資源要求演算法(Resource-Request Algorithm)
    • Request為行程的要求向量(Request[i][j]=k)
    • 如果Request>Need則發生錯誤，因為行程超過他的最大需求
    • 如果Request>Available則行程必須等待
    • 假設系統已配置行程所要求的資源:
      • Available = Available - Request
      • Allocation = Allocation + Request
      • Need = Need - Request
  • 舉例:
    
    • Need = Max - Allocation
      
    • 順序<P1,P3,P4,P2,P0>可滿足

死結的偵測(Deadlock Detection)

• 若所有資源只具單一例證，則我們可以使用等候圖(wait-for graph)定義出一種偵測死結的演算法

  • 等候圖上Pᵢ->Pⱼ代表Pᵢ必須等候Pⱼ釋放行程
  • 資源配置圖與其轉換的等候圖
    
  • 若等候圖有循環則必定有死結
  • 需n²次的運算

• 具多個例證的資源型式

  • 使用一些類似銀行家演算法的資料結構
  • Work=Available表示可用的資源，Allocation=0，Finish[i]=True，否則Finish[i]=False
  • 尋找Finish[i]=false且Request<Work的行程
    • Work=Work + Allocation
    • Finish[i]=True
    • 重複尋找
  • Finish[i]=false則系統處於死結，行程Pᵢ陷入死結
  • m*n²次運算

• 何時使用偵測演算法

  • 多久會產生一次死結
  • 有多少個行程受死結發生影響
  • 例如:當CPU使用率低落時使用或每小時使用一次

死結恢復(Recovery from Deadlock)

• 終止死結的方法:
  • 取消一個或多個行程，以終止循環式等候
    • 取消所有死結中的行程
    • 一次取消一個，直到死結結束
  • 搶先一個或多個行程，或的其資源
    • 選擇犧牲者(Selecting a victim):最小花費
    • 回撤(Rollback):將被搶先行程撤回到安全狀態，再重新開始
      • 最簡單的方法，全部撤回，再重新開始
      • 最有效率的方法，撤回到能解開死結的狀況，再重新開始
    • 飢餓(starvation):為避免同一行程一直被搶先，將撤回的次數包括在成本因素