操作系統(tǒng)課件：第3章 處理機的調(diào)度和死鎖

1、v 3.13.1高、中、低三級調(diào)度高、中、低三級調(diào)度 v 1 1、高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度）、高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度） 將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建PCBPCB等，插入就緒等，插入就緒隊列。隊列。 一般用于批處理系統(tǒng)，分一般用于批處理系統(tǒng)，分/ /實時系統(tǒng)一般直接實時系統(tǒng)一般直接入內(nèi)存，無此環(huán)節(jié)。入內(nèi)存，無此環(huán)節(jié)。 調(diào)度特性調(diào)度特性 1.1.接納作業(yè)數(shù)（內(nèi)存駐留數(shù)）接納作業(yè)數(shù)（內(nèi)存駐留數(shù)）太多太多 周轉(zhuǎn)時間周轉(zhuǎn)時間T T長長太少太少 系統(tǒng)效率低系統(tǒng)效率低 2.2.接納策略：即采用何種調(diào)度算法：接納策略：即采用何種調(diào)度算法：FCFSFCFS、短、

2、短作業(yè)優(yōu)先等作業(yè)優(yōu)先等v 2 2、低級調(diào)度（進程調(diào)度，短程調(diào)度）、低級調(diào)度（進程調(diào)度，短程調(diào)度）v 主要是由分派程序（主要是由分派程序（DispatcherDispatcher）分派處理機。）分派處理機。.1 1.非搶占方式：非搶占方式：簡單，實時性差簡單，實時性差 ( (如如win31)win31).2 2.搶占方式搶占方式（1 1）時間片原則）時間片原則（2 2）優(yōu)先權原則）優(yōu)先權原則（3 3）短作業(yè)優(yōu)先原則。）短作業(yè)優(yōu)先原則。 v運行頻率：低運行頻率：低 中中 高高。v三種調(diào)度被引發(fā)的事件？三種調(diào)度被引發(fā)的事件？v事件的表現(xiàn)方式？事件的表現(xiàn)方式？v一、僅有進程調(diào)度的隊列模型一、僅有進程調(diào)

3、度的隊列模型就緒隊列就緒隊列CPU阻塞隊列阻塞隊列交互用戶交互用戶時間片完時間片完進程調(diào)度進程調(diào)度進程完成進程完成等待事件等待事件事件出現(xiàn)事件出現(xiàn)v二、具有高二、具有高/ /低級模型低級模型就緒隊列就緒隊列CPU阻塞隊列阻塞隊列時間片完時間片完進程調(diào)度進程調(diào)度進程進程完成完成等待事件等待事件1事件事件1出現(xiàn)出現(xiàn)后備隊列后備隊列阻塞隊列阻塞隊列等待事件等待事件2事件事件2出現(xiàn)出現(xiàn)作業(yè)調(diào)度作業(yè)調(diào)度就緒隊列就緒隊列CPU就緒、掛起隊列就緒、掛起隊列時間片完時間片完進程調(diào)度進程調(diào)度進程進程完成完成后備隊列后備隊列阻塞、掛起隊列阻塞、掛起隊列事件出現(xiàn)事件出現(xiàn)作業(yè)調(diào)度作業(yè)調(diào)度阻塞隊列阻塞隊列等待事件等待事

4、件掛起掛起事件出現(xiàn)事件出現(xiàn)中級調(diào)度中級調(diào)度交互型作業(yè)交互型作業(yè)v 一、面向用戶的準則一、面向用戶的準則1 1 周轉(zhuǎn)時間短（常用于批處理系統(tǒng)）周轉(zhuǎn)時間短（常用于批處理系統(tǒng)） 概念：作業(yè)從提交概念：作業(yè)從提交 完成的時間完成的時間. .分為：分為： （1 1）駐外等待調(diào)度時間）駐外等待調(diào)度時間 （2 2）駐內(nèi)等待調(diào)度時間）駐內(nèi)等待調(diào)度時間 （3 3）執(zhí)行時間）執(zhí)行時間 （4 4）阻塞時間）阻塞時間v 一、面向用戶的準則一、面向用戶的準則 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間 平均帶權平均帶權 可見帶權可見帶權w w越小越好越小越好,Ts,Ts為實際服務時間。為實際服務時間。11niiTnT11nisiTTnW

