操作系統(tǒng)第10講new

第十講處理機(jī)調(diào)度算法、實(shí)時(shí)調(diào)度2023/2/315:27本次課程主要內(nèi)容調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度算法的分類常用的幾種實(shí)時(shí)調(diào)度算法2023/2/315:2722023/2/315:273job1job2job3…..外存內(nèi)存Process1Process2Process3…..CPU處理機(jī)處理機(jī)調(diào)度：Pro1Pro2Pro3…..作業(yè)掛起進(jìn)程作業(yè)調(diào)度算法中級(jí)調(diào)度進(jìn)程調(diào)度算法2023/2/315:274調(diào)度算法比較：FCFSSJ(P)F優(yōu)點(diǎn)有利于長作業(yè)（進(jìn)程）有利于短作業(yè)（進(jìn)程）缺點(diǎn)不利于短作業(yè)（進(jìn)程）算法未考慮作業(yè)（進(jìn)程）緊迫程度不利于長作業(yè)（進(jìn)程）算法未考慮作業(yè)（進(jìn)程）緊迫程度作業(yè)長短難以準(zhǔn)確估計(jì)2023/2/315:2753.3.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)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度算法，還可用于實(shí)時(shí)系統(tǒng)中。2023/2/315:276用于作業(yè)調(diào)度時(shí)：從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時(shí)：該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程job1job2job3…..外存內(nèi)存Process1Process2Process3…..CPU處理機(jī)作業(yè)作業(yè)調(diào)度算法進(jìn)程調(diào)度算法(1)非搶占式優(yōu)先權(quán)算法(2)搶占式優(yōu)先權(quán)調(diào)度算法

優(yōu)先權(quán)調(diào)度算法:2023/2/315:277優(yōu)先權(quán)的類型:優(yōu)先權(quán)確定的依據(jù)：進(jìn)程類型、進(jìn)程對(duì)資源的需求、用戶要求靜態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)描述創(chuàng)建時(shí)確定，0～7或0～255中的某一整數(shù)可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的優(yōu)點(diǎn)簡(jiǎn)單易行，系統(tǒng)開銷小能夠防止作業(yè)（進(jìn)程）餓死缺點(diǎn)不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)(進(jìn)程)長期沒有被調(diào)度的情況。實(shí)現(xiàn)相對(duì)復(fù)雜，動(dòng)態(tài)計(jì)算優(yōu)先權(quán)有一定的系統(tǒng)開銷2023/2/315:2782．高響應(yīng)比優(yōu)先調(diào)度算法在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運(yùn)行得不到保證。如果使作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率a提高，作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理機(jī)。2023/2/315:279由于等待時(shí)間與服務(wù)時(shí)間之和就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：

思考：優(yōu)先權(quán)會(huì)產(chǎn)生怎樣的動(dòng)態(tài)變化？2023/2/315:27103.3.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1．時(shí)間片輪轉(zhuǎn)法

1)基本原理內(nèi)存Process1Process2Process3…..CPU處理機(jī)時(shí)間片輪轉(zhuǎn)調(diào)度算法幾ms到幾百ms時(shí)鐘中斷請(qǐng)求2023/2/315:27112)時(shí)間片大小的確定在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響，如選擇很小的時(shí)間片將有利于短作業(yè)，因?yàn)樗茌^快地完成，但會(huì)頻繁地發(fā)生中斷、進(jìn)程上下文的切換，從而增加系統(tǒng)的開銷；反之，如選擇太長的時(shí)間片，使得每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成，時(shí)間片輪轉(zhuǎn)算法便退化為FCFS算法，無法滿足交互式用戶的需求。一個(gè)較為可取的大小是，時(shí)間片略大于一次典型的交互所需要的時(shí)間。這樣可使大多數(shù)進(jìn)程在一個(gè)時(shí)間片內(nèi)完成。2023/2/315:2712q=1和q=4時(shí)的進(jìn)程運(yùn)行情況2023/2/315:2713q=1和q=4時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間思考：什么類型的系統(tǒng)采用時(shí)間片輪轉(zhuǎn)調(diào)度算法？2023/2/315:27142．多級(jí)反饋隊(duì)列調(diào)度算法2023/2/315:27153．多級(jí)反饋隊(duì)列調(diào)度算法的性能(1)終端型作業(yè)用戶(2)短批處理作業(yè)用戶(3)長批處理作業(yè)用戶3.4實(shí)

時(shí)

調(diào)

度

2023/2/315:27163.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1．提供必要的信息為了實(shí)現(xiàn)實(shí)時(shí)調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述一些信息：

(1)就緒時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始時(shí)間，在周期任務(wù)的情況下，它就是事先預(yù)知的一串時(shí)間序列；而在非周期任務(wù)的情況下，它也可能是預(yù)知的。

