計(jì)算機(jī)操作系統(tǒng)_第三章_處理機(jī)調(diào)度與死鎖

1、本章討論處理器資源的管理問(wèn)題。本章討論處理器資源的管理問(wèn)題。處理器調(diào)度問(wèn)題決定著整個(gè)系統(tǒng)的綜合性能。處理器調(diào)度問(wèn)題決定著整個(gè)系統(tǒng)的綜合性能。不同的不同的CPU管理方法將為用戶(hù)提供不同性能的操管理方法將為用戶(hù)提供不同性能的操作系統(tǒng)。作系統(tǒng)。 從處理器調(diào)度的對(duì)象、時(shí)間、層次等不同角從處理器調(diào)度的對(duì)象、時(shí)間、層次等不同角度，可把處理器調(diào)度分成不同類(lèi)型。度，可把處理器調(diào)度分成不同類(lèi)型。按照調(diào)度涉及的層次不同，從用戶(hù)作業(yè)從進(jìn)按照調(diào)度涉及的層次不同，從用戶(hù)作業(yè)從進(jìn)入系統(tǒng)成為后備作業(yè)開(kāi)始，直到運(yùn)行結(jié)束退出系入系統(tǒng)成為后備作業(yè)開(kāi)始，直到運(yùn)行結(jié)束退出系統(tǒng)為止，可把處理器調(diào)度分成：統(tǒng)為止，可把處理器調(diào)度分成：高級(jí)

2、調(diào)度高級(jí)調(diào)度中級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度高級(jí)調(diào)度概念高級(jí)調(diào)度概念也稱(chēng)為也稱(chēng)為、長(zhǎng)程調(diào)度或接納調(diào)度。、長(zhǎng)程調(diào)度或接納調(diào)度。按照系統(tǒng)預(yù)定的調(diào)度策略，決定把外存上處于后備隊(duì)按照系統(tǒng)預(yù)定的調(diào)度策略，決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后再將創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備要的資源，然后再將創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。執(zhí)行。 在批處理操作系統(tǒng)中，作業(yè)首先進(jìn)入系統(tǒng)在輔存上的在批處理操作系統(tǒng)中，作業(yè)首先進(jìn)入系統(tǒng)在輔存上的后備作業(yè)隊(duì)列等候調(diào)度，因此，作業(yè)調(diào)度是必須的。在后備作業(yè)隊(duì)列等候調(diào)度，因此，作業(yè)調(diào)度是

3、必須的。在純粹的分時(shí)或?qū)崟r(shí)操作系統(tǒng)中，通常不需要配備作業(yè)調(diào)純粹的分時(shí)或?qū)崟r(shí)操作系統(tǒng)中，通常不需要配備作業(yè)調(diào)度。度。作業(yè)調(diào)度時(shí)要做的決定：作業(yè)調(diào)度時(shí)要做的決定：（1）接納多少個(gè)作業(yè)）接納多少個(gè)作業(yè)（2）接納哪些作業(yè)（調(diào)度算法）接納哪些作業(yè)（調(diào)度算法）作業(yè)調(diào)度的目標(biāo)：作業(yè)調(diào)度的目標(biāo)：（1）對(duì)所有作業(yè)盡量做到公平合理）對(duì)所有作業(yè)盡量做到公平合理（2）高設(shè)備利用率）高設(shè)備利用率（3）執(zhí)行盡可能多的作業(yè)）執(zhí)行盡可能多的作業(yè)（4）盡量短的響應(yīng)時(shí)間）盡量短的響應(yīng)時(shí)間也稱(chēng)為也稱(chēng)為、短程調(diào)度。、短程調(diào)度。用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程獲得處理機(jī)。低級(jí)調(diào)用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程獲得處理機(jī)。低級(jí)調(diào)度程序是操作系統(tǒng)

4、最為核心的部分，低級(jí)調(diào)度策略的優(yōu)度程序是操作系統(tǒng)最為核心的部分，低級(jí)調(diào)度策略的優(yōu)劣直接影響到整個(gè)系統(tǒng)的性能。劣直接影響到整個(gè)系統(tǒng)的性能。最初的調(diào)度對(duì)象是傳統(tǒng)操作系統(tǒng)中的進(jìn)程，隨著現(xiàn)代最初的調(diào)度對(duì)象是傳統(tǒng)操作系統(tǒng)中的進(jìn)程，隨著現(xiàn)代操作系統(tǒng)引入了多線程技術(shù)，進(jìn)程演變成資源管理的單操作系統(tǒng)引入了多線程技術(shù)，進(jìn)程演變成資源管理的單位，從而只作為中級(jí)調(diào)度的對(duì)象，內(nèi)核級(jí)線程則替代進(jìn)位，從而只作為中級(jí)調(diào)度的對(duì)象，內(nèi)核級(jí)線程則替代進(jìn)程成為低級(jí)調(diào)度的對(duì)象。程成為低級(jí)調(diào)度的對(duì)象。 （1）記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況）記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況（2）選擇占有處理機(jī)的進(jìn)程）選擇占有處理機(jī)的進(jìn)程(選擇算法選擇算法)（

5、3）進(jìn)行進(jìn)程上下文切換）進(jìn)行進(jìn)程上下文切換個(gè)進(jìn)程的上下文個(gè)進(jìn)程的上下文(context)包括進(jìn)程的狀態(tài)、包括進(jìn)程的狀態(tài)、有關(guān)變量和數(shù)據(jù)結(jié)構(gòu)的值、機(jī)器寄存器的值等相關(guān)有關(guān)變量和數(shù)據(jù)結(jié)構(gòu)的值、機(jī)器寄存器的值等相關(guān)程序、數(shù)據(jù)。當(dāng)正在執(zhí)行的進(jìn)程讓出處理機(jī)時(shí)，系程序、數(shù)據(jù)。當(dāng)正在執(zhí)行的進(jìn)程讓出處理機(jī)時(shí)，系統(tǒng)要做進(jìn)程上下文切換，以使另一個(gè)進(jìn)程得以執(zhí)行。統(tǒng)要做進(jìn)程上下文切換，以使另一個(gè)進(jìn)程得以執(zhí)行。 1）非搶占方式）非搶占方式進(jìn)程一旦獲得處理機(jī)后便一起執(zhí)行下去，直至該進(jìn)進(jìn)程一旦獲得處理機(jī)后便一起執(zhí)行下去，直至該進(jìn)程完成或發(fā)生某事件被阻塞時(shí)，才把處理機(jī)分配給其他程完成或發(fā)生某事件被阻塞時(shí)，才把處理機(jī)分配給其他

6、進(jìn)程。決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。進(jìn)程。決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。當(dāng)前進(jìn)程無(wú)論在用戶(hù)態(tài)還是核心態(tài)都不可以被搶用當(dāng)前進(jìn)程無(wú)論在用戶(hù)態(tài)還是核心態(tài)都不可以被搶用CPU。不可搶先式。不可搶先式OS：Windows98/95，在這些，在這些OS中，進(jìn)程從運(yùn)行態(tài)退出只能是自愿或阻塞，不能強(qiáng)迫運(yùn)中，進(jìn)程從運(yùn)行態(tài)退出只能是自愿或阻塞，不能強(qiáng)迫運(yùn)行態(tài)行態(tài)就緒態(tài)。就緒態(tài)。引起進(jìn)程調(diào)度的因素：引起進(jìn)程調(diào)度的因素：（1）進(jìn)程執(zhí)行完畢，或發(fā)生某事件不能再繼續(xù)）進(jìn)程執(zhí)行完畢，或發(fā)生某事件不能再繼續(xù)執(zhí)行執(zhí)行（2）I/O請(qǐng)求請(qǐng)求（3）進(jìn)程通信或同步過(guò)程中執(zhí)行了原語(yǔ)操作）進(jìn)程通信或同步過(guò)程中執(zhí)行了原語(yǔ)

