1、計(jì)算機(jī)操作系統(tǒng),東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,主講：李繼云jyli,2,第3章處理機(jī)調(diào)度與死鎖,3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除,3.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度3.1.2調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則,3.1處理機(jī)調(diào)度的基本概念,4,3.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度,1.高級(jí)調(diào)度(HighScheduling),又稱作業(yè)調(diào)度、長(zhǎng)程調(diào)度：決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為之創(chuàng)建進(jìn)程、分配必要的資源，然后，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列中。,5

2、,1.高級(jí)調(diào)度(HighScheduling),批處理系統(tǒng)：需作業(yè)調(diào)度分時(shí)系統(tǒng)：無需作業(yè)調(diào)度實(shí)時(shí)系統(tǒng)：通常無需作業(yè)調(diào)度,6,在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定：1)接納多少個(gè)作業(yè)2)接納哪些作業(yè),1.高級(jí)調(diào)度(HighScheduling),7,2.低級(jí)調(diào)度(LowLevelScheduling),進(jìn)程調(diào)度、短程調(diào)度：決定就緒隊(duì)列中哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。三種類型的OS均需配置進(jìn)程調(diào)度,8,進(jìn)程調(diào)度方式：1)非搶占方式(Non-preemptiveMode)進(jìn)程一旦獲得CPU則一直執(zhí)行，直至完成或被阻塞。,采用非搶占方式，引起進(jìn)程調(diào)度的

3、因素：正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。,2.低級(jí)調(diào)度(LowLevelScheduling),9,2)搶占方式(PreemptiveMode)正在執(zhí)行的進(jìn)程可以被中途剝奪CPU使用權(quán),進(jìn)程調(diào)度方式,搶占的原則有：,優(yōu)先權(quán)原則。(2)短作業(yè)(進(jìn)程)優(yōu)先原則(3)時(shí)間片原則。,10,3.中級(jí)調(diào)度(Intermediate-LevelScheduling),中級(jí)調(diào)度又稱中程調(diào)度(Medium-TermScheduling)。引入的主要

4、目的：是為了提高內(nèi)存利用率和系統(tǒng)吞吐量（存儲(chǔ)器管理的對(duì)換）中程調(diào)度：將那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。,3.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度3.1.2調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則,3.1處理機(jī)調(diào)度的基本概念,13,1.僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型,3.1.2調(diào)度隊(duì)列模型,14,2.具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型,15,(1

5、)就緒隊(duì)列的形式：優(yōu)先權(quán)隊(duì)列、無序鏈表等(2)設(shè)置多個(gè)阻塞隊(duì)列：每個(gè)隊(duì)列對(duì)應(yīng)于某一種進(jìn)程阻塞事件,該模型與上一模型的主要區(qū)別在于如下兩個(gè)方面：,2.具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型,16,3.同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型,3.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度3.1.2調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則,3.1處理機(jī)調(diào)度的基本概念,3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則,周轉(zhuǎn)時(shí)間的長(zhǎng)短是評(píng)價(jià)批處理系統(tǒng)性能、選擇作業(yè)調(diào)度方式與算法的重要準(zhǔn)則之一,1.面向用戶的準(zhǔn)則,(1)周轉(zhuǎn)時(shí)間短。,19,周轉(zhuǎn)時(shí)間：從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為之的這段時(shí)間間隔（作業(yè)周轉(zhuǎn)時(shí)間）作業(yè)在外存后