5、v 一、面向用戶的準則一、面向用戶的準則2 2 響應時間快：（對交互性作業(yè)）響應時間快：（對交互性作業(yè)） 概念：鍵盤提交請求到首次響應時間概念：鍵盤提交請求到首次響應時間 （1 1）輸入傳送時間）輸入傳送時間 （2 2）處理時間）處理時間 （3 3）響應傳送時間）響應傳送時間3 3 截止時間的保證（特別于實時系統(tǒng)）截止時間的保證（特別于實時系統(tǒng)）4 4 優(yōu)先權準則：（即需要搶占調(diào)度）優(yōu)先權準則：（即需要搶占調(diào)度）v 二、面向系統(tǒng)的準則二、面向系統(tǒng)的準則1 1 吞吐量高（特別于批處理）：單位時間完成作吞吐量高（特別于批處理）：單位時間完成作業(yè)數(shù)業(yè)數(shù)2 2 處理機利用率好：（因處理機利用率好：（因

6、CPUCPU貴，特別于大中型貴，特別于大中型多用戶系統(tǒng)）多用戶系統(tǒng)）3 3 各類資源的平衡利用。（？折算標準）各類資源的平衡利用。（？折算標準）v3.2.13.2.1先來先服務和短作業(yè)（進程）優(yōu)先調(diào)度算法先來先服務和短作業(yè)（進程）優(yōu)先調(diào)度算法 1.FCFS1.FCFS特點：簡單，有利于長作業(yè)特點：簡單，有利于長作業(yè) 即即CPUCPU繁忙性作業(yè)繁忙性作業(yè)2.2.短作業(yè)進程優(yōu)先調(diào)度算法：短作業(yè)進程優(yōu)先調(diào)度算法：SJ(P)FSJ(P)F提高了平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間（從而提提高了平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間（從而提高了系統(tǒng)吞吐量）高了系統(tǒng)吞吐量）特點：對長作業(yè)不利，有可能得不到服務（饑餓）特

7、點：對長作業(yè)不利，有可能得不到服務（饑餓）估計時間不易確定估計時間不易確定進程名到達時間服務時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間A010111B110011011001C21101102100100D31001022021991.99進程名進程名 A B C D E平均平均到達時間到達時間 0 1 2 3 4服務時間服務時間 4 3 5 2 4FCFS完成時間完成時間 4 7 12 14 18周轉(zhuǎn)時間周轉(zhuǎn)時間 4 6 10 11 149帶權周轉(zhuǎn)時間帶權周轉(zhuǎn)時間 1 2 2 5.5 3.52.8SJF完成時間完成時間 4 9 18 6 13周轉(zhuǎn)時間周轉(zhuǎn)時間 4 8 16 3 98帶權周轉(zhuǎn)

8、時間帶權周轉(zhuǎn)時間 1 2.67 3.1 1.5 2.252.1v 1.1.優(yōu)先權調(diào)度算法類型優(yōu)先權調(diào)度算法類型 非搶占式優(yōu)先權算法非搶占式優(yōu)先權算法 搶占式優(yōu)先權算法，實時性更好。搶占式優(yōu)先權算法，實時性更好。v 2.2.優(yōu)先權類型：優(yōu)先權類型：1 1 靜態(tài)優(yōu)先權：靜態(tài)優(yōu)先權： 進程優(yōu)先權在整個運行期不變。進程優(yōu)先權在整個運行期不變。 確定優(yōu)先權依據(jù)確定優(yōu)先權依據(jù)（1 1）進程類型）進程類型（2 2）進程對資源的需求；）進程對資源的需求；（3 3）根據(jù)用戶需求。）根據(jù)用戶需求。 特點：簡單，但低優(yōu)先權作業(yè)可能長期不被特點：簡單，但低優(yōu)先權作業(yè)可能長期不被調(diào)度。調(diào)度。v 2 2動態(tài)優(yōu)先權：動態(tài)優(yōu)

