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

第三章處理機(jī)調(diào)度與死鎖本章內(nèi)容處理機(jī)調(diào)度常用調(diào)度算法介紹死鎖與預(yù)防死鎖的方法本章討論處理器資源的管理問題。處理器調(diào)度問題決定著整個(gè)系統(tǒng)的綜合性能。不同的CPU管理方法將為用戶提供不同性能的操作系統(tǒng)。3.1處理機(jī)調(diào)度的層次從處理器調(diào)度的對象、時(shí)間、層次等不同角度，可把處理器調(diào)度分成不同類型。按照調(diào)度涉及的層次不同，從用戶作業(yè)從進(jìn)入系統(tǒng)成為后備作業(yè)開始，直到運(yùn)行結(jié)束退出系統(tǒng)為止，可把處理器調(diào)度分成：高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度3.1.1高級(jí)調(diào)度高級(jí)調(diào)度概念也稱為作業(yè)調(diào)度、長程調(diào)度或接納調(diào)度。按照系統(tǒng)預(yù)定的調(diào)度策略，決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后再將創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。在批處理操作系統(tǒng)中，作業(yè)首先進(jìn)入系統(tǒng)在輔存上的后備作業(yè)隊(duì)列等候調(diào)度，因此，作業(yè)調(diào)度是必須的。在純粹的分時(shí)或?qū)崟r(shí)操作系統(tǒng)中，通常不需要配備作業(yè)調(diào)度。作業(yè)相關(guān)概念作業(yè)：程序+數(shù)據(jù)+作業(yè)說明書作業(yè)步：相對獨(dú)立相互關(guān)聯(lián)的順序加工步驟作業(yè)流作業(yè)控制塊JCB：作業(yè)在系統(tǒng)中的標(biāo)識(shí)，保存有系統(tǒng)對作業(yè)進(jìn)行管理與調(diào)試所需要的全部信息作業(yè)標(biāo)識(shí)用戶名稱、用戶帳戶作業(yè)類型、作業(yè)狀態(tài)資源需求調(diào)度信息進(jìn)入時(shí)間、開始處理時(shí)間、需求時(shí)間……作業(yè)調(diào)度時(shí)要做的決定：（1）接納多少個(gè)作業(yè)（2）接納哪些作業(yè)（調(diào)度算法）作業(yè)調(diào)度的目標(biāo)：（1）對所有作業(yè)盡量做到公平合理（2）高設(shè)備利用率（3）執(zhí)行盡可能多的作業(yè)（4）盡量短的響應(yīng)時(shí)間3.1.2低級(jí)調(diào)度也稱為進(jìn)程調(diào)度、短程調(diào)度。用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程獲得處理機(jī)。低級(jí)調(diào)度程序是操作系統(tǒng)最為核心的部分，低級(jí)調(diào)度策略的優(yōu)劣直接影響到整個(gè)系統(tǒng)的性能。最初的調(diào)度對象是傳統(tǒng)操作系統(tǒng)中的進(jìn)程，隨著現(xiàn)代操作系統(tǒng)引入了多線程技術(shù)，進(jìn)程演變成資源管理的單位，從而只作為中級(jí)調(diào)度的對象，內(nèi)核級(jí)線程則替代進(jìn)程成為低級(jí)調(diào)度的對象。1.進(jìn)程調(diào)度功能（1）記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況（2）選擇占有處理機(jī)的進(jìn)程(選擇算法)（3）進(jìn)行進(jìn)程上下文切換—個(gè)進(jìn)程的上下文(context)包括進(jìn)程的狀態(tài)、有關(guān)變量和數(shù)據(jù)結(jié)構(gòu)的值、機(jī)器寄存器的值等相關(guān)程序、數(shù)據(jù)。當(dāng)正在執(zhí)行的進(jìn)程讓出處理機(jī)時(shí)，系統(tǒng)要做進(jìn)程上下文切換，以使另一個(gè)進(jìn)程得以執(zhí)行。2.進(jìn)程調(diào)試中的三個(gè)基本機(jī)制排隊(duì)器：負(fù)責(zé)組織各進(jìn)程隊(duì)列分派器：將選中的進(jìn)程從就緒隊(duì)列中取出，分配處理機(jī)上下文切換機(jī)制兩對上下文切換：保存當(dāng)前進(jìn)程上下文，裝入分派程序上下文移出分派程序上下文，裝入新選進(jìn)程現(xiàn)場信息3.進(jìn)程調(diào)度方式1）非搶占方式進(jìn)程一旦獲得處理機(jī)后便一起執(zhí)行下去，直至該進(jìn)程完成或發(fā)生某事件被阻塞時(shí)，才把處理機(jī)分配給其他進(jìn)程。決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。當(dāng)前進(jìn)程無論在用戶態(tài)還是核心態(tài)都不可以被搶用CPU。不可搶先式OS：Windows98/95，在這些OS中，進(jìn)程從運(yùn)行態(tài)退出只能是自愿或阻塞，不能強(qiáng)迫運(yùn)行態(tài)就緒態(tài)。引起進(jìn)程調(diào)度的因素：（1）進(jìn)程執(zhí)行完畢，或發(fā)生某事件不能再繼續(xù)執(zhí)行（2）I/O請求（3）進(jìn)程通信或同步過程中執(zhí)行了原語操作優(yōu)點(diǎn)：實(shí)現(xiàn)實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于批處理系統(tǒng)。缺點(diǎn)：不能滿足緊急任務(wù)的要求，不適用于實(shí)時(shí)系統(tǒng)。2）搶占方式當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，調(diào)度程序可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程。剝奪原則有：（1）優(yōu)先權(quán)原則（2）短進(jìn)程優(yōu)先原則（3）時(shí)間片原則。內(nèi)核完全不可搶先當(dāng)前進(jìn)程在用戶態(tài)時(shí)可隨時(shí)被搶用CPU，但處于核心態(tài)時(shí)完全不可以被搶用CPU。如：傳統(tǒng)的UNIX和Windows。這類操作系統(tǒng)通常在系統(tǒng)調(diào)用或中斷時(shí)屏蔽中斷，系統(tǒng)調(diào)用返回或中斷返回時(shí)開放中斷。內(nèi)核的部分可搶先當(dāng)前進(jìn)程在用戶態(tài)時(shí)隨時(shí)被搶用CPU，但處于核心態(tài)時(shí)則大部分時(shí)間不可以被搶用CPU，只在某些時(shí)刻點(diǎn)（可搶先點(diǎn)）可以被搶用CPU。如：UNIXSVR4。SVR4內(nèi)核定義了搶先點(diǎn)：內(nèi)核代碼中的這樣一些位置，內(nèi)核的數(shù)據(jù)結(jié)構(gòu)處在一個(gè)穩(wěn)定的狀態(tài)，并且內(nèi)核馬上要開始長時(shí)間的、大量的計(jì)算。此時(shí)，內(nèi)核檢查是否有實(shí)時(shí)進(jìn)程就緒需要運(yùn)行，若有則搶先當(dāng)前進(jìn)程。完全可搶先或內(nèi)核完全可搶先無論當(dāng)前進(jìn)程處于用戶態(tài)還是核心態(tài)，都可以隨時(shí)可被搶用CPU。如：SUNSolaris（最成功的UNIX商業(yè)變種之一）。為做到完全可搶先，Solaris對SVR4的核心代碼做了全面修改，大部分的內(nèi)核全局?jǐn)?shù)據(jù)結(jié)構(gòu)都用正確的同步對象如互斥鎖或信號(hào)量來保護(hù)，并通過特殊內(nèi)核線程實(shí)現(xiàn)中斷來避免用提高優(yōu)先級(jí)的方法保護(hù)臨界區(qū)。Solaris內(nèi)核中只有極少的不可搶先代碼段。3.1.3中級(jí)調(diào)度中級(jí)調(diào)度實(shí)現(xiàn)進(jìn)程在主存與外存間的對換。反映到進(jìn)程狀態(tài)上就是掛起和解除掛起。中級(jí)調(diào)度將那些暫時(shí)不能運(yùn)行的進(jìn)程調(diào)出主存，此時(shí)這些進(jìn)程處于掛起狀態(tài)。當(dāng)被掛起的進(jìn)程具備了運(yùn)行條件，且主存又有空閑區(qū)域時(shí)，再由中級(jí)調(diào)度決定一部分這樣的進(jìn)程重新調(diào)回主存工作。中級(jí)調(diào)度起到短期調(diào)整系統(tǒng)負(fù)荷的作用，調(diào)度的依據(jù)是存儲(chǔ)資源量和進(jìn)程的當(dāng)前狀態(tài)，目的是提高內(nèi)存利用率和系統(tǒng)吞吐量。3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則3.2.1調(diào)度隊(duì)列模型1．只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型內(nèi)存中維護(hù)就緒進(jìn)程隊(duì)列和阻塞進(jìn)程隊(duì)列。系統(tǒng)可能以棧、樹、鏈表的方式組織隊(duì)列。2．具有高級(jí)與低級(jí)調(diào)度的調(diào)度隊(duì)列模型外存維護(hù)一個(gè)后備隊(duì)列，內(nèi)存維護(hù)就緒進(jìn)程隊(duì)列和阻塞進(jìn)程隊(duì)列。3．同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型3.2.2選擇調(diào)度方式和調(diào)度算法的準(zhǔn)則不同類型及目標(biāo)的操作系統(tǒng)，其采用的調(diào)度方式與調(diào)度算法通常不同。1．面向用戶的準(zhǔn)則2．面向系統(tǒng)的準(zhǔn)則1．面向用戶的準(zhǔn)則（1）周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間：作業(yè)提交計(jì)算機(jī)開始到完成返回用戶為止的時(shí)間間隔。（2）響應(yīng)時(shí)間快響應(yīng)時(shí)間：從提交一個(gè)請求到首次產(chǎn)生響應(yīng)的時(shí)間間隔。或者說，用戶發(fā)送指令給計(jì)算機(jī)到計(jì)算機(jī)返回結(jié)果給用戶的時(shí)間間隔。1．面向用戶的準(zhǔn)則（3）截止時(shí)間的保證評價(jià)實(shí)時(shí)系統(tǒng)的重要指標(biāo)。截止時(shí)間：任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。（4）優(yōu)先權(quán)準(zhǔn)則：關(guān)鍵任務(wù)得到更好的性能指標(biāo)（5）公平性：確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的CPU份額或其他資源份額。2．面向系統(tǒng)的準(zhǔn)則（1）系統(tǒng)吞吐量高吞吐量：單位時(shí)間內(nèi)系統(tǒng)完成的作業(yè)數(shù)。（2）處理機(jī)利用率高：大中型系統(tǒng)的主要指標(biāo)（3）各類資源的平衡利用3.3調(diào)度算法常用的作業(yè)調(diào)度算法有：FCFS（先來先服務(wù)）方法SJP（最短作業(yè)優(yōu)先）法HRN（最高響應(yīng)比）法常用進(jìn)程調(diào)度算法：RR（輪轉(zhuǎn)）法FCFS（先來先服務(wù)）法優(yōu)先級(jí)法多級(jí)反饋隊(duì)列算法3.2.1先來先服務(wù)算法最簡單的調(diào)度算法，基本思想是按進(jìn)程（作業(yè)）到達(dá)的先后順序進(jìn)行調(diào)度。作業(yè)調(diào)度：按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。進(jìn)程調(diào)度：按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來分配處理器。先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先被挑選，運(yùn)行進(jìn)程一旦占有處理器將一直運(yùn)行下去直到運(yùn)行結(jié)束或阻塞，即采用非搶占調(diào)度方式。FCFS的特點(diǎn)：比較有利于長作業(yè)，而不利于短作業(yè)（進(jìn)程）。有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。實(shí)現(xiàn)簡單平均周轉(zhuǎn)時(shí)間長3.2.1短作業(yè)（進(jìn)程）優(yōu)先算法這是對FCFS算法的改進(jìn)，其目標(biāo)是減少平均周轉(zhuǎn)時(shí)間。SJF：從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的一個(gè)或幾個(gè)作業(yè)調(diào)入內(nèi)存。SPF：從就緒隊(duì)列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它。短進(jìn)程優(yōu)先法調(diào)度方式短進(jìn)程優(yōu)先算法既可以是非搶占式，也可以是搶占式。當(dāng)一個(gè)進(jìn)程正在執(zhí)行時(shí)，一個(gè)新進(jìn)程進(jìn)入就緒狀態(tài)，如果新進(jìn)程需要的CPU時(shí)間比當(dāng)前正在執(zhí)行的進(jìn)程剩余下來還需的CPU時(shí)間短，掄占式短進(jìn)程優(yōu)先算法強(qiáng)行趕走當(dāng)前正在執(zhí)行進(jìn)程，這種方式也叫最短剩余時(shí)間優(yōu)先算法(ShortestRemainingTimeFirst)。短作業(yè)優(yōu)先法的特性優(yōu)點(diǎn)：與FCFS相比，改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的平均等待時(shí)間。易于實(shí)現(xiàn)，系統(tǒng)吞吐量高。缺點(diǎn)：忽視了作業(yè)等待時(shí)間對長作業(yè)非常不利，長作業(yè)（進(jìn)程）可能長時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級(jí)；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。短作業(yè)優(yōu)先算法的變型：“最短剩余時(shí)間優(yōu)先”(ShortestRemainingTimeFirst)

