死鎖
這個概念是作業系統里面很重要的內容，前陣子面試位元組被問到了，太久沒復習，面經變涼經，
死鎖（Deadlock），又被翻譯為死結，是作業系統或軟體運行的一種狀態，在多任務系統下，當一個或多個行程等待系統資源、而資源又被行程本事或其他行程占用，就形成了死鎖，現如今的作業系統都是多任務執行，只有可以協調好不同的行程，才可以讓系統運行流暢不卡頓，如下丑圖所示：
起因
如果系統只有一個行程在運行，當然不會產生死鎖，就像獨生子女在家似的，不過這是理想狀態，在現實中可遇不可求，
死鎖的四個條件：
- 禁止搶占 (No preemption) ： 系統資源不能被強制從一個行程中退出
- 持有和等待 (Hold and wait) : 一個行程可以在等待時有系統資源
- 互斥 (Mutual exclusion) : 資源只能同時分配給一行程，無法多個行程共享，比如驅動器、列印機等
- 回圈等待 (Circular waiting) ：一系列行程互相持有其他行程所需要的資源
死鎖只有在四個條件（必要條件）同時發生，防止死鎖發生只需要破壞其中一項，一般的，解決死鎖的方法分為死鎖的預防、避免、檢測與恢復三種，
死鎖的預防
死鎖的預防是保證系統不進入死鎖狀態的一種策略，方法就是要求行程在創建時服從某種協議，從而打破產生死鎖的四個必要條件，
- 打破禁止搶占條件：允許行程強行從占有者那里奪取資源，
- 打破持有和等待條件：實行資源預先分配的策略，
- 打破互斥條件：允許行程同時訪問某些資源，但是某些資源（如列印機）不可以被同時訪問，這是由于資源本身的屬性所決定的，所以該方法價值不大
- 打破回圈等待條件：實行資源有序分配策略，即把資源事先分類編號，按號分配，這樣不會因為資源分配形成環路
死鎖的避免
該策略不限制行程有關申請資源的命令，而是對行程所發出的每一個申請資源命令加以動態檢查，并根據檢查結果決定是否進行資源分配，
該策略用到一個著名的避免死鎖的演算法--銀行家演算法，由Dijstra提出并加以解決的，具體分析這里不展開了，簡要概括下該演算法：銀行家演算法允許死鎖必要條件重的互斥條件、占有且申請條件、不可搶占條件的存在，這樣它與預防死鎖的方法相比限制較少，資源利用程度高了，
演算法的缺點如下：
- 演算法要求客戶數保持不變，這在實際使用作業系統中很難實作，
- 這個演算法保證客戶在有限時間內得到滿足，但是實時客戶要求快速回應，所以要考慮這個因素，
- 尋找安全序列的程序中，實際上增加了系統開銷，
檢測與恢復
死鎖檢測：
if 每種資源型別只有一個實體：{
構建資源分配圖，采用DFS確定是否由環路
} else if {
每種資源型別還有多個實體的情況：
構建向量矩陣
}
最簡單的消除死鎖的辦法是重啟～沒有重啟解決不了的事情，如果有，就重買臺機器，
逃）
死鎖恢復：
- 搶占：不通知原行程的情況下，將某一資源從一個行程強行取走給另一個行程使用，然后將資源再送回，
- 回滾：周期性對行程進行檢查點檢查，即將行程的狀態寫入一個檔案以備以后重啟，包括存盤映像、資源狀態，新的檢查點不覆寫原有檔案，而是寫到新檔案中，
- 殺死行程：殺死環中的一個或多個行程；
附加：
如果一個行程被多次回滾，遲遲不能占用必須的系統資源，可能會導致資源匱乏 (resource starvation)，
Resource starvation is a problem encounterd in concurrent computing where a process is perpetually denied necessary resources to process its work. Starvation may be caused by errors in a scheduling or mutual exclusion algorithm. Also, it can be caused by resource leaks.
Then what is resorce leaks? Resource leaks are particular type of resource consumption by a computer program where the program does not release resources it has acquired. Also, resource leaks are particularly a problem for resources avaliable in very low quantities. Leaking a unique resource, such as a lock, is pretty serious, as this causes immediate resource starvation and cause deadlock.
活鎖
活鎖（livelock），與死鎖相似，死鎖是行程都在等待對方先釋放資源，而活鎖則是行程彼此釋放資源后同時占用對方釋放的資源，當此情況持續發生時，盡管資源的狀態不斷改變，但每個形成都無法獲取所需資源，使得事情沒有任何進展，
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/20590.html
標籤：Linux