1、2020/8/6,阜陽師范學(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è)與解除,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,2,3.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)則,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,3,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,4,3.1.1 高級(jí)、中級(jí)和低級(jí)調(diào)度,經(jīng)歷下述三級(jí)調(diào)度: 高級(jí)調(diào)度（High

2、 Scheduling） 中級(jí)調(diào)度（Intermediate-Level Scheduling） 低級(jí)調(diào)度（Low Level Scheduling）,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,5,1. 高級(jí)調(diào)度,又稱為作業(yè)調(diào)度、宏觀調(diào)度或長(zhǎng)程調(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)度,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,6,1. 高級(jí)調(diào)度,執(zhí)行作業(yè)調(diào)度時(shí)，必須作出兩個(gè)決定： 接納多少作業(yè)每次接納多少作業(yè)進(jìn)入內(nèi)存，取決于多道程序度，即允許多少個(gè)作業(yè)同時(shí)在

3、內(nèi)存中運(yùn)行。 接納哪些作業(yè)應(yīng)接納哪些作業(yè)從外存調(diào)入內(nèi)存，取決于所采用的調(diào)度算法。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,7,2. 低級(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ì)器 分派器 上下文切換,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,8,2. 低級(jí)調(diào)度,進(jìn)程調(diào)度可采用下述兩種調(diào)度方式： 非搶占方式 搶占方式 搶占的原則有： （1）優(yōu)先權(quán)原則 （2）短作業(yè)（進(jìn)程）優(yōu)先原則 （3）時(shí)間片原則,2020/8/6

4、,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,9,3. 中級(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)度的層次,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,11,3.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ì)列模型,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,12,1. 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型,在分時(shí)系統(tǒng)中就緒進(jìn)程組織成FIFO隊(duì)列形式，按時(shí)間

5、片輪轉(zhuǎn)方式運(yùn)行。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,13,2. 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,14,3. 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,15,3.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)行

6、，則平均周轉(zhuǎn)時(shí)間為（ ） A. 1h B. 5h C. 2.5h D.8h,B,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,17,3.2 調(diào)度算法,3.2.1 FCFS與SJF/SPF調(diào)度算法 3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 3.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,18,3.2.1 FCFS與SJF/SPF調(diào)度算法,1. 先來先服務(wù)調(diào)度算法(FCFS) 按進(jìn)程申請(qǐng)CPU（就緒）的次序,0 27 30 35,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,19,FCFS實(shí)例 下表列出了A、B、C、D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開

7、始執(zhí)行的時(shí)間及各自的完成時(shí)間，計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。,FCFS（First Come First Serve),2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,20,FCFS（First Come First Serve),0,1,1,1,1,101,100,1,101,102,100,100,102,202,199,1.99,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,21,FCFS的特點(diǎn): FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)（進(jìn)程） 比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè),FCFS（First Come First Serve),2020/8/

8、6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,22,2. 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法,4,4,1,7,6,2,12,10,2,14,11,5.5,18,14,3.5,9,2.8,4,4,1,9,8,2.67,18,16,3.2,6,3,1.5,13,9,2.25,8,2.1,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,23,2 . 短作業(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ì)長(zhǎng)作業(yè)不利 (2) 不能保證緊迫性作業(yè)（進(jìn)程）的及時(shí)處理 (3) 不一定能真正做到短作業(yè)優(yōu)先,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,24,3

9、.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)度算法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,25,3.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í)間的增加而改變。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,26,3. 高響應(yīng)比優(yōu)先調(diào)度算法(HRRN),為每個(gè)作業(yè)引入動(dòng)態(tài)優(yōu)先權(quán)，并使作

10、業(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. 2 B.1 C.3 D.0.5,C,例題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ōu)先權(quán)（響應(yīng)比）=(等待時(shí)間+要求服務(wù)時(shí)間)/要求 服務(wù)時(shí)間響應(yīng)時(shí)間/要

