第三章_處理機(jī)調(diào)度

1、第三章第三章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖內(nèi)容提要內(nèi)容提要l 策略：處理機(jī)調(diào)度策略：處理機(jī)調(diào)度l 避免：死鎖避免：死鎖處理機(jī)調(diào)度處理機(jī)調(diào)度 處理機(jī)管理的工作是對處理機(jī)管理的工作是對CPUCPU資源進(jìn)行合理的分資源進(jìn)行合理的分配使用，以提高處理機(jī)利用率，并使各用戶公平配使用，以提高處理機(jī)利用率，并使各用戶公平地得到處理機(jī)資源。地得到處理機(jī)資源。3.1 3.1 處理機(jī)調(diào)度的類型及其功能處理機(jī)調(diào)度的類型及其功能什么是調(diào)度什么是調(diào)度n調(diào)度指在一個隊列中，按照某種方法，選擇一調(diào)度指在一個隊列中，按照某種方法，選擇一個合適的個體的過程個合適的個體的過程n調(diào)度的關(guān)鍵是使用好的調(diào)度算法，好的調(diào)度算調(diào)度的關(guān)

2、鍵是使用好的調(diào)度算法，好的調(diào)度算法有利于選擇到合適的個體法有利于選擇到合適的個體n如何判斷、設(shè)計一個好的調(diào)度算法？如何判斷、設(shè)計一個好的調(diào)度算法？調(diào)度實(shí)例調(diào)度目標(biāo)調(diào)度目標(biāo)n公平性：防止進(jìn)程長期不能獲得調(diào)度而饑餓；公平性：防止進(jìn)程長期不能獲得調(diào)度而饑餓；n盡量提高處理機(jī)利用率盡量提高處理機(jī)利用率n提高系統(tǒng)吞吐量提高系統(tǒng)吞吐量n盡量減少進(jìn)程的響應(yīng)時間盡量減少進(jìn)程的響應(yīng)時間調(diào)度原則調(diào)度原則n滿足用戶的要求：響應(yīng)時間、周轉(zhuǎn)時間滿足用戶的要求：響應(yīng)時間、周轉(zhuǎn)時間n滿足系統(tǒng)的需求：系統(tǒng)吞吐量、處理機(jī)利用率、滿足系統(tǒng)的需求：系統(tǒng)吞吐量、處理機(jī)利用率、各類資源的平衡使用、公平性及優(yōu)先級各類資源的平衡使用、公平

3、性及優(yōu)先級響應(yīng)時間響應(yīng)時間n響應(yīng)時間指從用戶提交一個請求開始，直到系響應(yīng)時間指從用戶提交一個請求開始，直到系統(tǒng)產(chǎn)生響應(yīng)為止的時間間隔統(tǒng)產(chǎn)生響應(yīng)為止的時間間隔n響應(yīng)時間響應(yīng)時間=輸入的請求傳送到處理機(jī)的時間輸入的請求傳送到處理機(jī)的時間+處處理機(jī)對請求信息進(jìn)行處理的時間理機(jī)對請求信息進(jìn)行處理的時間+將響應(yīng)結(jié)果發(fā)將響應(yīng)結(jié)果發(fā)送到輸出終端的時間送到輸出終端的時間n調(diào)度算法應(yīng)考慮盡可能使絕大多數(shù)用戶的請求調(diào)度算法應(yīng)考慮盡可能使絕大多數(shù)用戶的請求能在響應(yīng)時間內(nèi)完成能在響應(yīng)時間內(nèi)完成n常用于評價分時系統(tǒng)的性能常用于評價分時系統(tǒng)的性能 周轉(zhuǎn)時間周轉(zhuǎn)時間n指從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的指從作業(yè)提交給系

4、統(tǒng)開始，到作業(yè)完成為止的時間間隔時間間隔n周轉(zhuǎn)時間周轉(zhuǎn)時間=作業(yè)在外存排隊等待調(diào)度的時間作業(yè)在外存排隊等待調(diào)度的時間+進(jìn)進(jìn)程在就緒隊列中等待調(diào)度的時間程在就緒隊列中等待調(diào)度的時間+進(jìn)程被處理機(jī)進(jìn)程被處理機(jī)執(zhí)行的時間執(zhí)行的時間+等待等待I/O操作完成的時間操作完成的時間n常用于評價批處理系統(tǒng)的性能常用于評價批處理系統(tǒng)的性能影響周轉(zhuǎn)時間的調(diào)度影響周轉(zhuǎn)時間的調(diào)度n作業(yè)從外存調(diào)度到內(nèi)存（作業(yè)調(diào)度）作業(yè)從外存調(diào)度到內(nèi)存（作業(yè)調(diào)度）n進(jìn)入內(nèi)存還需在就緒隊列中排隊，等待進(jìn)程調(diào)進(jìn)入內(nèi)存還需在就緒隊列中排隊，等待進(jìn)程調(diào)度度n甚至，可能會掛起進(jìn)程，在外存等待被激活甚至，可能會掛起進(jìn)程，在外存等待被激活（存儲對換或

5、中級調(diào)度）（存儲對換或中級調(diào)度）截止時間截止時間n指實(shí)時系統(tǒng)中，某任務(wù)必須開始執(zhí)行的最遲時指實(shí)時系統(tǒng)中，某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間間，或必須完成的最遲時間n常用于評價實(shí)時系統(tǒng)的性能常用于評價實(shí)時系統(tǒng)的性能系統(tǒng)吞吐量系統(tǒng)吞吐量n指單位時間內(nèi)系統(tǒng)完成的作業(yè)數(shù)指單位時間內(nèi)系統(tǒng)完成的作業(yè)數(shù)n常用于評價批處理系統(tǒng)的性能常用于評價批處理系統(tǒng)的性能處理機(jī)利用率處理機(jī)利用率n處理機(jī)處于忙狀態(tài)的時間和處理機(jī)運(yùn)行總時間處理機(jī)處于忙狀態(tài)的時間和處理機(jī)運(yùn)行總時間的比值的比值n大中型多用戶系統(tǒng)，由于處理機(jī)價格昂貴，處大中型多用戶系統(tǒng)，由于處理機(jī)價格昂貴，處理機(jī)利用率是衡量系統(tǒng)性能的一個重要指標(biāo)。

6、理機(jī)利用率是衡量系統(tǒng)性能的一個重要指標(biāo)。n單用戶微機(jī)或某些實(shí)時系統(tǒng)，并非很重要。單用戶微機(jī)或某些實(shí)時系統(tǒng)，并非很重要。各類資源的平衡使用各類資源的平衡使用n多道程序系統(tǒng)的目標(biāo)之一就是為了提高系統(tǒng)資多道程序系統(tǒng)的目標(biāo)之一就是為了提高系統(tǒng)資源的利用率，因此，調(diào)度算法有責(zé)任使系統(tǒng)中源的利用率，因此，調(diào)度算法有責(zé)任使系統(tǒng)中的各種資源都盡量處于忙碌狀態(tài)。的各種資源都盡量處于忙碌狀態(tài)。n該原則同時適用于作業(yè)調(diào)度和中級調(diào)度，因?yàn)樵撛瓌t同時適用于作業(yè)調(diào)度和中級調(diào)度，因?yàn)樗鼈兛梢詻Q定哪些作業(yè)進(jìn)入內(nèi)存，可以考慮系它們可以決定哪些作業(yè)進(jìn)入內(nèi)存，可以考慮系統(tǒng)資源的均衡使用統(tǒng)資源的均衡使用公平性公平性n調(diào)度算法應(yīng)該對所

