Resource Allocation Graph

發表於 Disqus：
文章字數： 265 所需閱讀時間 ≈ 1 分鐘

Def: 令 G = (V, E) 為一有向圖，其中

  • V (頂點集合) 可分成兩類：
    • Process:
    • Resource: “•” 表示該資源的數量。
  • E (邊集合)也可分成兩類：
    • Request edge (申請邊)
    • Allocated edge (配置邊)
  • 範例:

在 Deadlock 中重要觀念

  • 若圖形沒有 Cycle 存在，則系統無死結 (No Cycle ⇒ No Deadlock)
  • 若圖形有 Cycle:
    • 若系統中毎類資源為 Multiple Instances (多個數量)，則有 Cycle 存在，不一定有死結
    • 若毎類資源皆為 Single Instance，則有 Cycle 存在，就一定有死結
  • 範例：