7、操作優(yōu)點(diǎn)：優(yōu)點(diǎn)：實(shí)現(xiàn)實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小，適用于批實(shí)現(xiàn)實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小，適用于批處理系統(tǒng)。處理系統(tǒng)。缺點(diǎn)：缺點(diǎn)：不能滿(mǎn)足緊急任務(wù)的要求，不適用于實(shí)不能滿(mǎn)足緊急任務(wù)的要求，不適用于實(shí)時(shí)系統(tǒng)。時(shí)系統(tǒng)。當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，調(diào)度程序可以基于某當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，調(diào)度程序可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程。它進(jìn)程。剝奪原則有：剝奪原則有：（1）優(yōu)先權(quán)原則）優(yōu)先權(quán)原則（2）短進(jìn)程優(yōu)先原則）短進(jìn)程優(yōu)先原則（3）時(shí)間片原則。）時(shí)間片原則。當(dāng)前進(jìn)程在用戶(hù)態(tài)時(shí)可隨時(shí)被搶用當(dāng)前進(jìn)程在用戶(hù)態(tài)時(shí)可隨時(shí)被搶用CPU，但，但處于核心態(tài)時(shí)完全不可以

8、被搶用處于核心態(tài)時(shí)完全不可以被搶用CPU。如：傳統(tǒng)。如：傳統(tǒng)的的UNIX和和Windows。這類(lèi)操作系統(tǒng)通常在系統(tǒng)調(diào)用或中斷時(shí)屏蔽這類(lèi)操作系統(tǒng)通常在系統(tǒng)調(diào)用或中斷時(shí)屏蔽中斷，系統(tǒng)調(diào)用返回或中斷返回時(shí)開(kāi)放中斷。中斷，系統(tǒng)調(diào)用返回或中斷返回時(shí)開(kāi)放中斷。當(dāng)前進(jìn)程在用戶(hù)態(tài)時(shí)隨時(shí)被搶用當(dāng)前進(jìn)程在用戶(hù)態(tài)時(shí)隨時(shí)被搶用CPU，但處，但處于核心態(tài)時(shí)則大部分時(shí)間不可以被搶用于核心態(tài)時(shí)則大部分時(shí)間不可以被搶用CPU，只，只在某些時(shí)刻點(diǎn)（可搶先點(diǎn)）可以被搶用在某些時(shí)刻點(diǎn)（可搶先點(diǎn)）可以被搶用CPU。如：。如：UNIX SVR4。SVR4內(nèi)核定義了內(nèi)核定義了搶先點(diǎn)搶先點(diǎn)：內(nèi)核代碼中的這：內(nèi)核代碼中的這樣一些位置，內(nèi)核的

9、數(shù)據(jù)結(jié)構(gòu)處在一個(gè)穩(wěn)定的狀樣一些位置，內(nèi)核的數(shù)據(jù)結(jié)構(gòu)處在一個(gè)穩(wěn)定的狀態(tài)，并且內(nèi)核馬上要開(kāi)始長(zhǎng)時(shí)間的、大量的計(jì)算。態(tài)，并且內(nèi)核馬上要開(kāi)始長(zhǎng)時(shí)間的、大量的計(jì)算。此時(shí)，內(nèi)核檢查是否有實(shí)時(shí)進(jìn)程就緒需要運(yùn)行，此時(shí)，內(nèi)核檢查是否有實(shí)時(shí)進(jìn)程就緒需要運(yùn)行，若有則搶先當(dāng)前進(jìn)程。若有則搶先當(dāng)前進(jìn)程。無(wú)論當(dāng)前進(jìn)程處于用戶(hù)態(tài)還是核心態(tài)，都可無(wú)論當(dāng)前進(jìn)程處于用戶(hù)態(tài)還是核心態(tài)，都可以隨時(shí)可被搶用以隨時(shí)可被搶用CPU。如：。如：SUN Solaris（最（最成功的成功的UNIX商業(yè)變種之一）。商業(yè)變種之一）。為做到完全可搶先，為做到完全可搶先，Solaris對(duì)對(duì)SVR4的核心的核心代碼做了全面修改，大部分的內(nèi)核全局?jǐn)?shù)據(jù)結(jié)構(gòu)代

10、碼做了全面修改，大部分的內(nèi)核全局?jǐn)?shù)據(jù)結(jié)構(gòu)都用正確的同步對(duì)象如互斥都用正確的同步對(duì)象如互斥 鎖或信號(hào)量來(lái)保護(hù)，鎖或信號(hào)量來(lái)保護(hù)，并通過(guò)特殊內(nèi)核線程實(shí)現(xiàn)中斷來(lái)避免用提高優(yōu)先并通過(guò)特殊內(nèi)核線程實(shí)現(xiàn)中斷來(lái)避免用提高優(yōu)先級(jí)的方法保護(hù)臨界區(qū)。級(jí)的方法保護(hù)臨界區(qū)。Solaris內(nèi)核中只有極少內(nèi)核中只有極少的不可搶先代碼段。的不可搶先代碼段。中級(jí)調(diào)度實(shí)現(xiàn)進(jìn)程在主存與外存間的對(duì)換。反映到中級(jí)調(diào)度實(shí)現(xiàn)進(jìn)程在主存與外存間的對(duì)換。反映到進(jìn)程狀態(tài)上就是掛起和解除掛起。進(jìn)程狀態(tài)上就是掛起和解除掛起。中級(jí)調(diào)度將那些暫時(shí)不能運(yùn)行的進(jìn)程調(diào)出主存，此中級(jí)調(diào)度將那些暫時(shí)不能運(yùn)行的進(jìn)程調(diào)出主存，此時(shí)這些進(jìn)程處于掛起狀態(tài)。當(dāng)被掛起的進(jìn)

11、程具備了運(yùn)行時(shí)這些進(jìn)程處于掛起狀態(tài)。當(dāng)被掛起的進(jìn)程具備了運(yùn)行條件，且主存又有空閑區(qū)域時(shí)，再由中級(jí)調(diào)度決定一部條件，且主存又有空閑區(qū)域時(shí)，再由中級(jí)調(diào)度決定一部分這樣的進(jìn)程重新調(diào)回主存工作。分這樣的進(jìn)程重新調(diào)回主存工作。中級(jí)調(diào)度起到短期調(diào)整系統(tǒng)負(fù)荷的作用，調(diào)度的依中級(jí)調(diào)度起到短期調(diào)整系統(tǒng)負(fù)荷的作用，調(diào)度的依據(jù)是存儲(chǔ)資源量和進(jìn)程的當(dāng)前狀態(tài)，目的是提高內(nèi)存利據(jù)是存儲(chǔ)資源量和進(jìn)程的當(dāng)前狀態(tài)，目的是提高內(nèi)存利用率和系統(tǒng)吞吐量。用率和系統(tǒng)吞吐量。3.2.1 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型1只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型內(nèi)存中維護(hù)就緒進(jìn)程隊(duì)列和阻塞進(jìn)程隊(duì)列。系統(tǒng)可內(nèi)存中維護(hù)就緒進(jìn)程隊(duì)列和阻塞進(jìn)