11、求服務(wù)時(shí)間,例題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)度算法,例題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í)間。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院,32,J1,10:00,J4:20m,10:10 J2到達(dá),J2,10:35 J1完成 J4進(jìn)內(nèi)存,分析：,J3,J4,J5,10:55 J4完成 J3進(jìn)內(nèi)存,J1:10m,J1:25m,11:25 J2完成 J

12、5進(jìn)內(nèi)存,J2:30m,J5:30m,11:55 J5完成,12:40 J3完成,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í)越高。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,33,（1）列出所有作業(yè)進(jìn)入內(nèi)存的時(shí)間及結(jié)束的時(shí)間 （2）計(jì)算平均周轉(zhuǎn)時(shí)間,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院,34,J1,8:00,J1:20m,8:20 J2到達(dá),J2,8:30,分析：,J3,J4,8:50 J2完成 J4進(jìn)入,J1:20m,J

13、2:10m,9:10 J1完成 J3進(jìn)內(nèi)存,J3:50m,J4:20m,10:00 J3完成,10:20 J4完成,J2:20m,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,35,3.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)中采用的是簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法，進(jìn)入90年代后，廣泛采用多級(jí)反饋隊(duì)列調(diào)度算法。,2020/8/6,阜陽師范學(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í)，將其送到

14、就緒隊(duì)列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。,一、時(shí)間片輪轉(zhuǎn)算法,1. 基本原理,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,37,2. 時(shí)間片長(zhǎng)度的確定,時(shí)間片長(zhǎng)度變化的影響 過長(zhǎng)退化為FCFS算法。 過短用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加。 對(duì)響應(yīng)時(shí)間的要求： T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片),一、時(shí)間片輪轉(zhuǎn)算法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,38,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,39,二、多級(jí)反饋隊(duì)列調(diào)度算法,實(shí)施過程如下： （1） 應(yīng)設(shè)置多個(gè)隊(duì)列并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)最高，依次降低。該算法賦

15、予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也不相同，優(yōu)先權(quán)越高，時(shí)間片越短。,1. 調(diào)度算法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,40,多級(jí)反饋隊(duì)列調(diào)度算法,2020/8/6,阜陽師范學(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)行。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,42,2. 多級(jí)反饋隊(duì)列調(diào)度算法的性能,終端型作業(yè)用戶 短作業(yè)優(yōu)先 短批處理作業(yè)用戶

16、 周轉(zhuǎn)時(shí)間較短 長(zhǎng)批處理作業(yè)用戶,二、多級(jí)反饋隊(duì)列調(diào)度算法,2020/8/6,阜陽師范學(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í)間。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,44,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è)進(jìn)入內(nèi)存的時(shí)刻以及結(jié)束的時(shí)刻

17、 計(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í)間。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,49,第3章 處理機(jī)調(diào)度與死鎖,3.3 實(shí)時(shí)調(diào)度 3.4 產(chǎn)生死鎖的原因和必要條件 3.5 預(yù)防死鎖的方法 3.

18、6 死鎖的檢測(cè)與解除,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,50,3.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ù),2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,51,3.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)度算法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,52,3.3.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,提供必要的信息 系統(tǒng)處理能力強(qiáng) 采用搶占式調(diào)度機(jī)制 具有快速切換機(jī)制,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,5

19、3,1. 提供必要的信息,就緒時(shí)間 開始截止時(shí)間和完成截止時(shí)間 處理時(shí)間 資源要求 優(yōu)先級(jí),2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,54,2. 系統(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 ）N,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,55,3. 采用搶占式調(diào)度機(jī)制,硬實(shí)時(shí)任務(wù)： 廣泛采用搶占機(jī)制 小的實(shí)時(shí)系統(tǒng)： 可采用非搶占調(diào)度機(jī)制（簡(jiǎn)化調(diào)度程序和對(duì)任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開銷）,3. 采用搶占式調(diào)度機(jī)制,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院

20、,56,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,57,4. 具有快速切換機(jī)制,(1) 對(duì)外部中斷的快速響應(yīng)能力 (2) 快速的任務(wù)分派能力,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,58,3.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)度算法；,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,59,3.3.3 常用的幾種實(shí)時(shí)調(diào)度算法,最早截止時(shí)間優(yōu)先EDF（Earliest Deadline First）算法 最低松弛度優(yōu)先LLF（Least Lax