6、備隊(duì)列上等待（作業(yè)）調(diào)度的時(shí)間進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間進(jìn)程在CPU上執(zhí)行的時(shí)間進(jìn)程等待I/O操作完成的時(shí)間,(1)周轉(zhuǎn)時(shí)間短。,20,帶權(quán)周轉(zhuǎn)時(shí)間：W=T/TSTs為系統(tǒng)為作業(yè)或進(jìn)程服務(wù)的時(shí)間；T為周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間:,平均周轉(zhuǎn)時(shí)間：,(1)周轉(zhuǎn)時(shí)間短。,21,(2)響應(yīng)時(shí)間快,響應(yīng)時(shí)間的長(zhǎng)短是評(píng)價(jià)分時(shí)系統(tǒng)性能、選擇分時(shí)系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則之一,響應(yīng)時(shí)間：用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者說直至屏幕上顯示出結(jié)果為止的一段時(shí)間間隔鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間形成的響應(yīng)信息回送到終端顯示器的時(shí)間,22,(

7、3)截止時(shí)間的保證,截止時(shí)間是評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)，是選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)則,截止時(shí)間：某任務(wù)必須開始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間,23,(4)優(yōu)先權(quán)準(zhǔn)則,三種系統(tǒng)均可應(yīng)用本準(zhǔn)則,24,2.面向系統(tǒng)的準(zhǔn)則,(1)系統(tǒng)吞吐量高評(píng)價(jià)批處理系統(tǒng)吞吐量：?jiǎn)挝粫r(shí)間內(nèi)所完成的作業(yè)數(shù)(2)處理機(jī)利用率好大中型系統(tǒng)中要考慮(3)各類資源的平衡利用大中型系統(tǒng)中要考慮,25,第3章處理機(jī)調(diào)度與死鎖,3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除,26,3.2調(diào)度算法,調(diào)度算法：根據(jù)系統(tǒng)的資源分

8、配策略所規(guī)定的資源分配算法,3.2.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法,3.2調(diào)度算法,28,3.2.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法,1.先來先服務(wù)（FCFS）調(diào)度算法,特點(diǎn)：可用于作業(yè)調(diào)度、也可用于進(jìn)程調(diào)度利于長(zhǎng)作業(yè)（進(jìn)程）、不利于短作業(yè)（進(jìn)程）利于CPU繁忙型作業(yè)，不利于I/O繁忙型的作業(yè)(進(jìn)程),FCFS實(shí)例,1.先來先服務(wù)調(diào)度算法,平均周轉(zhuǎn)時(shí)間：,30,2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法,短作業(yè)優(yōu)先(SJF)調(diào)度算法：從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先(SPF)調(diào)

9、度算法：從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。,平均周轉(zhuǎn)時(shí)間：,帶權(quán)周轉(zhuǎn)時(shí)間：W=T/TS,平均帶權(quán)周轉(zhuǎn)時(shí)間:,32,優(yōu)點(diǎn)：有效的降低作業(yè)的平均等待時(shí)間，提高了系統(tǒng)的吞吐量。缺點(diǎn)：對(duì)長(zhǎng)作業(yè)不利完全未考慮作業(yè)的緊迫程度作業(yè)的運(yùn)行時(shí)間不能準(zhǔn)確獲得,2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法,3.2.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法,3.2調(diào)度算法,34,3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法,1.優(yōu)先權(quán)調(diào)度算法的類型,1)非搶占式優(yōu)先權(quán)算法,主要用于

10、批處理系統(tǒng)中；也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。,35,這種搶占式的優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。,1.優(yōu)先權(quán)調(diào)度算法的類型,2)搶占式優(yōu)先權(quán)調(diào)度算法,36,2.優(yōu)先權(quán)的類型,靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。,1)靜態(tài)優(yōu)先權(quán),37,確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：(1)進(jìn)程類型。(2)進(jìn)程對(duì)資源的需求。(3)用戶要求。,1)靜態(tài)優(yōu)先權(quán),38,動(dòng)態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。,2)

