銀行家演算法求取安全進程執行序列

Ⅰ 避免死鎖的方法有哪些

1、避免給一個鎖嵌套上鎖，在持有一個鎖的時候，不要再給這個鎖上鎖。如果使用多個鎖，使用std::lock。

2、在持有鎖時，不要調用別人提供的函數，因為你不清楚別人的代碼怎麼實現的，不知道它是不是在使用鎖。

3、給多個鎖上鎖時，固定順序。如果在給多個所上鎖，並且無法使用std::lock，最好的做法就是在每一個線程中，都按照同樣的順序。

4、分層次來使用鎖，把程序分成幾個層次。區分每個層次中使用的鎖，當一個線程已經持有更低層次的鎖時，不允許使用高層次的鎖。可以在程序運行時給不同的鎖加上層次號，記錄每個線程持有的鎖。

(1)銀行家演算法求取安全進程執行序列擴展閱讀：

解決方法

在系統中已經出現死鎖後，應該及時檢測到死鎖的發生，並採取適當的措施來解除死鎖。

死鎖預防。

這是一種較簡單和直觀的事先預防的方法。方法是通過設置某些限制條件，去破壞產生死鎖的四個必要條件中的一個或者幾個，來預防發生死鎖。預防死鎖是一種較易實現的方法，已被廣泛使用。但是由於所施加的限制條件往往太嚴格，可能會導致系統資源利用率和系統吞吐量降低。

死鎖避免。

系統對進程發出的每一個系統能夠滿足的資源申請進行動態檢查，並根據檢查結果決定是否分配資源；如果分配後系統可能發生死鎖，則不予分配，否則予以分配。這是一種保證系統不進入死鎖狀態的動態策略。

死鎖檢測和解除。

先檢測：這種方法並不須事先採取任何限制性措施，也不必檢查系統是否已經進入不安全區，此方法允許系統在運行過程中發生死鎖。但可通過系統所設置的檢測機構，及時地檢測出死鎖的發生，並精確地確定與死鎖有關的進程和資源。檢測方法包括定時檢測、效率低時檢測、進程等待時檢測等。

然後解除死鎖：採取適當措施，從系統中將已發生的死鎖清除掉。

這是與檢測死鎖相配套的一種措施。當檢測到系統中已發生死鎖時，須將進程從死鎖狀態中解脫出來。常用的實施方法是撤銷或掛起一些進程，以便回收一些資源，再將這些資源分配給已處於阻塞狀態的進程，使之轉為就緒狀態，以繼續運行。死鎖的檢測和解除措施，有可能使系統獲得較好的資源利用率和吞吐量，但在實現上難度也最大。

Ⅱ 什麼是死鎖,簡述死鎖發生的四個必要條件,如何避免死鎖

死鎖是一種特定的程序狀態，它發生在兩個或多個進程永久性地等待對方釋放資源，從而導致它們都無法繼續執行。這種狀態是由於進程間的競爭條件和不恰當的同步機製造成的。

死鎖發生的四個必要條件是：

1. 互斥條件：至少有一個資源必須處於非共享模式，即一次只有一個進程能夠使用。如果其他進程請求該資源，請求者只能等待，直到資源被釋放。

2. 持有並等待：一個進程持有至少一個資源，但因等待另一進程釋放其他資源而處於阻塞狀態。這意味著進程不會釋放它持有的任何資源，除非得到其他所需的資源。

3. 非搶占條件：資源不能被強制從一個進程中奪走。進程必須主動釋放資源。這與操作系統的某些強制管理策略有關，但並不適用於所有情況。

4. 循環等待：存在一個進程等待循環，即進程集合{P1, P2, ..., Pn}中的P1正在等待由P2持有的資源，而P2又在等待由P3持有的資源，……，直到最後Pn在等待由P1持有的資源為止。這是一個循環依賴關系，導致所有相關進程都處於等待狀態。

避免死鎖的策略包括：

避免循環等待：通過確保系統始終處於安全狀態來避免死鎖。這可以通過銀行家演算法或其他資源分配演算法來實現，以確保每次資源請求都能被滿足而不會導致死鎖。此外，還可以預先分配所有必要的資源給進程，從而減少請求和等待的可能性。這意味著一次性獲取所有所需資源，然後進行操作，完成後釋放所有資源給其他進程使用。這樣的策略可以避免循環等待條件的發生。此外，合理設計系統並發級別和交互方式也可以減少死鎖的發生概率。通過檢測和恢復機制處理死鎖：即使採取了預防措施，死鎖仍然可能發生。因此，檢測和解決死鎖的策略也是必要的。這包括監視系統狀態並檢測死鎖的發生，然後採取措施解決它，如撤銷或中止導致死鎖的進程。採用破壞四個必要條件之一的方式預防死鎖：改變互斥條件是不可能的，但可以通過其他方式破壞四個必要條件中的某些條件來預防死鎖。例如，可以通過使用超時來破壞等待條件，讓一個進程持有多個資源的固定時間來迫使其他進程不得不放棄等待的資源；或者通過強制分配策略來破壞循環等待條件等。這些方法都需要系統管理員根據實際情況仔細選擇和使用，以最大限度地減少死鎖的風險。合理安排進程的執行順序：通過合理安排並發執行的進程順序，避免產生競爭條件和循環等待的情況。利用一次性封鎖的策略來防止系統發生死鎖，當要訪問某項數據時一定要獲取全部封鎖方可進行任務執行；避免在中間某個過程中將所需封鎖釋放掉的情況發生。合理設置進程的優先順序，保證不會出現互鎖或者一個循環互鎖的進程的組合產生以避免死鎖問題出現等都可以幫助解決該問題。在實際編程中可能根據系統需要靈活運用以上方法中的一種或多種來實現防止死鎖發生的目的從而保持系統穩定和數據的完整安全。

Ⅲ 什麼是死鎖，怎樣引入死鎖

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 調用,以免死鎖。