第3章處理機(jī)調(diào)度和死鎖

2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院1第3章處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4產(chǎn)生死鎖的原因和必要條件3.5預(yù)防死鎖的方法3.6死鎖的檢測(cè)與解除2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院23.1處理機(jī)調(diào)度的基本概念3.1.1高級(jí)調(diào)度、中級(jí)調(diào)度、低級(jí)調(diào)度3.1.2調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院32023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院43.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度經(jīng)歷下述三級(jí)調(diào)度:高級(jí)調(diào)度（HighScheduling）中級(jí)調(diào)度（Intermediate-LevelScheduling）低級(jí)調(diào)度（LowLevelScheduling）2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院51.高級(jí)調(diào)度

又稱為作業(yè)調(diào)度、宏觀調(diào)度或長程調(diào)度。用于決定把后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，為他們分配必要的資源，并創(chuàng)建進(jìn)程。批處理系統(tǒng)：分時(shí)系統(tǒng)：實(shí)時(shí)系統(tǒng)：需要作業(yè)調(diào)度不需作業(yè)調(diào)度不需作業(yè)調(diào)度2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院61.高級(jí)調(diào)度執(zhí)行作業(yè)調(diào)度時(shí)，必須作出兩個(gè)決定：接納多少作業(yè)——每次接納多少作業(yè)進(jìn)入內(nèi)存，取決于多道程序度，即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。接納哪些作業(yè)——應(yīng)接納哪些作業(yè)從外存調(diào)入內(nèi)存，取決于所采用的調(diào)度算法。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院72.低級(jí)調(diào)度

通常也稱為進(jìn)程調(diào)度、微觀調(diào)度或短程調(diào)度。進(jìn)程調(diào)度是最基本的一種調(diào)度，在三種OS中都有。用于決定就緒隊(duì)列中哪個(gè)進(jìn)程應(yīng)先獲得處理機(jī)，并將處理機(jī)分配給選中的進(jìn)程。為實(shí)現(xiàn)進(jìn)程調(diào)度，應(yīng)具有如下三個(gè)基本機(jī)制：排隊(duì)器分派器上下文切換2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院82.低級(jí)調(diào)度進(jìn)程調(diào)度可采用下述兩種調(diào)度方式：非搶占方式搶占方式搶占的原則有：（1）優(yōu)先權(quán)原則（2）短作業(yè)（進(jìn)程）優(yōu)先原則（3）時(shí)間片原則2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院93.中級(jí)調(diào)度

中級(jí)調(diào)度又稱為交換調(diào)度、中程調(diào)度或內(nèi)存調(diào)度。它按一定的算法將外存中已具備運(yùn)行條件的進(jìn)程換入內(nèi)存，而將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換出至外存。運(yùn)行就緒阻塞掛起阻塞掛起就緒創(chuàng)建退出進(jìn)程調(diào)度中級(jí)調(diào)度作業(yè)調(diào)度調(diào)度的層次2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院113.1.2調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院121.僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

