孫鐘秀操作系統(tǒng)第三章同步、通信與死鎖2

《孫鐘秀操作系統(tǒng)第三章同步、通信與死鎖2》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、3.5死鎖在多道程序系統(tǒng)中,多個進(jìn)程并發(fā)執(zhí)行可改善系統(tǒng)資源利用率,提高系統(tǒng)的吞吐量,但也有可能發(fā)生一種危險---死鎖。一、死鎖的概念例1：兩個小孩在一起玩耍，一個在玩皮球，另一個玩自動步槍，如果這兩個小孩都要對方手中的玩具，而又不肯先放掉自己拿著的玩具，這時就發(fā)生了僵持局面。1例2：系統(tǒng)有一臺打印機(jī)和一臺掃描儀，進(jìn)程P1、P2并發(fā)執(zhí)行，在執(zhí)行過程中均需使用打印機(jī)和掃描儀。CobeginProcessP1()ProcessP2(){……{……Request(打印機(jī))Request(掃描儀)…………Request(掃描儀)Request(打印機(jī))…………}Coe

2、nd當(dāng)P1、P2并發(fā)執(zhí)行時，可能出現(xiàn)如下序列：P1占用打印機(jī)，P2占用掃描儀。在以后某時刻P1又要申請掃描儀，但由于掃描儀被P2占用，P1只有等待；P2又申請打印機(jī)，但由于打印機(jī)被P1占用，P2只有等待。如此兩進(jìn)程均不能執(zhí)行而處于永遠(yuǎn)等待狀態(tài)，這種現(xiàn)象稱為死鎖。21.死鎖的定義在一組進(jìn)程中，每個進(jìn)程都等待被該組進(jìn)程中其他進(jìn)程所占有的資源，從而無限期陷入僵持的局面，這種現(xiàn)象稱為死鎖。如果死鎖發(fā)生，會浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。2.產(chǎn)生死鎖的原因競爭資源進(jìn)程間推進(jìn)順序不當(dāng)33.產(chǎn)生死鎖的必要條件1971年Coffman總結(jié)了系統(tǒng)產(chǎn)生死鎖的四個必要條件：互

3、斥條件：系統(tǒng)中存在臨界資源，進(jìn)程應(yīng)互斥地使用這些資源。占有和等待條件：進(jìn)程在請求資源得不到滿足而等待時，不釋放已占有的資源。不剝奪條件：進(jìn)程已占有的資源只能由屬主釋放，不能強(qiáng)行剝奪。循環(huán)等待條件：存在循環(huán)等待鏈，鏈中的每一個進(jìn)程都在等待下一進(jìn)程所持有的資源。44.處理死鎖的基本方法（1）死鎖防止（deadlockprevention）通過設(shè)置某些限制條件，去破壞死鎖四個必要條件中的一個或多個，來防止死鎖。較易實(shí)現(xiàn)，廣泛使用，但由于所施加的限制往往太嚴(yán)格，可能導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量的降低。5（2）死鎖避免不事先采取限制措施去破壞產(chǎn)生死鎖的條件，而是在資

4、源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。只需事先施加較弱的限制條件，可獲得較高的資源利用率和系統(tǒng)吞吐量，但在實(shí)現(xiàn)上有一定難度。在較完善的系統(tǒng)中常用此方法。6（3）檢測死鎖事先并不采取任何限制，允許死鎖發(fā)生，但可通過檢測機(jī)構(gòu)及時檢測出死鎖的發(fā)生，并精確確定與死鎖有關(guān)的進(jìn)程和資源。（4）解除死鎖與檢測死鎖相配套，當(dāng)檢測到發(fā)生死鎖時，采用一定的方法解除死鎖。實(shí)現(xiàn)難度大，但可獲得較好的資源利用率和系統(tǒng)吞吐量。7二、死鎖防止設(shè)法破壞產(chǎn)生死鎖的四個必要條件之一。條件1（互斥條件）是由設(shè)備的固有特性所決定的，不僅不能改變，還應(yīng)加以保證。

5、8破壞條件2（占有和等待條件）采用資源的靜態(tài)分配策略。靜態(tài)分配是指進(jìn)程必須在執(zhí)行前一次性地申請所需的全部資源，若系統(tǒng)有足夠資源則完全分配。若分配時只要有一種資源不能滿足，則不分配任何資源，而讓進(jìn)程等待。優(yōu)點(diǎn)：簡單、易于實(shí)現(xiàn)且安全。缺點(diǎn)：資源嚴(yán)重浪費(fèi)，嚴(yán)重降低資源的利用率；使進(jìn)程延遲運(yùn)行。9破壞條件3（不剝奪條件）采用剝奪式調(diào)度方法。占有資源的進(jìn)程，再提出新資源請求時，若有則分配，否則剝奪此進(jìn)程已占有的所有的資源，并讓進(jìn)城進(jìn)入等待狀態(tài)，資源充足后再喚醒它重新申請所需資源。實(shí)現(xiàn)復(fù)雜、要付出很大的代價。10破壞條件4（循環(huán)等待條件）資源按序分配：把系統(tǒng)中的所有資源

6、編號，所有分配請求必須以序號上升的次序進(jìn)行。例如：系統(tǒng)中有下列設(shè)備：輸入機(jī)（1），打印機(jī)（2），穿孔機(jī)（3），磁帶機(jī)（4），磁盤（5）。有一進(jìn)程要先后使用輸入機(jī)、磁盤、打印機(jī)，則它申請設(shè)備時要按輸入機(jī)、打印機(jī)、磁盤的順序申請。優(yōu)點(diǎn)：同前兩法相比，其資源利用率和系統(tǒng)吞吐量有較明顯的改善。缺點(diǎn)：進(jìn)程實(shí)際需要資源的順序不一定與資源的編號一致，因此仍會造成資源浪費(fèi)。11三、死鎖避免各種死鎖防止方法能夠防止死鎖發(fā)生，但由于所加限制條件太嚴(yán)格，會導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量的降低。另一種解決死鎖問題的方法稱為避免死鎖。避免死鎖基本思想：把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀

7、態(tài)，只要系統(tǒng)一直處于安全狀態(tài)即可避免死鎖的發(fā)生。121.系統(tǒng)狀態(tài)（1）安全狀態(tài)如果系統(tǒng)能按某種進(jìn)程順序（如P1，P2，…,Pn）為每個進(jìn)程分配其所需的資源，直至所有進(jìn)程都能運(yùn)行完成，此時稱系統(tǒng)處于安全狀態(tài)。進(jìn)程序列稱為安全序列。（2）不安全狀態(tài)若不存在這樣一個安全序列稱系統(tǒng)處于不安全狀態(tài)。系統(tǒng)進(jìn)入不安全狀態(tài)后，就有可能進(jìn)而進(jìn)入死鎖狀態(tài)，反之，只要系統(tǒng)處于安全狀態(tài)，便可避免進(jìn)入死鎖狀態(tài)。不安全狀態(tài)安全狀態(tài)死鎖13例：有三個進(jìn)程p1,p2,p3，有12臺磁帶機(jī)。P1共要求10臺，P2共要求4臺，P3共要求9臺。T0時刻：p1,p2,p

8、3分別獲得5、2、2臺，尚有3臺空閑。系統(tǒng)狀態(tài)見下圖