21、ity First）算法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,60,EDF算法用于非搶占調(diào)度圖示,1 3 4 2,t,按開始截止時(shí)間早晚的排序,任務(wù)執(zhí)行,任務(wù)到達(dá),1 3 4 2,1 2 3 4,1. 最早截止時(shí)間優(yōu)先EDF算法,截止時(shí)間越早，其優(yōu)先級(jí)越高,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,61,2. 最低松弛度優(yōu)先LLF算法,松弛度=完成截止時(shí)間運(yùn)行時(shí)間當(dāng)前時(shí)間 任務(wù)的緊急程度愈高，松弛度愈低，優(yōu)先級(jí)愈高。 要求系統(tǒng)有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列 該算法主要用于可搶占調(diào)度方式中,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,62,LLF算法例,假如在一個(gè)實(shí)時(shí)

22、系統(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如下圖：,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,63,LLF算法例圖示,4、對(duì)下面的5個(gè)非周期性實(shí)時(shí)任務(wù)，按最早開始截 止時(shí)間優(yōu)先調(diào)度算法，判斷是該用搶占方式還是非 搶占方式，并給出調(diào)度順序。,補(bǔ)充作業(yè),5、若有3個(gè)周期性任務(wù)，任務(wù)A要求每20ms執(zhí)行一次，執(zhí) 行時(shí)間為10ms；任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時(shí)間 為10ms；任務(wù)C要求每50ms執(zhí)行一次，執(zhí)行時(shí)間15ms

23、 應(yīng)如何按最低松弛度優(yōu)先算法對(duì)它們進(jìn)行調(diào)度？,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,67,3.5 產(chǎn)生死鎖的原因和必要條件,3.5.1 產(chǎn)生死鎖的原因 3.5.2 產(chǎn)生死鎖的必要條件 3.5.3 處理死鎖的基本方法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,68,關(guān)于死鎖,死鎖是指多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種狀態(tài)時(shí)，若無外力作用，它們都將無法再向前推進(jìn)。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,69,3.5.1 產(chǎn)生死鎖的原因,產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)： 競(jìng)爭(zhēng)資源 進(jìn)程間推進(jìn)順序非法,可搶占和非搶占性資源 可重用性（永久性）資源和

24、可消耗性（臨時(shí)性）資源,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,70,P,2,Rel(R,1,),P,2,Rel(R,2,),P,2,Req(R,1,),P,2,Req(R,2,),P,1,Req(R,1,),P,1,Req(R,2,),P,1,Rel(R,1,),P,1,Rel(R,2,),D,進(jìn)程推進(jìn)順序不當(dāng)引起死鎖,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,71,3.5.2 產(chǎn)生死鎖的必要條件,雖然進(jìn)程在運(yùn)行過程中可能發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件?？梢钥闯?，必須具備以下四個(gè)條件: 1. 互斥條件：進(jìn)程所競(jìng)爭(zhēng)的資源必須被互斥使用。 2. 請(qǐng)求和保持條件：指進(jìn)程已

25、經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其他資源保持不放。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,72,3.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)占有的資源。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,73,3.5.3 處理死鎖的基本方法,一、預(yù)防死鎖消除產(chǎn)生死鎖的必要條件 二、避免死鎖分配資源時(shí)防止進(jìn)入不安全狀態(tài) 三、檢測(cè)死鎖不預(yù)防死鎖，出現(xiàn)死鎖