7、有進(jìn)程公平，不偏袒任何進(jìn)調(diào)度算法應(yīng)該對所有進(jìn)程公平，不偏袒任何進(jìn)程程優(yōu)先權(quán)優(yōu)先權(quán)n優(yōu)先權(quán)高的進(jìn)程應(yīng)該先調(diào)度。優(yōu)先權(quán)高的進(jìn)程應(yīng)該先調(diào)度。n可以根據(jù)進(jìn)程的優(yōu)先權(quán)不同，組織不同的就緒可以根據(jù)進(jìn)程的優(yōu)先權(quán)不同，組織不同的就緒隊列。進(jìn)程調(diào)度時首先選擇高優(yōu)先權(quán)隊列中的隊列。進(jìn)程調(diào)度時首先選擇高優(yōu)先權(quán)隊列中的進(jìn)程，直到該隊列空，再調(diào)度較低優(yōu)先權(quán)隊列進(jìn)程，直到該隊列空，再調(diào)度較低優(yōu)先權(quán)隊列中的進(jìn)程。中的進(jìn)程。n幾乎所有操作系統(tǒng)的調(diào)度算法都可考慮優(yōu)先權(quán)幾乎所有操作系統(tǒng)的調(diào)度算法都可考慮優(yōu)先權(quán)原則。原則。n考慮優(yōu)先權(quán)，可能會出現(xiàn)饑餓現(xiàn)象，對低優(yōu)先考慮優(yōu)先權(quán)，可能會出現(xiàn)饑餓現(xiàn)象，對低優(yōu)先權(quán)的進(jìn)程不公平。權(quán)的進(jìn)程不公

8、平。n可以將進(jìn)程排隊的等待時間等因素納入優(yōu)先權(quán)可以將進(jìn)程排隊的等待時間等因素納入優(yōu)先權(quán)的計算，隨著進(jìn)程等待時間的增長，其優(yōu)先權(quán)的計算，隨著進(jìn)程等待時間的增長，其優(yōu)先權(quán)也不斷提高。也不斷提高。處理機(jī)調(diào)度的類型處理機(jī)調(diào)度的類型n作業(yè)調(diào)度（高級調(diào)度）作業(yè)調(diào)度（高級調(diào)度）n存儲對換（中級調(diào)度）存儲對換（中級調(diào)度）n進(jìn)程調(diào)度（低級調(diào)度）進(jìn)程調(diào)度（低級調(diào)度）處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次作業(yè)輸入作業(yè)輸入后備后備就緒就緒阻塞阻塞就緒就緒阻塞阻塞執(zhí)行執(zhí)行完成完成作業(yè)調(diào)度作業(yè)調(diào)度存儲對換存儲對換進(jìn)程調(diào)度進(jìn)程調(diào)度內(nèi)存內(nèi)存外存外存作業(yè)輸出作業(yè)輸出作業(yè)調(diào)度作業(yè)調(diào)度n在批處理系統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，先駐留在在批處理系

9、統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，先駐留在磁盤上，組織成批處理隊列，稱為后備隊列。磁盤上，組織成批處理隊列，稱為后備隊列。n作業(yè)調(diào)度從該隊列中選擇一個或多個作業(yè)，為作業(yè)調(diào)度從該隊列中選擇一個或多個作業(yè)，為之創(chuàng)建進(jìn)程，分配必要的系統(tǒng)資源，并將新創(chuàng)之創(chuàng)建進(jìn)程，分配必要的系統(tǒng)資源，并將新創(chuàng)建的進(jìn)程插入就緒隊列，等待進(jìn)程調(diào)度。建的進(jìn)程插入就緒隊列，等待進(jìn)程調(diào)度。n某些具有交換技術(shù)的系統(tǒng)將新創(chuàng)建的進(jìn)程插入某些具有交換技術(shù)的系統(tǒng)將新創(chuàng)建的進(jìn)程插入到就緒到就緒/掛起隊列，等待中級調(diào)度。掛起隊列，等待中級調(diào)度。作業(yè)調(diào)度模型后備隊列就緒隊列就緒/掛起隊列處理機(jī)進(jìn)程調(diào)度作業(yè)調(diào)度交互用戶中級調(diào)度作業(yè)調(diào)度需要考慮的問題作業(yè)調(diào)度需

10、要考慮的問題n選擇多少個作業(yè)進(jìn)入內(nèi)存，為之創(chuàng)建進(jìn)程？選擇多少個作業(yè)進(jìn)入內(nèi)存，為之創(chuàng)建進(jìn)程？取決于允許同時在內(nèi)存中運(yùn)行的進(jìn)程數(shù)取決于允許同時在內(nèi)存中運(yùn)行的進(jìn)程數(shù)n選擇哪些作業(yè)？選擇哪些作業(yè)？取決于作業(yè)調(diào)度算法取決于作業(yè)調(diào)度算法進(jìn)程調(diào)度進(jìn)程調(diào)度n也稱低級調(diào)度，決定就緒隊列中的哪個進(jìn)程將也稱低級調(diào)度，決定就緒隊列中的哪個進(jìn)程將獲得處理機(jī)。獲得處理機(jī)。n進(jìn)程調(diào)度的運(yùn)行頻率是最高的。進(jìn)程調(diào)度的運(yùn)行頻率是最高的。n現(xiàn)代操作系統(tǒng)幾乎都具有進(jìn)程調(diào)度。現(xiàn)代操作系統(tǒng)幾乎都具有進(jìn)程調(diào)度。進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式n根據(jù)執(zhí)行進(jìn)程的處理機(jī)是由進(jìn)程自己釋放，還根據(jù)執(zhí)行進(jìn)程的處理機(jī)是由進(jìn)程自己釋放，還是被強(qiáng)行剝奪，可以將進(jìn)程

11、調(diào)度方式分為兩種是被強(qiáng)行剝奪，可以將進(jìn)程調(diào)度方式分為兩種非搶占方式非搶占方式搶占方式搶占方式進(jìn)程調(diào)度方式：非搶占方式進(jìn)程調(diào)度方式：非搶占方式n一旦把一旦把CPUCPU分配給某一進(jìn)程后分配給某一進(jìn)程后, ,便讓它一直運(yùn)行便讓它一直運(yùn)行下去，直到進(jìn)程運(yùn)行完成或發(fā)生某事件（申請下去，直到進(jìn)程運(yùn)行完成或發(fā)生某事件（申請I/OI/O）而不能運(yùn)行時，才將）而不能運(yùn)行時，才將CPUCPU分給其它進(jìn)程分給其它進(jìn)程n主要優(yōu)點(diǎn)是簡單、系統(tǒng)開銷小。主要優(yōu)點(diǎn)是簡單、系統(tǒng)開銷小。n該方式不利于該方式不利于“及時性及時性”要求較高的分時系統(tǒng)要求較高的分時系統(tǒng)和實(shí)時系統(tǒng)，主要用在批處理系統(tǒng)中。和實(shí)時系統(tǒng)，主要用在批處理系統(tǒng)

12、中。進(jìn)程調(diào)度方式：搶占方式進(jìn)程調(diào)度方式：搶占方式n系統(tǒng)可以基于某種策略（優(yōu)先級策略、時間片系統(tǒng)可以基于某種策略（優(yōu)先級策略、時間片策略等）剝奪現(xiàn)行進(jìn)程的策略等）剝奪現(xiàn)行進(jìn)程的CPUCPU，調(diào)度新的進(jìn)程執(zhí)，調(diào)度新的進(jìn)程執(zhí)行。行。n操作系統(tǒng)可以在新進(jìn)程到來時，或某個具有較操作系統(tǒng)可以在新進(jìn)程到來時，或某個具有較高優(yōu)先權(quán)的被阻塞進(jìn)程插入就緒隊列時，或在高優(yōu)先權(quán)的被阻塞進(jìn)程插入就緒隊列時，或在基于時間片調(diào)度的系統(tǒng)中，時間片用完而中斷基于時間片調(diào)度的系統(tǒng)中，時間片用完而中斷當(dāng)前進(jìn)程的運(yùn)行，調(diào)度新的進(jìn)程執(zhí)行。當(dāng)前進(jìn)程的運(yùn)行，調(diào)度新的進(jìn)程執(zhí)行。n該方式會產(chǎn)生較多的中斷，主要用在對實(shí)時性該方式會產(chǎn)生較多的中斷