12、程隊(duì)列。系統(tǒng)可能以棧、樹(shù)、鏈表的方式組織隊(duì)列。能以棧、樹(shù)、鏈表的方式組織隊(duì)列。 外存維護(hù)一個(gè)后備隊(duì)列，內(nèi)存維護(hù)就緒進(jìn)程外存維護(hù)一個(gè)后備隊(duì)列，內(nèi)存維護(hù)就緒進(jìn)程隊(duì)列和阻塞進(jìn)程隊(duì)列。隊(duì)列和阻塞進(jìn)程隊(duì)列。不同類(lèi)型及目標(biāo)的操作系統(tǒng)，其采用的調(diào)度不同類(lèi)型及目標(biāo)的操作系統(tǒng)，其采用的調(diào)度方式與調(diào)度算法通常不同。方式與調(diào)度算法通常不同。1面向用戶(hù)的準(zhǔn)則面向用戶(hù)的準(zhǔn)則2面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則（1）周轉(zhuǎn)時(shí)間短）周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間：作業(yè)提交計(jì)算機(jī)開(kāi)始到完成返回周轉(zhuǎn)時(shí)間：作業(yè)提交計(jì)算機(jī)開(kāi)始到完成返回用戶(hù)為止的時(shí)間間隔。用戶(hù)為止的時(shí)間間隔。（2）響應(yīng)時(shí)間快）響應(yīng)時(shí)間快響應(yīng)時(shí)間：從提交一個(gè)請(qǐng)求到首次產(chǎn)生響應(yīng)響應(yīng)時(shí)間：

13、從提交一個(gè)請(qǐng)求到首次產(chǎn)生響應(yīng)的時(shí)間間隔?；蛘哒f(shuō)，用戶(hù)發(fā)送指令給計(jì)算機(jī)到的時(shí)間間隔。或者說(shuō)，用戶(hù)發(fā)送指令給計(jì)算機(jī)到計(jì)算機(jī)返回結(jié)果給用戶(hù)的時(shí)間間隔。計(jì)算機(jī)返回結(jié)果給用戶(hù)的時(shí)間間隔。（3）截止時(shí)間的保證）截止時(shí)間的保證評(píng)價(jià)實(shí)時(shí)系統(tǒng)的重要指標(biāo)。評(píng)價(jià)實(shí)時(shí)系統(tǒng)的重要指標(biāo)。截止時(shí)間：任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或截止時(shí)間：任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。必須完成的最遲時(shí)間。（4）優(yōu)先權(quán)準(zhǔn)則：關(guān)鍵任務(wù)得到更好的性能指）優(yōu)先權(quán)準(zhǔn)則：關(guān)鍵任務(wù)得到更好的性能指標(biāo)標(biāo)（5）公平性：確保每個(gè)用戶(hù)每個(gè)進(jìn)程獲得合理）公平性：確保每個(gè)用戶(hù)每個(gè)進(jìn)程獲得合理的的CPU份額或其他資源份額。份額或其他資源份額。（1）

14、系統(tǒng)吞吐量高）系統(tǒng)吞吐量高吞吐量：?jiǎn)挝粫r(shí)間內(nèi)系統(tǒng)完成的作業(yè)數(shù)。吞吐量：?jiǎn)挝粫r(shí)間內(nèi)系統(tǒng)完成的作業(yè)數(shù)。（2）處理機(jī)利用率高：大中型系統(tǒng)的主要）處理機(jī)利用率高：大中型系統(tǒng)的主要指標(biāo)指標(biāo)（3）各類(lèi)資源的平衡利用）各類(lèi)資源的平衡利用常用的作業(yè)調(diào)度算法有：常用的作業(yè)調(diào)度算法有：常用進(jìn)程調(diào)度算法：常用進(jìn)程調(diào)度算法：最簡(jiǎn)單的調(diào)度算法，基本思想是按進(jìn)程（作業(yè)）最簡(jiǎn)單的調(diào)度算法，基本思想是按進(jìn)程（作業(yè)）到達(dá)的先后順序進(jìn)行調(diào)度。到達(dá)的先后順序進(jìn)行調(diào)度。作業(yè)調(diào)度：作業(yè)調(diào)度：按照作業(yè)進(jìn)入系統(tǒng)的先后次序來(lái)挑按照作業(yè)進(jìn)入系統(tǒng)的先后次序來(lái)挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。進(jìn)程調(diào)度：進(jìn)程

15、調(diào)度：按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來(lái)分配處理器。先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先被挑選，來(lái)分配處理器。先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先被挑選，運(yùn)行進(jìn)程一旦占有處理器將一直運(yùn)行下去直到運(yùn)行運(yùn)行進(jìn)程一旦占有處理器將一直運(yùn)行下去直到運(yùn)行結(jié)束或阻塞，即采用非搶占調(diào)度方式。結(jié)束或阻塞，即采用非搶占調(diào)度方式。FCFS的特點(diǎn)：的特點(diǎn)：l比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè)（進(jìn)比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè)（進(jìn)程）。程）。l有利于有利于CPU繁忙型作業(yè)，而不利于繁忙型作業(yè)，而不利于I/O繁忙型繁忙型作業(yè)。作業(yè)。l實(shí)現(xiàn)簡(jiǎn)單實(shí)現(xiàn)簡(jiǎn)單l平均周轉(zhuǎn)時(shí)間長(zhǎng)平均周轉(zhuǎn)時(shí)間長(zhǎng)這是對(duì)這是對(duì)FCFS算法的改進(jìn)，其目標(biāo)

16、是減少平算法的改進(jìn)，其目標(biāo)是減少平均周轉(zhuǎn)時(shí)間。均周轉(zhuǎn)時(shí)間。SJF：從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的一個(gè)或幾個(gè)作業(yè)調(diào)入內(nèi)存。的一個(gè)或幾個(gè)作業(yè)調(diào)入內(nèi)存。SPF：從就緒隊(duì)列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間從就緒隊(duì)列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它。最短的進(jìn)程，將處理機(jī)分配給它。短進(jìn)程優(yōu)先算法既可以是非搶占式，也可以是短進(jìn)程優(yōu)先算法既可以是非搶占式，也可以是搶占式。搶占式。當(dāng)一個(gè)進(jìn)程正在執(zhí)行時(shí)，一個(gè)新進(jìn)程進(jìn)入就緒當(dāng)一個(gè)進(jìn)程正在執(zhí)行時(shí)，一個(gè)新進(jìn)程進(jìn)入就緒狀態(tài)，如果新進(jìn)程需要的狀態(tài)，如果新進(jìn)程需要的CPU時(shí)間比當(dāng)前正在執(zhí)行時(shí)間比當(dāng)前正在執(zhí)行的進(jìn)程剩余下來(lái)還需的的進(jìn)

