一．處理機調(diào)度相關(guān)基本概念

????????處理機調(diào)度：多道程序環(huán)境下，動態(tài)的把處理機分配給就緒隊列中的一個進程使之執(zhí)行软啼。

????????提高處理機的利用率桑谍、改善系統(tǒng)性能，很大程度上取決于處理機調(diào)度的性能祸挪。

????????處理機調(diào)度便成為OS設(shè)計的中心問題之一锣披。分配的任務(wù)由處理機調(diào)度程序完成。

????????作業(yè)進入系統(tǒng)駐留在外存的后備隊列上贿条，再至調(diào)入內(nèi)存運行完畢雹仿，可能要經(jīng)歷下述三級調(diào)度。

????????????????1整以、高級調(diào)度（High Scheduling）

????????????????????????又稱作業(yè)調(diào)度或長程調(diào)度(Long-Term Scheduling),接納調(diào)度(Admission Scheduling)

? ????????????????????????主要在早期批處理階段胧辽，處理在外存上的作業(yè)。

?????????????????????????????????決定外存后備隊列中的哪些作業(yè)調(diào)入內(nèi)存;

?????????????????????????????????為它們創(chuàng)建進程公黑、分配必要的資源;

?????????????????????????????????將新創(chuàng)建的進程排在就緒隊列上邑商，準(zhǔn)備執(zhí)行。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? *管理的方面比較多凡蚜。

????????????????????????作業(yè)調(diào)度決定的細節(jié)

????????????????????????????????在每次執(zhí)行作業(yè)調(diào)度時奠骄，都須作出兩個決定：

????????????????????????????????????????接納多少作業(yè)——取決于多道程序度。應(yīng)根據(jù)系統(tǒng)的規(guī)模和運行速度等情況綜合考慮番刊。

????????????????????????????????????????接納哪些作業(yè)——取決于采用的調(diào)度算法含鳞。如先來先服務(wù)，短作業(yè)優(yōu)先等（后面詳細介紹）

????????????????????????系統(tǒng)運行并不一定存在高級調(diào)度

????????????????????????????????批處理系統(tǒng)：作業(yè)進入系統(tǒng)后先駐留外存芹务，故需要有作業(yè)調(diào)度蝉绷。

????????????????????????????????分時系統(tǒng)：為及時響應(yīng)鸭廷，作業(yè)由終端直接送入內(nèi)存，故不需作業(yè)調(diào)度熔吗。

????????????????????????????????實時系統(tǒng)中辆床，通常也不需作業(yè)調(diào)度。

????????????????2桅狠、低級調(diào)度（Low Level Scheduling）

????????????????????????也稱為進程調(diào)度讼载、微觀調(diào)度或短程調(diào)度（Short-Term Scheduling）

? ? ? ? ? ? ? ? ? ? ? ? ?決定內(nèi)存就緒隊列中的哪個進程獲得處理機，進行分配工作中跌。是最基本的一種調(diào)度咨堤，在三種基本OS中都有。

????????????????????????進程調(diào)度方式

????????????????????????????????1）非搶占方式（Non-preemptive Mode）

????????????????????????????????????????? 一旦處理機分配給某進程漩符，該進程一直執(zhí)行一喘。決不允許其他進程搶占已分配運行進程的處理機。

????????????????????????????????2）搶占方式（Preemptive Mode）

????? ????????????????????????????????????允許調(diào)度程序根據(jù)某種原則嗜暴，暫停某個正在執(zhí)行的進程凸克，將處理機重新分配給另一進程。

????????????????????????調(diào)度程序的任務(wù)職能：調(diào)度和分派闷沥。

????????????????????????????????(1) 記錄系統(tǒng)中所有進程的有關(guān)情況

????????????????????????????????(2) 確定分配處理機的原則

????????????????????????????????(3) 分配處理機給進程

????????????????????????????????(4) 從進程收回處理機

3萎战、中級調(diào)度（Intermediate-Level Scheduling）

????????又稱交換調(diào)度或中程調(diào)度（Medium-Term Scheduling）

????????引入目的：提高內(nèi)存利用率和系統(tǒng)吞吐量。根據(jù)條件將一些進程調(diào)出或再調(diào)入內(nèi)存舆逃。

三種調(diào)度的頻率和復(fù)雜度

????????進程調(diào)度：運行頻率最高蚂维，算法不能太復(fù)雜，以免占用太多的CPU時間颖侄。分時系統(tǒng)通常10~100ms便進行一次。

????????作業(yè)調(diào)度：一個作業(yè)運行完畢退出系統(tǒng)時即觸發(fā)重新調(diào)度一個新作業(yè)入內(nèi)存享郊，周期較長览祖，大約幾分鐘一次。因而也允許作業(yè)調(diào)度算法花費較多的時間炊琉。

????????中級調(diào)度：運行頻率基本上介于上述兩種調(diào)度之間展蒂。