9、先權： 如：優(yōu)先權隨執(zhí)行時間而下降，隨等待時間而升高。如：優(yōu)先權隨執(zhí)行時間而下降，隨等待時間而升高。 響應比響應比RpRp= =（等待時間服務時間）（等待時間服務時間）/ /服務時間服務時間 作為優(yōu)作為優(yōu)先權先權 優(yōu)點：長短兼顧優(yōu)點：長短兼顧 缺點：需計算缺點：需計算RpRpv 3.3.高響應比優(yōu)先算法：高響應比優(yōu)先算法： 特點：特點： 響應比響應比RpRp= =（tw+tstw+ts）/ts/ts（ （1 1）短作業(yè)）短作業(yè)R RP P大。大。（ （2 2）tsts（要求服務時間）相同的進程間相當于（要求服務時間）相同的進程間相當于FCFSFCFS。（ （3 3）長作業(yè)等待一段時間仍能得到服

10、務。）長作業(yè)等待一段時間仍能得到服務。v 1.1.時間片輪轉(zhuǎn)時間片輪轉(zhuǎn) 時間片大小的確定時間片大小的確定 太大：退化為太大：退化為FCFSFCFS； 太小：系統(tǒng)開銷過大太?。合到y(tǒng)開銷過大 系統(tǒng)對響應時間的要求；系統(tǒng)對響應時間的要求；T=nqT=nq 就緒隊列中進程的數(shù)目；就緒隊列中進程的數(shù)目； 系統(tǒng)的處理能力：（應保證一個時間片處理完常用命令）系統(tǒng)的處理能力：（應保證一個時間片處理完常用命令）v 2.2.多級反饋隊列調(diào)度多級反饋隊列調(diào)度 特點：長、短作業(yè)兼顧，有較好的響應時間特點：長、短作業(yè)兼顧，有較好的響應時間 （1 1）短作業(yè)一次完成；）短作業(yè)一次完成； （2 2）中型作業(yè)周轉(zhuǎn)時間不長；）

11、中型作業(yè)周轉(zhuǎn)時間不長； （3 3）大型作業(yè)不會長期不處理。）大型作業(yè)不會長期不處理。就緒隊列就緒隊列1 1至至CPUS1就緒隊列就緒隊列2 2S2至至CPU就緒隊列就緒隊列3 3S3至至CPU就緒隊列就緒隊列n nSn至至CPU時間片：時間片：S1S2S3圖圖35多級隊列反饋調(diào)度算法多級隊列反饋調(diào)度算法v 3 3.3.1.3.1實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件1 1 提供必要的調(diào)度信息提供必要的調(diào)度信息 （1 1）就緒時間；）就緒時間； （2 2）開始）開始/ /完成截止時間；完成截止時間； （3 3）處理時間；）處理時間； （4 4）資源要求；）資源要求； （5 5）優(yōu)先級；）優(yōu)

12、先級；2 2 系統(tǒng)處理能力強系統(tǒng)處理能力強NPCPCmiiimiii111Ci為處理時間，為處理時間，Pi為周期時間（基于周期性實時任務）為周期時間（基于周期性實時任務）v 3 3.3.1.3.1實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件.3 3.采用搶占調(diào)度方式采用搶占調(diào)度方式 剝奪方式：一般都采用此剝奪方式：一般都采用此 非剝奪方式（實現(xiàn)簡單）：一般應使實時任務較小，非剝奪方式（實現(xiàn)簡單）：一般應使實時任務較小，以及時放棄以及時放棄CPUCPU。.4 4.具有快速切換機制具有快速切換機制 具有快速響應外部中斷能力。具有快速響應外部中斷能力。 快速任務分派快速任務分派v 1 1非搶占式調(diào)度