17、程剩余下來(lái)還需的CPU時(shí)間短，掄占式短進(jìn)程時(shí)間短，掄占式短進(jìn)程優(yōu)先算法強(qiáng)行趕走當(dāng)前正在執(zhí)行進(jìn)程，這種方式也優(yōu)先算法強(qiáng)行趕走當(dāng)前正在執(zhí)行進(jìn)程，這種方式也叫叫最短剩余時(shí)間優(yōu)先算法最短剩余時(shí)間優(yōu)先算法(Shortest Remaining Time First) 。優(yōu)點(diǎn)：優(yōu)點(diǎn)：與與FCFS相比，改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮相比，改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的平均等待時(shí)間。短作業(yè)的平均等待時(shí)間。易于實(shí)現(xiàn)，系統(tǒng)吞吐量高。易于實(shí)現(xiàn)，系統(tǒng)吞吐量高。缺點(diǎn)：缺點(diǎn)：忽視了作業(yè)等待時(shí)間忽視了作業(yè)等待時(shí)間對(duì)長(zhǎng)作業(yè)非常不利，長(zhǎng)作業(yè)（進(jìn)程）可能長(zhǎng)時(shí)間得不到執(zhí)行；對(duì)長(zhǎng)作業(yè)非常不利，長(zhǎng)作業(yè)（進(jìn)程）可

18、能長(zhǎng)時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)；未能依據(jù)作業(yè)的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。短作業(yè)優(yōu)先算法的變型：短作業(yè)優(yōu)先算法的變型：“最短剩余時(shí)間優(yōu)先最短剩余時(shí)間優(yōu)先”(Shortest Remaining Time First) 允許比當(dāng)前進(jìn)程剩余時(shí)間更短的進(jìn)程搶占當(dāng)前進(jìn)允許比當(dāng)前進(jìn)程剩余時(shí)間更短的進(jìn)程搶占當(dāng)前進(jìn)程程“最高響應(yīng)比優(yōu)先最高響應(yīng)比優(yōu)先” (Highest Response Ratio Next) 響應(yīng)比響應(yīng)比R = (等待時(shí)間等待時(shí)間 + 要求執(zhí)行時(shí)間要求執(zhí)

19、行時(shí)間) / 要求要求執(zhí)行時(shí)間執(zhí)行時(shí)間 是是FCFS和和SJF的折衷的折衷作業(yè)調(diào)度：作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)進(jìn)入內(nèi)存。最高的作業(yè)進(jìn)入內(nèi)存。進(jìn)程調(diào)度：進(jìn)程調(diào)度：每一個(gè)進(jìn)程給出一個(gè)優(yōu)先數(shù)，處每一個(gè)進(jìn)程給出一個(gè)優(yōu)先數(shù)，處理器調(diào)度每次選擇就緒進(jìn)程隊(duì)列中優(yōu)先數(shù)最大者，理器調(diào)度每次選擇就緒進(jìn)程隊(duì)列中優(yōu)先數(shù)最大者，讓它占用處理器運(yùn)行。讓它占用處理器運(yùn)行。（1）非搶占式優(yōu)先權(quán)算法）非搶占式優(yōu)先權(quán)算法系統(tǒng)一旦將處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程后，該系統(tǒng)一旦將處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去直到完成。主要用于批處理系統(tǒng)，進(jìn)程便一直執(zhí)行下去直到完成

20、。主要用于批處理系統(tǒng)，也用于某些實(shí)時(shí)要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。也用于某些實(shí)時(shí)要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。（2）搶占式優(yōu)先權(quán)調(diào)度算法）搶占式優(yōu)先權(quán)調(diào)度算法系統(tǒng)按最高優(yōu)先權(quán)分配處理機(jī)。只要出現(xiàn)另一個(gè)優(yōu)系統(tǒng)按最高優(yōu)先權(quán)分配處理機(jī)。只要出現(xiàn)另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，則進(jìn)程調(diào)度程序停止當(dāng)前進(jìn)程的執(zhí)行，先權(quán)更高的進(jìn)程，則進(jìn)程調(diào)度程序停止當(dāng)前進(jìn)程的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。常用于嚴(yán)格的實(shí)時(shí)系統(tǒng)中，或?qū)π阅芤筝^高的批常用于嚴(yán)格的實(shí)時(shí)系統(tǒng)中，或?qū)π阅芤筝^高的批處理和分時(shí)系統(tǒng)中。處理和分時(shí)系統(tǒng)中。（1）靜態(tài)優(yōu)先權(quán)）靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，在

21、整個(gè)運(yùn)行期靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，在整個(gè)運(yùn)行期間不再改變。間不再改變。確定優(yōu)先權(quán)的依據(jù)有：確定優(yōu)先權(quán)的依據(jù)有：進(jìn)程類(lèi)型。如系統(tǒng)進(jìn)程優(yōu)先權(quán)高于用戶(hù)進(jìn)程。進(jìn)程類(lèi)型。如系統(tǒng)進(jìn)程優(yōu)先權(quán)高于用戶(hù)進(jìn)程。進(jìn)程對(duì)資源的需求。如估計(jì)運(yùn)行時(shí)間、內(nèi)存需求等。進(jìn)程對(duì)資源的需求。如估計(jì)運(yùn)行時(shí)間、內(nèi)存需求等。用戶(hù)要求。由用戶(hù)或操作員根據(jù)作業(yè)的緊急程序指用戶(hù)要求。由用戶(hù)或操作員根據(jù)作業(yè)的緊急程序指定一個(gè)優(yōu)先級(jí)。定一個(gè)優(yōu)先級(jí)。靜態(tài)優(yōu)先權(quán)法簡(jiǎn)單易行，系統(tǒng)開(kāi)銷(xiāo)小，但不夠精確。靜態(tài)優(yōu)先權(quán)法簡(jiǎn)單易行，系統(tǒng)開(kāi)銷(xiāo)小，但不夠精確。（2）動(dòng)態(tài)優(yōu)先權(quán)）動(dòng)態(tài)優(yōu)先權(quán)創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，在進(jìn)程周期內(nèi)創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，在進(jìn)程周期

22、內(nèi)可以動(dòng)態(tài)變化。如隨等待時(shí)間的增加而改變?？梢詣?dòng)態(tài)變化。如隨等待時(shí)間的增加而改變。優(yōu)先權(quán)確定依據(jù)：優(yōu)先權(quán)確定依據(jù)：根據(jù)進(jìn)程占用有根據(jù)進(jìn)程占用有CPU時(shí)間的長(zhǎng)短來(lái)決定。時(shí)間的長(zhǎng)短來(lái)決定。根據(jù)就緒進(jìn)程等待根據(jù)就緒進(jìn)程等待CPU的時(shí)間長(zhǎng)短來(lái)決定。的時(shí)間長(zhǎng)短來(lái)決定。最高響應(yīng)比優(yōu)先法（最高響應(yīng)比優(yōu)先法（HRN）是對(duì)）是對(duì)FCFS方式和方式和SJF方式的一種綜合平衡。方式的一種綜合平衡。 HRN調(diào)度策略同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長(zhǎng)調(diào)度策略同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長(zhǎng)短和估計(jì)需要的執(zhí)行時(shí)間長(zhǎng)短，從中選出響應(yīng)比短和估計(jì)需要的執(zhí)行時(shí)間長(zhǎng)短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。最高的作業(yè)投入執(zhí)行。響應(yīng)比響應(yīng)比=（等

