死結
死結避免(deadlock avoidance)
想像一位謹慎的銀行經理,在批准每一筆貸款前都問自己:「如果我批了這筆,我還能不能滿足所有人最壞情況下的未來需求、把錢全部收回來?」若能,就批;若可能把銀行逼進死角,就讓借款人等。經理從不直接禁止貸款(那是預防)——而是把每筆請求拿去對未來檢驗,只有能讓銀行保持安全的請求才放行。死結避免正是這種小心翼翼、逐筆審核的做法。
避免假設每個行程事先宣告它對每種資源類型可能用到的最大數量。有了這份資訊,作業系統在批准任何請求前都會問:批准它會不會讓系統處於安全狀態——也就是存在至少一種行程的排序,使每個行程能輪流取得其最大需求、完成、然後釋放,讓下一個繼續?若批准後系統仍安全,就放行;若會導致不安全狀態(沒有任何這種保證完成順序的狀態),就讓請求的行程等待,即使此刻資源在實體上是有的。銀行家演算法就是執行這項安全檢查的標準程序。
避免比預防限制更少,因為它允許預防會禁止的請求,只要未來看起來仍安全就放行。但坦白說它要求很高,在通用作業系統中很少使用。它要求每個行程事先知道並宣告其最大需求(常常不可能),假設行程與資源的數量固定,且每筆請求都要跑一次安全檢查,代價不小。關鍵是:不安全狀態還不是死結——它是一個「死結變得可能」的狀態;避免不過是拒絕踏進任何這種狀態而已。
十台磁帶機,三個行程最終可能分別需要 7、4、6 台。即使某個請求在實體上可以批准,作業系統也只在仍存在安全序列時才批(例如先讓需要 4 台的行程完成、釋放,再服務其他)。若不再存在安全序列,該請求就等待。
避免只在批准後系統仍處於安全狀態時才放行請求。
避免需要每個行程事先宣告其未來最大需求,並對每筆請求做安全檢查——通常不切實際,所以通用作業系統很少採用。不安全狀態並非死結,只是一個可能演變出死結的狀態。
又称
另见