07處理機(jī)調(diào)度講解課件

Page12023/7/22第三章處理機(jī)調(diào)度與死鎖錢斌dnhistory@Page22023/7/22處理機(jī)調(diào)度

1.調(diào)度的基本概念

2.調(diào)度時(shí)機(jī)、切換與過程

3.調(diào)度的基本準(zhǔn)則

4.調(diào)度方式

5.典型調(diào)度算法先來先服務(wù)調(diào)度算法;短作業(yè)(短進(jìn)程、短線程)優(yōu)先調(diào)度算法;時(shí)間片輪轉(zhuǎn)調(diào)度算法;優(yōu)先級(jí)調(diào)度算法;高響應(yīng)比優(yōu)先調(diào)度算法;多級(jí)反饋隊(duì)列調(diào)度算法。Page32023/7/22死鎖

1.死鎖的概念

2.死鎖處理策略

3.死鎖預(yù)防

4.死鎖避免系統(tǒng)安全狀態(tài)：銀行家算法。

5.死鎖檢測和解除Page42023/7/22第三章處理機(jī)調(diào)度與死鎖重點(diǎn)掌握進(jìn)程調(diào)度算法，各適用于何種情況

理解常用的幾種實(shí)時(shí)調(diào)度算法

理解產(chǎn)生死鎖的原因

掌握銀行家算法避免死鎖難點(diǎn)多道程序設(shè)計(jì)中的各種調(diào)度算法

響應(yīng)比高者優(yōu)先調(diào)度算法的計(jì)算過程

銀行家算法

Page52023/7/22第三章處理機(jī)調(diào)度與死鎖知識(shí)點(diǎn)處理機(jī)調(diào)度及調(diào)度算法多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法，死鎖的檢測與解除銀行家算法Page62023/7/22第三章處理機(jī)調(diào)度與死鎖處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源在多道程序環(huán)境下，進(jìn)程數(shù)目通常多于處理機(jī)的數(shù)目系統(tǒng)必須按一定方法動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程處理機(jī)利用率和系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間）在很大程度上取決于處理機(jī)調(diào)度分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問題之一。WHAT：按什么原則分配CPU—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU—進(jìn)程調(diào)度的時(shí)機(jī)

HOW：如何分配CPU—CPU調(diào)度過程（進(jìn)程的上下文切換）Page72023/7/22第三章處理機(jī)調(diào)度與死鎖

處理機(jī)調(diào)度的基本概念作業(yè)與作業(yè)調(diào)度算法進(jìn)程調(diào)度實(shí)時(shí)調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測與解除Page82023/7/22處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page92023/7/22處理機(jī)調(diào)度的基本概念作業(yè)是用戶在一次解題或一個(gè)事務(wù)處理過程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合，包括用戶程序、所需的數(shù)據(jù)及命令等作業(yè)的狀態(tài)：一個(gè)作業(yè)進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一般需要經(jīng)歷收容、運(yùn)行、完成三個(gè)階段，與之相對應(yīng)的是作業(yè)的三種狀態(tài)后備狀態(tài)運(yùn)行狀態(tài)完成狀態(tài)Page102023/7/22運(yùn)行狀態(tài)處理機(jī)調(diào)度的基本概念后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/O完成I/O請求時(shí)間片完作業(yè)注冊作業(yè)調(diào)度進(jìn)程調(diào)度終止作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換Page112023/7/223.1處理機(jī)調(diào)度的基本概念3.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度1.高級(jí)調(diào)度(HighScheduling)2.低級(jí)調(diào)度(LowLevelScheduling)3.中級(jí)調(diào)度(Intermediate-LevelScheduling)Page122023/7/22高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)調(diào)度(HighScheduling)

作業(yè)調(diào)度或長程調(diào)度（Long-TermScheduling）主要任務(wù)是按一定的原則對外存上處于后備狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)分配內(nèi)存、輸入/輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程，放入就緒隊(duì)列，以使該作業(yè)的進(jìn)程獲得競爭處理機(jī)的權(quán)利也稱為接納調(diào)度（AdmissionScheduling）高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天Page132023/7/22高級(jí)、中級(jí)和低級(jí)調(diào)度在每次作業(yè)調(diào)度時(shí)，須決定：接納多少個(gè)作業(yè)即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于多道程序度（DegreeofMultiprogramming）作業(yè)太多服務(wù)質(zhì)量下降作業(yè)太少資源利用率低接納哪些作業(yè)