在分時(shí)系統(tǒng)中就緒進(jìn)程組織成FIFO隊(duì)列形式，按時(shí)間片輪轉(zhuǎn)方式運(yùn)行。CPU就緒隊(duì)列阻塞隊(duì)列時(shí)間片完進(jìn)程調(diào)度等待事件進(jìn)程完成交互用戶事件出現(xiàn)2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院132.具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型CPU就緒隊(duì)列時(shí)間片完進(jìn)程調(diào)度等待事件1進(jìn)程完成后備隊(duì)列等待事件2等待事件n事件1出現(xiàn)事件2出現(xiàn)事件n出現(xiàn)作業(yè)調(diào)度2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院143.同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型CPU就緒隊(duì)列時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成后備隊(duì)列等待事件事件出現(xiàn)作業(yè)調(diào)度批量作業(yè)交互型作業(yè)中級(jí)調(diào)度就緒、掛起隊(duì)列事件出現(xiàn)阻塞、掛起隊(duì)列掛起阻塞隊(duì)列掛起中級(jí)調(diào)度2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院153.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短平均周轉(zhuǎn)時(shí)間T平均帶權(quán)周轉(zhuǎn)時(shí)間（W=T(周轉(zhuǎn))/Ts(CPU執(zhí)行))響應(yīng)時(shí)間快截止時(shí)間的保證優(yōu)先權(quán)準(zhǔn)則面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高處理機(jī)利用率好各類資源的平衡利用練習(xí)1設(shè)有4個(gè)作業(yè)同時(shí)到達(dá)，每個(gè)作業(yè)執(zhí)行時(shí)間均為2h，它們?cè)谝慌_(tái)處理器上按單道方式運(yùn)行，則平均周轉(zhuǎn)時(shí)間為（）A.1hB.5hC.2.5hD.8hB2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院173.2調(diào)度算法3.2.1FCFS與SJF/SPF調(diào)度算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院183.2.1FCFS與SJF/SPF調(diào)度算法1.先來先服務(wù)調(diào)度算法(FCFS)

按進(jìn)程申請(qǐng)CPU（就緒）的次序processRuntimeP127P23P35P1P2P302730352023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院19

FCFS實(shí)例下表列出了A、B、C、D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開始執(zhí)行的時(shí)間及各自的完成時(shí)間，計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。FCFS（FirstComeFirstServe)2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院20作業(yè)名到達(dá)時(shí)間服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A01B1100C21D3100FCFS（FirstComeFirstServe)0111110110011011021001001022021991.992023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院21FCFS的特點(diǎn):

FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)（進(jìn)程）比較有利于長作業(yè)，而不利于短作業(yè)FCFS（FirstComeFirstServe)2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院222.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間完成時(shí)間SJF帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間完成時(shí)間FCFS42534服務(wù)時(shí)間43210到達(dá)時(shí)間平均EDCBA作業(yè)名

作業(yè)情況調(diào)度算法4417621210214115.518143.592.8441982.6718163.2631.51392.2582.12023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院232.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJF調(diào)度算法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：有效降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量缺點(diǎn)：(1)對(duì)長作業(yè)不利(2)不能保證緊迫性作業(yè)（進(jìn)程）的及時(shí)處理(3)不一定能真正做到短作業(yè)優(yōu)先2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院243.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.優(yōu)先權(quán)調(diào)度算法的類型為照顧緊迫性作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先（HPF）調(diào)度算法。它分為兩種：非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)調(diào)度算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院253.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法2.優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)：在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變,又稱優(yōu)先數(shù)。動(dòng)態(tài)優(yōu)先權(quán)：在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院263.高響應(yīng)比優(yōu)先調(diào)度算法(HRRN)

為每個(gè)作業(yè)引入動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率a提高，則可解決問題。見下式：