13、算法非搶占式調(diào)度算法 時間片輪轉(zhuǎn)時間片輪轉(zhuǎn) 秒級秒級 非搶占優(yōu)先權（協(xié)同）非搶占優(yōu)先權（協(xié)同） 秒秒 毫秒級毫秒級v 2 2搶占式調(diào)度算法搶占式調(diào)度算法 時鐘中斷搶占優(yōu)先權時鐘中斷搶占優(yōu)先權 毫秒級毫秒級 基于搶占點搶占基于搶占點搶占 立即搶占立即搶占immediate preemption immediate preemption 毫秒毫秒 微秒級微秒級 只要不在臨界區(qū)即搶占（中斷引發(fā)）只要不在臨界區(qū)即搶占（中斷引發(fā)）進程1進程2進程n實時進程調(diào)度時間調(diào)度時間實時進程要求調(diào)度實時進程要求調(diào)度調(diào)度實時進程運行調(diào)度實時進程運行a 非搶占輪轉(zhuǎn)調(diào)度非搶占輪轉(zhuǎn)調(diào)度當前進程實時進程實時進程要求調(diào)度實時進

14、程要求調(diào)度當前進程運行完成當前進程運行完成b 非搶占優(yōu)先權調(diào)度非搶占優(yōu)先權調(diào)度調(diào)度時間調(diào)度時間c 基于時鐘中斷搶占的優(yōu)先權搶占調(diào)度基于時鐘中斷搶占的優(yōu)先權搶占調(diào)度當前進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度搶占時刻（其它中斷）搶占時刻（其它中斷）b 立即搶占優(yōu)先權調(diào)度立即搶占優(yōu)先權調(diào)度當前進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度時鐘中斷到達時時鐘中斷到達時調(diào)度時間調(diào)度時間調(diào)度時間調(diào)度時間v 1.1.最早截止時間優(yōu)先最早截止時間優(yōu)先EDFEDF（earliest deadline first)earliest deadline first)算算法法 根據(jù)任務的截止時間來確定任務的優(yōu)先級根

15、據(jù)任務的截止時間來確定任務的優(yōu)先級 截止時間越早，優(yōu)先級越高截止時間越早，優(yōu)先級越高 可以是搶占式或非搶占式可以是搶占式或非搶占式1342134212 34t開始截止時間開始截止時間任務到達任務到達任務執(zhí)行任務執(zhí)行圖圖37 EDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式v 松弛度：松弛度： 若若A A進程進程需在需在200ms200ms時完成，其本身運行需要時完成，其本身運行需要100ms100ms，當，當前時刻是前時刻是10ms10ms，則，則A A的松弛度為：的松弛度為：20020010010010109090 主要用于可搶占的調(diào)度方式中主要用于可搶占的調(diào)度方式中 例：例：A1A2A3

16、A4A5A6A7A8B1B2B3020406080 100120 140160t圖圖38 A/B任務每次必須完成的時間任務每次必須完成的時間A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8v 1.1.緊密耦合緊密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS 緊密耦合緊密耦合 共享共享RAMRAM和和I/OI/O 高速總線和交叉開關連接高速總線和交叉開關連接 松弛耦合松弛耦合 獨立獨立RAMRAM和和I/OI/O 通道和通信線路連接通道和通信線路連接v 2.2.對稱多處理