11、動(dòng)態(tài)優(yōu)先權(quán),39,3.高響應(yīng)比優(yōu)先調(diào)度算法,優(yōu)先權(quán)的變化規(guī)律可描述為：,由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：,40,(1)等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高有利于短作業(yè)(2)當(dāng)要求服務(wù)的時(shí)間相同時(shí)，則等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高先來先服務(wù)(3)長(zhǎng)作業(yè)只要等待時(shí)間足夠長(zhǎng)，其優(yōu)先級(jí)便可升到很高，從而也可獲得處理機(jī)(4)響應(yīng)比的計(jì)算增加了系統(tǒng)開銷,3.高響應(yīng)比優(yōu)先調(diào)度算法,例：,單道批處理系統(tǒng)中，一組作業(yè)的提交時(shí)刻和運(yùn)行時(shí)間如表所示。采用高響應(yīng)比優(yōu)先調(diào)度算法,作業(yè)1到達(dá)時(shí)，沒有其它作業(yè)到達(dá)，故作業(yè)1執(zhí)行,作業(yè)1執(zhí)行完成時(shí)

12、刻為9.0，作業(yè)2、3均已到達(dá)，此時(shí)作業(yè)2、3的響應(yīng)比分別是：作業(yè)2=1+0.5/0.5=2；作業(yè)3=1+0/0.2=1；即選擇2運(yùn)行,作業(yè)2執(zhí)行完成時(shí)刻為9.5，作業(yè)3、4均已到達(dá)，其響應(yīng)比分別是：作業(yè)3=1+0.5/0.2=3.5作業(yè)4=1+0.4/0.1=5，即選擇作業(yè)4運(yùn)行。,最后只剩下作業(yè)3，執(zhí)行,3.2.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法,3.2調(diào)度算法,43,3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法,時(shí)間片太大，每個(gè)進(jìn)程均可在時(shí)間片內(nèi)執(zhí)行完畢退化為FCFS,1.時(shí)間片輪轉(zhuǎn)法,確定時(shí)間片大小的考慮因素：1、系統(tǒng)對(duì)響應(yīng)時(shí)

13、間的要求2、就緒隊(duì)列中進(jìn)程的數(shù)目3、系統(tǒng)的處理能力,44,2.多級(jí)反饋隊(duì)列調(diào)度算法,(1)應(yīng)設(shè)置多個(gè)就緒隊(duì)列,優(yōu)先級(jí),45,(2)當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按時(shí)間片輪轉(zhuǎn)法等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按時(shí)間片輪轉(zhuǎn)法等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，如此下去，當(dāng)一個(gè)長(zhǎng)作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。,2.多級(jí)反饋隊(duì)列調(diào)度算法,46,(3)僅當(dāng)?shù)谝魂?duì)列空

