【正文】 求中 ， 只能請(qǐng)求排在 Ri后面的資源 ， 不能在申請(qǐng)編號(hào)低于Ri的那些資源 。 對(duì)資源申請(qǐng)作了這樣的限制之后，在進(jìn)程資源分配圖中不可能再出現(xiàn)環(huán)路的情況。 這種防止死鎖的策略較之前兩種策略，不論是資源利用率還是系統(tǒng)吞吐量，都有顯著的改善。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 48 問(wèn)題： 1） 為系統(tǒng)中各種資源類型分配的序號(hào)．必須相對(duì)穩(wěn)定，這就限制了新設(shè)備類型的增加； 2） 盡管在為資源類型分配序號(hào)時(shí)，已考慮到大多數(shù)作業(yè)實(shí)際使用這些資源的順序，但也經(jīng)常會(huì)發(fā)生作業(yè)使用資源的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源的浪費(fèi)，如某進(jìn)程先用磁帶機(jī)，后用打印機(jī)，但按系統(tǒng)規(guī)定，它應(yīng)先申請(qǐng)打印機(jī)，后申請(qǐng)磁帶機(jī)，致使打印機(jī)長(zhǎng)期閑置。 3） 按規(guī)定次序申請(qǐng)資源，限制了用戶簡(jiǎn)單、自由的編程。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 49 （二）死鎖的避免 (銀行家算法 ) 1．安全狀態(tài)與不安全狀態(tài) 為了說(shuō)明死鎖避免的策略，我們把系統(tǒng)的狀態(tài)分為 安全狀態(tài) 和 不安全狀態(tài) ，引入了 安全狀態(tài)的定義 ：所謂安全狀態(tài)是指如果系統(tǒng)中的所有進(jìn)程能夠按照某一種次序依次執(zhí)行完，則說(shuō)系統(tǒng)處于安全狀態(tài)，否則稱系統(tǒng)處于不安全狀態(tài)。 顯然，只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。因此， 避免死鎖的實(shí)質(zhì)在于如何保證系統(tǒng)處于安全狀態(tài) ，最具有代表性的避免死鎖的算法是： 銀行家算法 為了避免可能產(chǎn)生的死鎖，在進(jìn)行資源分配時(shí)，應(yīng)采用某種算法來(lái)預(yù)測(cè)是否有可能會(huì)發(fā)生死鎖，若存在可能性，就拒絕企圖獲得資源的請(qǐng)求。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 50 銀行家算法 : 最具有代表性的避免死鎖的算法稱為銀行家算法 。 這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名 。 這種算法要求事先知道每個(gè)進(jìn)程對(duì)資源的最大需求量 。 基本思想： 當(dāng)一個(gè)新進(jìn)程進(jìn)入系統(tǒng)時(shí) ， 它必須申明其資源的最大需求量 ， 即每個(gè)資源類各需多少資源 ， 當(dāng)進(jìn)程發(fā)出資源申請(qǐng)命令而且系統(tǒng)能夠滿足該請(qǐng)求時(shí) ， 在分配資源前 ， 系統(tǒng)先要進(jìn)行一個(gè)序列檢查 ， 以判斷如果分配資源 ， 系統(tǒng)的狀態(tài)是否為安全 ， 如果安全則分配資源 ， 并讓申請(qǐng)者繼續(xù)執(zhí)行；否則 ， 不分配資源 ， 并讓申請(qǐng)者等待 。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 51 例如，設(shè)系統(tǒng)共有 10臺(tái)磁帶機(jī)，由三個(gè)進(jìn)程 P1， P2和 P3共享。假定 P1， P2和 P3已分別占用了 2臺(tái)、 3臺(tái)和 3臺(tái)，它們的最大需求量分別是 4臺(tái)、 6臺(tái)和 8臺(tái)。如下表所示，并假定只有當(dāng)滿足了最大需求量后才能釋放所占用的全部資源。 現(xiàn)在系統(tǒng)還剩 2臺(tái)磁帶機(jī)。經(jīng)分析可知，此時(shí)存在一個(gè)安全序列 P1， P2， P3 ，即系統(tǒng)只要按此序列分配磁帶機(jī)，每個(gè)進(jìn)程都可順利完成，不會(huì)發(fā)生死鎖。如果不按照安全順序分配資源，則系統(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ā)生死鎖。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 52 (三 ) 死鎖檢測(cè)與恢復(fù) 當(dāng)系統(tǒng)為進(jìn)程分配資源時(shí)，若未采取任何限制性措施來(lái)保證不進(jìn)入死鎖狀態(tài)，則系統(tǒng)必須提供檢測(cè)和解除死鎖的手段。 1)保存有關(guān)資源的請(qǐng)求和分配信息； 2)提供一種算法，以利用這些信息來(lái)檢測(cè)系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。 發(fā)現(xiàn)死鎖是根據(jù)死鎖狀態(tài)的定義，利用死鎖描述中介紹的資源分配圖來(lái)考察某一時(shí)刻系統(tǒng)狀態(tài)是否合理，即是否能使所有進(jìn)程都得到它們所申請(qǐng)的資源而運(yùn)行結(jié)束。 操作系統(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)。 檢測(cè)死鎖可以在每次分配后進(jìn)行。但用于檢測(cè)死鎖的算法比較復(fù)雜，所花費(fèi)的檢測(cè)時(shí)間較長(zhǎng)，系統(tǒng)開銷大，因此，可以選取比較長(zhǎng)的時(shí)間間隔來(lái)進(jìn)行。 2) 死鎖的恢復(fù) (解除 ) 常采用的兩種方法： (1)剝奪資源。 從其它進(jìn)程剝奪足夠數(shù)量的資源給死鎖進(jìn)程，以解除死鎖狀態(tài)； (2)撤消進(jìn)程。 最簡(jiǎn)單的撤消進(jìn)程的方法是使全部死鎖進(jìn)程都夭折掉，稍為溫和一點(diǎn)的方法是按照某種順序逐個(gè)地撤消進(jìn)程，直至有足夠的資源可用，死鎖狀態(tài)消除為止。 操作系統(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í)行、完成。 作業(yè)控制塊 ——JCB 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 55 周轉(zhuǎn)時(shí)間 Ti = 完成時(shí)刻 Tci－ 提交時(shí)刻 Tsi = 等待時(shí)間 Twi + 運(yùn)行時(shí)間 Tri 帶權(quán)周轉(zhuǎn)時(shí)間 Wi = Ti／ Tri 作業(yè)調(diào)度功能： 1）記錄各作業(yè)的狀況。 2) 按調(diào)度算法，從后備作業(yè)中挑選作業(yè)進(jìn)入主存運(yùn)行。 3) 為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作。 4) 在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 56 作業(yè)調(diào)度算法： （ FCFS） 調(diào)度算法 （ SJF） 調(diào)度算法 (HRN) 調(diào)度算法 調(diào)度程序： 將進(jìn)程插入到就緒隊(duì)列，按一定原則保持隊(duì)列結(jié)構(gòu)； 分派程序： 將進(jìn)程從就緒隊(duì)列中移出，建立它執(zhí)行的機(jī)器狀態(tài)。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 57 進(jìn)程調(diào)度功能： 。 。 。 進(jìn)程調(diào)度方式： 進(jìn)程調(diào)度時(shí)機(jī)： ； ； 時(shí)間片到； ，當(dāng)具有更高優(yōu)先級(jí)的進(jìn)程要求使用處理機(jī)。 操作系統(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ìn)程優(yōu)先數(shù)的方法： ； 。 進(jìn)程調(diào)度算法： ； 。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖 59 死鎖： 各并發(fā)進(jìn)程因?yàn)楦?jìng)爭(zhēng)資源，造成處于無(wú)休止的等待狀態(tài)，在無(wú)外力作用的情況下，這些進(jìn)程永遠(yuǎn)也不能繼續(xù)前進(jìn)。 產(chǎn)生死鎖的原因： 系統(tǒng)資源不足； 1）進(jìn)程推進(jìn)順序非法； 2)資源的分配策略不當(dāng) 。 產(chǎn)生死鎖的必要條件： 1）互斥條件。 2）不剝奪條件。 3）占有且等待條件 。 4）環(huán)路條件。