17、器系統(tǒng)和非對稱多處理器系統(tǒng)對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng) 處理器是否結構相同處理器是否結構相同v 1.1.SMPSMP中進程分配方式中進程分配方式 靜態(tài)分配靜態(tài)分配 動態(tài)分配動態(tài)分配 可防止系統(tǒng)中多個處理器忙閑不均可防止系統(tǒng)中多個處理器忙閑不均v 2.2.非非SMPSMP中進程分配方式中進程分配方式 進程調(diào)度在主處理器上執(zhí)行進程調(diào)度在主處理器上執(zhí)行 有潛在的不可靠性有潛在的不可靠性 v 1.1.自調(diào)度自調(diào)度 各個處理機自行在就緒隊列中取任務。各個處理機自行在就緒隊列中取任務。 特點；簡單，分布式調(diào)度，調(diào)度算法可采用特點；簡單，分布式調(diào)度，調(diào)度算法可采用前述方法，多個前述方法，多個CPUC

18、PU利用率都不錯（不會閑）利用率都不錯（不會閑） 但：但： 瓶頸問題，（單隊列）瓶頸問題，（單隊列） 低效性；（需拷貝現(xiàn)場）低效性；（需拷貝現(xiàn)場） 線程切換頻繁（當線程合作時線程切換頻繁（當線程合作時, ,各線程并各線程并行的條件不容易滿足）行的條件不容易滿足） v 優(yōu)點：優(yōu)點：（1 1）對相互合作的進（線）程組調(diào)度，可以減小切換，）對相互合作的進（線）程組調(diào)度，可以減小切換，減小系統(tǒng)開銷。減小系統(tǒng)開銷。（2 2）每次分配一組）每次分配一組CPUCPU，減少了調(diào)度頻率。，減少了調(diào)度頻率。v 分配時間分配時間（1 1）面向程序）面向程序（2 2）面向線程：使處理機利用率更高。）面向線程：使處理機

19、利用率更高。 應用程序應用程序A應用程應用程序序BCpu1線程線程1線程線程1Cpu2線程線程2空閑空閑Cpu3線程線程3空閑空閑Cpu4線程線程4空閑空閑時間時間1/21/2浪費浪費37.5%應用程序應用程序A應用程應用程序序BCpu1線程線程1線程線程1Cpu2線程線程2空閑空閑Cpu3線程線程3空閑空閑Cpu4線程線程4空閑空閑時間時間4/51/5浪費浪費15%v 引入：多處理機系統(tǒng)，每個處理已不再屬寶貴資源。引入：多處理機系統(tǒng)，每個處理已不再屬寶貴資源。v 特點：每個進（線）程專用處理機，使其切換小，特點：每個進（線）程專用處理機，使其切換小，提高效率。提高效率。v 主要用于大型計算，

20、實時系統(tǒng)主要用于大型計算，實時系統(tǒng)v 3 3.5.5.1.1產(chǎn)生死鎖的原因。產(chǎn)生死鎖的原因。v 一、競爭資源引起死鎖。一、競爭資源引起死鎖。1 1 可剝奪（可剝奪（CPUCPU、內(nèi)存，）和非剝奪性（打印機，磁、內(nèi)存，）和非剝奪性（打印機，磁帶機）資源帶機）資源2 2 競爭非剝奪性資源競爭非剝奪性資源可造成死鎖可造成死鎖 p1p2R1R2v 3 3競爭臨時性資源競爭臨時性資源 臨時性資源是指由一個進程產(chǎn)生，被另一個進程使用臨時性資源是指由一個進程產(chǎn)生，被另一個進程使用一段時間后便無用的資源。一段時間后便無用的資源。213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)

21、P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R2)4v 1 1互斥條件（資源的臨界性）互斥條件（資源的臨界性）v 2 2請求和保持條件請求和保持條件v 3 3不剝奪條件不剝奪條件v 4 4環(huán)路等待環(huán)路等待v 1 1預防；破壞預防；破壞4 4個條件之一：有效，使資源個條件之一：有效，使資源利用率低。利用率低。v 2 2避免：防止進入不安全態(tài)。避免：防止進入不安全態(tài)。v 3 3檢測：檢測到死鎖再清除。檢測：檢測到死鎖再清除。v 4 4解除：與解除：與“檢檢”配套。配套。v 3.6.1 3.6.1 死鎖預防死鎖預防 一、互斥條件是資源固有屬性，不能避免。一、互斥條件是資源固有