取決于作業(yè)調(diào)度算法先來先服務(wù)短作業(yè)優(yōu)先作業(yè)優(yōu)先權(quán)調(diào)度響應(yīng)比調(diào)度→周轉(zhuǎn)時(shí)間太長→系統(tǒng)吞吐量太低

適當(dāng)?shù)恼壑远嗟莱绦蚨龋杭丛试S多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。周轉(zhuǎn)時(shí)間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。吞吐量：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。Page142023/7/22高級(jí)、中級(jí)和低級(jí)調(diào)度低級(jí)調(diào)度

進(jìn)程調(diào)度或短程調(diào)度（Short-TermScheduling）主要任務(wù)是按照某種策略和方法選取一個(gè)處于就緒狀態(tài)的進(jìn)程，將處理機(jī)分配給它常見的低級(jí)調(diào)度有非搶占式和搶占式兩種低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的頻繁使用，要求在實(shí)現(xiàn)時(shí)做到高效Page152023/7/22高級(jí)、中級(jí)和低級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-LevelScheduling)

中程調(diào)度(Medium-TermScheduling)引入目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待主要任務(wù)是按照給定的原則和策略，將處于外存對換區(qū)中的重又具備運(yùn)行條件的就緒進(jìn)程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進(jìn)程交換到外存對換區(qū)Page162023/7/22處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page172023/7/22進(jìn)程調(diào)度的任務(wù)

進(jìn)程調(diào)度的任務(wù)是控制、協(xié)調(diào)進(jìn)程對CPU的競爭,即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程Page182023/7/22處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)

確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page192023/7/22確定算法的原則

具有公平性資源利用率高（特別是CPU利用率）在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間（越短越好）在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量Page202023/7/22處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則

進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page212023/7/22進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMode)搶占方式(PreemptiveMode)Page222023/7/22處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式

調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page232023/7/22調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型Page242023/7/22調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完P(guān)age252023/7/22調(diào)度隊(duì)列模型進(jìn)程調(diào)度CPU進(jìn)程完成時(shí)間片完就緒隊(duì)列…12等待事件等待事件等待事件n12n事件出現(xiàn)事件出現(xiàn)…事件出現(xiàn)后備隊(duì)列作業(yè)調(diào)度……與上一模型的主要區(qū)別：就緒隊(duì)列的形式；設(shè)置多個(gè)阻塞隊(duì)列阻隊(duì)列塞2阻隊(duì)列塞n阻隊(duì)列塞1Page262023/7/22調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列進(jìn)程調(diào)度就緒，掛起隊(duì)列中級(jí)調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起掛起事件出現(xiàn)事件出現(xiàn)CPUPage272023/7/22處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，如何考慮？？如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，應(yīng)如何考慮？？Page282023/7/223.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則2.面向系統(tǒng)的準(zhǔn)則Page292023/7/223.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時(shí)間短。

(2)響應(yīng)時(shí)間快。(3)截止時(shí)間的保證。(4)優(yōu)先權(quán)準(zhǔn)則。Page302023/7/22選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短平均周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：進(jìn)程（或作業(yè)）的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS

。而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為:Page312023/7/22選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則響應(yīng)時(shí)間快響應(yīng)時(shí)間是指從用戶通過鍵盤提交一個(gè)請求開始，直至系統(tǒng)中首次產(chǎn)生響應(yīng)為止的時(shí)間交互式系統(tǒng)用周轉(zhuǎn)時(shí)間衡量不是最佳截止時(shí)間保證截止時(shí)間是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間截止時(shí)間是實(shí)時(shí)系統(tǒng)中的重要指標(biāo)Page322023/7/22選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則等待時(shí)間短等待時(shí)間是在就緒隊(duì)列中等待所花的時(shí)間調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行I/O的時(shí)間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi)的時(shí)間優(yōu)先權(quán)準(zhǔn)則在批處理、實(shí)時(shí)和分時(shí)系統(tǒng)中都可以選擇優(yōu)先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理有時(shí)還選擇搶占式調(diào)度方式Page332023/7/22選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響處理機(jī)利用率高各類資源的平衡利用使內(nèi)存、外存和I/O設(shè)備的利用率高基于這樣的準(zhǔn)則，你設(shè)計(jì)操作系統(tǒng)的調(diào)度策略應(yīng)如何？Page342023/7/22第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念