4、調(diào)度隊列模型

????????不論高級苔咪、中級或者低級調(diào)度锰悼，都涉及到進程隊列，由此形成了三類調(diào)度隊列模型团赏。從這三種方式中體驗調(diào)度的過程箕般。

????????1）僅有進程調(diào)度的調(diào)度隊列模型

????????????????常見情況：

????????????????????????分時系統(tǒng)。

????????????????????????通常僅設(shè)置進程調(diào)度舔清，用戶鍵入的命令和數(shù)據(jù)丝里，都直接送入內(nèi)存曲初。

????????????????調(diào)度對象：

????????????????????????處于就緒狀態(tài)的進程。

????????????????組織形式：

????????????????????????棧杯聚、樹或一個無序鏈表

????????????????????????用何種形式取決于OS類型和采用的調(diào)度算法臼婆。如：分時系統(tǒng)中把就緒進程組織成FIFO隊列形式：按時間片輪轉(zhuǎn)方式運行。

? ????????????????進程調(diào)度過程如下圖：

????????????????????????每個進程在執(zhí)行時按規(guī)定的時間片算法幌绍，在給定時間片內(nèi)任務(wù)有三種執(zhí)行情況：

????????????????????????????????①完成工作颁褂，釋放處理機進入完成狀態(tài)

????????????????????????????????②未完成，將該任務(wù)再放入就緒隊列末尾

????????????????????????????????③因某事件而被阻塞傀广，被OS放入阻塞隊列

????????2）具有高級和低級調(diào)度的調(diào)度隊列模型

????????????????批處理系統(tǒng)中颁独，還需要作業(yè)調(diào)度

????????3）同時具有三級調(diào)度的調(diào)度隊列模型

????????????????引入中級調(diào)度后，進程的狀態(tài)變化：

????????????????????????就緒狀態(tài)：分為內(nèi)存就緒和外存就緒主儡。

????????????????????????阻塞狀態(tài)：分為內(nèi)存阻塞和外存阻塞奖唯。

? ????????????????中級調(diào)度使進程在上述狀態(tài)間變化，并使數(shù)據(jù)在內(nèi)外存間互換糜值。

5. 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則

????????什么算法是好算法丰捷？

????????????????不同的情況和對象需求不同，適用的方式和算法也不同寂汇。

????????1)面向用戶的準(zhǔn)則

????????????????周轉(zhuǎn)時間短：

? ????????????????????????針對批處理系統(tǒng)的性能指標(biāo)病往。作業(yè)從提交到完成所經(jīng)歷的時間。

?????????????????????????CPU執(zhí)行用時Ts

?????????????????????????總的等待時間Tw = 在后備隊列中等待 + 就緒隊列上等待+阻塞隊列中等待（等待I/O操作用時）

?????????????????????????周轉(zhuǎn)時間T=Ts+Tw

?????????????????????????帶權(quán)周轉(zhuǎn)時間W= T/Ts

?????????????????????????平均周轉(zhuǎn)時間骄瓣、平均帶權(quán)周轉(zhuǎn)時間（n個作業(yè)求平均）

????????????????響應(yīng)時間快：針對分時系統(tǒng)停巷。用戶輸入一個請求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時間

????????????????均衡性：系統(tǒng)響應(yīng)時間的快慢與用戶所請求的復(fù)雜性相適應(yīng)。

????????????????截止時間的保證：針對實時系統(tǒng)的性能指標(biāo)榕栏。開始截止時間和完成截止時間畔勤。任務(wù)必須按規(guī)定的時間開始或完成，調(diào)度方式和算法必須能保證該要求扒磁。

????????????????優(yōu)先權(quán)準(zhǔn)則：三大基本OS在調(diào)度算法的選擇時都可遵循庆揪。可以使關(guān)鍵任務(wù)達到更好的指標(biāo)妨托。

????????2)面向系統(tǒng)的準(zhǔn)則

????????????????系統(tǒng)吞吐量高：批處理系統(tǒng)的重要指標(biāo)缸榛。

?????????????????????????單位時間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身（與作業(yè)平均長度密切相關(guān)）和調(diào)度算法都有關(guān)系兰伤；

????????????????處理機利用率好(主要針對大中型主機)

????????????????各類資源的平衡利用(主要針對大中型主機)

????????????????不同系統(tǒng)需求各有側(cè)重

????????????????????????批處理系統(tǒng)?

?????????????????????????????????平均周轉(zhuǎn)時間短

?????????????????????????????????系統(tǒng)吞吐量高

?????????????????????????????????處理機利用率好

????????????????????????分時系統(tǒng)

?????????????????????????????????響應(yīng)時間快

?????????????????????????????????均衡

????????????????????????實時系統(tǒng)

?????????????????????????????????截至?xí)r間的保證

?????????????????????????????????可預(yù)測性