23、待時(shí)間（等待時(shí)間+要求服務(wù)時(shí)間）要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間要求服務(wù)時(shí)間特點(diǎn)：特點(diǎn)：（1）在等待時(shí)間相同時(shí)，此算法是優(yōu)待短作業(yè)）在等待時(shí)間相同時(shí)，此算法是優(yōu)待短作業(yè)的，實(shí)現(xiàn)的是的，實(shí)現(xiàn)的是SJF。（2）在要求服務(wù)時(shí)間相同時(shí)，優(yōu)先權(quán)決定于等）在要求服務(wù)時(shí)間相同時(shí)，優(yōu)先權(quán)決定于等待時(shí)間，實(shí)現(xiàn)的是待時(shí)間，實(shí)現(xiàn)的是FCFS。（3）長(zhǎng)作業(yè)在等待足夠長(zhǎng)時(shí)，也可獲得處理機(jī)。）長(zhǎng)作業(yè)在等待足夠長(zhǎng)時(shí)，也可獲得處理機(jī)。這種算法是介于這種算法是介于FCFS和和SJF之間的一種折中算之間的一種折中算法。但是由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開(kāi)銷(xiāo)法。但是由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開(kāi)銷(xiāo)也要相應(yīng)增加。也要相應(yīng)增加。1.

24、 時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法系統(tǒng)將所有就緒進(jìn)程按系統(tǒng)將所有就緒進(jìn)程按FIFS規(guī)則排隊(duì)，每個(gè)進(jìn)程規(guī)則排隊(duì)，每個(gè)進(jìn)程輪流運(yùn)行一個(gè)相同的時(shí)間片。輪流運(yùn)行一個(gè)相同的時(shí)間片。每次調(diào)度時(shí)將每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷，調(diào)度程時(shí)間片。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷，調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，再將處理機(jī)分配給就緒隊(duì)列的隊(duì)首進(jìn)程。這樣可保證就再將處理機(jī)分配給就緒隊(duì)列的隊(duì)首進(jìn)程。這樣可保證就緒隊(duì)列中的所有進(jìn)程在一定時(shí)間內(nèi)均能獲得一時(shí)間片的緒隊(duì)列中的所

25、有進(jìn)程在一定時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)，即系統(tǒng)在能在給定時(shí)間內(nèi)響應(yīng)所有用戶(hù)的請(qǐng)求。處理機(jī)，即系統(tǒng)在能在給定時(shí)間內(nèi)響應(yīng)所有用戶(hù)的請(qǐng)求。 好處：好處：使系統(tǒng)及時(shí)響應(yīng)。使系統(tǒng)及時(shí)響應(yīng)。缺點(diǎn)：缺點(diǎn)：輪轉(zhuǎn)法調(diào)度是一種剝奪式調(diào)度，系統(tǒng)耗輪轉(zhuǎn)法調(diào)度是一種剝奪式調(diào)度，系統(tǒng)耗費(fèi)在進(jìn)程切換上的開(kāi)銷(xiāo)比較大，費(fèi)在進(jìn)程切換上的開(kāi)銷(xiāo)比較大，時(shí)間片長(zhǎng)度變化的影響時(shí)間片長(zhǎng)度變化的影響:過(guò)長(zhǎng)過(guò)長(zhǎng)退化為退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。過(guò)短過(guò)短用戶(hù)的一次請(qǐng)求需要多個(gè)時(shí)間片才能用戶(hù)的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，切換次數(shù)增加，系統(tǒng)開(kāi)銷(xiāo)大。處理完，切換次

26、數(shù)增加，系統(tǒng)開(kāi)銷(xiāo)大。時(shí)間片長(zhǎng)度的確定：時(shí)間片長(zhǎng)度的確定：（1）系統(tǒng)效率）系統(tǒng)效率（2）對(duì)響應(yīng)時(shí)間的要求：）對(duì)響應(yīng)時(shí)間的要求： T(響應(yīng)時(shí)間響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目進(jìn)程數(shù)目)*q(時(shí)間片時(shí)間片)（3）就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越?。┚途w進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越?。?）CPU的處理能力：應(yīng)當(dāng)使用戶(hù)輸入通常在的處理能力：應(yīng)當(dāng)使用戶(hù)輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)。平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)。 多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法的綜合和發(fā)展。優(yōu)先級(jí)算法

27、的綜合和發(fā)展。 1）實(shí)現(xiàn)）實(shí)現(xiàn)（1）系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先）系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先級(jí)，并逐級(jí)降低。級(jí)，并逐級(jí)降低。（2）為不同隊(duì)列所規(guī)定的時(shí)間片長(zhǎng)度不同，優(yōu)先權(quán)越）為不同隊(duì)列所規(guī)定的時(shí)間片長(zhǎng)度不同，優(yōu)先權(quán)越高的隊(duì)列分配的時(shí)間片越小。如逐級(jí)加倍。高的隊(duì)列分配的時(shí)間片越小。如逐級(jí)加倍。（3）新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列）新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列1的末尾，按的末尾，按FCFS算法排隊(duì)調(diào)度；若按隊(duì)列算法排隊(duì)調(diào)度；若按隊(duì)列1的一個(gè)時(shí)間片未的一個(gè)時(shí)間片未能執(zhí)行完，則降低投入到隊(duì)列能執(zhí)行完，則降低投入到隊(duì)列2的末尾。如果在的末尾。如果在隊(duì)列隊(duì)列2的時(shí)間片內(nèi)未能完成

28、，則降低投入到隊(duì)列的時(shí)間片內(nèi)未能完成，則降低投入到隊(duì)列3；如此下去，降低到最后的隊(duì)列，則按；如此下去，降低到最后的隊(duì)列，則按“時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)”算法調(diào)度直到完成。算法調(diào)度直到完成。（4）僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)）僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程的隊(duì)列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)程，并進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾。把被搶先的進(jìn)程投入原隊(duì)列的末尾。（5）阻塞進(jìn)程被喚醒時(shí)，進(jìn)入原來(lái)的就緒隊(duì)列中。）阻塞進(jìn)程被喚醒時(shí)，進(jìn)入原來(lái)的就緒隊(duì)列中。（1

29、）終端型作業(yè)用戶(hù)）終端型作業(yè)用戶(hù)提供高的響應(yīng)時(shí)間。提供高的響應(yīng)時(shí)間。（2）短批處理作業(yè)用戶(hù)）短批處理作業(yè)用戶(hù)在第一個(gè)或前在第一個(gè)或前2個(gè)時(shí)間片中即可完成，平均周個(gè)時(shí)間片中即可完成，平均周轉(zhuǎn)時(shí)間短。轉(zhuǎn)時(shí)間短。（3）長(zhǎng)批處理作業(yè)用戶(hù)）長(zhǎng)批處理作業(yè)用戶(hù)不會(huì)饑餓。不會(huì)饑餓。為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程。照顧短進(jìn)程。為獲得較好的為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧時(shí)間而照顧I/O型進(jìn)程。型進(jìn)程。不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié)。不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié)。實(shí)時(shí)系統(tǒng)中存在若干個(gè)實(shí)時(shí)進(jìn)程或?qū)崟r(shí)任務(wù)，實(shí)時(shí)系統(tǒng)中存在若干