13、，主要用在對實(shí)時性要求較高的實(shí)時系統(tǒng)及對性能要求較高的分時要求較高的實(shí)時系統(tǒng)及對性能要求較高的分時系統(tǒng)和批處理系統(tǒng)中，以便及時響應(yīng)各進(jìn)程的系統(tǒng)和批處理系統(tǒng)中，以便及時響應(yīng)各進(jìn)程的請求。請求。存儲對換存儲對換n又稱中級調(diào)度，它是對換功能的一部分。又稱中級調(diào)度，它是對換功能的一部分。n目的：為了提高內(nèi)存的利用率和系統(tǒng)吞吐量目的：為了提高內(nèi)存的利用率和系統(tǒng)吞吐量n當(dāng)內(nèi)存空間非常緊張時，或處理機(jī)找不到一個當(dāng)內(nèi)存空間非常緊張時，或處理機(jī)找不到一個可執(zhí)行的就緒進(jìn)程時，需要選擇一個進(jìn)程（阻可執(zhí)行的就緒進(jìn)程時，需要選擇一個進(jìn)程（阻塞或就緒狀態(tài)）換出到外存，釋放出內(nèi)存空間塞或就緒狀態(tài)）換出到外存，釋放出內(nèi)存空間

14、給別的進(jìn)程使用；當(dāng)內(nèi)存空間較充裕時，從外給別的進(jìn)程使用；當(dāng)內(nèi)存空間較充裕時，從外存選擇一個掛起狀態(tài)的進(jìn)程調(diào)度到內(nèi)存（換存選擇一個掛起狀態(tài)的進(jìn)程調(diào)度到內(nèi)存（換入）。入）。處理機(jī)調(diào)度模型就緒隊列就緒/掛起隊列阻塞/掛起隊列阻塞隊列作業(yè)調(diào)度進(jìn)程調(diào)度處理機(jī)存儲對換時間片用完完成事件發(fā)生事件等待后備隊列3.2 3.2 調(diào)度算法調(diào)度算法先來先服務(wù)（先來先服務(wù)（FCFS）n該方法按照進(jìn)程（作業(yè)）到達(dá)的先后順序排隊，每次調(diào)度隊首的進(jìn)程（作業(yè)）。nFCFS算法屬于非剝奪調(diào)度方式，實(shí)現(xiàn)簡單，看似公平n但是，對于那些后進(jìn)入隊列而運(yùn)行時間較短的進(jìn)程（作業(yè)） ，或I/O型的進(jìn)程（作業(yè)）而言，可能需要長時間等待。先來先服

15、務(wù)（先來先服務(wù)（FCFS）n假設(shè)就緒隊列中從隊首開始依次排列有三個進(jìn)程P1，P2，P3，P4（四個進(jìn)程同時到達(dá)內(nèi)存）。進(jìn)程P1運(yùn)行時間為12，進(jìn)程P2運(yùn)行時間為5，進(jìn)程P3運(yùn)行時間為3，進(jìn)程P4運(yùn)行時間為6 。若采用FCFS方法調(diào)度，試計算進(jìn)程P1，P2，P3，P4的周轉(zhuǎn)時間分別是多少？平均周轉(zhuǎn)時間是多少？先來先服務(wù)（先來先服務(wù)（FCFS）進(jìn)程進(jìn)程 到達(dá)時間到達(dá)時間 運(yùn)行時間運(yùn)行時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間 T=18.75P1 0 12 0 12 12P2 0 5 12 17 17P3 0 3 17 20 20FCFS調(diào)度算法性能調(diào)度算法性

16、能P4 0 6 20 26 26先來先服務(wù)（先來先服務(wù)（FCFS）n對短進(jìn)程（作業(yè)）不公平。n平均周轉(zhuǎn)時間長：由于長進(jìn)程（作業(yè)）可能排在隊列前面，必將增加隊列后部進(jìn)程（作業(yè)）的等待時間，從而將增加平均周轉(zhuǎn)時間。n不利于I/O型進(jìn)程（作業(yè)） ，未有效利用系統(tǒng)資源。n一般地，F(xiàn)CFS與其它調(diào)度算法混合使用。nFCFS算法同時適合于作業(yè)調(diào)度，進(jìn)程調(diào)度和存儲對換三種調(diào)度類型。短進(jìn)程（作業(yè)）優(yōu)先算法短進(jìn)程（作業(yè)）優(yōu)先算法n從就緒隊列中選出一估計運(yùn)行時間最短的進(jìn)程（作業(yè)） ，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成或發(fā)生某事件而被阻塞放棄處理機(jī)時。n屬于非剝奪調(diào)度算法。當(dāng)某進(jìn)程獲得處理機(jī)，直到其執(zhí)行

17、完成，或需要等待某事件而阻塞時，才自動釋放處理機(jī)。系統(tǒng)又調(diào)度新的進(jìn)程。短進(jìn)程（作業(yè)）優(yōu)先算法短進(jìn)程（作業(yè)）優(yōu)先算法n假設(shè)就緒隊列中從隊首開始依次排列有三個進(jìn)程P1，P2，P3，P4（四個進(jìn)程同時到達(dá)內(nèi)存）。進(jìn)程P1運(yùn)行時間為12，進(jìn)程P2運(yùn)行時間為5，進(jìn)程P3運(yùn)行時間為3，進(jìn)程P4運(yùn)行時間為6 。 若采用短進(jìn)程優(yōu)先方法調(diào)度，按照進(jìn)程預(yù)期執(zhí)行時間排序?yàn)檫M(jìn)程P3、進(jìn)程P2、進(jìn)程P4，進(jìn)程P1。試分別計算進(jìn)程P1，P2，P3，P4的周轉(zhuǎn)時間分別是多少？平均周轉(zhuǎn)時間是多少？短進(jìn)程（作業(yè)）優(yōu)先算法短進(jìn)程（作業(yè)）優(yōu)先算法進(jìn)程進(jìn)程 到達(dá)時間到達(dá)時間 運(yùn)行時間運(yùn)行時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)

18、時間周轉(zhuǎn)時間平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間 T=12.75P1 0 12 14 26 26 P2 0 5 3 8 8P3 0 3 0 3 3短進(jìn)程優(yōu)先調(diào)度算法性能短進(jìn)程優(yōu)先調(diào)度算法性能P4 0 6 8 14 14短作業(yè)（進(jìn)程）優(yōu)先算法短作業(yè)（進(jìn)程）優(yōu)先算法n與FCFS算法比較，短進(jìn)程優(yōu)先算法改善了系統(tǒng)的性能，降低了系統(tǒng)的平均等待時間，提高了系統(tǒng)的吞吐量。但是，該算法也存在一些問題：（1）可能導(dǎo)致長進(jìn)程饑餓，這對長進(jìn)程不公平（2）采用非剝奪調(diào)度方式，未考慮進(jìn)程的緊迫程度，不適合分時系統(tǒng)和事務(wù)處理系統(tǒng)。（3）很難準(zhǔn)確預(yù)測進(jìn)程的執(zhí)行時間時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法n在一個分時聯(lián)機(jī)系統(tǒng)中，同時有n個人通過各自的