允許比當(dāng)前進(jìn)程剩余時(shí)間更短的進(jìn)程搶占當(dāng)前進(jìn)程“最高響應(yīng)比優(yōu)先”

(HighestResponseRatioNext)

響應(yīng)比R=(等待時(shí)間+要求執(zhí)行時(shí)間)/要求執(zhí)行時(shí)間是FCFS和SJF的折衷3.3.2最高優(yōu)先權(quán)優(yōu)先算法（FPF）作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)進(jìn)入內(nèi)存。進(jìn)程調(diào)度：每一個(gè)進(jìn)程給出一個(gè)優(yōu)先數(shù)，處理器調(diào)度每次選擇就緒進(jìn)程隊(duì)列中優(yōu)先數(shù)最大者，讓它占用處理器運(yùn)行。1．優(yōu)先權(quán)調(diào)度算法的類型（1）非搶占式優(yōu)先權(quán)算法系統(tǒng)一旦將處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去直到完成。主要用于批處理系統(tǒng)，也用于某些實(shí)時(shí)要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。（2）搶占式優(yōu)先權(quán)調(diào)度算法系統(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í)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。常用于嚴(yán)格的實(shí)時(shí)系統(tǒng)中，或?qū)π阅芤筝^高的批處理和分時(shí)系統(tǒng)中。2．優(yōu)先權(quán)的類型（1）靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，在整個(gè)運(yùn)行期間不再改變。確定優(yōu)先權(quán)的依據(jù)有：進(jìn)程類型。如系統(tǒng)進(jìn)程優(yōu)先權(quán)高于用戶進(jìn)程。進(jìn)程對資源的需求。如估計(jì)運(yùn)行時(shí)間、內(nèi)存需求等。用戶要求。由用戶或操作員根據(jù)作業(yè)的緊急程序指定一個(gè)優(yōu)先級(jí)。靜態(tài)優(yōu)先權(quán)法簡單易行，系統(tǒng)開銷小，但不夠精確。2．優(yōu)先權(quán)的類型（2）動(dòng)態(tài)優(yōu)先權(quán)創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，在進(jìn)程周期內(nèi)可以動(dòng)態(tài)變化。如隨等待時(shí)間的增加而改變。優(yōu)先權(quán)確定依據(jù)：根據(jù)進(jìn)程占用有CPU時(shí)間的長短來決定。根據(jù)就緒進(jìn)程等待CPU的時(shí)間長短來決定。3.高響應(yīng)比優(yōu)先算法最高響應(yīng)比優(yōu)先法（HRN）是對FCFS方式和SJF方式的一種綜合平衡。HRN調(diào)度策略同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長短和估計(jì)需要的執(zhí)行時(shí)間長短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。響應(yīng)比=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間特點(diǎn)：（1）在等待時(shí)間相同時(shí)，此算法是優(yōu)待短作業(yè)的，實(shí)現(xiàn)的是SJF。（2）在要求服務(wù)時(shí)間相同時(shí)，優(yōu)先權(quán)決定于等待時(shí)間，實(shí)現(xiàn)的是FCFS。（3）長作業(yè)在等待足夠長時(shí)，也可獲得處理機(jī)。這種算法是介于FCFS和SJF之間的一種折中算法。但是由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。3.3.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1.時(shí)間片輪轉(zhuǎn)法系統(tǒng)將所有就緒進(jìn)程按FIFS規(guī)則排隊(duì)，每個(gè)進(jìn)程輪流運(yùn)行一個(gè)相同的時(shí)間片。每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷，調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，再將處理機(jī)分配給就緒隊(duì)列的隊(duì)首進(jìn)程。這樣可保證就緒隊(duì)列中的所有進(jìn)程在一定時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)，即系統(tǒng)在能在給定時(shí)間內(nèi)響應(yīng)所有用戶的請求。好處：使系統(tǒng)及時(shí)響應(yīng)。缺點(diǎn)：輪轉(zhuǎn)法調(diào)度是一種剝奪式調(diào)度，系統(tǒng)耗費(fèi)在進(jìn)程切換上的開銷比較大，時(shí)間片長度變化的影響:過長－>退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長。過短－>用戶的一次請求需要多個(gè)時(shí)間片才能處理完，切換次數(shù)增加，系統(tǒng)開銷大。時(shí)間片長度的確定：（1）系統(tǒng)效率（2）對響應(yīng)時(shí)間的要求：