優(yōu)先權(quán)=(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間＝響應(yīng)時(shí)間/要求服務(wù)時(shí)間3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法練習(xí)2一個(gè)作業(yè)8：00到達(dá)系統(tǒng)，估計(jì)運(yùn)行時(shí)間為1h。若10:00開始執(zhí)行該作業(yè)，其響應(yīng)比是（）A.2B.1C.3D.0.5C例題1設(shè)有4個(gè)作業(yè)J1、J2、J3、J4，它們的到達(dá)時(shí)間和計(jì)算時(shí)間如表所示。若這4個(gè)作業(yè)在一臺(tái)處理器上按單道方式運(yùn)行，采用高響應(yīng)比優(yōu)先調(diào)度算法，試寫出各作業(yè)的執(zhí)行順序、各作業(yè)的周轉(zhuǎn)時(shí)間及平均周轉(zhuǎn)時(shí)間作業(yè)到達(dá)時(shí)間計(jì)算時(shí)間J18：00120minJ28：3040minJ39：0025minJ49：3030min解析：優(yōu)先權(quán)（響應(yīng)比）=(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間＝響應(yīng)時(shí)間/要求服務(wù)時(shí)間作業(yè)提交時(shí)間開始時(shí)間執(zhí)行時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間J18：008：00120min10：00120minJ28：3010：2540min11：05155minJ39：0010：0025min10：2585minJ49：3011：0530min11：35125min例題2在一個(gè)批處理系統(tǒng)中，有兩個(gè)作業(yè)進(jìn)程。有一個(gè)作業(yè)序列，其到達(dá)時(shí)間及估計(jì)運(yùn)行時(shí)間如表所示。系統(tǒng)作業(yè)采用最高響應(yīng)比優(yōu)先調(diào)度算法，進(jìn)程的調(diào)度采用短進(jìn)程優(yōu)先的搶占式調(diào)度算法作業(yè)到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間J110：0035minJ210：1030minJ310：1545minJ410：2020minJ510：3030min例題2（1）列出各作業(yè)的執(zhí)行時(shí)間（即列出每個(gè)作業(yè)運(yùn)行的時(shí)間片段，如作業(yè)i的運(yùn)行時(shí)間序列為10：00-10：40）（2）計(jì)算這批作業(yè)的平均周轉(zhuǎn)時(shí)間。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院32J110:00J4:20m10:10J2到達(dá)J210:35J1完成J4進(jìn)內(nèi)存分析：J3J4J510:55J4完成J3進(jìn)內(nèi)存J1:10mJ1:25m11:25J2完成J5進(jìn)內(nèi)存J2:30mJ5:30m11:55J5完成12:40J3完成J3:45m例題3有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用搶占式優(yōu)先級(jí)調(diào)度算法，作業(yè)的運(yùn)行情況如表所示，其中作業(yè)的優(yōu)先數(shù)即為進(jìn)程的優(yōu)先數(shù)，優(yōu)先數(shù)越小，優(yōu)先級(jí)越高。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院33作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先數(shù)J18：0040min5J28：2030min3J38：3050min4J48：5020min6（1）列出所有作業(yè)進(jìn)入內(nèi)存的時(shí)間及結(jié)束的時(shí)間（2）計(jì)算平均周轉(zhuǎn)時(shí)間2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院34J18:00J1:20m8:20J2到達(dá)J28:30分析：J3J48:50J2完成J4進(jìn)入J1:20mJ2:10m9:10J1完成J3進(jìn)內(nèi)存J3:50mJ4:20m10:00J3完成10:20J4完成J2:20m2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院353.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法(RR)

在分時(shí)系統(tǒng)中，為保證能及時(shí)響應(yīng)用戶的請(qǐng)求，必須采用基于時(shí)間片的輪轉(zhuǎn)式進(jìn)程調(diào)度算法。在早期，分時(shí)系統(tǒng)中采用的是簡單的時(shí)間片輪轉(zhuǎn)法，進(jìn)入90年代后，廣泛采用多級(jí)反饋隊(duì)列調(diào)度算法。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院36將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。在一個(gè)時(shí)間片結(jié)束時(shí)，將其送到就緒隊(duì)列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。一、時(shí)間片輪轉(zhuǎn)算法1.基本原理2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院372.時(shí)間片長度的確定時(shí)間片長度變化的影響過長－>退化為FCFS算法。過短－>用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加。對(duì)響應(yīng)時(shí)間的要求：T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片)一、時(shí)間片輪轉(zhuǎn)算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院382023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院39二、多級(jí)反饋隊(duì)列調(diào)度算法

實(shí)施過程如下：（1）應(yīng)設(shè)置多個(gè)隊(duì)列并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)最高，依次降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也不相同，優(yōu)先權(quán)越高，時(shí)間片越短。1.調(diào)度算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院40多級(jí)反饋隊(duì)列調(diào)度算法