30、個(gè)實(shí)時(shí)進(jìn)程或?qū)崟r(shí)任務(wù)，反應(yīng)或控制某些外部事件。反應(yīng)或控制某些外部事件。實(shí)時(shí)系統(tǒng)要響應(yīng)的事件（要處理的實(shí)時(shí)任務(wù)）實(shí)時(shí)系統(tǒng)要響應(yīng)的事件（要處理的實(shí)時(shí)任務(wù)）可以進(jìn)一步劃分為周期性事件和非周期性事件，可以進(jìn)一步劃分為周期性事件和非周期性事件，都聯(lián)系著一個(gè)截止響應(yīng)時(shí)間。都聯(lián)系著一個(gè)截止響應(yīng)時(shí)間。提供必要的信息提供必要的信息系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng)多采用搶占式調(diào)度機(jī)制多采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制具有快速切換機(jī)制1非搶占式調(diào)度算法非搶占式調(diào)度算法（1）非搶占式輪轉(zhuǎn)調(diào)度算法）非搶占式輪轉(zhuǎn)調(diào)度算法 通過(guò)對(duì)所有周期性任務(wù)的分析預(yù)測(cè)（到達(dá)時(shí)間、運(yùn)行通過(guò)對(duì)所有周期性任務(wù)的分析預(yù)測(cè)（到達(dá)時(shí)間、運(yùn)行時(shí)間、結(jié)束

31、時(shí)間、任務(wù)間的優(yōu)先關(guān)系），事先確定一個(gè)時(shí)間、結(jié)束時(shí)間、任務(wù)間的優(yōu)先關(guān)系），事先確定一個(gè)固定的調(diào)度方案。這種方法的特點(diǎn)是有效但不靈活。固定的調(diào)度方案。這種方法的特點(diǎn)是有效但不靈活。 （2）非搶占式優(yōu)先級(jí)調(diào)度算法）非搶占式優(yōu)先級(jí)調(diào)度算法2搶占式調(diào)度算法搶占式調(diào)度算法（1）基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。）基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。（2）立即搶占的優(yōu)先權(quán)調(diào)度算法）立即搶占的優(yōu)先權(quán)調(diào)度算法實(shí)時(shí)調(diào)度算法可以分為實(shí)時(shí)調(diào)度算法可以分為動(dòng)態(tài)實(shí)時(shí)動(dòng)態(tài)實(shí)時(shí)調(diào)度算法和調(diào)度算法和靜態(tài)實(shí)時(shí)靜態(tài)實(shí)時(shí)調(diào)度算法兩類(lèi)。動(dòng)態(tài)實(shí)時(shí)調(diào)度算法在運(yùn)調(diào)度算法兩類(lèi)。動(dòng)態(tài)實(shí)時(shí)調(diào)度算法在運(yùn)行時(shí)作出調(diào)度決定，靜態(tài)實(shí)時(shí)調(diào)度算法在系統(tǒng)啟

32、行時(shí)作出調(diào)度決定，靜態(tài)實(shí)時(shí)調(diào)度算法在系統(tǒng)啟動(dòng)之前完成所有的調(diào)度決策。動(dòng)之前完成所有的調(diào)度決策。常用的實(shí)時(shí)算法都是基于優(yōu)先權(quán)的算法。常用的實(shí)時(shí)算法都是基于優(yōu)先權(quán)的算法。根據(jù)任務(wù)的開(kāi)始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)。截根據(jù)任務(wù)的開(kāi)始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間越早，優(yōu)先級(jí)越高。止時(shí)間越早，優(yōu)先級(jí)越高。實(shí)時(shí)任務(wù)的就緒隊(duì)列按優(yōu)先級(jí)排序，調(diào)度程序總是實(shí)時(shí)任務(wù)的就緒隊(duì)列按優(yōu)先級(jí)排序，調(diào)度程序總是選擇隊(duì)首進(jìn)程占有處理機(jī)。選擇隊(duì)首進(jìn)程占有處理機(jī)。EDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式根據(jù)任務(wù)的緊急（或松馳）程序來(lái)確定任務(wù)根據(jù)任務(wù)的緊急（或松馳）程序來(lái)確定任務(wù)的優(yōu)先級(jí)。任務(wù)緊急程序高，為該任務(wù)所

33、賦予的的優(yōu)先級(jí)。任務(wù)緊急程序高，為該任務(wù)所賦予的優(yōu)先級(jí)愈高。優(yōu)先級(jí)愈高。該算法主要用于搶占式調(diào)度方式。該算法主要用于搶占式調(diào)度方式。松弛度松弛度=必須完成時(shí)間必須完成時(shí)間-其本身的運(yùn)行時(shí)間其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間當(dāng)前時(shí)間假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和和B，任務(wù)，任務(wù)A要求每要求每 20 ms執(zhí)行一次，執(zhí)行時(shí)間執(zhí)行一次，執(zhí)行時(shí)間為為 10 ms；任務(wù)；任務(wù)B只要求每只要求每50 ms執(zhí)行一次，執(zhí)執(zhí)行一次，執(zhí)行時(shí)間為行時(shí)間為 25 ms。 A A和和B B任務(wù)每次任務(wù)每次必須完成的時(shí)間必須完成的時(shí)間利用利用LLFLLF算法算法進(jìn)行調(diào)度的情

34、況進(jìn)行調(diào)度的情況死鎖實(shí)例死鎖實(shí)例設(shè)系統(tǒng)有一臺(tái)打印機(jī)設(shè)系統(tǒng)有一臺(tái)打印機(jī)(R1)一臺(tái)掃描儀一臺(tái)掃描儀(R2)，被并發(fā)的，被并發(fā)的A、B兩進(jìn)程共享。用信號(hào)量?jī)蛇M(jìn)程共享。用信號(hào)量S1、S2表示表示R1、R2是否可是否可用，用， S1、 S2初值為初值為1。A、B并發(fā)時(shí)就可能產(chǎn)生死并發(fā)時(shí)就可能產(chǎn)生死鎖。鎖。 死鎖：死鎖：多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。再向前推進(jìn)。一組并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資一組并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前不

35、會(huì)源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前不會(huì)釋放自己所擁有的資源。從而造成大家都想得到釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進(jìn)程不能繼續(xù)向資源而又都得不到資源，各并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。這一組進(jìn)程就稱(chēng)為死鎖進(jìn)程。前推進(jìn)的狀態(tài)。這一組進(jìn)程就稱(chēng)為死鎖進(jìn)程。產(chǎn)生死鎖的因素不僅與系統(tǒng)擁有的資源數(shù)量有關(guān)，而且與資源分配策略，進(jìn)程對(duì)資源的使用要求以及并發(fā)進(jìn)程的速率有關(guān)。1.1.競(jìng)爭(zhēng)系統(tǒng)資源競(jìng)爭(zhēng)系統(tǒng)資源2.2.進(jìn)程的推進(jìn)順序不當(dāng)進(jìn)程的推進(jìn)順序不當(dāng) 可剝奪資源：分配給某進(jìn)程后又可以被其他進(jìn)可剝奪資源：分配給某進(jìn)程后又可以被其他進(jìn)程或系統(tǒng)剝奪的資源。如處理機(jī)、內(nèi)存。程或系