19、終端共享一臺主機(jī)。終端完成輸入/輸出操作，主機(jī)負(fù)責(zé)處理從終端發(fā)來的請求，為之建立進(jìn)程、協(xié)調(diào)各進(jìn)程的運(yùn)行，調(diào)度各個進(jìn)程等，并盡量滿足每個終端用戶對響應(yīng)時間的要求。時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法終端1服務(wù)進(jìn)程終端2服務(wù)進(jìn)程終端n服務(wù)進(jìn)程終端1終端2終端n基于時間片輪轉(zhuǎn)調(diào)度主機(jī)一個基于時間片輪轉(zhuǎn)調(diào)度的聯(lián)機(jī)系統(tǒng)時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法n在分時聯(lián)機(jī)系統(tǒng)中，n個進(jìn)程循環(huán)地獲得時間片而執(zhí)行。從系統(tǒng)中來看，它們是交替執(zhí)行的，但就每個終端用戶而言，都感覺到自己獨(dú)占了一臺主機(jī)，不受其他用戶的影響。這是通過進(jìn)程并發(fā)執(zhí)行實(shí)現(xiàn)的。n如果用戶數(shù)太多，主機(jī)處理的進(jìn)程將會急劇增加，進(jìn)程排隊等待的時間也會很長，進(jìn)程的響應(yīng)時間也可能增

20、長，用戶將明顯感覺到主機(jī)的速度變慢而不滿意n另外，時間片的大小也會影響進(jìn)程的響應(yīng)時間。時間片的設(shè)置時間片的設(shè)置n時間片輪轉(zhuǎn)屬于剝奪的調(diào)度算法，會產(chǎn)生中斷，進(jìn)行進(jìn)程切換。而進(jìn)程切換將會增加系統(tǒng)的額外開銷。n時間片太長 ， 不能保證系統(tǒng)各個用戶進(jìn)程及時得到響應(yīng)；時間片太短 ，用戶的一次請求需要多個時間片才能執(zhí)行完，增加調(diào)度開銷，降低系統(tǒng)的效率。n時間片大小的確定應(yīng)該綜合考慮系統(tǒng)的最大用戶數(shù)、響應(yīng)時間、系統(tǒng)效率等多種因素。時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法n假設(shè)就緒隊列中從隊首開始依次排列有四個進(jìn)程P1，P2，P3，P4（四個進(jìn)程同時到達(dá)內(nèi)存）。進(jìn)程P1運(yùn)行時間為12，進(jìn)程P2運(yùn)行時間為5，進(jìn)程P3運(yùn)行時間為

21、3，進(jìn)程P4運(yùn)行時間為6 。若采用時間片輪轉(zhuǎn)調(diào)度算法，設(shè)時間片分別為4和1，試分別計算進(jìn)程P1，P2，P3，P4的周轉(zhuǎn)時間分別是多少？平均周轉(zhuǎn)時間是多少？時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法0 5 10 15 20 25 TDCBADCBA進(jìn)程進(jìn)程q=4q=1運(yùn)行實(shí)例常用的調(diào)度算法（續(xù)）常用的調(diào)度算法（續(xù)）進(jìn)程名進(jìn)程名到達(dá)時間到達(dá)時間到達(dá)時間到達(dá)時間 運(yùn)行時間運(yùn)行時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間P1P2P3P4P1P2P3P4時間片時間片q=1時間片時間片q=4 0 12 0 26 26 0 5 1 17 17 0 3 2 11 11 0 6 3 20 20 平均周轉(zhuǎn)時間平均周轉(zhuǎn)

22、時間 T = 18.5 0 12 0 26 26 0 5 4 20 20 0 3 8 11 11 0 6 11 22 22 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間 T = 19.75時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法n為了簡單，圖中忽略了進(jìn)程切換時的系統(tǒng)開銷，而實(shí)際操作系統(tǒng)中，這類額外開銷是客觀存在的。n可見，采用基于時間片輪轉(zhuǎn)調(diào)度法，進(jìn)程的周轉(zhuǎn)時間和平均周轉(zhuǎn)時間并不比采用FCFS和短進(jìn)程優(yōu)先調(diào)度算法小。n加上進(jìn)程切換所需要的系統(tǒng)開銷，該算法的平均周轉(zhuǎn)時間還會增長。時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法n常用于分時系統(tǒng)及事務(wù)處理系統(tǒng)，合理的時間片大小將帶來滿意的響應(yīng)時間n通常，合理的時間片指，能讓80%左右的進(jìn)程在一個時間片內(nèi)完成

23、。n對于短的、計算型的進(jìn)程較有利n不適合于批處理系統(tǒng)的進(jìn)程調(diào)度n不利于I/O型的進(jìn)程基于優(yōu)先級的調(diào)度算法基于優(yōu)先級的調(diào)度算法n基于時間片輪轉(zhuǎn)調(diào)度法循環(huán)式地為每個被調(diào)度的進(jìn)程分配一個時間片，對每個進(jìn)程都是公平的。n然而，實(shí)際應(yīng)用中，進(jìn)程的性質(zhì)可能是不同的。例如，一個與用戶進(jìn)行交互的前臺進(jìn)程急迫地需要對用戶的輸入作出響應(yīng)，而一個后臺打印進(jìn)程的迫切性也許就不那么重要。n因此，可以為每個進(jìn)程定義一個優(yōu)先級，優(yōu)先級高的進(jìn)程將優(yōu)先獲得處理機(jī)的調(diào)度。如何設(shè)定進(jìn)程的優(yōu)先級如何設(shè)定進(jìn)程的優(yōu)先級n進(jìn)程完成功能的重要性n進(jìn)程完成功能的急迫性n為均衡系統(tǒng)資源的使用，指定進(jìn)程（作業(yè)）優(yōu)先級n進(jìn)程對資源的占用程度，例如，

24、可以為短進(jìn)程（或作業(yè)）賦予較高的優(yōu)先級靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級n靜態(tài)優(yōu)先級：靜態(tài)優(yōu)先級：在進(jìn)程創(chuàng)建時確定的，運(yùn)行時保持不變通常賦予系統(tǒng)進(jìn)程較高優(yōu)先級；申請資源量少的賦予較高優(yōu)先級。n動態(tài)優(yōu)先級：動態(tài)優(yōu)先級：在創(chuàng)建進(jìn)程時賦予的優(yōu)先級，在進(jìn)程運(yùn)行過程中可以自動改變，以使進(jìn)程獲得更好的調(diào)度性能。動態(tài)優(yōu)先級動態(tài)優(yōu)先級n影響進(jìn)程動態(tài)優(yōu)先級的因素：進(jìn)程等待時間和占用處理機(jī)時間 進(jìn)程優(yōu)先級隨著進(jìn)程運(yùn)行的剩余時間的減少而上升，使將要執(zhí)行結(jié)束的進(jìn)程盡快完成。就緒隊列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進(jìn)程在等待足夠的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行。n具體實(shí)現(xiàn)方法，可以在每個時

25、鐘中斷時，或需要進(jìn)程切換時，重新計算就緒隊列中各進(jìn)程的優(yōu)先級，并優(yōu)先調(diào)度優(yōu)先級高的進(jìn)程。動態(tài)優(yōu)先級動態(tài)優(yōu)先級n采用動態(tài)優(yōu)先級的兩種調(diào)度算法：剩余時間最短者優(yōu)先和響應(yīng)比高者優(yōu)先剩余時間最短者優(yōu)先剩余時間最短者優(yōu)先n為了使將要結(jié)束的進(jìn)程盡早結(jié)束，釋放系統(tǒng)資源，讓別的進(jìn)程執(zhí)行?？梢栽诿總€時鐘中斷時，根據(jù)就緒隊列中各進(jìn)程的剩余執(zhí)行時間動態(tài)調(diào)整其優(yōu)先級，剩余時間最短的進(jìn)程優(yōu)先級最高。n顯然，該算法是剝奪型的短進(jìn)程優(yōu)先調(diào)度算法，調(diào)度程序總是選擇剩余執(zhí)行時間最短的進(jìn)程調(diào)度執(zhí)行。剩余時間最短者優(yōu)先剩余時間最短者優(yōu)先n與短進(jìn)程優(yōu)先調(diào)度算法一樣，該調(diào)度算法很難準(zhǔn)確估計進(jìn)程的剩余執(zhí)行時間n由于長進(jìn)程在未執(zhí)行時，或剛