作業(yè)與作業(yè)調(diào)度算法進(jìn)程調(diào)度實(shí)時(shí)調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測與解除Page352023/7/22調(diào)度算法在OS中調(diào)度的實(shí)質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法問題提出如何制定分配策略：對不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的算法，如短作業(yè)優(yōu)先，時(shí)間片輪轉(zhuǎn)等有些算法適用于作業(yè)調(diào)度，有些適用于進(jìn)程調(diào)度，有些兩者皆可Page362023/7/22調(diào)度算法

先來先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page372023/7/22先來先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E044476先來先服務(wù)（先進(jìn)先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518tPage382023/7/22先來先服務(wù)和短作業(yè)優(yōu)先算法

先來先服務(wù)（先進(jìn)先出）優(yōu)缺點(diǎn)

比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）有利于CPU繁忙型作業(yè)（進(jìn)程），而不利于I/O繁忙型作業(yè)（進(jìn)程）用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng)Page392023/7/22先來先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E0441短作業(yè)/短進(jìn)程優(yōu)先（SJF/SPF）：4633/26988/391399/413181616/540/52.1AAAABBBCCCCCDDEEEE05101518tPage402023/7/22先來先服務(wù)和短作業(yè)優(yōu)先算法SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)對長作業(yè)不利。嚴(yán)重的是，若一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度——饑餓完全未考慮作業(yè)(進(jìn)程)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。Page412023/7/22調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page422023/7/22高優(yōu)先權(quán)優(yōu)先（HPF，HighestPriorityFirst）調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法③Page432023/7/22高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)Page442023/7/22進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間靜態(tài)優(yōu)先權(quán)開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均靜態(tài)優(yōu)先權(quán)，非搶占式（1為高優(yōu)先權(quán)）高優(yōu)先權(quán)優(yōu)先調(diào)度算法04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考慮一下?lián)屨际?，情況如何？Page452023/7/22高優(yōu)先權(quán)優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法（HRF）是FCFS和SJF的結(jié)合，克服了兩種算法的缺點(diǎn)調(diào)度策略：響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)因等待時(shí)間+服務(wù)時(shí)間=該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為④Page462023/7/22高優(yōu)先權(quán)優(yōu)先調(diào)度算法對HRF的小結(jié)等待時(shí)間相同的作業(yè)，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，要求服務(wù)的時(shí)間相同的作業(yè)，則等待時(shí)間愈長，其優(yōu)先權(quán)愈高，長作業(yè)，優(yōu)先權(quán)隨等待時(shí)間的增加而提高，其等待時(shí)間足夠長時(shí)，其優(yōu)先權(quán)便可升到很高，從而也可獲得處理機(jī)是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，又不會(huì)使長作業(yè)長期得不到服務(wù)。缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開銷——對短作業(yè)有利——是先來先服務(wù)——對長作業(yè)有利Page472023/7/22調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page482023/7/22基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E012349121517181515/41111/31616/566/21313/412.22.12若到達(dá)時(shí)間為0、1、2、3、4，又如何？Page492023/7/22多級(jí)反饋隊(duì)列調(diào)度算法設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長一倍，……，第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)隊(duì)列的時(shí)間片長一倍⑦Page502023/7/22就緒隊(duì)列1基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片：S1＜S2＜S3)調(diào)度方式高低優(yōu)先級(jí)時(shí)間片小大Sn按FIFO原則排隊(duì)等待調(diào)度尚未完成轉(zhuǎn)入第二隊(duì)列的末尾，按FIFO原則等待調(diào)度采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行因等待而放棄CPU后，進(jìn)入阻塞隊(duì)列，一旦等待的事件發(fā)生，則回到原來的就緒隊(duì)列Page512023/7/22進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢或由于某種錯(cuò)誤而終止運(yùn)行當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)（等待I/O）分時(shí)系統(tǒng)中時(shí)間片到當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式）例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)阻塞進(jìn)程變成就緒在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作（P操作，阻塞原語，喚醒原語）Page522023/7/22何時(shí)切換進(jìn)程只要OS取得對CPU的控制，進(jìn)程切換就可能發(fā)生:超級(jí)用戶調(diào)用來自程序的顯式請求(如：打開文件)，該進(jìn)程通常會(huì)被阻塞陷阱最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程移至退出狀態(tài)中斷外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移至IH（中斷處理程序）Page532023/7/22引起進(jìn)程調(diào)度的原因正在執(zhí)行的進(jìn)程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作如P操作、阻塞、掛起原語等；在可剝奪式調(diào)度中，有比當(dāng)前進(jìn)程優(yōu)先權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列；在時(shí)間片輪轉(zhuǎn)法中，時(shí)間片完。通常系統(tǒng)是按先來先服務(wù)或優(yōu)先權(quán)形式來組織調(diào)度隊(duì)列。Page542023/7/22第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念