T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片)（3）就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越小（4）CPU的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長。2.多級(jí)反饋隊(duì)列調(diào)度算法

多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法的綜合和發(fā)展。1）實(shí)現(xiàn)（1）系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先級(jí)，并逐級(jí)降低。（2）為不同隊(duì)列所規(guī)定的時(shí)間片長度不同，優(yōu)先權(quán)越高的隊(duì)列分配的時(shí)間片越小。如逐級(jí)加倍。（3）新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列1的末尾，按FCFS算法排隊(duì)調(diào)度；若按隊(duì)列1的一個(gè)時(shí)間片未能執(zhí)行完，則降低投入到隊(duì)列2的末尾。如果在隊(duì)列2的時(shí)間片內(nèi)未能完成，則降低投入到隊(duì)列3……；如此下去，降低到最后的隊(duì)列，則按“時(shí)間片輪轉(zhuǎn)”算法調(diào)度直到完成。（4）僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾。（5）阻塞進(jìn)程被喚醒時(shí)，進(jìn)入原來的就緒隊(duì)列中。2）性能（1）終端型作業(yè)用戶提供高的響應(yīng)時(shí)間。（2）短批處理作業(yè)用戶在第一個(gè)或前2個(gè)時(shí)間片中即可完成，平均周轉(zhuǎn)時(shí)間短。（3）長批處理作業(yè)用戶不會(huì)饑餓。3）優(yōu)點(diǎn)為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程。為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧I/O型進(jìn)程。不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié)。3.4實(shí)時(shí)調(diào)度實(shí)時(shí)系統(tǒng)中存在若干個(gè)實(shí)時(shí)進(jìn)程或?qū)崟r(shí)任務(wù)，反應(yīng)或控制某些外部事件。實(shí)時(shí)系統(tǒng)要響應(yīng)的事件（要處理的實(shí)時(shí)任務(wù)）可以進(jìn)一步劃分為周期性事件和非周期性事件，都聯(lián)系著一個(gè)截止響應(yīng)時(shí)間。3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件提供必要的信息就緒時(shí)間、截止時(shí)間、處理時(shí)間、資源要求、優(yōu)先級(jí)系統(tǒng)處理能力強(qiáng)多采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制設(shè)置快速的硬件中斷機(jī)構(gòu)適當(dāng)?shù)臋C(jī)制使進(jìn)行切換開銷小3.4.2實(shí)時(shí)調(diào)度算法分類1．非搶占式調(diào)度算法（1）非搶占式輪轉(zhuǎn)調(diào)度算法通過對所有周期性任務(wù)的分析預(yù)測（到達(dá)時(shí)間、運(yùn)行時(shí)間、結(jié)束時(shí)間、任務(wù)間的優(yōu)先關(guān)系），事先確定一個(gè)固定的調(diào)度方案。這種方法的特點(diǎn)是有效但不靈活。（2）非搶占式優(yōu)先級(jí)調(diào)度算法2．搶占式調(diào)度算法（1）基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。（2）立即搶占的優(yōu)先權(quán)調(diào)度算法3.4.3常用的實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算法可以分為動(dòng)態(tài)實(shí)時(shí)調(diào)度算法和靜態(tài)實(shí)時(shí)調(diào)度算法兩類。動(dòng)態(tài)實(shí)時(shí)調(diào)度算法在運(yùn)行時(shí)作出調(diào)度決定，靜態(tài)實(shí)時(shí)調(diào)度算法在系統(tǒng)啟動(dòng)之前完成所有的調(diào)度決策。常用的實(shí)時(shí)算法都是基于優(yōu)先權(quán)的算法。1．最早截止時(shí)間優(yōu)先即EDF算法

