死鎖檢測演算法

1. 產生死鎖的必要條件有哪些如何預防死鎖

產生死鎖的必要條件有互斥條件、佔有並等待條件、不可剝奪條件和循環等待條件四個。預防死鎖的方法：死鎖預防、死鎖避免、死鎖檢測及恢復和死鎖忽略。

死鎖處理的策略和具體應用：

1、死鎖預防策略

在實際應用中，可以通過對資源訪問進行規劃，例如按照一定順序申請資源，避免同一時間佔有多個資源等。這種策略適合於資源需求較為明確且可控的場景，例如資料庫事務處理、多線程編程等。

2、死鎖避免策略

在系統設計階段，通過引入資源分配演算法，如銀行家演算法等，對進程進行評估，確保系統始終處於安全狀態。這種策略適用於資源需求和資源分配可以預測的場景，例如操作系統資源管理、分布式系統等。

3、死鎖檢測及恢復策略

在系統運行過程中，通過設計死鎖檢測機制，對死鎖進行實時監控並在發現死鎖時採取措施恢復。這種策略適用於資源需求和資源分配具有一定不確定性的場景，例如雲計算、大規模分布式計算等。

4、實際應用

對於死鎖忽略策略，實際應用中往往作為一種補充手段。在對系統性能和穩定性要求較高的場景下，可以設定一定的監控和報警機制，通過重啟系統或其他錯誤恢復手段解決死鎖問題，以保障系統的持續運行。

2. 死鎖怎麼解決

處理死鎖的思路如下：

預防死鎖：破壞四個必要條件中的一個或多個來預防死鎖。

避免死鎖：在資源動態分配的過程中，用某種方式防止系統進入不安全的狀態。

檢測死鎖：運行時產生死鎖，及時發現思索，將程序解脫出來。

解除死鎖：發生死鎖後，撤銷進程，回收資源，分配給正在阻塞狀態的進程。

預防死鎖的辦法：

破壞請求和保持條件：

1、一次性的申請所有資源。之後不在申請資源，如果不滿足資源條件則得不到資源分配。

2、只獲得初期資源運行，之後將運行完的資源釋放，請求新的資源。

破壞不可搶占條件：當一個進程獲得某種不可搶占資源，提出新的資源申請，若不能滿足，則釋放所有資源，以後需要，再次重新申請。

破壞循環等待條件：對資源進行排號，按照序號遞增的順序請求資源。若進程獲得序號高的資源想要獲取序號低的資源，就需要先釋放序號高的資源。

(2)死鎖檢測演算法擴展閱讀

形成死鎖的四個必要條件：

（1） 互斥條件：一個資源每次只能被一個進程使用。

（2） 請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。

（3） 不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪。

（4） 循環等待條件:若干進程之間形成一種頭尾相接的循環等待資源關系。

如果一組進程中每一個進程都在等待僅由該組進程中的其他進程才能引發的事件，那麼該組進程是死鎖的。

舉例來說：有兩個進程A和B,A持有資源a等待b資源，B持有資源b等待a資源，兩個進程都在等待另一個資源的同時不釋放資源，就形成死鎖。

3. 什麼是死鎖，怎樣引入死鎖

1.死鎖：如果一組進程中的每一個進程都在等待僅由該組進程中的其它進程才能引發的事件，那麼該組進程是死鎖的。
2.產生死鎖的原因：
（1）競爭不可搶占性資源。
（2）競爭可消耗資源。
當系統中供多個進程共享的資源如列印機，公用隊列等，其數目不足以滿足諸進程的需要時，會引起諸進程對資源的競爭而產生死鎖。12

（3）進程推進順序不當。
進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致產生進程死鎖。12

如果系統資源充足，進程的資源請求都能夠得到滿足，死鎖出現的可能性就很低，否則就會因爭奪有限的資源而陷入死鎖。其次，進程運行推進順序與速度不同，也可能產生死鎖。
一個線程也可引起死鎖。12

3.產生死鎖的四個必要條件：
（1） 互斥條件：一個資源每次只能被一個進程使用。
（2） 請求和保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。
（3） 不可搶占條件:進程已獲得的資源，在末使用完之前，不能強行剝奪，只能在進程使用完時由自己釋放。
（4） 循環等待條件:若干進程之間形成一種頭尾相接的循環等待資源關系。
這四個條件是死鎖的必要條件，只要系統發生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發生死鎖。因此可以寫下如下的預防死鎖的方法。
4.避免死鎖的方法：
（1）破壞「互斥」條件:就是在系統里取消互斥。若資源不被一個進程獨占使用，那麼死鎖是肯定不會發生的。但一般「互斥」條件是無法破壞的。因此，在死鎖預防里主要是破壞其他三個必要條件，而不去涉及破壞「互斥」條件。
（2）破壞「請求和保持」條件:在系統中不允許進程在已獲得某種資源的情況下，申請其他資源。即要想出一個辦法，阻止進程在持有資源的同時申請其他資源。
方法一：所有進程在運行之前，必須一次性地申請在整個運行過程中所需的全部資源。這樣，該進程在整個運行期間，便不會再提出資源請求，從而破壞了「請求」條件。系統在分配資源時，只要有一種資源不能滿足進程的要求，即使其它所需的各資源都空閑也不分配給該進程，而讓該進程等待。由於該進程在等待期間未佔有任何資源，於是破壞了「保持」條件。
該方法優點：簡單、易行且安全。
缺點：a.資源被嚴重浪費，嚴重惡化了資源的利用率。
b.使進程經常會發生飢餓現象。12

