第十講處理機調(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處理機處理機調(diào)度：Pro1Pro2Pro3…..作業(yè)掛起進程作業(yè)調(diào)度算法中級調(diào)度進程調(diào)度算法2023/2/315:274調(diào)度算法比較：FCFSSJ(P)F優(yōu)點有利于長作業(yè)（進程）有利于短作業(yè)（進程）缺點不利于短作業(yè)（進程）算法未考慮作業(yè)（進程）緊迫程度不利于長作業(yè)（進程）算法未考慮作業(yè)（進程）緊迫程度作業(yè)長短難以準確估計2023/2/315:2753.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1．優(yōu)先權(quán)調(diào)度算法的類型為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進程調(diào)度算法，還可用于實時系統(tǒng)中。2023/2/315:276用于作業(yè)調(diào)度時：從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當用于進程調(diào)度時：該算法是把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程job1job2job3…..外存內(nèi)存Process1Process2Process3…..CPU處理機作業(yè)作業(yè)調(diào)度算法進程調(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ù)：進程類型、進程對資源的需求、用戶要求靜態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)描述創(chuàng)建時確定，0～7或0～255中的某一整數(shù)可以隨進程的推進或隨其等待時間的增加而改變的優(yōu)點簡單易行，系統(tǒng)開銷小能夠防止作業(yè)（進程）餓死缺點不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)(進程)長期沒有被調(diào)度的情況。實現(xiàn)相對復雜，動態(tài)計算優(yōu)先權(quán)有一定的系統(tǒng)開銷2023/2/315:2782．高響應比優(yōu)先調(diào)度算法在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運行得不到保證。如果使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a提高，作業(yè)在等待一定的時間后，必然有機會分配到處理機。2023/2/315:279由于等待時間與服務時間之和就是系統(tǒng)對該作業(yè)的響應時間，故該優(yōu)先權(quán)又相當于響應比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處理機時間片輪轉(zhuǎn)調(diào)度算法幾ms到幾百ms時鐘中斷請求2023/2/315:27112)時間片大小的確定在時間片輪轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很大的影響，如選擇很小的時間片將有利于短作業(yè)，因為它能較快地完成，但會頻繁地發(fā)生中斷、進程上下文的切換，從而增加系統(tǒng)的開銷；反之，如選擇太長的時間片，使得每個進程都能在一個時間片內(nèi)完成，時間片輪轉(zhuǎn)算法便退化為FCFS算法，無法滿足交互式用戶的需求。一個較為可取的大小是，時間片略大于一次典型的交互所需要的時間。這樣可使大多數(shù)進程在一個時間片內(nèi)完成。2023/2/315:2712q=1和q=4時的進程運行情況2023/2/315:2713q=1和q=4時進程的周轉(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)應向調(diào)度程序提供有關(guān)任務的下述一些信息：

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

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

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

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

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

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

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

2023/2/315:2723

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

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

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