(EarliestDeadlineFirst)根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間越早，優(yōu)先級(jí)越高。實(shí)時(shí)任務(wù)的就緒隊(duì)列按優(yōu)先級(jí)排序，調(diào)度程序總是選擇隊(duì)首進(jìn)程占有處理機(jī)。EDF算法用于非搶占調(diào)度方式2．最低松弛度優(yōu)先(LLF)算法根據(jù)任務(wù)的緊急（或松馳）程序來確定任務(wù)的優(yōu)先級(jí)。任務(wù)緊急程序高，為該任務(wù)所賦予的優(yōu)先級(jí)愈高。該算法主要用于搶占式調(diào)度方式。松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為25ms。A和B任務(wù)每次必須完成的時(shí)間利用LLF算法進(jìn)行調(diào)度的情況3.5產(chǎn)生死鎖的原因和必要條件死鎖實(shí)例設(shè)系統(tǒng)有一臺(tái)打印機(jī)(R1)一臺(tái)掃描儀(R2)，被并發(fā)的A、B兩進(jìn)程共享。用信號(hào)量S1、S2表示R1、R2是否可用，S1、S2初值為1。A、B并發(fā)時(shí)就可能產(chǎn)生死鎖。死鎖概念死鎖：多個(gè)進(jìn)程因競爭共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。一組并發(fā)進(jìn)程彼此互相等待對方所擁有的資源，且這些并發(fā)進(jìn)程在得到對方的資源之前不會(huì)釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。這一組進(jìn)程就稱為死鎖進(jìn)程。3.5.1產(chǎn)生死鎖的原因產(chǎn)生死鎖的因素不僅與系統(tǒng)擁有的資源數(shù)量有關(guān)，而且與資源分配策略，進(jìn)程對資源的使用要求以及并發(fā)進(jìn)程的速率有關(guān)。1.競爭系統(tǒng)資源2.進(jìn)程的推進(jìn)順序不當(dāng)