2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院41二、多級(jí)反饋隊(duì)列調(diào)度算法(2)當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。如它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾。(3）僅當(dāng)?shù)?～（i-1）隊(duì)列空閑時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院422.多級(jí)反饋隊(duì)列調(diào)度算法的性能終端型作業(yè)用戶短作業(yè)優(yōu)先短批處理作業(yè)用戶周轉(zhuǎn)時(shí)間較短長批處理作業(yè)用戶二、多級(jí)反饋隊(duì)列調(diào)度算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院43補(bǔ)充作業(yè)1、假如有四道作業(yè)，它們的進(jìn)入時(shí)間和運(yùn)行時(shí)間由下表給出，在單道程序環(huán)境下，分別填寫先來先服務(wù)、短作業(yè)優(yōu)先和RR（2）算法的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院44作業(yè)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間FCFSSJFRR（3）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1042110326432平均2、有一個(gè)內(nèi)存只能裝入兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法。下表中所列的優(yōu)先數(shù)是指進(jìn)程調(diào)度的優(yōu)先數(shù)，且優(yōu)先數(shù)越小優(yōu)先級(jí)越高。作業(yè)名到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間優(yōu)先數(shù)A10:0040分5B10:2030分3C10:3050分4D10:5020分6問：列出所有作業(yè)進(jìn)入內(nèi)存的時(shí)刻以及結(jié)束的時(shí)刻計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間3、假設(shè)一個(gè)系統(tǒng)中有5個(gè)進(jìn)程，它們的到達(dá)時(shí)間和服務(wù)時(shí)間如表所示，忽略I/O以及其他開銷時(shí)間，若分別按先來先服務(wù)（FCFS），非搶占及搶占的短進(jìn)程優(yōu)先（SPF）、高響應(yīng)比優(yōu)先（HRRN）、時(shí)間片輪轉(zhuǎn)（RR=1）、多級(jí)反饋隊(duì)列調(diào)度算法（FB，第i級(jí)隊(duì)列的時(shí)間片=2i-1)以及立即搶占的多級(jí)反饋隊(duì)列調(diào)度算法進(jìn)行CPU調(diào)度，請(qǐng)給出各進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間A03B26C44D65E822023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院49第3章處理機(jī)調(diào)度與死鎖3.3實(shí)時(shí)調(diào)度3.4產(chǎn)生死鎖的原因和必要條件3.5預(yù)防死鎖的方法3.6死鎖的檢測(cè)與解除2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院503.3實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度：合理安排就緒實(shí)時(shí)任務(wù)的執(zhí)行次序，滿足每個(gè)實(shí)時(shí)任務(wù)時(shí)間約束條件的調(diào)度實(shí)時(shí)任務(wù)：具有明確時(shí)間約束的計(jì)算任務(wù)2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院513.3實(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)度算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院523.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件提供必要的信息系統(tǒng)處理能力強(qiáng)采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院531.提供必要的信息就緒時(shí)間開始截止時(shí)間和完成截止時(shí)間處理時(shí)間資源要求優(yōu)先級(jí)2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院542.系統(tǒng)處理能力強(qiáng)

假如系統(tǒng)中有M個(gè)周期性的硬實(shí)時(shí)任務(wù)，處理時(shí)間為Ci，周期時(shí)間表示為Pi

則單機(jī)系統(tǒng)中必須滿足條件

∑（Ci/

Pi）≤1

多處理機(jī)系統(tǒng)∑（Ci/

Pi）≤N2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院553.采用搶占式調(diào)度機(jī)制

硬實(shí)時(shí)任務(wù)：廣泛采用搶占機(jī)制小的實(shí)時(shí)系統(tǒng)：可采用非搶占調(diào)度機(jī)制（簡化調(diào)度程序和對(duì)任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開銷）3.采用搶占式調(diào)度機(jī)制2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院562023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院574.具有快速切換機(jī)制

