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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48、最大值。 （2）如果）如果RequestijAvailablej，便轉(zhuǎn)向，便轉(zhuǎn)向步驟步驟(3)；否則，表示尚無足夠資源，；否則，表示尚無足夠資源，Pi須等待。須等待。 （3）系統(tǒng)試著把資源分配給進程）系統(tǒng)試著把資源分配給進程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)。若安全，才正式將資源分配給進程式將資源分配給進程Pi，以完成本次分配；否則，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀將本次的試探分配作