36、統(tǒng)剝奪的資源。如處理機(jī)、內(nèi)存。非剝奪資源：一旦分配給某進(jìn)程后不能強(qiáng)行收非剝奪資源：一旦分配給某進(jìn)程后不能強(qiáng)行收回，只能由進(jìn)程自行釋放的資源。回，只能由進(jìn)程自行釋放的資源。u永久性資源：可以被多個(gè)進(jìn)程多次使用的資源永久性資源：可以被多個(gè)進(jìn)程多次使用的資源（可再用資源）。（可再用資源）。u臨時(shí)性資源：由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使臨時(shí)性資源：由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用一段時(shí)間后便無(wú)用的資源。如消息，中斷信用一段時(shí)間后便無(wú)用的資源。如消息，中斷信號(hào)，同步信號(hào)等（可消耗性資源）。號(hào)，同步信號(hào)等（可消耗性資源）。（1）競(jìng)爭(zhēng)非剝奪資源）競(jìng)爭(zhēng)非剝奪資源（2）競(jìng)爭(zhēng)臨時(shí)性資源）競(jìng)爭(zhēng)臨時(shí)性資源P1P2Reque

37、st(R1);Request(R2);Request(R2);Request(R1);Releast(R1);Releast(R2);Releast(R2);Releast(R1);1互斥條件：資源獨(dú)占，排他性使用?；コ鈼l件：資源獨(dú)占，排他性使用。 2請(qǐng)求和保持條件：當(dāng)進(jìn)程因請(qǐng)求資源而阻塞時(shí)，請(qǐng)求和保持條件：當(dāng)進(jìn)程因請(qǐng)求資源而阻塞時(shí)，不釋放已占有的資源。不釋放已占有的資源。3不剝奪條件：進(jìn)程已獲得的資源不能被剝奪，不剝奪條件：進(jìn)程已獲得的資源不能被剝奪，只能在使用完時(shí)由自己釋放。只能在使用完時(shí)由自己釋放。4環(huán)路等待條件：在發(fā)生死鎖時(shí)，必然存在一個(gè)環(huán)路等待條件：在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程進(jìn)程

38、-資源的環(huán)形循環(huán)鏈，鏈中每一個(gè)進(jìn)程已資源的環(huán)形循環(huán)鏈，鏈中每一個(gè)進(jìn)程已獲得的資源被下一個(gè)進(jìn)程所請(qǐng)求，同時(shí)它又獲得的資源被下一個(gè)進(jìn)程所請(qǐng)求，同時(shí)它又請(qǐng)求上一進(jìn)程所擁有的資源。請(qǐng)求上一進(jìn)程所擁有的資源。M預(yù)防死鎖：設(shè)置限制條件，破壞產(chǎn)生死鎖的預(yù)防死鎖：設(shè)置限制條件，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件四個(gè)必要條件中的一個(gè)或幾個(gè)條件 。M避免死鎖：在每次的資源動(dòng)態(tài)分配過(guò)程中，避免死鎖：在每次的資源動(dòng)態(tài)分配過(guò)程中，對(duì)系統(tǒng)能夠滿(mǎn)足的資源申請(qǐng)進(jìn)行安全性檢查對(duì)系統(tǒng)能夠滿(mǎn)足的資源申請(qǐng)進(jìn)行安全性檢查 ，根據(jù)結(jié)果決定是否進(jìn)行此次分配。根據(jù)結(jié)果決定是否進(jìn)行此次分配。M檢測(cè)死鎖：允許系統(tǒng)發(fā)生死鎖，但設(shè)置檢測(cè)檢

39、測(cè)死鎖：允許系統(tǒng)發(fā)生死鎖，但設(shè)置檢測(cè)機(jī)構(gòu)，及時(shí)檢測(cè)出死鎖的發(fā)生。機(jī)構(gòu)，及時(shí)檢測(cè)出死鎖的發(fā)生。M解除死鎖：外力推動(dòng)解除死鎖。具體方法有：解除死鎖：外力推動(dòng)解除死鎖。具體方法有：撤消或掛起死鎖進(jìn)程、剝奪資源等。撤消或掛起死鎖進(jìn)程、剝奪資源等。 死鎖的預(yù)防：通過(guò)設(shè)置限制條件，破壞產(chǎn)生死死鎖的預(yù)防：通過(guò)設(shè)置限制條件，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，使系統(tǒng)鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，使系統(tǒng)在任何時(shí)刻都不滿(mǎn)足死鎖的必要條件，從而預(yù)防在任何時(shí)刻都不滿(mǎn)足死鎖的必要條件，從而預(yù)防死鎖的發(fā)生。死鎖的發(fā)生。進(jìn)程必須在運(yùn)行前一次性地申請(qǐng)運(yùn)行期間所進(jìn)程必須在運(yùn)行前一次性地申請(qǐng)運(yùn)行期間所需的全部資源

40、，這樣進(jìn)程在整個(gè)運(yùn)行期間不會(huì)再需的全部資源，這樣進(jìn)程在整個(gè)運(yùn)行期間不會(huì)再提出資源請(qǐng)求，從而提出資源請(qǐng)求，從而摒棄了請(qǐng)求和保持條件。摒棄了請(qǐng)求和保持條件。優(yōu)點(diǎn)：簡(jiǎn)單，易于實(shí)現(xiàn)，安全。優(yōu)點(diǎn)：簡(jiǎn)單，易于實(shí)現(xiàn)，安全。缺點(diǎn)：缺點(diǎn)：（1）資源浪費(fèi)嚴(yán)重。降低進(jìn)程并發(fā)度。）資源浪費(fèi)嚴(yán)重。降低進(jìn)程并發(fā)度。（2）進(jìn)程延遲運(yùn)行。）進(jìn)程延遲運(yùn)行。（3）不適用資源需要未知的進(jìn)程。）不適用資源需要未知的進(jìn)程。允許進(jìn)程逐個(gè)申請(qǐng)資源，當(dāng)進(jìn)程新的資源請(qǐng)?jiān)试S進(jìn)程逐個(gè)申請(qǐng)資源，當(dāng)進(jìn)程新的資源請(qǐng)求未滿(mǎn)足時(shí)，必須釋放已占有的資源，待以后需求未滿(mǎn)足時(shí)，必須釋放已占有的資源，待以后需要時(shí)再重新申請(qǐng)。要時(shí)再重新申請(qǐng)。此策略表明進(jìn)程已占有的資

41、源可被暫時(shí)釋放，此策略表明進(jìn)程已占有的資源可被暫時(shí)釋放，即被剝奪了，從而即被剝奪了，從而摒棄摒棄“不剝奪不剝奪”條件條件。缺點(diǎn)：缺點(diǎn)：（1）復(fù)雜，實(shí)現(xiàn)困難且代價(jià)大。）復(fù)雜，實(shí)現(xiàn)困難且代價(jià)大。（2）延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，增加系統(tǒng)開(kāi)）延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，增加系統(tǒng)開(kāi)銷(xiāo)。銷(xiāo)。系統(tǒng)給每類(lèi)資源賦予一個(gè)序號(hào)，每一個(gè)進(jìn)程嚴(yán)格按系統(tǒng)給每類(lèi)資源賦予一個(gè)序號(hào)，每一個(gè)進(jìn)程嚴(yán)格按照序號(hào)遞增的順序請(qǐng)求資源，釋放則相反。此方法不可照序號(hào)遞增的順序請(qǐng)求資源，釋放則相反。此方法不可能形成資源占有與請(qǐng)求的環(huán)路，從而能形成資源占有與請(qǐng)求的環(huán)路，從而破壞環(huán)路等待條件破壞環(huán)路等待條件。優(yōu)點(diǎn)：相對(duì)而言，系統(tǒng)利用率高，系統(tǒng)吞吐量大。優(yōu)點(diǎn)