26、開始執(zhí)行的一段時間內(nèi)，其剩余執(zhí)行時間都不會最短，所以該算法對長進(jìn)程不公平n但是，它不像FCFS算法偏袒長進(jìn)程，也不像輪轉(zhuǎn)調(diào)度算法會產(chǎn)生很多中斷而增加系統(tǒng)負(fù)擔(dān)。另一方面，它必須記錄過去的服務(wù)時間，增加了系統(tǒng)開銷。n由于短進(jìn)程提前完成，故采用剩余時間最短者優(yōu)先的調(diào)度算法獲得的平均周轉(zhuǎn)時間比采用短進(jìn)程優(yōu)先算法短。響應(yīng)比高者優(yōu)先響應(yīng)比高者優(yōu)先n將進(jìn)程的等待時間和進(jìn)程的預(yù)期執(zhí)行時間納入優(yōu)先級的計算，進(jìn)程預(yù)期執(zhí)行時間越長優(yōu)先級越低，而隨著進(jìn)程的等待時間增長優(yōu)先級上升，即進(jìn)程的優(yōu)先級與等待時間成正比，與進(jìn)程執(zhí)行時間成反比。令w表示等待時間，s表示預(yù)期執(zhí)行時間，則響應(yīng)比： w+ss=ws+1R=響應(yīng)比高者優(yōu)先

27、響應(yīng)比高者優(yōu)先n調(diào)度方法：若當(dāng)前執(zhí)行進(jìn)程執(zhí)行完畢，或需要阻塞等待某事件而釋放處理機(jī)，調(diào)度程序選擇就緒隊列中響應(yīng)比最大的進(jìn)程執(zhí)行n若等待時間相同，短進(jìn)程因?yàn)閟較小，R較大而優(yōu)先調(diào)度。若進(jìn)程的預(yù)期執(zhí)行時間相同，則等待時間長的進(jìn)程優(yōu)先調(diào)度，相當(dāng)于FCFS。n隨著等待時間的增加，長進(jìn)程的響應(yīng)比不斷增大，在某個時刻，也必然被調(diào)度。 響應(yīng)比高者優(yōu)先響應(yīng)比高者優(yōu)先n同短進(jìn)程優(yōu)先和剩余時間最短者優(yōu)先調(diào)度算法一樣，很難準(zhǔn)確估計進(jìn)程的預(yù)期執(zhí)行時間n每次調(diào)度之前都需要計算響應(yīng)比，增加了系統(tǒng)開銷。 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法n前面介紹的幾種調(diào)度算法都存在各自不同的問題，尤其是短進(jìn)程優(yōu)先、剩余時間最短者優(yōu)

28、先以及響應(yīng)比高者優(yōu)先調(diào)度算法都需要估計進(jìn)程的預(yù)期執(zhí)行時間，如果估計不準(zhǔn)確，將影響調(diào)度結(jié)果和系統(tǒng)性能。n如果根據(jù)進(jìn)程執(zhí)行歷史，而非未來，進(jìn)行調(diào)度，將解決這個問題。n反饋調(diào)度法就是一種根據(jù)進(jìn)程執(zhí)行歷史調(diào)整調(diào)度方式的調(diào)度方法，它結(jié)合了優(yōu)先級和時間片輪轉(zhuǎn)調(diào)度思想。 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法n多級反饋隊列算法中，系統(tǒng)設(shè)置多個就緒隊列，進(jìn)程在其生命期內(nèi)可能在多個就緒隊列中存在。n各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，其余各隊列的優(yōu)先權(quán)逐個降低。n各個隊列中進(jìn)程執(zhí)行的時間片大小也各不相同，在優(yōu)先權(quán)越高的隊列中，每個進(jìn)程的執(zhí)行時間片就越小。就緒隊列0就緒隊列1就緒隊列n處理機(jī)處理機(jī)

29、處理機(jī)調(diào)度調(diào)度調(diào)度完成完成完成接納其中，優(yōu)先級按就緒隊列0,1，,n逐級降低 時間片按就緒隊列0,1，,n逐級增長多級反饋隊列調(diào)度算法的實(shí)施過程多級反饋隊列調(diào)度算法的實(shí)施過程n新創(chuàng)建的進(jìn)程進(jìn)入內(nèi)存后，排在最高優(yōu)先級隊列的末尾，按FCFS原則等待調(diào)度。n該進(jìn)程執(zhí)行時， 如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入下一個較低優(yōu)先級隊列的隊尾。n當(dāng)一個長進(jìn)程從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運(yùn)行。n調(diào)度時，總是先調(diào)度優(yōu)先級高的隊列。僅當(dāng)該隊列空時，才調(diào)度次高優(yōu)先級隊列，以此類推，第n個隊列進(jìn)程被調(diào)度時，必須是前n-1個隊列為空。n如果處理機(jī)正在第i個隊列中

30、為某進(jìn)程服務(wù)時，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊列，則此時新進(jìn)程將搶占處理機(jī)，由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i+1個隊列的末尾，把處理機(jī)分配給新到的進(jìn)程。多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法l優(yōu)點(diǎn)：多級反饋隊列調(diào)度算法能較好的滿足各種類型用戶的需要 終端型作業(yè)用戶：終端型作業(yè)大都屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)在第一就緒隊列所規(guī)定的時間片內(nèi)完成，便可使終端用戶得到滿意。短批處理作業(yè)用戶：如果可在第一隊列中執(zhí)行一個時間片即可完成，便可獲得與終端用戶一樣的響應(yīng)時間，對于稍長的作業(yè)，通常也只須在第二隊列和第三隊列各執(zhí)行一個時間片即可完成。長批處理作業(yè)用戶：對于長作業(yè)，它將依次在

31、第1,2，,n個隊列中運(yùn)行，然后再按時間片輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長期得不到處理。多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法缺點(diǎn)：n但可能使長進(jìn)程的周轉(zhuǎn)時間急劇增加。n如果不斷地有新進(jìn)程到來，還可能出現(xiàn)長進(jìn)程饑餓現(xiàn)象。進(jìn)程調(diào)度算法小結(jié)進(jìn)程調(diào)度算法小結(jié)n如何選擇進(jìn)程調(diào)度算法與系統(tǒng)設(shè)計的目標(biāo)有關(guān)n交互式多任務(wù)系統(tǒng)，主要考慮聯(lián)機(jī)用戶對響應(yīng)時間的要求，一般采用基于時間片輪轉(zhuǎn)調(diào)度算法，同時，根據(jù)進(jìn)程的性質(zhì)設(shè)置不同的優(yōu)先級n批處理系統(tǒng)往往以作業(yè)的平均周轉(zhuǎn)時間來衡量調(diào)度性能，常選用基于優(yōu)先級的短進(jìn)程優(yōu)先調(diào)度算法。3.3 3.3 死鎖死鎖n進(jìn)程的并發(fā)控制不僅要控制若干進(jìn)程的同步和互斥，確保進(jìn)程之間正常通

