【正文】 4）環(huán)路條件。 2）不剝奪條件。 產(chǎn)生死鎖的原因： 系統(tǒng)資源不足； 1）進(jìn)程推進(jìn)順序非法； 2)資源的分配策略不當(dāng) 。 進(jìn)程調(diào)度算法： ； 。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 58 時(shí)間片輪轉(zhuǎn)調(diào)度算法： (固定時(shí)間片輪轉(zhuǎn)法）； 2. 可變時(shí)間片輪轉(zhuǎn)法； 3. 多級(jí)反饋輪轉(zhuǎn)法。 。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 57 進(jìn)程調(diào)度功能： 。 4) 在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作。 2) 按調(diào)度算法，從后備作業(yè)中挑選作業(yè)進(jìn)入主存運(yùn)行。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 54 總結(jié)： 處理機(jī)調(diào)度可以分為 4級(jí)： 1） 作業(yè)調(diào)度（高級(jí)調(diào)度） 2）交換調(diào)度（中級(jí)調(diào)度） 3） 進(jìn)程調(diào)度（低級(jí)調(diào)度） 4) 線程調(diào)度 作業(yè)的 4個(gè)狀態(tài)： 提交、后備（收容）、執(zhí)行、完成。 從其它進(jìn)程剝奪足夠數(shù)量的資源給死鎖進(jìn)程，以解除死鎖狀態(tài)； (2)撤消進(jìn)程。但用于檢測(cè)死鎖的算法比較復(fù)雜，所花費(fèi)的檢測(cè)時(shí)間較長(zhǎng)，系統(tǒng)開(kāi)銷大，因此，可以選取比較長(zhǎng)的時(shí)間間隔來(lái)進(jìn)行。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 53 1)死鎖的檢測(cè)： 由于系統(tǒng)狀態(tài)與進(jìn)程 —資源狀態(tài)圖一一對(duì)應(yīng)，故可以利用進(jìn)程 —資源狀態(tài)圖加以簡(jiǎn)化的方法，來(lái)檢測(cè)系統(tǒng)在某一狀態(tài)時(shí)是否為死鎖狀態(tài)。 1)保存有關(guān)資源的請(qǐng)求和分配信息； 2)提供一種算法，以利用這些信息來(lái)檢測(cè)系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。 進(jìn)程名 已分配數(shù) 尚需申請(qǐng)數(shù) 最大需求數(shù) A B C 2 3 3 2 3 5 4 6 8 銀行家算法是通過(guò)動(dòng)態(tài)地檢測(cè)系統(tǒng)中資源分配情況和進(jìn)程對(duì)資源的需求情況來(lái)決定如何分配資源的，在能確保系統(tǒng)處于安全狀態(tài)時(shí)才把資源分配給申請(qǐng)者，從而避免系統(tǒng)發(fā)生死鎖。經(jīng)分析可知，此時(shí)存在一個(gè)安全序列 P1， P2， P3 ，即系統(tǒng)只要按此序列分配磁帶機(jī)，每個(gè)進(jìn)程都可順利完成，不會(huì)發(fā)生死鎖。如下表所示，并假定只有當(dāng)滿足了最大需求量后才能釋放所占用的全部資源。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 51 例如，設(shè)系統(tǒng)共有 10臺(tái)磁帶機(jī)，由三個(gè)進(jìn)程 P1， P2和 P3共享。 這種算法要求事先知道每個(gè)進(jìn)程對(duì)資源的最大需求量 。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 50 銀行家算法 : 最具有代表性的避免死鎖的算法稱為銀行家算法 。 顯然，只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。 3） 按規(guī)定次序申請(qǐng)資源，限制了用戶簡(jiǎn)單、自由的編程。 這種防止死鎖的策略較之前兩種策略，不論是資源利用率還是系統(tǒng)吞吐量，都有顯著的改善。 也就是說(shuō) ， 只要進(jìn)程提出請(qǐng)求資源 Ri（ i為系統(tǒng)資源編號(hào) ） ， 則在以后的請(qǐng)求中 ， 只能請(qǐng)求排在 Ri后面的資源 ， 不能在申請(qǐng)編號(hào)低于Ri的那些資源 。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 47 4. 破壞環(huán)路條件 有序資源分配策略 對(duì)系統(tǒng)中的全部資源按類型進(jìn)行編號(hào) ， 編號(hào)的原則是較為緊缺的資源給以一個(gè)較大的序號(hào) 。一個(gè)進(jìn)程一次獲得其所需的全部資源且獨(dú)占，其中可能有些資源很少使用，甚至在整個(gè)運(yùn)行期間都未使用，這就嚴(yán)重地惡化了系統(tǒng)資源利用率： 2）進(jìn)程延遲運(yùn)行。 優(yōu)點(diǎn)： 簡(jiǎn)單、易于實(shí)現(xiàn)，且很安全。但在分配時(shí)只要有一種資源要求不能滿足，則已有的其它資源也全部不分配給該進(jìn)程，該進(jìn)程只能等待。若系統(tǒng)有足夠的資源分配給該進(jìn)程時(shí)，便一次把所有其所需的資源分配給該進(jìn)程。這不僅延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)開(kāi)銷，又降低了系統(tǒng)吞吐量。 問(wèn)題： 1）這種防止死鎖的策略實(shí)現(xiàn)起來(lái)比較復(fù)雜； 2）一個(gè)資源在使用一段時(shí)間后被釋放，可能會(huì)造成前階段工作的失效，即使采取某些防范措施，也還會(huì)使前后兩次運(yùn)行的信息不連續(xù)。以后再需要時(shí)重新申請(qǐng) 。 死鎖的防止是通過(guò)設(shè)置某些嚴(yán)格的限制條件，以破壞產(chǎn)生死鎖的必要條件來(lái)防止死鎖的發(fā)生。而文件，可能允許多個(gè)進(jìn)程對(duì)其進(jìn)行讀訪問(wèn)，但只允許互斥地寫(xiě)訪問(wèn)。但是這種方法受到資源本身固有特性的限制，對(duì)某些資源是行不通的。 P1 P2 R1 R2 被占有 被占有 請(qǐng)求 請(qǐng)求 4）環(huán)路條件。 3）占有且等待條件 。 2） 不剝奪條件 。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 41 P1和 P2都占用 R1 P1和 P2都占用 R2 P2的進(jìn)展 P1的進(jìn)展 占用 R1 占用 R2 釋放 R1 釋放 R2 請(qǐng)求 R1 請(qǐng)求 R2 請(qǐng)求 R1 請(qǐng)求 R2 釋放 R1 釋放 R2 占用 R1 1 2 3 占用 R2 下面用圖示來(lái)說(shuō)明進(jìn)程 P1和 P2的三種可能的進(jìn)展情況： 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 42 產(chǎn)生死鎖的必要條件 1） 互斥條件 。但資源競(jìng)爭(zhēng)并不一定產(chǎn)生死鎖。 1）對(duì)資源的分配策略（請(qǐng)求順序）不當(dāng) ； 2）進(jìn)程推進(jìn)順序非法。此時(shí)，出現(xiàn)了生產(chǎn)者和消費(fèi)者之間僵死的局面，亦即發(fā)生了死鎖。 例如，在生產(chǎn)者 —消費(fèi)者問(wèn)題中，若把生產(chǎn)者進(jìn)程中兩個(gè) P操作的順序顛倒如下圖所示： 生產(chǎn)者進(jìn)程 Pi 生產(chǎn)一個(gè)產(chǎn)品 產(chǎn)品送入緩沖區(qū) P(avail) P(mutex) V(mutex) V(full) 在這種情況下 ， 當(dāng)緩沖區(qū)都已放滿了產(chǎn)品時(shí) ， 生產(chǎn)者仍可執(zhí)行 P(mutex)操作 ， 于是該生產(chǎn)者掌握了對(duì)緩沖區(qū)的存取控制權(quán) ， 當(dāng)它繼續(xù)執(zhí)行P(avail)操作時(shí) ， 由于沒(méi)有空緩沖區(qū) ， 該生產(chǎn)者被阻塞 ， 并 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 40 在 avail上等待。 例： 系統(tǒng)中只有一臺(tái)輸入機(jī) R1和一臺(tái)打印機(jī) R2可供進(jìn)程 P1和 P2共享。從而造成系統(tǒng)中一些進(jìn)程處于無(wú)休止的等待狀態(tài)，在無(wú)外力作用的情況下，這些進(jìn)程永遠(yuǎn)也不能繼續(xù)前進(jìn)。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 37 167。 ， 調(diào)度程序才調(diào)度第二個(gè)就緒隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?1至第 i–1個(gè)就緒隊(duì)列均為空時(shí) ，才會(huì)調(diào)度第 i個(gè)就緒隊(duì)列中的進(jìn)程運(yùn)行 。 進(jìn)入就緒隊(duì)列后，首先將它加入第一個(gè)就緒隊(duì)列的隊(duì)尾，按先來(lái)先服務(wù)的原則排隊(duì)等待調(diào)度。 第一個(gè)就緒隊(duì)列的優(yōu)先級(jí)最高 ， 第二個(gè)就緒隊(duì)列的優(yōu)先級(jí)次之 ， 其余各個(gè)就緒隊(duì)列的優(yōu)先級(jí)逐個(gè)降低 。 3) 短作業(yè)的時(shí)間片較小 ， 長(zhǎng)作業(yè)的時(shí)間片較大 。 系統(tǒng)根據(jù)此時(shí)就緒隊(duì)列的進(jìn)程數(shù)重新計(jì)算時(shí)間片 q＇ ， 然后開(kāi)始下一輪循環(huán) 。 系統(tǒng)的響應(yīng)時(shí)間 T固定 ， 在每一輪調(diào)度中 ， 根據(jù)當(dāng)前就緒隊(duì)列中的進(jìn)程數(shù) n計(jì)算這一輪調(diào)度的時(shí)間片： q＇＝ T/ n ， 然后進(jìn)行輪轉(zhuǎn)