(1)對(duì)外部中斷的快速響應(yīng)能力(2)快速的任務(wù)分派能力2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院583.3.2實(shí)時(shí)調(diào)度算法的分類可以按照不同方式對(duì)實(shí)時(shí)調(diào)度算法加以分類：根據(jù)實(shí)時(shí)任務(wù)性質(zhì)的不同可分為硬實(shí)時(shí)調(diào)度算法和軟實(shí)時(shí)調(diào)度算法；按調(diào)度方式的不同可分為非搶占調(diào)度算法和搶占調(diào)度算法；2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院593.3.3常用的幾種實(shí)時(shí)調(diào)度算法

最早截止時(shí)間優(yōu)先EDF（EarliestDeadlineFirst）算法最低松弛度優(yōu)先LLF（LeastLaxityFirst）算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院60EDF算法用于非搶占調(diào)度圖示

1342t按開始截止時(shí)間早晚的排序任務(wù)執(zhí)行任務(wù)到達(dá)134212341.最早截止時(shí)間優(yōu)先EDF算法

截止時(shí)間越早，其優(yōu)先級(jí)越高2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院612.最低松弛度優(yōu)先LLF算法松弛度=完成截止時(shí)間—運(yùn)行時(shí)間—當(dāng)前時(shí)間任務(wù)的緊急程度愈高，松弛度愈低，優(yōu)先級(jí)愈高。要求系統(tǒng)有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列該算法主要用于可搶占調(diào)度方式中2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院62LLF算法例tA1A2A3A4A5A6B1B2020406080100120

假如在一個(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；由此可得知AB任務(wù)每次必須完成的時(shí)間分別為A1、A2、A3…和B1、B2、B3…如下圖：2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院63LLF算法例圖示tt1

t2

t3

t4

t5

t6

t7

t8

01020304050607080A1(10)A2(10)A3(10)A4(10)B1(20)B1(5)B2(15)B2(10)

4、對(duì)下面的5個(gè)非周期性實(shí)時(shí)任務(wù)，按最早開始截止時(shí)間優(yōu)先調(diào)度算法，判斷是該用搶占方式還是非搶占方式，并給出調(diào)度順序。補(bǔ)充作業(yè)進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間開始截止時(shí)間A1020110B202020C402050D502090E6020705、若有3個(gè)周期性任務(wù)，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)C要求每50ms執(zhí)行一次，執(zhí)行時(shí)間15ms應(yīng)如何按最低松弛度優(yōu)先算法對(duì)它們進(jìn)行調(diào)度？2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院673.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院68關(guān)于死鎖

死鎖是指多個(gè)進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種狀態(tài)時(shí)，若無外力作用，它們都將無法再向前推進(jìn)。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院693.5.1產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)：競爭資源

進(jìn)程間推進(jìn)順序非法可搶占和非搶占性資源可重用性（永久性）資源和可消耗性（臨時(shí)性）資源2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院70P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D進(jìn)程推進(jìn)順序不當(dāng)引起死鎖2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院713.5.2產(chǎn)生死鎖的必要條件

雖然進(jìn)程在運(yùn)行過程中可能發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件?？梢钥闯?，必須具備以下四個(gè)條件:1.互斥條件：進(jìn)程所競爭的資源必須被互斥使用。2.請(qǐng)求和保持條件：指進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其他資源保持不放。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院723.5.2產(chǎn)生死鎖的必要條件

3.不剝奪條件：指進(jìn)程已獲得的資源，只能在使用完時(shí)由自己釋放。

4.環(huán)路等待條件：指在發(fā)生死鎖時(shí)，必然存在一個(gè)“進(jìn)程——資源”的環(huán)形鏈，環(huán)路中的每一條邊是進(jìn)程在請(qǐng)求另一進(jìn)程已經(jīng)占有的資源。