32、信，還需要解決進(jìn)程死鎖問題n一旦出現(xiàn)進(jìn)程死鎖，相應(yīng)的進(jìn)程將無法向前推進(jìn)。如果系統(tǒng)內(nèi)的絕大多數(shù)進(jìn)程或全部進(jìn)程死鎖，那么，整個系統(tǒng)將處于癱瘓狀態(tài)，造成系統(tǒng)“死機(jī)”。交通中的死鎖現(xiàn)象交通中的死鎖現(xiàn)象死鎖的例子死鎖的例子1例：一個計算機(jī)系統(tǒng)中，有兩臺打印機(jī)和兩個進(jìn)程，某一時刻，每個進(jìn)程都各自占有一臺打印機(jī)，同時還要再請求一臺打印機(jī)才能完成他們各自的任務(wù)，由于系統(tǒng)再無空閑的打印機(jī)，兩個進(jìn)程就處于永遠(yuǎn)的等待狀態(tài)。我們就說系統(tǒng)產(chǎn)生了死鎖。死鎖的例子死鎖的例子2例：兩個進(jìn)程：P1，P2 共享兩類系統(tǒng)資源：R1，R2進(jìn)程 P1:Get(R1)Get(R2)Release(R1)Release(R2)進(jìn)程 P2:

33、Get(R2)Get(R1)Release(R2)Release(R1)死鎖的例子死鎖的例子2P1、P2推進(jìn)順序l合法順序 P1：Get（R1）；P1： Get （R2）； P1：Release（R1）； P1：Release（R2）； P2： Get （R2）；P2： Get （R1）； P2：Release（R2）； P2：Release（R1）；l非法順序死鎖 P1： Get （R1）；P2： Get （R2）； P1： Get （R2）；P2： Get （R1）；進(jìn)程推進(jìn)順序和死鎖進(jìn)程推進(jìn)順序和死鎖P2得到R2P2得到R1P2釋放R2P2釋放R1死鎖區(qū)P1得到R1P1得到R2P1釋放R

34、1P1釋放R2進(jìn)程P2進(jìn)程P1死鎖的定義死鎖的定義n多個進(jìn)程在運(yùn)行過程中因競爭資源或推進(jìn)順序不當(dāng)而造成的一種僵局，處于這種僵局狀態(tài)的進(jìn)程，若無外力作用，將永遠(yuǎn)不能向前推進(jìn)。n若系統(tǒng)出現(xiàn)死鎖，必須有相應(yīng)的措施進(jìn)行解決。死鎖產(chǎn)生的原因死鎖產(chǎn)生的原因n競爭資源。競爭資源。當(dāng)系統(tǒng)中供多個進(jìn)程共享的資源數(shù)目不足以滿足進(jìn)程的需要時，會引起諸進(jìn)程對資源的競爭而可能產(chǎn)生死鎖。n進(jìn)程推進(jìn)順序不當(dāng)。進(jìn)程推進(jìn)順序不當(dāng)。進(jìn)程運(yùn)行過程中，請求和釋放資源的順序不當(dāng)而產(chǎn)生死鎖。競爭資源n引起進(jìn)程死鎖的一個主要原因是由于進(jìn)程競爭系統(tǒng)中的資源，而進(jìn)程對資源的總需求量超過系統(tǒng)能夠提供的最大資源量。n系統(tǒng)中的資源大體可以分為兩類：

35、可重用資源和可消耗資源可重用資源n可重用資源指某一時刻僅允許一個進(jìn)程使用的、不能被進(jìn)程消耗的、釋放以后還可以被其他進(jìn)程使用的資源n如處理機(jī)、I/O通道、主存和輔存、設(shè)備以及諸如文件、數(shù)據(jù)庫、信號量之類的數(shù)據(jù)結(jié)構(gòu)。剝奪資源和不可剝奪資源剝奪資源和不可剝奪資源n按照可重用資源的特性，可分成兩類： 可剝奪性資源，又稱可搶占資源可剝奪性資源，又稱可搶占資源，當(dāng)資源從占用它的進(jìn)程被剝奪走時，對進(jìn)程不產(chǎn)生破壞性的影響。如CPU 不可剝奪性資源，又稱不可搶占資源不可剝奪性資源，又稱不可搶占資源，資源一旦分配，不能強(qiáng)行回收，只能在進(jìn)程用完后由其自動釋放。如打印機(jī)，磁帶機(jī)，刻錄機(jī)進(jìn)程對不可搶占資源的使用順序進(jìn)程

36、對不可搶占資源的使用順序n一個進(jìn)程必須按照下述順序使用不可搶占資源 請求資源：請求資源：若請求的資源不能立即滿足，則申請者等待。 使用資源：使用資源：獲得資源后，可以使用它。 釋放資源：釋放資源：資源使用完畢，要?dú)w還系統(tǒng)。進(jìn)程競爭不可搶占資源可能會發(fā)生死鎖n例如：兩個進(jìn)程P1和P2，競爭磁盤文件D和磁帶設(shè)備T。某一時刻，進(jìn)程P1獲得了磁盤文件D，進(jìn)程P2獲得了磁帶設(shè)備T，進(jìn)程P1要想繼續(xù)執(zhí)行必須得到磁帶設(shè)備T，而磁帶設(shè)備T已經(jīng)分配給了進(jìn)程P2，所有P1阻塞等待；而進(jìn)程P2要想繼續(xù)執(zhí)行必須得到磁盤文件D，而磁盤文件已經(jīng)分配給了進(jìn)程P1，所以P2阻塞等待。這樣系統(tǒng)出現(xiàn)了死鎖?？上馁Y源n可消費(fèi)資源

37、，指可以創(chuàng)造（生產(chǎn)）和撤消（消耗）的資源，其數(shù)量不限。n如中斷、信號、消息、緩沖區(qū)中的數(shù)據(jù)等。n進(jìn)程競爭可消耗資源也可能產(chǎn)生死鎖。進(jìn)程競爭可消耗資源可能會發(fā)生死鎖Process P1：receive(P2,msg1)send(P2,msg3)Process P2：receive(P1,msg2)send(P1,msg4)資源分配圖資源分配圖n用有向圖研究進(jìn)程和資源的關(guān)系資源已經(jīng)分配給進(jìn)程進(jìn)程請求資源進(jìn)程對資源的各種情況進(jìn)程對資源的各種情況RA資源R分配給進(jìn)程ASB進(jìn)程B請求資源SP1P2R1R2死鎖狀態(tài)資源分配圖資源分配圖進(jìn)進(jìn)程程占用情況占用情況請求情況請求情況r1r2r3r1r2r3P11個

38、個2個個1個個P22個個1個個P32個個2個個1個個死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件1. 1. 互斥條件互斥條件：指進(jìn)程對所分配到的資源進(jìn)行排它性使用。2. 2. 請求和保持條件請求和保持條件：進(jìn)程已經(jīng)保持了至少一個資源，但又請求新資源，而所請求的資源已被其它進(jìn)程占用，此時請求進(jìn)程阻塞等待，但又對已經(jīng)分配給它的資源保持不放。3. 3. 不剝奪條件不剝奪條件：進(jìn)程已經(jīng)獲得的資源，在未用完之前不能被剝奪，只能是使用完時自己釋放。死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件4. 4. 環(huán)路等待條件環(huán)路等待條件：發(fā)生死鎖時，必然存在一個進(jìn)程-資源循環(huán)鏈，鏈中有二個或多個進(jìn)程，每一個進(jìn)程正在等待鏈中的下一個成員保持的資源。

39、死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件n前三個條件是死鎖產(chǎn)生的必要條件，但不是充分條件。n互斥條件是臨界資源固有的屬性，保證進(jìn)程互斥訪問臨界資源是必要的。不能因?yàn)榛コ鈺?dǎo)致死鎖而禁止互斥。n“請求和保持”條件很多時候都存在，也是合理的。不可能要求進(jìn)程每次申請新資源時，必須釋放已占有資源。n“不剝奪”條件也是應(yīng)該保留的。允許剝奪的資源是指那些一旦剝奪中斷進(jìn)程的執(zhí)行以后，可以從斷點(diǎn)恢復(fù)執(zhí)行的資源。否則，屬于非剝奪資源。死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件n第四個條件實(shí)際上是前三個條件的可能導(dǎo)致的結(jié)果，即只有存在互斥、占有且等待與非剝奪條件，就可能出現(xiàn)循環(huán)等待。n只要系統(tǒng)出現(xiàn)循環(huán)等待，則一定出現(xiàn)死鎖。n這四個條件構(gòu)成