作業(yè)和作業(yè)調(diào)度算法進(jìn)程調(diào)度實(shí)時(shí)調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測與解除3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1．提供必要的調(diào)度信息（1）就緒時(shí)間；（2）開始/完成截止時(shí)間；（3）處理時(shí)間；（4）資源要求；（5）優(yōu)先級(jí)；2．系統(tǒng)處理能力強(qiáng)3.4實(shí)時(shí)調(diào)度Ci為處理時(shí)間，Pi為周期時(shí)間（基于周期性實(shí)時(shí)任務(wù)）3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3.采用搶占調(diào)度方式剝奪方式：一般都采用此非剝奪方式（實(shí)現(xiàn)簡單）：一般應(yīng)使實(shí)時(shí)任務(wù)較小，以及時(shí)放棄CPU。4.具有快速切換機(jī)制具有快速響應(yīng)外部中斷能力?？焖偃蝿?wù)分派3.4實(shí)時(shí)調(diào)度3.4.2實(shí)時(shí)調(diào)度算法的分類1非搶占式調(diào)度算法時(shí)間片輪轉(zhuǎn) 秒級(jí)非搶占優(yōu)先權(quán)（協(xié)同） 秒~毫秒級(jí)2搶占式調(diào)度算法時(shí)鐘中斷搶占優(yōu)先權(quán) 毫秒級(jí)基于搶占點(diǎn)搶占立即搶占immediatepreemption毫秒~微秒級(jí)只要不在臨界區(qū)即搶占（中斷引發(fā)）進(jìn)程1進(jìn)程2進(jìn)程n實(shí)時(shí)進(jìn)程調(diào)度時(shí)間實(shí)時(shí)進(jìn)程要求調(diào)度調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行a非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成b非搶占優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間c基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度搶占時(shí)刻（其它中斷）b立即搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度時(shí)鐘中斷到達(dá)時(shí)調(diào)度時(shí)間調(diào)度時(shí)間3.4.3常用的幾種實(shí)時(shí)調(diào)度算法1.最早截止時(shí)間優(yōu)先EDF（earliestdeadlinefirst)算法根據(jù)任務(wù)的截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)截止時(shí)間越早，優(yōu)先級(jí)越高可以是搶占式或非搶占式最早截止時(shí)間優(yōu)先EDF例134213421234t開始截止時(shí)間任務(wù)到達(dá)任務(wù)執(zhí)行圖3－6EDF算法用于非搶占調(diào)度方式2.最低松弛度優(yōu)先LLF算法松弛度：若A進(jìn)程需在200ms時(shí)完成，其本身運(yùn)行需要100ms，當(dāng)前時(shí)刻是10ms，則A的松弛度為：200－100－10＝90主要用于可搶占的調(diào)度方式中例：A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t圖3－8A/B任務(wù)每次必須完成的時(shí)間最低松弛度優(yōu)先LLF算法(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8Page642023/7/223.5死鎖概述死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page652023/7/22死鎖的基本概念死鎖的概念指多個(gè)進(jìn)程因競爭共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。即：如果一組進(jìn)程中，每個(gè)進(jìn)程都在等待僅有該組進(jìn)程中其他進(jìn)程才能引發(fā)的事件，那么該組進(jìn)程就稱為死鎖進(jìn)程。Page662023/7/22死鎖的基本概念關(guān)于死鎖的一些結(jié)論參與死鎖的進(jìn)程最少是兩個(gè)

參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。Page672023/7/22產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page682023/7/22產(chǎn)生死鎖的原因競爭資源。當(dāng)系統(tǒng)中供多個(gè)進(jìn)程所共享的資源，不足以同時(shí)滿足它們的需要時(shí)，引起它們對資源的競爭而產(chǎn)生死鎖。

(2)進(jìn)程間推進(jìn)順序非法。

進(jìn)程在運(yùn)行過程中，請求和釋放資源的順序不當(dāng)，導(dǎo)致了進(jìn)程死鎖。

所謂死鎖（Deadlock），是指多個(gè)進(jìn)程因競爭資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。Page692023/7/22產(chǎn)生死鎖的原因競爭資源引起進(jìn)程死鎖可剝奪和非剝奪性資源可剝奪性資源是指進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪，如處理機(jī)、內(nèi)存等非剝奪性資源是指當(dāng)系統(tǒng)把這類資源分配給某個(gè)進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放，如磁帶機(jī)、打印機(jī)等競爭非剝奪性資源系統(tǒng)中的非剝奪性資源由于數(shù)量有限而不能滿足進(jìn)程運(yùn)行的需要，進(jìn)程在運(yùn)行過程中因爭奪這些資源而限入僵局競爭臨時(shí)性資源Page702023/7/22產(chǎn)生死鎖的原因I/O設(shè)備共享時(shí)的死鎖情況

若系統(tǒng)中只有一臺(tái)打印機(jī)R1和一臺(tái)讀卡機(jī)R2，可供進(jìn)程P1和P2共享。若形成環(huán)路，這樣會(huì)產(chǎn)生死鎖。R1R2P1P2分配分配請求請求Page712023/7/22產(chǎn)生死鎖的原因

進(jìn)程之間通信時(shí)的死鎖S2P1S3P3S1P2產(chǎn)生P2產(chǎn)生P3產(chǎn)生要求接收要求接收要求接收Page722023/7/22產(chǎn)生死鎖的原因進(jìn)程推進(jìn)順序不當(dāng)引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D不安全區(qū)Page732023/7/22產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page742023/7/22產(chǎn)生死鎖的必要條件互斥條件

進(jìn)程對所分配到的資源進(jìn)行排它性的使用請求和保持條件

進(jìn)程已經(jīng)至少保持了一個(gè)資源，但又提出了新的資源請求，而該資源又已被其他進(jìn)程占有不剝奪條件

進(jìn)程已獲得的資源在未使用完之前不能被剝奪環(huán)路等待條件在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程--資源循環(huán)等待的環(huán)形鏈Page752023/7/22產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page762023/7/22處理死鎖的基本方法預(yù)防死鎖避免死鎖檢測死鎖解除死鎖Page772023/7/22第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念

作業(yè)與作業(yè)調(diào)度算法進(jìn)程調(diào)度實(shí)時(shí)調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測與解除Page782023/7/223.6預(yù)防死鎖摒棄“請求和保持”條件所有進(jìn)程在開始運(yùn)行之前必須一次性的申請整個(gè)運(yùn)行過程所需的全部資源簡單、易于實(shí)現(xiàn)、安全資源浪費(fèi)嚴(yán)重進(jìn)程延遲運(yùn)行Page792023/7/22預(yù)防死鎖摒棄“不剝奪”條件進(jìn)程逐個(gè)地申請所需資源當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程申請新資源而不能得到滿足時(shí)，必須放棄所有已保持的資源實(shí)現(xiàn)復(fù)雜、代價(jià)高昂延長了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)開銷，降低了系統(tǒng)的吞吐量Page802023/7/22預(yù)防死鎖摒棄“環(huán)路等待”條件系統(tǒng)將所有資源按類型分配序號(hào)并排隊(duì)所有進(jìn)程申請資源必須按序號(hào)遞增的順序資源利用率和系統(tǒng)吞吐量較高但在資源管理和資源申請方面仍有問題Page812023/7/223.7避免死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖Page822023/7/22產(chǎn)生死鎖的原因進(jìn)程推進(jìn)順序不當(dāng)引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④DPage832023/7/22系統(tǒng)安全狀態(tài)安全狀態(tài)在避免死鎖的方法中，允許進(jìn)程動(dòng)態(tài)地申請資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，令進(jìn)程等待所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)Page842023/7/223.7.2利用銀行家算法避免死鎖1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。

Page852023/7/22(2)最大需求矩陣Max。這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對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ù)。Need[i,j]=Max[i,j]–Allocation[i,j]Page862023/7/22

2.銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti[j]=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：

(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須等待。Page872023/7/22(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)程Pi等待。Page882023/7/224.銀行家算法之例

假定系統(tǒng)中有五個(gè)進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖3-15所示。圖3-15T0時(shí)刻的資源分配表2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeed[i,j]=Max[i,j]–Allocation[i,j]Page892023/7/22(1)T0時(shí)刻的安全性：圖3-16T0時(shí)刻的安全序列truetruetruetruetrueFinish77532C54443B02210C10010B30112