42、：相對(duì)而言，系統(tǒng)利用率高，系統(tǒng)吞吐量大。缺點(diǎn)：缺點(diǎn)：（1）限制設(shè)備擴(kuò)充。系統(tǒng)事先確定資源序號(hào)，限）限制設(shè)備擴(kuò)充。系統(tǒng)事先確定資源序號(hào)，限制了新類(lèi)型設(shè)備的增加。制了新類(lèi)型設(shè)備的增加。（2）限制了進(jìn)程對(duì)資源的請(qǐng)求，編程困難。）限制了進(jìn)程對(duì)資源的請(qǐng)求，編程困難。（3）資源浪費(fèi)。當(dāng)進(jìn)程使用順序與資源序號(hào)不相）資源浪費(fèi)。當(dāng)進(jìn)程使用順序與資源序號(hào)不相符時(shí)，也會(huì)造成資源浪費(fèi)。符時(shí)，也會(huì)造成資源浪費(fèi)。避免死鎖的方法就是讓系統(tǒng)處于安全狀態(tài)中。避免死鎖的方法就是讓系統(tǒng)處于安全狀態(tài)中。在避免死鎖的策略中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)?jiān)诒苊馑梨i的策略中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源。資源。死鎖避免死鎖避免：系統(tǒng)對(duì)進(jìn)程運(yùn)行過(guò)程中發(fā)出的

43、每：系統(tǒng)對(duì)進(jìn)程運(yùn)行過(guò)程中發(fā)出的每一個(gè)系統(tǒng)能夠滿(mǎn)足的資源申請(qǐng)進(jìn)行安全檢查，根一個(gè)系統(tǒng)能夠滿(mǎn)足的資源申請(qǐng)進(jìn)行安全檢查，根據(jù)檢查結(jié)果決定是否分配資源。若此次分配會(huì)導(dǎo)據(jù)檢查結(jié)果決定是否分配資源。若此次分配會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則不予分配；否則予以致系統(tǒng)進(jìn)入不安全狀態(tài)，則不予分配；否則予以分配。分配。1安全狀態(tài)安全狀態(tài)安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序來(lái)為每個(gè)安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序來(lái)為每個(gè)進(jìn)程分配其所需資源，直至每個(gè)進(jìn)程的最大需求，進(jìn)程分配其所需資源，直至每個(gè)進(jìn)程的最大需求，使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在這樣一使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在這樣一個(gè)序列，則稱(chēng)系統(tǒng)處于不安全狀態(tài)，不安全

44、狀態(tài)個(gè)序列，則稱(chēng)系統(tǒng)處于不安全狀態(tài)，不安全狀態(tài)一般會(huì)導(dǎo)致死鎖。一般會(huì)導(dǎo)致死鎖。2安全狀態(tài)實(shí)例安全狀態(tài)實(shí)例 P953由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。單種資源的銀行家算法描述：假定一個(gè)銀行家擁有資金，數(shù)量為，被N個(gè)客戶(hù)共享。銀行家對(duì)客戶(hù)提出下列約束條件：每個(gè)客戶(hù)必須預(yù)先說(shuō)明自己所要求的最大資金量每個(gè)客戶(hù)每次提出部分資金量申請(qǐng)和獲得分配如果銀行滿(mǎn)足了客戶(hù)對(duì)資金的最大需求量，那么，客戶(hù)在資金運(yùn)作后，應(yīng)在有限時(shí)間內(nèi)全部歸還銀行。銀行則保證：若一個(gè)客

45、戶(hù)所要求的最大資金量不超過(guò)，則銀行一定接納該客戶(hù)，并處理他的資金需求；銀行在收到一個(gè)客戶(hù)的資金申請(qǐng)時(shí)，可能因資金不足而讓客戶(hù)等待，但保證在有限時(shí)間內(nèi)讓客戶(hù)獲得資金。（1） 可利用資源向量可利用資源向量Availablem。每一個(gè)元素代表一類(lèi)可利用的資源數(shù)目，其初始值每一個(gè)元素代表一類(lèi)可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類(lèi)全部可用資源的數(shù)目，其數(shù)值隨是系統(tǒng)中所配置的該類(lèi)全部可用資源的數(shù)目，其數(shù)值隨該類(lèi)資源的分配和回收而動(dòng)態(tài)地改變。如果該類(lèi)資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有，則表示系統(tǒng)中現(xiàn)有Rj類(lèi)資源類(lèi)資源K個(gè)。個(gè)。 （2） 最大需求矩陣最大需求矩

46、陣Maxnm。定義了系統(tǒng)中定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類(lèi)資源類(lèi)資源的最大需求。如果的最大需求。如果Maxij=K，則表示進(jìn)程，則表示進(jìn)程i需要需要Rj類(lèi)資源的最大數(shù)目為類(lèi)資源的最大數(shù)目為K。（3）分配矩陣）分配矩陣Allocationnm定義了系統(tǒng)中每一類(lèi)資源當(dāng)前已分配給每一進(jìn)程的定義了系統(tǒng)中每一類(lèi)資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果資源數(shù)。如果Allocationij=K，則表示進(jìn)程，則表示進(jìn)程i當(dāng)前當(dāng)前已分得已分得Rj類(lèi)資源的數(shù)目為類(lèi)資源的數(shù)目為K。（4）需求矩陣）需求矩陣Neednm用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源數(shù)。如果用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源

47、數(shù)。如果Needij=K，則表示進(jìn)程，則表示進(jìn)程i還需要還需要Rj類(lèi)資源類(lèi)資源K個(gè)，方個(gè)，方能完成任務(wù)。能完成任務(wù)。Needij=Maxij-Allocationij 設(shè)設(shè)Requesti是進(jìn)程是進(jìn)程Pi的資源請(qǐng)求向量，如果的資源請(qǐng)求向量，如果Requestij =K，表示進(jìn)程，表示進(jìn)程Pi需要需要K個(gè)個(gè)Rj類(lèi)型的資源。類(lèi)型的資源。當(dāng)當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟檢查：發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟檢查：（1）如果）如果RequestijNeedij ，便轉(zhuǎn)向，便轉(zhuǎn)向步驟步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。過(guò)它所宣布的

48、最大值。 （2）如果）如果RequestijAvailablej，便轉(zhuǎn)向，便轉(zhuǎn)向步驟步驟(3)；否則，表示尚無(wú)足夠資源，；否則，表示尚無(wú)足夠資源，Pi須等待。須等待。 （3）系統(tǒng)試著把資源分配給進(jìn)程）系統(tǒng)試著把資源分配給進(jìn)程Pi，并修，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej=Availablej-Requestij;Allocationij=Allocationij+Requestij;Needij=Needij-Requestij;（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程式將資源分配給進(jìn)程Pi，以完成本次分配；否則，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀將本次的試探分配作