40、了死鎖產(chǎn)生的充分必要條件。處理死鎖的方法處理死鎖的方法n預(yù)防死鎖預(yù)防死鎖：通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個。n避免死鎖避免死鎖：在系統(tǒng)的資源分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)（可能會導(dǎo)致思索的狀態(tài)），從而避免發(fā)生死鎖。n檢測和解除死鎖檢測和解除死鎖：當(dāng)進(jìn)程申請資源時，不進(jìn)行任何限制，即允許死鎖發(fā)生。但要求系統(tǒng)定期或不定期檢測是否有死鎖發(fā)生。當(dāng)檢測到系統(tǒng)中已發(fā)生死鎖時，將進(jìn)程從死鎖狀態(tài)中解脫出來。預(yù)防死鎖預(yù)防死鎖破壞死鎖產(chǎn)生的條件：l破壞互斥條件l破壞保持和請求條件l破壞非剝奪條件l破壞循環(huán)等待條件預(yù)防死鎖：破壞“互斥”n產(chǎn)生死鎖的第一個條件是“互斥”

41、，而資源“互斥使用”是臨界資源的固有屬性，保證進(jìn)程互斥訪問臨界資源是必要的。不能因?yàn)榛コ鈺?dǎo)致死鎖而禁止互斥。預(yù)防死鎖：破壞“請求和保持”n為了破壞“請求和保持”條件，系統(tǒng)將要求所有進(jìn)程一次性地申請其所需的全部資源。n不合理 第一，降低了系統(tǒng)吞吐量和資源利用率 第二，浪費(fèi)資源。預(yù)防死鎖：破壞“非剝奪”n當(dāng)一個已經(jīng)獲得了某些資源的進(jìn)程，再申請的新資源不能立即得到滿足時，必須釋放其已獲得的所有資源， 不論是何種資源。n這種預(yù)防死鎖的策略實(shí)現(xiàn)起來比較復(fù)雜，而且要付出很大代價。n只有在資源狀態(tài)可以很容易地保存和恢復(fù)的情況下，這種方法才是實(shí)用的。預(yù)防死鎖：破壞“環(huán)路等待”n為了避免進(jìn)程申請資源形成環(huán)路，

42、首先將系統(tǒng)中的所有資源按類型進(jìn)行線性排序，并賦予不同的序號。n所有進(jìn)程對資源的請求，必須嚴(yán)格按資源序號遞增的次序提出，這樣在所形成的資源分配圖中不可能再出現(xiàn)環(huán)路。預(yù)防死鎖：破壞“環(huán)路等待”例題： 系統(tǒng)擁有資源為：輸入機(jī)（序號1），打印機(jī)（序號2） ，繪圖機(jī)（序號3） ，磁帶機(jī)（序號4） ，光盤（序號5） 。 系統(tǒng)有兩個進(jìn)程A和B 所有進(jìn)程對資源的請求必須嚴(yán)格按序號遞增順序進(jìn)行。如果A占有資源j，B占有資源i。若ij，允許A請求B占有的資源i，但絕不允許B請求A占有的資源j，故進(jìn)程資源分配圖絕不會形成環(huán)路。預(yù)防死鎖：破壞“環(huán)路等待”n較之前兩種策略，不論是資源利用率還是系統(tǒng)吞吐量，都有顯著的改善

43、。n但也存在嚴(yán)重問題 第一，為系統(tǒng)中各類資源分配的序號必須相對穩(wěn)定，這就限制了新設(shè)備類型的增加 第二，會經(jīng)常發(fā)生作業(yè)使用的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源浪費(fèi) 第三，增加了程序設(shè)計難度。避免死鎖n預(yù)防死鎖限制條件太強(qiáng)，不利于提高系統(tǒng)吞吐量和資源利用率，而且增加了程序設(shè)計難度。因此，該方法在死鎖解決中不常用。n避免死鎖方法通過資源分配之前預(yù)測是否會導(dǎo)致死鎖，決定是否進(jìn)行此次資源分配。只有不會導(dǎo)致死鎖的資源請求才實(shí)施分配，否則，讓請求進(jìn)程阻塞等待。n首先介紹系統(tǒng)的兩種狀態(tài)：安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)和不安全狀態(tài)n安全狀態(tài)：安全狀態(tài)：是指系統(tǒng)如果能夠按照某種進(jìn)程順序（p1,p2,pn）,來

44、為每個進(jìn)程pi分配其所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利的完成，則稱系統(tǒng)處于不安全狀態(tài)。n稱（p1，p2，,pn）序列為安全序列n不安全狀態(tài)：不安全狀態(tài)：如果系統(tǒng)無法找到一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。安全狀態(tài)和不安全狀態(tài)n若系統(tǒng)處于安全狀態(tài)，且按照某個安全序列分配資源，可以保證系統(tǒng)不會出現(xiàn)死鎖。n并非所有不安全狀態(tài)都是死鎖狀態(tài)。n當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)以后，便可能進(jìn)入死鎖狀態(tài)。n因此，避免死鎖的實(shí)質(zhì)在于：如何避免系統(tǒng)進(jìn)入不安全狀態(tài)。安全狀態(tài)的實(shí)例n假定系統(tǒng)中有三個進(jìn)程P1、P2、P3，共有16臺打印機(jī)，進(jìn)程P1總共要求12臺打印機(jī)，進(jìn)程P2總共要求7臺打印機(jī)，進(jìn)

45、程P3總共要求10臺打印機(jī)，在T0時刻，資源分配情況如下表所示： 進(jìn)程最大需求已分配尚需請求系統(tǒng)可用數(shù)P112483P2743P31055安全狀態(tài)的實(shí)例 在上表中，空閑打印機(jī)的數(shù)目為3臺，可把3臺打印機(jī)分配給P2，使P2繼續(xù)運(yùn)行直至完成；P2完成后便釋放出所占據(jù)的4臺打印機(jī)，使可用打印機(jī)數(shù)目增至7臺，可取出5臺分配給P3，使P3運(yùn)行直至完成；P3完成后將釋放出10臺打印機(jī)，P1便能獲得足夠的資源，從而P1、P2、P3均能順利完成。 由上分析可知，在T0時刻存在著一個安全序列P2,P3,P1，因此T0時刻是安全的。不安全狀態(tài)的實(shí)例n假定系統(tǒng)中有三個進(jìn)程P1、P2、P3，共有16臺打印機(jī)，進(jìn)程P1

46、總共要求12臺打印機(jī)，進(jìn)程P2總共要求7臺打印機(jī)，進(jìn)程P3總共要求10臺打印機(jī)，在T1時刻，資源分配情況如下表所示： 進(jìn)程最大需求已分配尚需請求系統(tǒng)可用數(shù)P112661P2743P31055不安全狀態(tài)的實(shí)例 此時，系統(tǒng)中只剩下1臺打印機(jī)，不能滿足P1P3任一進(jìn)程的資源需求，因此，從T1狀態(tài)繼續(xù)向前推進(jìn)，無論按照何種序列，P1P3進(jìn)程都將因?yàn)榈貌坏阶銐虻拇蛴C(jī)資源而相繼進(jìn)入阻塞，系統(tǒng)將陷入死鎖狀態(tài)。 由于在T1時刻找不到一個安全序列，故T1時刻是一個不安全狀態(tài)。安全狀態(tài)可以向不安全狀態(tài)轉(zhuǎn)換n如果不按照安全序列分配資源，系統(tǒng)將由安全狀態(tài)進(jìn)入不安全狀態(tài)n例如，在T0時刻，P3請求一臺打印機(jī)，若系統(tǒng)把