22、屬性，不能避免。 二、摒棄請求和保持條件二、摒棄請求和保持條件全分配，全釋放（全分配，全釋放（ANDAND）缺點：（缺點：（1 1）延遲進程運行）延遲進程運行（2 2）資源嚴重浪費）資源嚴重浪費 三、摒棄三、摒棄“不剝奪不剝奪”條件條件增加系統(tǒng)開銷，且進程前段工作可能失效。增加系統(tǒng)開銷，且進程前段工作可能失效。v 3.6.1 3.6.1 死鎖預防死鎖預防 四、摒棄四、摒棄“環(huán)路環(huán)路”條件條件有序資源分配法：為資源編號，申請時需按編號進有序資源分配法：為資源編號，申請時需按編號進行。行。缺點：缺點：（1 1）新增資源不便，（原序號已排定）新增資源不便，（原序號已排定）（2 2）用戶不自由）用戶不

23、自由（3 3）資源與進程使用順序不同造成浪費）資源與進程使用順序不同造成浪費v在在“避免死鎖避免死鎖”方法中的判斷條件方法中的判斷條件 v1. 1. 安全狀態(tài)安全狀態(tài)按某種順序并發(fā)進程都能達到獲得最大資源而順序按某種順序并發(fā)進程都能達到獲得最大資源而順序完成的序列為安全序列。完成的序列為安全序列。能找到安全序列的狀態(tài)為安全狀態(tài)。能找到安全序列的狀態(tài)為安全狀態(tài)。v2.2.安全狀態(tài)例安全狀態(tài)例進程進程最大需求最大需求已分配已分配可用可用P11053P242P392安全序列：安全序列：p2p2p1p1p3 p3 v3 3安全安全不安全的轉(zhuǎn)換不安全的轉(zhuǎn)換 上例中，若上例中，若P3P3再申請一臺，則不安

24、全再申請一臺，則不安全 進程進程最大需求最大需求已分配已分配可用可用P11052P242P393v 1 1數(shù)據(jù)結構數(shù)據(jù)結構 availablejavailablej=k: =k: 系統(tǒng)現(xiàn)有系統(tǒng)現(xiàn)有RjRj類資源類資源k k個；個； maxi,jmaxi,j=k: =k: 進程進程i i需要需要RjRj的最大數(shù)的最大數(shù)k k個；個； alloci,jalloci,j=k: =k: 進程進程i i已得到已得到RjRj類資源類資源k k個；個； needi,jneedi,j=k:=k: 進程進程i i需要需要RjRj類資源類資源k k個個 有：有：needi,j= maxi,jneedi,j= ma

25、xi,j alloci,jalloci,j requestirequesti進程進程i i請求資源數(shù)請求資源數(shù) workiworki：進程：進程i i執(zhí)行完后系統(tǒng)應有資源數(shù)（也即可用數(shù)）執(zhí)行完后系統(tǒng)應有資源數(shù)（也即可用數(shù)） finishifinishi ：布爾量，表進程：布爾量，表進程i i能否順序完成。能否順序完成。 v 2 2銀行家算法銀行家算法 reqi=needierrorreqi=availiblockavail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinis

26、hi=.T. Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3 0 1 0 7 4 3 3 3 2(2 3 0) p1 3 2 2 2 0 0(3 0 2) 1 2 2(0 2 0) p2 9 0 2 3 0 2 6 0 0 p3 2 2 2 2 1 1 0 1 1 p4 4 3 3 0 0 2 4 3 1T0時刻的資源分配表時刻的資源分配表Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 3 3 2 1 2 2 2 0 0 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p2 7 4 5 6 0 0 3 0 2 1