2023/2/315:2717(2)開始截止時(shí)間和完成截止時(shí)間。對(duì)于典型的實(shí)時(shí)應(yīng)用，只須知道開始截止時(shí)間，或者知道完成截止時(shí)間。(3)處理時(shí)間。這是指一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)間。在某些情況下，該時(shí)間也是系統(tǒng)提供的。

(4)資源要求。這是指任務(wù)執(zhí)行時(shí)所需的一組資源。

(5)優(yōu)先級(jí)。如果某任務(wù)的開始截止時(shí)間已經(jīng)錯(cuò)過，就會(huì)引起故障，則應(yīng)為該任務(wù)賦予“絕對(duì)”優(yōu)先級(jí)；如果開始截止時(shí)間的推遲對(duì)任務(wù)的繼續(xù)運(yùn)行無重大影響，則可為該任務(wù)賦予“相對(duì)”優(yōu)先級(jí)，供調(diào)度程序參考。

2023/2/315:27182．系統(tǒng)處理能力強(qiáng)在實(shí)時(shí)系統(tǒng)中，通常都有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：

2023/2/315:2719系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是50ms，而每次的處理時(shí)間為10ms，則不難算出，此時(shí)是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。2023/2/315:27203．采用搶占式調(diào)度機(jī)制在含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)制。當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿足該硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。2023/2/315:27214．具有快速切換機(jī)制為保證要求較高的硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)行，在實(shí)時(shí)系統(tǒng)中還應(yīng)具有快速切換機(jī)制，以保證能進(jìn)行任務(wù)的快速切換。2023/2/315:27223.4.2實(shí)時(shí)調(diào)度算法的分類1．非搶占式調(diào)度算法

1)非搶占式輪轉(zhuǎn)調(diào)度算法該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺(tái)計(jì)算機(jī)控制若干個(gè)相同的(或類似的)對(duì)象，為每一個(gè)被控對(duì)象建立一個(gè)實(shí)時(shí)任務(wù)，并將它們排成一個(gè)輪轉(zhuǎn)隊(duì)列。調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)投入運(yùn)行。當(dāng)該任務(wù)完成后，便把它掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行，而調(diào)度程序再選擇下一個(gè)(隊(duì)首)任務(wù)運(yùn)行。這種調(diào)度算法可獲得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間，可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)中。

2023/2/315:2723

2)非搶占式優(yōu)先調(diào)度算法如果在實(shí)時(shí)系統(tǒng)中存在著要求較為嚴(yán)格(響應(yīng)時(shí)間為數(shù)百毫秒)的任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法為這些任務(wù)賦予較高的優(yōu)先級(jí)。當(dāng)這些實(shí)時(shí)任務(wù)到達(dá)時(shí)，把它們安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后才能被調(diào)度執(zhí)行。這種調(diào)度算法在做了精心的處理后，有可能獲得僅為數(shù)秒至數(shù)百毫秒級(jí)的響應(yīng)時(shí)間，因而可用于有一定要求的實(shí)時(shí)控制系統(tǒng)中。2023/2/315:27242．搶占式調(diào)度算法在要求較嚴(yán)格的(響應(yīng)時(shí)間為數(shù)十毫秒以下)的實(shí)時(shí)系統(tǒng)中，應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法?？筛鶕?jù)搶占發(fā)生時(shí)間的不同而進(jìn)一步分成以下兩種調(diào)度算法。1)基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法在某實(shí)時(shí)任務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)的優(yōu)先級(jí)，這時(shí)并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來時(shí)，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先權(quán)任務(wù)。2023/2/315:2725這種調(diào)度算法能獲得較好的響應(yīng)效果，其調(diào)度延遲可降為幾十毫秒至幾毫秒。因此，此算法可用于大多數(shù)的實(shí)時(shí)系統(tǒng)中。2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法在這種調(diào)度策略中，要求操作系統(tǒng)具有快速響應(yīng)外部事件中斷的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)。這種算法能獲得非?？斓捻憫?yīng)，可把調(diào)度延遲降低到幾毫秒至100微秒，甚至更低。2023/2/315:27262023/2/315:27273.4.3常用的幾種實(shí)時(shí)調(diào)度算法

1．最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算法該算法是根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間愈早，其優(yōu)先級(jí)愈高。該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的早晚排序；當(dāng)然，具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序在選擇任務(wù)時(shí)，總是選擇就緒隊(duì)列中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。最早截止時(shí)間優(yōu)先算法既可用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。2023/2/315:27281)非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)圖3-9

EDF算法用于非搶占調(diào)度的調(diào)度方式2023/2/315:27292．最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。例如，一個(gè)任務(wù)在200ms時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間就有100ms，因此，調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100ms。又如，另一任務(wù)在400ms時(shí)必須完成，它本身需要運(yùn)行150ms，則其松弛程度為2