47、剩余的3臺中的1臺分配給P3，則系統(tǒng)進(jìn)入不安全狀態(tài)。避免死鎖：銀行家算法n最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。n該算法可用于銀行發(fā)放一筆貸款前，預(yù)測該筆貸款是否會引起銀行資金周轉(zhuǎn)問題。n例如：有四個顧客：A，B，C，D，每個顧客提出的最大貸款數(shù)量分別為6、5、4、7(以千美元為單位)。銀行家知道不是所有顧客都馬上需要其全部貸款（22）。因此，他只保留10個單位的貸款數(shù)量為這些顧客服務(wù)。n這里，銀行的資金就類似于計算機(jī)系統(tǒng)的資源，貸款業(yè)務(wù)類似于計算機(jī)的資源分配。初始狀態(tài)n銀行家擁有的貸款數(shù)量: 10顧客最大貸款數(shù) 擁有貸款數(shù) 還需貸款數(shù)A606B505C404D707安全

48、狀態(tài)n當(dāng)前銀行家擁有的貸款數(shù)量2，存在安全序列：CBAD，系統(tǒng)處于安全狀態(tài)。顧客最大貸款數(shù)擁有貸款數(shù)還需貸款數(shù)A615B514C422D743不安全狀態(tài)n當(dāng)B請求一個單位的貸款時，銀行家把錢貸給他，當(dāng)前銀行家擁有的貸款數(shù)量: 1，系統(tǒng)處于不安全狀態(tài)。顧客最大貸款數(shù)擁有貸款數(shù)還需貸款數(shù)A615B523C422D743銀行家算法n 銀行家算法可陳述如下：當(dāng)一個進(jìn)程提出資源請求時，假定分配給它，并檢查系統(tǒng)因此是否會不安全。如果安全，則滿足它的請求。否則，推遲它的請求。為了檢查狀態(tài)是否安全，銀行家要檢查他是否還有足夠資源滿足某一個顧客。如果能滿足，這個顧客很快將貸款歸還。如果所有貸款都能滿足，這個狀態(tài)

49、是安全的，實(shí)施實(shí)際的分配。安全性算法銀行家算法銀行家算法n這個算法利用了避免進(jìn)程進(jìn)入不安全狀態(tài)的原理。n要求進(jìn)程在執(zhí)行前，能提供所需資源的數(shù)量。n為實(shí)現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。銀行家算法的數(shù)據(jù)結(jié)構(gòu)銀行家算法的數(shù)據(jù)結(jié)構(gòu)lAvailable：可用資源向量。一個含有m個元素的數(shù)組，每個元素代表一類資源可用的數(shù)目。lMax：最大需求矩陣。nm矩陣，Max(i,j)=k表示進(jìn)程i 需要j類資源最大數(shù)目為k。lA l l o c a t i o n ： 分 配 矩 陣 。 n m 矩 陣 ，Allocation(i,j)=k表示進(jìn)程i當(dāng)前已分得j類資源數(shù)目為k。lNeed：需求矩陣。 nm

50、矩陣，Need(i,j)=k表示進(jìn)程i 還需要j類資源k個。銀行家算法的數(shù)據(jù)結(jié)構(gòu)銀行家算法的數(shù)據(jù)結(jié)構(gòu)l上述三個矩陣存在下述關(guān)系： Max(i,j) -Allocation(i,j)=Need(i,j)銀行家算法銀行家算法 設(shè) R e q u e s ti是 進(jìn) 程 Pi的 請 求 向 量 。 若Requestij=k，表示進(jìn)程Pi需要k個j類資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查： 若RequestiNeedi ，則轉(zhuǎn)；否則，認(rèn)為出錯。因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大它所需要的資源數(shù)已超過它所宣布的最大值值。 若RequestiAvailable，則轉(zhuǎn)；否則，表示系表示系統(tǒng)

51、中尚無足夠的資源統(tǒng)中尚無足夠的資源，Pi必須等待。 系統(tǒng)試探把要求的資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值。 Available=Available Requesti Allocationi = Allocationi + Requesti Needi = Needi Requesti系統(tǒng)執(zhí)行安全性算法，檢測此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分給進(jìn)程Pi；否則，將試探分配作廢，恢復(fù)資源狀態(tài)，讓Pi等待。銀行家算法銀行家算法安全性算法安全性算法n安全性算法： 設(shè)置兩個向量work和finishp工作向量work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)，含有m個

52、元素，其初始值為：workj=availablej。p完成向量finish，它表示系統(tǒng)是否有足夠資源使進(jìn)程推進(jìn)完成，開始執(zhí)行安全性算法時，F(xiàn)inishi=false;當(dāng)有足夠資源分配給進(jìn)程Pi，Pi推進(jìn)完成時，令Finishi=true。安全性算法安全性算法 從進(jìn)程集合中找到一個進(jìn)程，其滿足： Finishi=false Needi,j Workj 如找到則執(zhí)行步驟 ，找不到則執(zhí)行步驟。 當(dāng)進(jìn)程Pi獲得資源后，便可以向前推進(jìn)，直至完 成，并釋放出分配給它的全部資源，故應(yīng)執(zhí)行： Workj=Workj+Allocationi,j; Finishi=true; 執(zhí)行步驟。 若所有進(jìn)程的Finish

53、都為true，則系統(tǒng)為安全狀態(tài)；否則，系統(tǒng)為不安全狀態(tài)。銀行家算法示例銀行家算法示例 假定系統(tǒng)中有五個進(jìn)程P0， P1， P2， P3， P4和三類資源A，B，C，各類資源的數(shù)目分別是10、5、7。在T0時刻的資源分配圖如下表所示。銀行家算法示例銀行家算法示例MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P4 7 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2l利用安全性算法，利用安全性算法，T0時刻存在一個安全序列

54、時刻存在一個安全序列P1， P3， P4， P2， P0，故系統(tǒng)是安全的。，故系統(tǒng)是安全的。lP1請求資源，請求向量為請求資源，請求向量為Request1，0，2，系統(tǒng)按銀，系統(tǒng)按銀行家算法進(jìn)行檢查，可以找到一個安全序列行家算法進(jìn)行檢查，可以找到一個安全序列P1， P3， P4， P2， P0，因此系統(tǒng)是安全的。可以立即將，因此系統(tǒng)是安全的?？梢粤⒓磳1所申請的資所申請的資源分配給它。資源分配表如下表所示。源分配給它。資源分配表如下表所示。銀行家算法示例銀行家算法示例MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P47 5

55、 33 2 29 0 22 2 24 3 30 1 03 0 23 0 22 1 10 0 27 4 30 2 06 0 00 1 14 3 12 3 0lP4請求資源，請求向量為請求資源，請求向量為Request3，3，0，系統(tǒng)按，系統(tǒng)按銀行家算法進(jìn)行檢查，可用資源不能滿足請求資源，銀行家算法進(jìn)行檢查，可用資源不能滿足請求資源， P4等待。等待。lP0請求資源，請求向量為請求資源，請求向量為Request0，2，0，系統(tǒng)按，系統(tǒng)按銀行家算法進(jìn)行檢查，銀行家算法進(jìn)行檢查， P0分配資源后已不能滿足任何進(jìn)分配資源后已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時系統(tǒng)不分配資程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時系統(tǒng)不分配資源。如下圖。源。如下圖。銀行家算法示例銀行家算法示例MaxA B CAllocationA B CNee