14、閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?(i-1)隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1(i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。,2.多級(jí)反饋隊(duì)列調(diào)度算法,47,3.多級(jí)反饋隊(duì)列調(diào)度算法的性能,(1)終端型作業(yè)用戶。(2)短批處理作業(yè)用戶。(3)長(zhǎng)批處理作業(yè)用戶。,48,第3章處理機(jī)調(diào)度與死鎖,3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因

15、和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除,49,3.3實(shí)時(shí)調(diào)度,實(shí)時(shí)系統(tǒng),能及時(shí)響應(yīng)外部事件的請(qǐng)求，在規(guī)定的時(shí)間內(nèi)完成對(duì)該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行的計(jì)算機(jī)系統(tǒng)分為實(shí)時(shí)控制系統(tǒng)和實(shí)時(shí)信息處理系統(tǒng)兩類,實(shí)時(shí)任務(wù),周期性實(shí)時(shí)任務(wù)、非周期實(shí)時(shí)任務(wù)硬實(shí)時(shí)任務(wù)、軟實(shí)時(shí)任務(wù),3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3.3.2實(shí)時(shí)調(diào)度算法的分類3.3.3常用的幾種實(shí)時(shí)調(diào)度算法,3.3實(shí)時(shí)調(diào)度,51,3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,1.提供必要的信息,(1)就緒時(shí)間。(2)開始截止時(shí)間和完成截止時(shí)間。(3)處理時(shí)間。(4)資源要求。(5)優(yōu)先級(jí)。,52,2.系統(tǒng)處理能力強(qiáng),假定系統(tǒng)中有

16、m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間為Ci，周期時(shí)間為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：,3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,53,提高系統(tǒng)處理能力的途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：,3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,54,3.采用搶占式調(diào)度機(jī)制,搶占機(jī)制非搶占機(jī)制,3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,55,4.具有快速切換機(jī)制,該機(jī)制應(yīng)具有如下兩方面的能力：(1)對(duì)外部中斷的快速響應(yīng)能力(2)快速的任務(wù)分派能力,3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,

17、3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3.3.2實(shí)時(shí)調(diào)度算法的分類3.3.3常用的幾種實(shí)時(shí)調(diào)度算法,3.3實(shí)時(shí)調(diào)度,57,3.3.2實(shí)時(shí)調(diào)度算法的分類,1.非搶占式調(diào)度算法,(1)非搶占式輪轉(zhuǎn)調(diào)度算法,58,1.非搶占式調(diào)度算法,(2)非搶占式優(yōu)先調(diào)度算法。,3.3.2實(shí)時(shí)調(diào)度算法的分類,59,2.搶占式調(diào)度算法,(1)基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法,3.3.2實(shí)時(shí)調(diào)度算法的分類,60,(2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法,2.搶占式調(diào)度算法,3.3.2實(shí)時(shí)調(diào)度算法的分類,3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3.3.2實(shí)時(shí)調(diào)度算法的分類3.3.3常用的幾種實(shí)時(shí)調(diào)度

18、算法,3.3實(shí)時(shí)調(diào)度,62,3.3.3常用的幾種實(shí)時(shí)調(diào)度算法,1.最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算法,根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí),既可用于搶占式調(diào)度、也可用于非搶占式調(diào)度,63,1.最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算法,64,1.最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算法,采用搶占式最早開始截至?xí)r間優(yōu)先調(diào)度算法,0,10,20,30,40,90,70,50,60,80,100,110,120,A,B,C,E,D,A,65,2.最低松弛度優(yōu)先即LLF(LeastLaxity

19、First)算法,該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。該算法主要用于可搶占調(diào)度方式中,2.最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法,周期性實(shí)時(shí)任務(wù)A、B，A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間10ms；B要求每50ms執(zhí)行一次，執(zhí)行時(shí)間25ms,在剛開始時(shí)(t1=0)，A1必須在20ms時(shí)完成，而它本身運(yùn)行又需10ms，可算出A1的松弛度為10ms；B1必須在50ms時(shí)完成，而它本身運(yùn)行就需25ms，可算出B1的松弛度為25ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。,在t2=10ms時(shí)，A2的松弛

20、度可按下式算出：A2的松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間=40ms-10ms-10ms=20ms類似地，可算出B1的松弛度為15ms故調(diào)度程序應(yīng)選擇B1運(yùn)行。,在t3=30ms時(shí)，A2的松弛度為（40-10-30)=0ms，而B1的松弛度為15ms。故搶占B1處理機(jī)而調(diào)度A2運(yùn)行,依次計(jì)算下去,67,第3章處理機(jī)調(diào)度與死鎖,3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除,3.4.1多處理器系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式,3.4多處理機(jī)系統(tǒng)中的調(diào)

21、度,69,3.4.1多處理器系統(tǒng)的類型,(1)緊密耦合(TightlyCoupled)MPS：共享主存儲(chǔ)器系統(tǒng)和I/O設(shè)備(2)松散耦合(LooselyCoupled)MPS：擁有獨(dú)立的存儲(chǔ)器和I/O設(shè)備,70,(1)對(duì)稱多處理器系統(tǒng)SMPS(SymmetricMultiProcessorSystem)(2)非對(duì)稱多處理器系統(tǒng),3.4.1多處理器系統(tǒng)的類型,3.4.1多處理器系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式,3.4多處理機(jī)系統(tǒng)中的調(diào)度,72,3.4.2進(jìn)程分配方式,1.對(duì)稱多處理器系統(tǒng)中的進(jìn)程分配方式在SMP系統(tǒng)中，所有的處理器都是相同的，因而可把所有的處理器作為