1）可剝奪資源和非剝奪資源可剝奪資源：分配給某進(jìn)程后又可以被其他進(jìn)程或系統(tǒng)剝奪的資源。如處理機(jī)、內(nèi)存。非剝奪資源：一旦分配給某進(jìn)程后不能強(qiáng)行收回，只能由進(jìn)程自行釋放的資源。永久性資源：可以被多個(gè)進(jìn)程多次使用的資源（可再用資源）。臨時(shí)性資源：由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用一段時(shí)間后便無用的資源。如消息，中斷信號(hào)，同步信號(hào)等（可消耗性資源）。2）競爭資源引起死鎖（1）競爭非剝奪資源（2）競爭臨時(shí)性資源3．進(jìn)程推進(jìn)順序不當(dāng)P1P2Request(R1);Request(R2);Request(R2);Request(R1);Releast(R1);Releast(R2);Releast(R2);Releast(R1);3.5.2產(chǎn)生死鎖的必要條件1．互斥條件：資源獨(dú)占，排他性使用。2．請求和保持條件：當(dāng)進(jìn)程因請求資源而阻塞時(shí)，不釋放已占有的資源。3．不剝奪條件：進(jìn)程已獲得的資源不能被剝奪，只能在使用完時(shí)由自己釋放。4．環(huán)路等待條件：在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程--資源的環(huán)形循環(huán)鏈，鏈中每一個(gè)進(jìn)程已獲得的資源被下一個(gè)進(jìn)程所請求，同時(shí)它又請求上一進(jìn)程所擁有的資源。3.5.3處理死鎖的基本方法預(yù)防死鎖：設(shè)置限制條件，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件。避免死鎖：在每次的資源動(dòng)態(tài)分配過程中，對系統(tǒng)能夠滿足的資源申請進(jìn)行安全性檢查，根據(jù)結(jié)果決定是否進(jìn)行此次分配。檢測死鎖：允許系統(tǒng)發(fā)生死鎖，但設(shè)置檢測機(jī)構(gòu)，及時(shí)檢測出死鎖的發(fā)生。解除死鎖：外力推動(dòng)解除死鎖。具體方法有：撤消或掛起死鎖進(jìn)程、剝奪資源等。3.6預(yù)防死鎖的方法3.6.1預(yù)防死鎖死鎖的預(yù)防：通過設(shè)置限制條件，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，使系統(tǒng)在任何時(shí)刻都不滿足死鎖的必要條件，從而預(yù)防死鎖的發(fā)生。1．資源一次性分配進(jìn)程必須在運(yùn)行前一次性地申請運(yùn)行期間所需的全部資源，這樣進(jìn)程在整個(gè)運(yùn)行期間不會(huì)再提出資源請求，從而摒棄了請求和保持條件。優(yōu)點(diǎn)：簡單，易于實(shí)現(xiàn)，安全。缺點(diǎn)：（1）資源浪費(fèi)嚴(yán)重。降低進(jìn)程并發(fā)度。（2）進(jìn)程延遲運(yùn)行。（3）不適用資源需要未知的進(jìn)程。2．可剝奪資源允許進(jìn)程逐個(gè)申請資源，當(dāng)進(jìn)程新的資源請求未滿足時(shí)，必須釋放已占有的資源，待以后需要時(shí)再重新申請。此策略表明進(jìn)程已占有的資源可被暫時(shí)釋放，即被剝奪了，從而摒棄“不剝奪”條件。缺點(diǎn)：（1）復(fù)雜，實(shí)現(xiàn)困難且代價(jià)大。（2）延長了進(jìn)程的周轉(zhuǎn)時(shí)間，增加系統(tǒng)開銷。3．資源有序申請系統(tǒng)給每類資源賦予一個(gè)序號(hào)，每一個(gè)進(jìn)程嚴(yán)格按照序號(hào)遞增的順序請求資源，釋放則相反。此方法不可能形成資源占有與請求的環(huán)路，從而破壞環(huán)路等待條件。優(yōu)點(diǎn)：相對而言，系統(tǒng)利用率高，系統(tǒng)吞吐量大。缺點(diǎn)：（1）限制設(shè)備擴(kuò)充。系統(tǒng)事先確定資源序號(hào)，限制了新類型設(shè)備的增加。（2）限制了進(jìn)程對資源的請求，編程困難。（3）資源浪費(fèi)。當(dāng)進(jìn)程使用順序與資源序號(hào)不相符時(shí)，也會(huì)造成資源浪費(fèi)。3.6.3避免死鎖避免死鎖的方法就是讓系統(tǒng)處于安全狀態(tài)中。在避免死鎖的策略中，允許進(jìn)程動(dòng)態(tài)地申請資源。死鎖避免：系統(tǒng)對進(jìn)程運(yùn)行過程中發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請進(jìn)行安全檢查，根據(jù)檢查結(jié)果決定是否分配資源。若此次分配會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則不予分配；否則予以分配。1．安全狀態(tài)安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序來為每個(gè)進(jìn)程分配其所需資源，直至每個(gè)進(jìn)程的最大需求，使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在這樣一個(gè)序列，則稱系統(tǒng)處于不安全狀態(tài)，不安全狀態(tài)一般會(huì)導(dǎo)致死鎖。2．安全狀態(tài)實(shí)例P953．由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換