二.常用調(diào)度算法

調(diào)度的實質(zhì)就是一種資源分配内颗。不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法——適合自己的才是最好的敦腔。

?????????如批處理系統(tǒng)為照顧為數(shù)眾多的短作業(yè)均澳，應(yīng)采用短作業(yè)優(yōu)先的調(diào)度算法；

?????????如分時系統(tǒng)為保證系統(tǒng)具有合理的響應(yīng)時間，應(yīng)采用輪轉(zhuǎn)法進行調(diào)度负懦。

?????????目前存在的多種調(diào)度算法中筒捺，有的算法適用于作業(yè)調(diào)度，有的算法適用于進程調(diào)度纸厉；但有些算法作業(yè)調(diào)度和進程調(diào)度都可以采用系吭。

1、先來先服務(wù)調(diào)度算法FCFS(First Come First Service)

????????一種最簡單的調(diào)度算法颗品，按先后順序進行調(diào)度肯尺。既可用于作業(yè)調(diào)度，也可用于進程調(diào)度躯枢。

????????按照作業(yè)提交则吟，或進程變?yōu)榫途w狀態(tài)的先后次序分派CPU；

????????新作業(yè)只有當(dāng)當(dāng)前作業(yè)或進程執(zhí)行完或阻塞才獲得CPU運行

????????被喚醒的作業(yè)或進程不立即恢復(fù)執(zhí)行锄蹂，通常等到當(dāng)前作業(yè)或進程出讓CPU氓仲。 （所以，默認(rèn)即是非搶占方式）

????????不足：短作業(yè)C的帶權(quán)周轉(zhuǎn)時間竟高達100得糜，這是不能容忍的敬扛；而長作業(yè)D的帶權(quán)周轉(zhuǎn)時間僅為1.99。

????????關(guān)于應(yīng)用：有利于CPU繁忙型的作業(yè)朝抖，而不利于I/O繁忙的作業(yè)（進程）啥箭。

????????????????從程序規(guī)模上看，一般I/O繁忙型作業(yè)CPU進行處理的用時相對比較短治宣，CPU繁忙型的作業(yè)相對較長急侥。而FCFS不利于短作業(yè)，I/O繁忙型作業(yè)一旦排隊靠后就會處于劣勢侮邀。

????????????????另一方面坏怪，I/O繁忙型作業(yè)需頻繁的請求I/O，即使排隊靠前绊茧，但由于I/O請求阻塞铝宵，重新排隊可能就會排到隊尾（這一情況在其他算法下也是普遍的，但不同的算法按傅，排隊情況不同捉超，相對的在照顧公平性上也會有所不同）胧卤。

????????????????目前大多數(shù)事務(wù)處理都屬于I/O繁忙型作業(yè)唯绍。

2. 短作業(yè)（進程）優(yōu)先調(diào)度算法SJF/SPF(Shortest Job First) OR (Shortest Process?First)

????????優(yōu)點：

????????????????通過上表可見采用SJF/SPF算法，平均周轉(zhuǎn)時間枝誊、平均帶權(quán)周轉(zhuǎn)時間都有明顯改善况芒。SJF/SPF調(diào)度算法能有效的降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量。

????????方式：

????????????????分搶占和非搶占兩種方式绝骚，上例為簡單的非搶占式耐版。

????????SJF/SPF的不足：

? ? ? ? ? ? ? ? 1.對短作業(yè)有利，但同時造成了對長作業(yè)的不利压汪。

? ? ? ? ? ? ? ? 2.由于作業(yè)（進程）的長短含主觀因素粪牲，不一定能真正做到短作業(yè)優(yōu)先。

? ? ? ? ? ? ? ? 3.未考慮作業(yè)的緊迫程度止剖，因而不能保證緊迫性作業(yè)（進程）的及時處理腺阳。

3. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法HPF Highest Priority First

????????照顧緊迫性作業(yè)，使其獲得優(yōu)先處理而引入調(diào)度算法穿香。常用于批處理系統(tǒng)中的作業(yè)調(diào)度算法亭引，以及多種操作系統(tǒng)中的進程調(diào)度算法

????????1)分兩種方式：

????????????????非搶占式優(yōu)先權(quán)算法

????????????????搶占式優(yōu)先權(quán)算法 關(guān)鍵點：新作業(yè)產(chǎn)生時

????????2)優(yōu)先權(quán)的類型

????????????????靜態(tài)優(yōu)先權(quán)：創(chuàng)建進程時確定，整個運行期間保持不變皮获。一般利用某一范圍的一個整數(shù)來表示焙蚓，又稱為優(yōu)先數(shù)。

????????????????動態(tài)優(yōu)先權(quán)：創(chuàng)建進程時賦予的優(yōu)先權(quán)可隨進程的推進或隨其等待時間的增加而改變洒宝。