方法二：要求每個進程提出新的資源申請前，釋放它所佔有的資源。這樣，一個進程在需要資源S時，須先把它先前佔有的資源R釋放掉，然後才能提出對S的申請，即使它可能很快又要用到資源R。
（3）破壞「不可搶占」條件：允許對資源實行搶奪。
方法一：如果佔有某些資源的一個進程進行進一步資源請求被拒絕，則該進程必須釋放它最初佔有的資源，如果有必要，可再次請求這些資源和另外的資源。
方法二：如果一個進程請求當前被另一個進程佔有的一個資源，則操作系統可以搶占另一個進程，要求它釋放資源。只有在任意兩個進程的優先順序都不相同的條件下，該方法才能預防死鎖。
（4）破壞「循環等待」條件：將系統中的所有資源統一編號，進程可在任何時刻提出資源申請，但所有申請必須按照資源的編號順序（升序）提出。這樣做就能保證系統不出現死鎖。
利用銀行家演算法避免死鎖：
銀行家演算法:
設進程i提出請求Request[j]，則銀行家演算法按如下規則進行判斷。
(1) 如果Request[j]≤Need[i,j]，則轉向（2），否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。
(2) 如果Request[j]≤Available[j]，則轉向（3）；否則表示尚無足夠資源，Pi需等待。
(3) 假設進程i的申請已獲批准，於是修改系統狀態：
Available[j]=Available[j]-Request[i]
Allocation[i,j]=Allocation[i,j]+Request[j]
Need[i,j]=Need[i,j]-Request[j]
(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。
安全性演算法：
(1) 設置兩個工作向量Work=Available；Finish[i]=False
(2) 從進程集合中找到一個滿足下述條件的進程，
Finish [i]=False;

Need[i,j]≤Work[j];

如找到，執行(3)；否則，執行(4)123456

(3) 設進程獲得資源，可順利執行，直至完成，從而釋放資源。
Work[j]=Work[j]+Allocation[i,j];

Finish[i]=True;

Go to step 2;123456

(4) 如所有的進程Finish[i]=true，則表示安全；否則系統不安全。
5.死鎖的解除：
一旦檢測出死鎖，就應立即釆取相應的措施，以解除死鎖。死鎖解除的主要兩種方法：
1) 搶占資源。從一個或多個進程中搶占足夠數量的資源，分配給死鎖進程，以解除死鎖狀態。
2) 終止（或撤銷）進程。終止（或撤銷）系統中的一個或多個死鎖進程，直至打破循環環路，使系統從死鎖狀態解脫出來。
總結：
一般情況下,如果同一個線程先後兩次調用lock,在第二次調用時,由於鎖已經被佔用,該線程會掛起等待別的線程釋放鎖,然而鎖正是被自己佔用著的,該線程又被掛起而沒有機會釋放鎖,因此就永遠處於掛起等待狀態了,這叫做死鎖(Deadlock)。另⼀一種典型的死鎖情形是這樣:線程A獲得了鎖1,線程B獲得了鎖2,這時線程A調⽤用lock試圖獲得鎖2,結果是需要掛起等待線程B釋放鎖2,而這時線程B也調⽤用lock試圖獲得鎖1,結果是需要掛起等待線程A釋放鎖1,於是線程A和B都永遠處於掛起狀態了。12

注意：
寫程序時應該盡量避免同時獲得多個鎖,如果一定有必要這么做,則有一個原則:如果所有線程在需要多個鎖時都按相同的先後順序(常見的是按Mutex變數的地址順序)獲得鎖,則不會出現死鎖。比如一個程序中用到鎖1、鎖2、鎖3,它們所對應的Mutex變數的地址是鎖1<鎖2<鎖3,那麼所有線程在需要同時獲得2個或3個鎖時都應該按鎖1、鎖2、鎖3的順序獲得。如果要為所有的鎖確定一個先後順序比較困難,則應pthread_mutex_trylock調用代替pthread_mutex_lock 調用,以免死鎖。