22、一個(gè)處理器池(Processorpool)，由調(diào)度程序或基于處理器的請(qǐng)求，將任何一個(gè)進(jìn)程分配給池中的任何一個(gè)處理器去處理。在進(jìn)行進(jìn)程分配時(shí)，可采用以下兩種方式之一。1)靜態(tài)分配(StaticAssignment)方式：忙閑不均2)動(dòng)態(tài)分配(DynamicAssignment)方式,73,2.非對(duì)稱MPS中的進(jìn)程分配方式對(duì)于非對(duì)稱MPS，其OS大多采用主從(Master-Slave)式OS，即OS的核心部分駐留在一臺(tái)主機(jī)上(Master)，而從機(jī)(Slave)上只是用戶程序，進(jìn)程調(diào)度只由主機(jī)執(zhí)行。每當(dāng)從機(jī)空閑時(shí)，便向主機(jī)發(fā)送一索求進(jìn)程的信號(hào)，然后，便等待主機(jī)為它分配進(jìn)程。在主機(jī)中保持有一個(gè)就緒隊(duì)

23、列，只要就緒隊(duì)列不空，主機(jī)便從其隊(duì)首摘下一進(jìn)程分配給請(qǐng)求的從機(jī)。從機(jī)接收到分配的進(jìn)程后便運(yùn)行該進(jìn)程，該進(jìn)程結(jié)束后從機(jī)又向主機(jī)發(fā)出請(qǐng)求。,3.4.2進(jìn)程分配方式,3.4.1多處理器系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式,3.4多處理機(jī)系統(tǒng)中的調(diào)度,75,3.4.3進(jìn)程(線程)調(diào)度方式,1.自調(diào)度(Self-Scheduling)方式1)自調(diào)度機(jī)制直接由單處理機(jī)環(huán)境下的調(diào)度方式演變而來的維護(hù)一個(gè)公共的進(jìn)程或線程就緒隊(duì)列可采用在單處理機(jī)環(huán)境下所用的調(diào)度算法，如先來先服務(wù)(FCFS)調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等。,76,2)自調(diào)度方

24、式的優(yōu)點(diǎn)1、很容易將單處理機(jī)環(huán)境下的調(diào)度機(jī)制移植到多處理機(jī)系統(tǒng)中2、不會(huì)出現(xiàn)處理機(jī)空閑的情況，也不會(huì)發(fā)生處理器忙閑不均的現(xiàn)象有利于提高處理器的利用率。,1.自調(diào)度(Self-Scheduling)方式,77,3)自調(diào)度方式的缺點(diǎn),(1)瓶頸問題：共享就緒隊(duì)列(2)低效性：高速緩存使用效率低(3)線程切換頻繁：合作型線程相互等待,1.自調(diào)度(Self-Scheduling)方式,78,2.成組調(diào)度(GangScheduling)方式,為解決自調(diào)度方式中線程被頻繁切換的問題提出的,79,2.成組調(diào)度(GangScheduling)方式,在成組調(diào)度時(shí)，為應(yīng)用程序分配處理器時(shí)間的方式：1)面向所有應(yīng)用

25、程序平均分配處理器時(shí)間2)面向所有線程平均分配處理器時(shí)間,80,2.成組調(diào)度(GangScheduling)方式,優(yōu)點(diǎn)：相互合作型進(jìn)程或線程，能并行執(zhí)行，有效減少線程（進(jìn)程）阻塞的發(fā)生，從而減少線程切換，改善系統(tǒng)性能依次調(diào)度一組線程，顯著減少調(diào)度頻率，減小了調(diào)度開銷,81,3.專用處理器分配(DedicatedProcessorAssigement)方式,在一個(gè)應(yīng)用程序的執(zhí)行期間，專門為該程序分配一組處理器，每一個(gè)線程一個(gè)處理器。這組處理器僅供該應(yīng)用程序?qū)Ｓ?，直至該?yīng)用程序完成在同時(shí)加工的應(yīng)用程序中，其線程數(shù)的總和，不應(yīng)超過系統(tǒng)中處理機(jī)的數(shù)目,82,小結(jié),分級(jí)調(diào)度調(diào)度算法實(shí)時(shí)調(diào)度多處理機(jī)調(diào)度,