????????關(guān)于進程優(yōu)先權(quán)的確定购公？依據(jù)如下：

? ? ? ? ? ? ? ? ①進程類型：一般來，系統(tǒng)進程高于用戶進程待德。

? ? ? ? ? ? ? ? ②進程對資源的需求：如進程的估計時間及內(nèi)存需要量的多少君丁，對要求少的進程賦予較高優(yōu)先權(quán)。

? ? ? ? ? ? ? ? ③用戶要求：由用戶進程的緊迫程度及用戶所付費用的多少來確定優(yōu)先權(quán)的将宪。

? ??????3）高響應(yīng)比優(yōu)先調(diào)度算法HRRN Highest Response Raito Next

????????????????短作業(yè)優(yōu)先算法是一種比較好的算法（相當(dāng)于根據(jù)作業(yè)長度設(shè)定的靜態(tài)優(yōu)先權(quán)算法）绘闷，適用于短作業(yè)較多的批處理系統(tǒng)中，其主要不足是長作業(yè)的運行得不到保證较坛。

????????????????HRRN為每個作業(yè)引入動態(tài)優(yōu)先權(quán)印蔗，使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a提高：

????????????????優(yōu)先權(quán) =（等待時間+要求服務(wù)時間)/要求服務(wù)時間= 響應(yīng)時間 / 要求服務(wù)時間

? ??????*對不同作業(yè)都有照顧*

? ? ? ? ? ? ? ? ①同時到達的作業(yè)優(yōu)先權(quán)相同。

????????????????????????初始t=0丑勤，隨著時間增長华嘹，如果等待時間 t相同，執(zhí)行時間愈短的優(yōu)先權(quán)愈高法竞，利于短作業(yè)耙厚。

????????????????????????對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高岔霸，當(dāng)其等待時間足夠長也可獲得處理機薛躬。長作業(yè)有照顧。

? ? ? ? ? ? ? ? ②當(dāng)執(zhí)行時間相同的作業(yè)呆细，優(yōu)先權(quán)的高低決定于其等待時間的長短型宝，也就是先來先服務(wù)。

????????什么時候計算各進程的響應(yīng)比優(yōu)先權(quán)？

????????????????需要進行調(diào)度選擇的時候比較各自優(yōu)先權(quán)

?????????????????????????作業(yè)完成時

?????????????????????????新作業(yè)產(chǎn)生時（搶占趴酣、非搶占）

?????????????????????????時間片完成時

?????????????????????????進程阻塞時

4.基于時間片的輪轉(zhuǎn)調(diào)度算法RR(Round Robin)

????????分時系統(tǒng)新需求：及時響應(yīng)用戶的請求梨树；采用基于時間片的輪轉(zhuǎn)式進程調(diào)度算法。

????????早期分時系統(tǒng)采用的是簡單的時間片輪轉(zhuǎn)法岖寞，進入90年代后廣泛采用多級反饋隊列調(diào)度算法抡四。

????????（1）時間片輪轉(zhuǎn)算法

? ? ? ? ? ? ? ? ①將系統(tǒng)中所有的就緒進程按照FCFS原則，排成一個隊列仗谆。

? ? ? ? ? ? ? ? ②每次調(diào)度時將CPU分派給隊首進程床嫌，讓其執(zhí)行一個時間片。時間片的長度從幾個ms到幾百ms胸私。

? ? ? ? ? ? ? ? ③在一個時間片結(jié)束時厌处，發(fā)生時鐘中斷。

? ? ? ? ? ? ? ? ④調(diào)度程序據(jù)此暫停當(dāng)前進程的執(zhí)行岁疼，將其送到就緒隊列的末尾阔涉，并通過上下文切換執(zhí)行當(dāng)前就緒的隊首進程。

????????????????進程阻塞情況發(fā)生時捷绒，未用完時間片也要出讓CPU

????????????????能夠及時響應(yīng)晨雳，但沒有考慮作業(yè)長短等問題秧廉。

????????關(guān)于時間片長度

????????????????時間片長度的選擇要與完成一個基本的交互過程所需的時間相當(dāng)，保證一個基本的交互過程可在一個時間片內(nèi)完成。

????????????????設(shè)置不合適反而都會導(dǎo)致響應(yīng)時間長闺鲸。

?????????????????????????過長會怎樣巡通？——FCFS

?????????????????????????過短會怎樣鸠按？——頻繁切換

????????影響時間片長度的主要因素

????????????????系統(tǒng)的處理能力和系統(tǒng)的負載狀態(tài)醒陆。（依據(jù)系統(tǒng)的處理能力確定時間片長度，使用戶輸人通常在一個時間片內(nèi)能處理完葫掉，否則使響應(yīng)時間些举、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。為了保證不同負載狀態(tài)下用戶交互的響應(yīng)時間俭厚，需要對時間片長度進行適當(dāng)調(diào)整户魏。）