2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院733.5.3處理死鎖的基本方法一、預(yù)防死鎖——消除產(chǎn)生死鎖的必要條件二、避免死鎖——分配資源時(shí)防止進(jìn)入不安全狀態(tài)三、檢測(cè)死鎖——不預(yù)防死鎖，出現(xiàn)死鎖就解除四、解除死鎖——與檢測(cè)死鎖配合使用2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院743.6預(yù)防與避免死鎖的方法3.6.1預(yù)防死鎖3.6.2系統(tǒng)安全狀態(tài)3.6.3利用銀行家算法避免死鎖2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院753.6.1預(yù)防死鎖1.摒棄“請(qǐng)求和保持”條件靜態(tài)資源分配法一次性地申請(qǐng)其在整個(gè)過程運(yùn)行過程中所需要的全部資源優(yōu)點(diǎn)：算法簡單、易于實(shí)現(xiàn)且很安全缺點(diǎn)：資源浪費(fèi)嚴(yán)重，進(jìn)程延遲運(yùn)行2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院762.摒棄“不剝奪”條件資源暫時(shí)釋放策略:申請(qǐng)新的資源得不到滿足則暫時(shí)釋放已有的所有資源。從而摒棄了“不剝奪”條件。該方法實(shí)現(xiàn)起來比較復(fù)雜且付出很大代價(jià)?？赡軙?huì)造成前功盡棄，反復(fù)申請(qǐng)和釋放情況。3.6.1預(yù)防死鎖2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院773.摒棄“環(huán)路等待”條件有序資源分配法：

與前兩種策略比較，資源利用率和系統(tǒng)吞吐量都有較明顯的改善。但也存在嚴(yán)重問題：為資源編號(hào)限制新設(shè)備的增加；進(jìn)程使用設(shè)備順序與申請(qǐng)順序相反；限制用戶編程自由。r1r2rk......申請(qǐng)次序rm2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院78檢測(cè)可滿足請(qǐng)求

分配

不分配安全不安全系統(tǒng)處于安全狀態(tài)：存在安全進(jìn)程序列<p1,p2,…,pn>;安全不安全死鎖1.安全狀態(tài)3.6.2系統(tǒng)安全狀態(tài)避免死鎖的實(shí)質(zhì)就是系統(tǒng)在進(jìn)行資源分配時(shí)，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院792.安全狀態(tài)之例

假定系統(tǒng)中有三個(gè)進(jìn)程A、B和C，共有12臺(tái)磁帶機(jī)。進(jìn)程A總共要求10臺(tái)，B和C分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻,進(jìn)程A、B和C已分別獲得5臺(tái)、2臺(tái)和2臺(tái)，尚有3臺(tái)未分配，如下表所示：進(jìn)程最大需求已分配還需可用ABC10495225273進(jìn)程最大需求已分配還需可用B42235A105510C92712

經(jīng)分析發(fā)現(xiàn)，在T0時(shí)刻系統(tǒng)是安全的，因?yàn)榇藭r(shí)存在一個(gè)安全序列<B,A,C>，即只要系統(tǒng)按此進(jìn)程序列分配資源，就能使每個(gè)進(jìn)程都順利完成。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院803.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果在T0時(shí)刻后，C又請(qǐng)求到一臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給C，則系統(tǒng)便進(jìn)入不安全狀態(tài)。因?yàn)椋藭r(shí)再也無法找到一個(gè)安全序列，結(jié)果導(dǎo)致死鎖。進(jìn)程最大需求已分配還需可用A10553B422C927