26、就解除 四、解除死鎖與檢測(cè)死鎖配合使用,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,74,3.6 預(yù)防與避免死鎖的方法,3.6.1 預(yù)防死鎖 3.6.2 系統(tǒng)安全狀態(tài) 3.6.3 利用銀行家算法避免死鎖,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,75,3.6.1 預(yù)防死鎖,1. 摒棄“請(qǐng)求和保持”條件,靜態(tài)資源分配法 一次性地申請(qǐng)其在整個(gè)過程運(yùn)行過程中所需要的全部資源 優(yōu)點(diǎn)：算法簡(jiǎn)單、易于實(shí)現(xiàn)且很安全 缺點(diǎn)：資源浪費(fèi)嚴(yán)重，進(jìn)程延遲運(yùn)行,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,76,2. 摒棄“不剝奪”條件,資源暫時(shí)釋放策略:申請(qǐng)新的資源得不到滿足則暫時(shí)釋放已有的所有資源。從而

27、摒棄了“不剝奪”條件。 該方法實(shí)現(xiàn)起來比較復(fù)雜且付出很大代價(jià)。可能會(huì)造成前功盡棄，反復(fù)申請(qǐng)和釋放情況。,3.6.1 預(yù)防死鎖,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,77,3. 摒棄“環(huán)路等待”條件,有序資源分配法： 與前兩種策略比較，資源利用率和系統(tǒng)吞吐量都有較明顯的改善。 但也存在嚴(yán)重問題：為資源編號(hào)限制新設(shè)備的增加；進(jìn)程使用設(shè)備順序與申請(qǐng)順序相反；限制用戶編程自由。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,78,系統(tǒng)處于安全狀態(tài)：存在安全進(jìn)程序列;,1. 安全狀態(tài),3.6.2 系統(tǒng)安全狀態(tài),避免死鎖的實(shí)質(zhì)就是系統(tǒng)在進(jìn)行資源分配時(shí)，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。,2020/8

28、/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,79,2. 安全狀態(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)未分配，如下表所示：,10,4,9,5,2,2,5,2,7,3,B 4 2 2,3,5,A 10 5 5,10,C 9 2 7,12,經(jīng)分析發(fā)現(xiàn)，在T0時(shí)刻系統(tǒng)是安全的，因?yàn)榇藭r(shí)存在一個(gè)安全序列，即只要系統(tǒng)按此進(jìn)程序列分配資源，就能使每個(gè)進(jìn)程都順利完成。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,80,3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換,如果在T0時(shí)刻后，C又請(qǐng)求到

29、一臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給C，則系統(tǒng)便進(jìn)入不安全狀態(tài)。因?yàn)?，此時(shí)再也無法找到一個(gè)安全序列，結(jié)果導(dǎo)致死鎖。,所以，引入安全狀態(tài)的目的在于進(jìn)行資源分配時(shí)，要使系統(tǒng)不發(fā)生死鎖，只要保證當(dāng)前的系統(tǒng)狀態(tài)是安全的，即每次資源分配之后系統(tǒng)都處于安全狀態(tài)。,2,C 9 3 6,練習(xí)1,某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，由K個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（ ），不會(huì)發(fā)生死鎖的最大值是（ ）。 A. 2 B. 3 C. 4 D. 5,解析：,R類資源共m個(gè)， n個(gè)進(jìn)程互斥使用，每個(gè)進(jìn)程對(duì)R類資源最大需求量為w 設(shè)：M=n*（w-1）+1 則m=M絕對(duì)不

30、會(huì)死鎖,練習(xí)1,某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，由K個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（ ），不會(huì)發(fā)生死鎖的最大值是（ ）。 A. 2 B. 3 C. 4 D. 5,C,B,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,84,3.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ù)

31、目，其數(shù)值隨該類資源的分配與回收而動(dòng)態(tài)的改變。如果Availablej=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。,（2）最大需求矩陣Max。這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K,則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。,（3）分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K,則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。,（4）需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K,則表示進(jìn)程i還