????????爭議：若同時有時間片到放棄CPU的A進程、新就緒的進程B挪挤，二者在就緒隊列中如何排序叼丑。

????????做題時給出統(tǒng)一的假設(shè)：

????????????????若設(shè)新進程就緒比較快，就統(tǒng)一按BA的順序排入就緒隊列扛门。

?????????????????若設(shè)舊進程該為就緒比較快鸠信，則統(tǒng)一按AB排序

????????（2）多級反饋隊列算法FB(Multiple-level Feed Back Queue)

????????????????特點：多個就緒隊列，循環(huán)反饋尖飞；動態(tài)優(yōu)先級症副、時間片輪轉(zhuǎn)

? ? ? ? ? ? ? ? ①設(shè)置多個就緒隊列，各隊列有不同的優(yōu)先級,優(yōu)先級從第一個隊列依次降低政基。

? ? ? ? ? ? ? ? ②賦予各隊列進程執(zhí)行時間片大小不同, 優(yōu)先權(quán)越高贞铣，時間片越短。

? ? ? ? ? ? ? ? ③當(dāng)一個新進程進入內(nèi)存沮明，引發(fā)的調(diào)度過程

? ? ? ? ? ? ? ? ? ? ? ? a.準(zhǔn)備調(diào)度：先將它放入第一個隊列的末尾辕坝，按FCFS原則排隊等待調(diào)度。

? ? ? ? ? ? ? ? ? ? ? ? b.IF時間片內(nèi)完成荐健，便可準(zhǔn)備撤離系統(tǒng)酱畅；

? ? ? ? ? ? ? ? ? ? ? ? c.IF時間片內(nèi)未能完成，調(diào)度程序便將該進程轉(zhuǎn)入第二隊列的末尾等待再次被調(diào)度執(zhí)行江场。

? ? ? ? ? ? ? ? ? ? ? ? d.當(dāng)?shù)谝魂犃兄械倪M程都執(zhí)行完纺酸，系統(tǒng)再按FCFS原則調(diào)度第二隊列。在第二隊列的稍放長些的時間片內(nèi)仍未完成址否，再依次將它放入第三隊列餐蔬。

? ? ? ? ? ? ? ? ? ? ? ? e.依次降到第n隊列后，在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運行佑附。

????????注意：

????????????????各隊列的時間片逐漸增大樊诺。優(yōu)先級逐漸降低

????????????????僅當(dāng)優(yōu)先權(quán)高的隊列（如第一隊列）空閑時，調(diào)度程序才調(diào)度第二隊列中的進程運行音同；僅當(dāng)?shù)?~（i-1）隊列均空時词爬，才會調(diào)度第i隊列中的進程運行。

????????????????高優(yōu)先級搶占問題:

?????????????????????????第i隊列中為某進程正占有CPU权均，又有新進程進入優(yōu)先權(quán)較高的隊列（第1~i-1隊中）顿膨；

?????????????????????????被搶占的進程放回原就緒隊列末尾；

????????* 多級反饋隊列調(diào)度算法的性能 *

????????????????多級反饋隊列調(diào)度算法具有較好的性能叽赊，能較好的滿足各種類型用戶的需要虽惭。

????????????????終端型作業(yè)用戶。大多屬于較小的交互性作業(yè)蛇尚，只要能使作業(yè)在第一隊列的時間片內(nèi)完成芽唇，便可令用戶滿意。

????????????????短批處理作業(yè)用戶取劫。周轉(zhuǎn)時間仍然較短匆笤，至多在第二到三隊列即可完成。

????????????????長批處理作業(yè)用戶谱邪。將依次在1~n級隊列中輪轉(zhuǎn)執(zhí)行炮捧，不必擔(dān)心作業(yè)長期得不到處理。

????????基于公平原則的更多算法

? ? ? ? ? ? ? ? ①保證調(diào)度算法

?????????????????????????處理機分配的公平性：

?????????????????????????已經(jīng)執(zhí)行時間/應(yīng)獲得執(zhí)行的時間惦银，比值小的優(yōu)先獲得處理機

? ? ? ? ? ? ? ? ②公平分享調(diào)度算法

?????????????????????????針對用戶考慮咆课，如根據(jù)a（4個進程）末誓，b（2個進程）用戶所擁有進程數(shù)目，決定一個比率

?????????????????????????a1书蚪，a2喇澡，b1，a3殊校，a4晴玖，b2……

????????優(yōu)先級倒置問題的討論

?????????????????????????有人罩著就是好^_^

?????????????????????????p1，p2为流，p3?優(yōu)先級從高到低

?????????????????????????p3（運行）先占有一互斥信號mutex

?????????????????????????p2（運行）可以搶p3（就緒）

?????????????????????????p1來申請mutex呕屎，即使優(yōu)先級高，但信號量拿不到只能阻塞敬察，又回到p2