如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。3.6.3銀行家算法避免死鎖單種資源的銀行家算法描述：假定一個(gè)銀行家擁有資金，數(shù)量為∑，被N個(gè)客戶共享。銀行家對客戶提出下列約束條件：每個(gè)客戶必須預(yù)先說明自己所要求的最大資金量每個(gè)客戶每次提出部分資金量申請和獲得分配如果銀行滿足了客戶對資金的最大需求量，那么，客戶在資金運(yùn)作后，應(yīng)在有限時(shí)間內(nèi)全部歸還銀行。銀行則保證：若一個(gè)客戶所要求的最大資金量不超過∑，則銀行一定接納該客戶，并處理他的資金需求；銀行在收到一個(gè)客戶的資金申請時(shí)，可能因資金不足而讓客戶等待，但保證在有限時(shí)間內(nèi)讓客戶獲得資金。三種資源分配狀態(tài)：(a)安全(b)安全(c)不安全

銀行家算法就是對每一個(gè)請求進(jìn)行檢查，檢查這次資源申請是否會(huì)導(dǎo)致不安全狀態(tài)。若是，則不滿足該請求；否則便滿足。1．銀行家算法中的數(shù)據(jù)結(jié)構(gòu)（1）可利用資源向量Available[m]。每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。（2）最大需求矩陣Max[n][m]。定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求。如果Max[i][j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。1．銀行家算法中的數(shù)據(jù)結(jié)構(gòu)（3）分配矩陣Allocation[n][m]定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i][j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。（4）需求矩陣Need[n][m]用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i][j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成任務(wù)。Need[i][j]=Max[i][j]-Allocation[i][j]

2．銀行家算法設(shè)Requesti是進(jìn)程Pi的資源請求向量，如果Requesti[j]=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟檢查：（1）如果Requesti[j]≤Need[i][j]，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。（2）如果Requesti[j]≤Available[j]，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。（3）系統(tǒng)試著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available[j]=Available[j]-Requesti[j];Allocation[i][j]=Allocation[i][j]+Requesti[j];Need[i][j]=Need[i][j]-Requesti[j];（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)