32、需要Rj類資源K個(gè)，方能完成其任務(wù)。 上述三個(gè)矩陣間存在的關(guān)系：Needi,j=Maxi,j-Allocationi,j,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,85,3.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í)先做Finishi:=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi:=true。,2020/8/

33、6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,86,安全性檢測(cè)算法,F,Work:=Available; Finish:=false;,有滿足條件的j: Finishi=false NeedjWork,Finishi=true; Work:=Work+Allocationj,T,i ,Finishi=true,T,F,安全,不安全,賦初值,進(jìn)程是否完成 資源是否夠用,進(jìn)程獲得資源后，順利完成并釋放資源,進(jìn)程是否都完成,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,87,（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false;Needi,j=workj;若找到，執(zhí)行步驟3，否則執(zhí)行步

34、驟4。 （3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： workj:= worki+ Allocationi,j ; Finishi:=true; goto step 2; （4）如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。,安全性算法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,88,4. 銀行家算法之例,假定系統(tǒng)中有五個(gè)進(jìn)程P0,P1,P2,P3,P4和三類資源A,B,C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖所示。,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,89,4

35、. 銀行家算法之例,T0時(shí)刻的安全性：利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析可知，在T0時(shí)刻存在著一個(gè)安全序列P1,P3,P4,P2,P0，故系統(tǒng)是安全的。,False,False,False,False,False,True,10 5 7,0 1 0,7 4 3,10 4 7,P0,True,10 4 7,3 0 2,6 0 0,7 4 5,P2,True,7 4 5,0 0 2,4 3 1,7 4 3,P4,True,7 4 3,2 1 1,0 1 1,5 3 2,P3,True,5 3 2,2 0 0,1 2 2,3 3 2,P1,Finish,Work+Allocation A

36、 B C,Allocation A B C,Need A B C,Work A B C,資源情況 進(jìn)程,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,90,3.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)行檢查：,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,91,Pi請(qǐng)求資源,RequestijNeedj,請(qǐng)求超量，錯(cuò)返,RequestijAvailablej,不滿足，等待,Availablej:=Availablej-Requestij All

37、ocationi,j:=Allocationi,j+Requestij Needi,j:=Needi,j-Requestij,安全,確認(rèn)，pi繼續(xù),Availablej:=Availablej+Requestij Allocationi,j:=Allocationi,j-Requestij Needi,j:=Needi,j+Requestij pi等待,F,T,F,T,T,F,請(qǐng)求的資源是否超出實(shí)際需求,是否有足夠的資源,暫時(shí)分配資源,恢復(fù)原來的資源分配狀態(tài),2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,92,（1）如果Requestij= Needi,j,便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗?/p>

38、所需要的資源數(shù)已超過它所宣布的最大值。 （2）如果Requestij= Availablej,便轉(zhuǎn)向步驟3；否則，表示尚無足夠資源，Pi需等待。 （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; （4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否出于安全狀態(tài)以決定是否完成本次分配。,銀行家算法,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,93,4. 銀行家算法之例

39、,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)是否安全。如下表：,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,94,False,False,False,False,False,4. 銀行家算法之例,由所進(jìn)行的安全性檢查得知，可以找到一個(gè)安全序列P1,P3,P4,P0,P2

40、,因此，系統(tǒng)是安全的，可以立即將P1所申請(qǐng)的資源分配給它。,True,10 5 7,3 0 2,6 0 0,7 5 5,P2,True,7 5 5,0 1 0,7 4 3,7 4 5,P0,True,7 4 5,0 0 2,4 3 1,7 4 3,P4,True,7 4 3,2 1 1,0 1 1,5 3 2,P3,True,5 3 2,3 0 2,0 2 0,2 3 0,P1,Finish,Work+Allocation A B C,Allocation A B C,Need A B C,Work A B C,資源情況 進(jìn)程,2020/8/6,阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院,95,4. 銀行家算法之例,P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0),系統(tǒng)按銀行家算法進(jìn)行檢查： （1）Request4(3，3，0)=Need4(4，3，1); （2）Request4(3，3，0)=Ava