?????????????????????????p2來了秀睛，p3

三.實時調(diào)度

????????什么是實時系統(tǒng)？

????????????????指系統(tǒng)能夠在限定的響應(yīng)時間內(nèi)提供所需水平的服務(wù)莲祸。

????????????????指計算的正確性不僅取決于程序的邏輯正確性琅催，也取決于結(jié)果產(chǎn)生的時間，如果系統(tǒng)的時間約束條件得不到滿足虫给，將會發(fā)生系統(tǒng)出錯藤抡。

? ??????實時任務(wù)：具有明確時間約束的計算任務(wù)，有軟/硬抹估，隨機/周期性之分缠黍。

????????硬實時任務(wù)：必須滿足任務(wù)對截止時間的要求

? ? ????軟實時任務(wù)：聯(lián)系著一個截止時間，但不嚴(yán)格药蜻，可偶爾錯過瓷式，不會對系統(tǒng)造成大的影響。

?????????????????實時系統(tǒng)的任務(wù)往往帶有某種程度的緊迫性语泽，因而實時系統(tǒng)的調(diào)度有某些特殊要求贸典。

? ? ????為此引入適合的實時調(diào)度算法

????????為保證系統(tǒng)正常工作，調(diào)度應(yīng)具備下列條件

1. 實現(xiàn)實時調(diào)度的基本條件

????????1）提供必要的信息

? ? ? ? ? ? ? ? 為了實現(xiàn)實時調(diào)度踱卵，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述信息：

????????????????就緒時間廊驼。該任務(wù)成為就緒狀態(tài)的時間。

????????????????開始截止時間惋砂、完成截止時間妒挎。

????????????????處理時間。從開始執(zhí)行到完成所需時間西饵。

????????????????資源要求酝掩。任務(wù)執(zhí)行時所需的一組資源。

????????????????優(yōu)先級眷柔。根據(jù)任務(wù)性質(zhì)賦予不同優(yōu)先級期虾。

? ??????2）系統(tǒng)處理能力足夠強

????????????????處理能力不足可能會出現(xiàn)某些實時任務(wù)不能得到及時處理原朝，導(dǎo)致難以預(yù)料的后果。

????????????????如：

????????????????????????系統(tǒng)中有M個周期性的硬實時任務(wù)镶苞，處理時間為Ci喳坠，周期時間表示為Pi,單機系統(tǒng)中必須滿足條件

????????????????????????一個系統(tǒng)，6個硬實時任務(wù)宾尚，周期都是50ms，每次處理時間10ms谢澈。根據(jù)公式煌贴，系統(tǒng)是不可調(diào)度的。10*6/50

????????提高系統(tǒng)處理能力的方法

????????????????增強單機系統(tǒng)的處理能力

????????????????采用多處理機系統(tǒng)

????????????????此情況下需滿足

????????????????????????∑（ Ci / Pi ）≤N锥忿，N為處理機數(shù)

? ??????3）采用搶占式調(diào)度機制

????????????????硬實時任務(wù)：廣泛采用搶占機制牛郑。

????????????????小的實時系統(tǒng)：如能預(yù)知任務(wù)的開始截止時間，為簡化調(diào)度程序和對任務(wù)調(diào)度時所花費的系統(tǒng)開銷敬鬓，可采用非搶占調(diào)度機制

????????4）具有快速切換機制

? ? ? ? ? ? ? ? ①對外部中斷的快速響應(yīng)能力淹朋。

????????????????????????利用快速硬件中斷機構(gòu)，可在緊迫的外部事件請求中及時響應(yīng)钉答。

? ? ? ? ? ? ? ? ②快速的任務(wù)分派能力础芍。

????????????????????????使系統(tǒng)中的運行功能單位適當(dāng)?shù)男。岣咔袚Q速度数尿。類如線程的思想

2. 實時調(diào)度算法的分類

????????根據(jù)實時任務(wù)的性質(zhì)? ??????????????????????????????根據(jù)調(diào)度時間不同

????????????????硬實時調(diào)度算法????????????????????????????????????????靜態(tài)調(diào)度算法

????????????????軟實時調(diào)度算法仑性；????????????????????????????????????動態(tài)調(diào)度算法。

????????按調(diào)度方式? ??????????????????????????????????????????????多處理機環(huán)境下

????????????????非搶占調(diào)度算法????????????????????????????????????????集中式調(diào)度

????????????????搶占調(diào)度算法右蹦；????????????????????????????????????????分布式調(diào)度

? ??????1）非搶占調(diào)度算法

????????????????該算法較簡單诊杆，用于一些小型實時系統(tǒng)或要求不太嚴(yán)格的實時系統(tǒng)中，又可分為：

? ? ? ? ? ? ? ? ? ? ? ? ①非搶占式輪轉(zhuǎn)調(diào)度算法何陆。常用于工業(yè)生產(chǎn)的群控系統(tǒng)中晨汹，要求不太嚴(yán)格。

