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

第十講處理機(jī)調(diào)度算法、實時調(diào)度2023/2/315:27本次課程主要內(nèi)容調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法實時調(diào)度實時調(diào)度算法的分類常用的幾種實時調(diào)度算法2023/2/315:2722023/2/315:273job1job2job3…..外存內(nèi)存Process1Process2Process3…..CPU處理機(jī)處理機(jī)調(diào)度：Pro1Pro2Pro3…..作業(yè)掛起進(jìn)程作業(yè)調(diào)度算法中級調(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)確估計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)度算法，還可用于實時系統(tǒng)中。2023/2/315:276用于作業(yè)調(diào)度時：從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時：該算法是把處理機(jī)分配給就緒隊列中優(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)程對資源的需求、用戶要求靜態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)描述創(chuàng)建時確定，0～7或0～255中的某一整數(shù)可以隨進(jìn)程的推進(jìn)或隨其等待時間的增加而改變的優(yōu)點(diǎn)簡單易行，系統(tǒng)開銷小能夠防止作業(yè)（進(jìn)程）餓死缺點(diǎn)不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)(進(jìn)程)長期沒有被調(diào)度的情況。實現(xiàn)相對復(fù)雜，動態(tài)計算優(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)先級隨著等待時間的增加而以速率a提高，作業(yè)在等待一定的時間后，必然有機(jī)會分配到處理機(jī)。2023/2/315:279由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：

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

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

時

調(diào)

度

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

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

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

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

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

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

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

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

2023/2/315:2723

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

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

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