26、83,第3章處理機(jī)調(diào)度與死鎖,3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除,3.5產(chǎn)生死鎖的原因和必要條件,死鎖：多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局。,3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法,3.5產(chǎn)生死鎖的原因和必要條件,3.5.1產(chǎn)生死鎖的原因,1.競(jìng)爭(zhēng)資源引起進(jìn)程死鎖,(1)可剝奪和非剝奪性資源(2)競(jìng)爭(zhēng)非剝奪性資源(3)競(jìng)爭(zhēng)臨時(shí)性資源,競(jìng)爭(zhēng)非剝奪性資源,1.競(jìng)爭(zhēng)資源引起進(jìn)程死鎖,1.競(jìng)爭(zhēng)資源引起進(jìn)程死鎖,競(jìng)爭(zhēng)臨時(shí)性資源,2.進(jìn)

27、程推進(jìn)順序不當(dāng)引起死鎖,1)進(jìn)程推進(jìn)順序合法,2)進(jìn)程推進(jìn)順序非法,3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法,3.5產(chǎn)生死鎖的原因和必要條件,3.5.2產(chǎn)生死鎖的必要條件,(1)互斥條件(2)請(qǐng)求和保持條件(3)不剝奪條件(4)環(huán)路等待條件,3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法,3.5產(chǎn)生死鎖的原因和必要條件,3.5.3處理死鎖的基本方法,(1)預(yù)防死鎖(2)避免死鎖(3)檢測(cè)死鎖與解除死鎖,95,第3章處理機(jī)調(diào)度與死鎖,3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生

28、死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除,3.6.1預(yù)防死鎖3.6.2死鎖避免3.6.3利用銀行家算法避免死鎖,3.6預(yù)防死鎖的方法,3.6.1預(yù)防死鎖,(1)摒棄“請(qǐng)求和保持”條件資源分配方案：要么分配進(jìn)程所需的所有資源，要么不分配資源,優(yōu)點(diǎn)：簡(jiǎn)單、易于實(shí)現(xiàn)、安全缺點(diǎn)：資源嚴(yán)重浪費(fèi)、進(jìn)程延遲執(zhí)行,(2)摒棄“不剝奪”條件,資源分配方案：需要時(shí)才請(qǐng)求資源，一旦不能獲得需要的資源，則釋放所有已保持的資源,缺點(diǎn)：實(shí)現(xiàn)復(fù)雜、代價(jià)大延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間增加了系統(tǒng)開銷，降低了系統(tǒng)吞吐量,3.6.1預(yù)防死鎖,3.摒棄“環(huán)路等待”條件,將所有資源按類型進(jìn)行線性排隊(duì)，并賦予不同序號(hào)。所有

29、進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按照資源序號(hào)遞增的次序提出。,缺點(diǎn)：各類資源所分配的序號(hào)需相對(duì)穩(wěn)定，從而限制了新類型設(shè)備的增加進(jìn)程使用資源的順序可能與系統(tǒng)規(guī)定的順序不同限制了用戶簡(jiǎn)單、自主的編程,3.6.1預(yù)防死鎖,3.6.1預(yù)防死鎖3.6.2死鎖避免3.6.3利用銀行家算法避免死鎖,3.6預(yù)防死鎖的方法,3.6.2死鎖避免,1.安全狀態(tài)所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,，Pn)(稱P1,P2,Pn序列為安全序列)，來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。避免死鎖的實(shí)質(zhì)：在進(jìn)