? ? ? ? ? ? ? ? ? ? ? ? ②非搶占式優(yōu)先調(diào)度算法贷盲。要求相對嚴(yán)格淘这，根據(jù)任務(wù)的優(yōu)先級安排等待位置」剩可用于有一定要求的實時控制系統(tǒng)中慨灭。（精心設(shè)置可獲得百ms級的響應(yīng)時間）

????????2）搶占式調(diào)度算法

????????????????較嚴(yán)格的實時系統(tǒng)中（t約為數(shù)十ms），選擇采用搶占式優(yōu)先權(quán)調(diào)度算法球及。根據(jù)搶占發(fā)生時間可分為：

? ? ? ? ? ? ? ? ? ? ? ? ①基于時鐘：某高優(yōu)先級任務(wù)到達后并不立即搶占氧骤，而等下一個時鐘中斷時搶占。

? ? ? ? ? ? ? ? ? ? ? ? ②立即搶占：一旦出現(xiàn)外部中斷吃引，只要當(dāng)前任務(wù)未處于臨界區(qū)筹陵，就立即搶占處理機刽锤。

3. 常用的幾種實時調(diào)度算法

????????目前有許多實時調(diào)度算法，在常用的算法中簡單介紹兩種實時調(diào)度算法：

????????1）最早截止時間優(yōu)先EDF（Earliest Deadline First）

????????????????根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級朦佩。截止時間越早并思，其優(yōu)先級越高。

????????????????????????系統(tǒng)保持一個實時任務(wù)就緒隊列

????????????????????????隊列按各任務(wù)截止時間的早晚排序

????????????????????????調(diào)度程序總是選擇就緒隊列中的第一個任務(wù)语稠，分配處理機使之投入運行宋彼。

????????????????新任務(wù)產(chǎn)生時，是否等當(dāng)前程序執(zhí)行完：

????????????????????????搶占式/非搶占式

????????????????可能會使作業(yè)錯過仙畦，但可適用于軟實時系統(tǒng)

????????2）最低松弛度優(yōu)先LLF（Least Laxity First）

????????????????根據(jù)任務(wù)緊急（或松弛）的程度输涕，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度越高（松弛度值越锌）莱坎，優(yōu)先級就越高。

????????????????松弛度= 截止完成時間 – 還需執(zhí)行時間 - 當(dāng)前時間

????????????????可理解為當(dāng)前時刻到開始截止時刻間的差距寸士，隨著時間的推進檐什，這個差值逐漸變小，任務(wù)越來越緊迫弱卡。

????????進程切換發(fā)生的時機

????????????????進程執(zhí)行完

????????????????進程I/O阻塞

????????????????新進程出現(xiàn)時可能的搶占

????????????????某進程松弛度為0時發(fā)生搶占

????????????????有的時刻乃正，其他并發(fā)的實時任務(wù)下一周期未到來，會出現(xiàn)只有一個任務(wù)的情況婶博。

????????多處理機系統(tǒng)中的調(diào)度

????????????????提高計算機系統(tǒng)性能的途徑：

????????????????提高計算機元器件速度

????????????????改進計算機系統(tǒng)體系結(jié)構(gòu)

????????????????20世紀(jì)70年代出現(xiàn)多處理器系統(tǒng)MPS（MultiProcessor System）烫葬。90年代中后期，功能較強的主機或服務(wù)器都采用了MPS凡蜻。

1. 多處理器系統(tǒng)的類型

????????不同角度分類

????????1）緊密耦合MPS和松弛耦合MPS

????????????????緊密耦合（Tightly Coupted）

????????????????????????高速總線或高速交叉開關(guān)來實現(xiàn)多個處理器之間的互連搭综。

????????????????????????共享主存儲器系統(tǒng)和I/O設(shè)備。系統(tǒng)中所有進程和資源由OS統(tǒng)一控制管理划栓。

????????????????松散耦合（Loosely Coupted）

????????????????????????通過通道或通信線路來實現(xiàn)多臺計算機之間互連兑巾。

????????????????????????每臺計算機都有自己的存儲器和I/O設(shè)備，可以獨立工作忠荞。

????????2）對稱MPS和非對稱MPS

????????????????對稱多處理系統(tǒng)SMPS（Symmetric MultiProcessor System）平等型：在系統(tǒng)中所包含的各處理器單元在功能上和結(jié)構(gòu)上都相同蒋歌。當(dāng)前的絕大多數(shù)MPS屬于此類。

????????????????非對稱多處理器系統(tǒng)委煤。主從型：系統(tǒng)中有多種類型的處理單元堂油，它們的功能和結(jié)構(gòu)各不相同，其中只有一個主處理器碧绞，其余為從處理器府框。

2. 進程分配方式