所以，引入安全狀態(tài)的目的在于進(jìn)行資源分配時(shí)，要使系統(tǒng)不發(fā)生死鎖，只要保證當(dāng)前的系統(tǒng)狀態(tài)是安全的，即每次資源分配之后系統(tǒng)都處于安全狀態(tài)。2C936練習(xí)1某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，由K個(gè)進(jìn)程競爭使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（），不會(huì)發(fā)生死鎖的最大值是（）。A.2B.3C.4D.5解析：R類資源共m個(gè)，n個(gè)進(jìn)程互斥使用，每個(gè)進(jìn)程對(duì)R類資源最大需求量為w設(shè)：M=n*（w-1）+1則m<M的可能會(huì)發(fā)生死鎖，m>=M絕對(duì)不會(huì)死鎖練習(xí)1某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，由K個(gè)進(jìn)程競爭使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（），不會(huì)發(fā)生死鎖的最大值是（）。A.2B.3C.4D.5CB2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院843.6.3利用銀行家算法避免死鎖最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名的。銀行家算法中的數(shù)據(jù)結(jié)構(gòu)（1）可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其動(dòng)態(tài)初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配與回收而動(dòng)態(tài)的改變。如果Available[j]=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。（2）最大需求矩陣Max。這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i,j]=K,則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。（3）分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K,則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。（4）需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K,則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。上述三個(gè)矩陣間存在的關(guān)系：Need[i,j]=Max[i,j]-Allocation[i,j]2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院853.6.3利用銀行家算法避免死鎖安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：（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í)先做Finish[i]:=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish[i]:=true。2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院86安全性檢測(cè)算法FWork:=Available;Finish:=false;有滿足條件的j:Finish[i]=falseNeed[j]WorkFinish[i]=true;Work:=Work+Allocation[j]Ti,Finish[i]=trueTF安全不安全賦初值進(jìn)程是否完成資源是否夠用進(jìn)程獲得資源后，順利完成并釋放資源進(jìn)程是否都完成2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院87（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：

Finish[i]=false;Need[i,j]<=work[j];若找到，執(zhí)行步驟3，否則執(zhí)行步驟4。（3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

work[j]:=work[i]+Allocation[i,j];Finish[i]:=true;gotostep2;（4）如果所有進(jìn)程的Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。安全性算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院884.銀行家算法之例

假定系統(tǒng)中有五個(gè)進(jìn)程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖所示。431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC

資源情況進(jìn)程2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院894.銀行家算法之例T0時(shí)刻的安全性：利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析可知，在T0時(shí)刻存在著一個(gè)安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的。FalseFalseFalseFalseFalseTrue10570107431047P0True1047302600745P2True745002431743P4True743211011532P3True532200122332P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC

資源情況進(jìn)程2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院903.6.3利用銀行家算法避免死鎖銀行家算法設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requesti

[j]=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院91Pi請(qǐng)求資源Requesti[j]Need[j]請(qǐng)求超量，錯(cuò)返Requesti[j]Available[j]不滿足，等待Available[j]:=Available[j]-Requesti[j]Allocation[i,j]:=Allocation[i,j]+Requesti[j]Need[i,j]:=Need[i,j]-Requesti[j]安全確認(rèn)，pi繼續(xù)Available[j]:=Available[j]+Requesti[j]Allocation[i,j]:=Allocation[i,j]-Requesti[j]Need[i,j]:=Need[i,j]+Requesti[j]pi等待FTFTTF請(qǐng)求的資源是否超出實(shí)際需求是否有足夠的資源暫時(shí)分配資源恢復(fù)原來的資源分配狀態(tài)2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院92（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)以決定是否完成本次分配。銀行家算法2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院934.銀行家算法之例P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2),系統(tǒng)按銀行家算法進(jìn)行檢查：（1）Request1(1，0，2)<=Need1(1，2，2)（2）Request1(1，0，2)<=Available1(3，3，2)（3）系統(tǒng)先假定可為P1分配資源，并修改Available、Allocation1和Need1向量。（4）再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。如下表：2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院94FalseFalseFalseFalseFalse4.銀行家算法之例

由所進(jìn)行的安全性檢查得知，可以找到一個(gè)安全序列{P1,P3,P4,P0,P2},因此，系統(tǒng)是安全的，可以立即將P1所申請(qǐng)的資源分配給它。True1057302600755P2True755010743745P0True745002431743P4True743211011532P3True532302020230P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC

資源情況進(jìn)程2023/2/4阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院954.銀行家算法之例P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0),系統(tǒng)按銀行家算法進(jìn)行檢查：（1）Request4(3，3，0)<=Need4(4