30、行資源分配時(shí)，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。,系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示：,2.安全狀態(tài)之例,如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。,3.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換,3.6.1預(yù)防死鎖3.6.2死鎖避免3.6.3利用銀行家算法避免死鎖,3.6預(yù)防死鎖的方法,主要思想：,銀行家算法是從當(dāng)前的狀態(tài)S出發(fā)，逐個(gè)檢查各申請(qǐng)者中誰獲得資源能完成其工作，然后假定其完成工作且歸還全部資源，再進(jìn)一步

31、檢查誰又獲得資源能完成其工作。若所有申請(qǐng)者均能完成工作，則系統(tǒng)狀態(tài)是安全的。,3.6.3利用銀行家算法避免死鎖,1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu),(1)可利用資源向量Available這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。,3.6.3利用銀行家算法避免死鎖,(2)最大需求矩陣Max這是一個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K

32、。,1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu),(3)分配矩陣Allocation這也是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K,1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu),(4)需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。,Needi,j=Maxi,j-Allocationi,j,1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu),設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requestij=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)

33、Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1)如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。(2)如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。,2.銀行家算法,(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;,2.銀行家算法,(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配

34、后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。,2.銀行家算法,3.安全性算法,(1)設(shè)置兩個(gè)向量：工作向量Work:它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work=Available;Finish:它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi=true。,(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：Finishi=false;Needi,jWorkj；

35、若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4),3.安全性算法,(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Workj=Worki+Allocationi,j;Finishi=true;gotostep2;,(4)如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。,3.安全性算法,例在銀行家算法中，若出現(xiàn)下面的資源分配情況,1）該狀態(tài)是否安全？2）若進(jìn)程P2提出請(qǐng)求Request(1,2,2,2)后，系統(tǒng)能否將資源分配給它,解：,系統(tǒng)是安全的,若進(jìn)程P2提出請(qǐng)求Request(1,2,2,2),Request2

36、(1,2,2,2)Need2(2,3,5,6)Request2(1,2,2,2)Available(1,6,2,2)假定系統(tǒng)將資源分配給它，則,系統(tǒng)進(jìn)入不安全狀態(tài)，故不能分配資源,119,第3章處理機(jī)調(diào)度與死鎖,3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除,3.7.1死鎖的檢測(cè)3.7.2死鎖的解除,3.7死鎖的檢測(cè)與解除,3.7.1死鎖的檢測(cè),1.資源分配圖(ResourceAllocationGraph),凡屬于E中的一個(gè)邊eE，都連接著P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn)，e=pi,rj是

37、資源請(qǐng)求邊，由進(jìn)程pi指向資源rj，它表示進(jìn)程pi請(qǐng)求一個(gè)單位的rj資源。e=rj,pi是資源分配邊，由資源rj指向進(jìn)程pi,它表示把一個(gè)單位的資源rj分配給進(jìn)程pi。,現(xiàn)假定有3類資源R1，R2，R3，其中R1和R3都只有1個(gè)資源，R2有2個(gè)資源。有3個(gè)進(jìn)程P1，P2，P3，每個(gè)進(jìn)程占用資源和等待資源的情況如下表所示。,例,如果P3進(jìn)程再提出申請(qǐng)一個(gè)R2資源,則存在兩條環(huán)路：P1R1P2R3P3R2PlP2R3P3R2P2死鎖產(chǎn)生,下圖所示的例子中存在一個(gè)環(huán)路，但不形成死鎖,P1R1P3R2P1,（1）如果資源分配圖中無環(huán)路，則系統(tǒng)中沒有死鎖發(fā)生。,（2）如果資源分配圖中有環(huán)路，且環(huán)中每個(gè)進(jìn)程處于永久等待，則死鎖形成，環(huán)路中的進(jìn)程就處于死鎖狀態(tài)。,（3）如果資源分配圖中有環(huán)路，但涉及到的資源類中有多個(gè)資源，則環(huán)路的存在未必就有死鎖形成。,從上面的討論中可以得到如下結(jié)論：,2.死鎖定理,（1）在資源分配圖中，找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)pi。在順利情況下，pi可獲得所需資源