????????在多處理器系統(tǒng)中，進程的調(diào)度與系統(tǒng)結(jié)構(gòu)有關(guān)讥邻。

????????????????同構(gòu)性系統(tǒng)中迫靖，所有處理器都相同院峡，可將進程分配到任一處理器上運行；

????????????????非對稱MPS系宜，對任一進程而言照激，都只能將其分配到某一適合于其運行的處理機上去執(zhí)行。下面分別介紹對稱MPS和非對稱MPS中的進程分配方式盹牧。

????????1）對稱MPS中的進程分配方式

? ? ? ? ? ? ? ? ①靜態(tài)分配（Static Assignment）方式：

????????????????????????進程從開始至完成被固定分配到一個處理器上俩垃。

????????????????????????優(yōu)點是進程調(diào)度開銷小，缺點是各處理器可能出現(xiàn)忙閑不均汰寓。

? ? ? ? ? ? ? ? ②動態(tài)分配（Dynamic Assignment）方式：

????????????????????????系統(tǒng)中僅設(shè)置一個公共的就緒隊列口柳，分配進程總是給空閑處理器。某一進程的執(zhí)行可能曾在不同的處理器上踩寇。

????????????????????????優(yōu)點是消除忙閑不均現(xiàn)象啄清。但松散耦合系統(tǒng)增大調(diào)度開銷六水。

????????2）非對稱MPS中的進程分配方式

????????????????OS的核心部分駐留在一臺主機上俺孙，而從機上只是用戶程序，進程調(diào)度只由主機執(zhí)行掷贾。主機中保持有一個就緒隊列睛榄。

????????????????每當(dāng)從機空閑時向主機發(fā)一索求進程信號，然后等待主機分配進程想帅。

????????????????優(yōu)點是系統(tǒng)處理比較簡單场靴，缺點是處理靠一臺主機導(dǎo)致不可靠。（克服缺點的方法是利用多臺而非一臺管理系統(tǒng)）

3. 進程（線程）調(diào)度方式

????????MPS已廣為流行多年港准，存在著多種調(diào)度方式旨剥，許多都是以線程作為基本調(diào)度單位的，比較有代表的如下：

1）自調(diào)度（Self-Scheduling）方式

????????自調(diào)度機制浅缸，最簡單的一種調(diào)度方式轨帜。

????????系統(tǒng)中設(shè)置一個公共的進程或線程就緒隊列，所有的處理器空閑時衩椒，都可自己到該隊列中取得一進程（線程）來運行蚌父。

????????調(diào)度算法：可采用FCFS、FPF和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等毛萌。經(jīng)實驗證明FCFS算法在多處理器環(huán)境下簡單開銷小苟弛，目前成為較好的調(diào)度算法。

自調(diào)度方式的特點

????????優(yōu)點：

? ????????????????1）易將單機環(huán)境下的調(diào)度機制移植到MPS中阁将；

? ????????????????2）不會發(fā)生處理器忙閑不均的現(xiàn)象膏秫，有利于提高處理器的利用率。

????????缺點：? ?

? ????????????????1）瓶頸問題做盅。多處理器互斥訪問唯一就緒隊列荔睹。

????????????????? 2）低效性狸演。高速緩存的使用效率很低。

? ????????????????3）線程切換頻繁僻他。相關(guān)的其他線程未必會同時獲得處理器導(dǎo)致切換頻繁宵距。

2）成組調(diào)度（Gang Scheduling）方式

????????為解決自調(diào)度方式中線程頻繁切換的問題

????????將進程的一組線程分配到一組處理器上去執(zhí)行。分配處理器時間的方式：

? ? ? ? ? ? ? ? ①面向所有應(yīng)用程序平均分配處理器時間

? ? ? ? ? ? ? ? ②面向所有線程平均分配處理器時間

????????優(yōu)點：

????????????????相互合作的進程或線程能并行執(zhí)行吨拗，可有效的減少阻塞满哪，減少切換使系統(tǒng)性能得到改善；

????????????????每次調(diào)度都可以解決一組線程的處理器分配問題劝篷，故可顯著減少調(diào)度頻率哨鸭，減少了調(diào)度開銷。

3）專用處理器（Dedicated Processor Assignment）方式

????????1989年Tucker提出該方式娇妓。在一個應(yīng)用程序的執(zhí)行期間像鸡，專為該應(yīng)用程序分配一組處理器，每一個線程一個處理器哈恰。

????????這種方式很浪費只估。但仍有利用市場，適用于并發(fā)程度相當(dāng)高的多處理機環(huán)境：

????????????????對系統(tǒng)的性能和效率來講着绷，單個處理器的利用率已不太重要蛔钙。

????????????????“專用”完全避免了切換，從而大大加速了程序運行荠医。

????????????????同時加工的應(yīng)用程序吁脱，線程總和不應(yīng)超過系統(tǒng)處理機的數(shù)目。