第3章-處理機(jī)調(diào)度與死鎖

12023/1/20調(diào)度算法與實(shí)時(shí)調(diào)度22023/1/20主要內(nèi)容3.3調(diào)度算法3.4實(shí)時(shí)調(diào)度32023/1/203.3調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法42023/1/20二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法1、優(yōu)先級(jí)調(diào)度算法的類型調(diào)度時(shí)，系統(tǒng)把處理機(jī)分配給優(yōu)先級(jí)最高的就緒進(jìn)程。分為兩大類：（1）非搶占式優(yōu)先級(jí)調(diào)度算法（2）搶占式優(yōu)先級(jí)調(diào)度算法52023/1/20非搶占式優(yōu)先級(jí)算法把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程后便一直執(zhí)行下去直至完成；或發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，可再將處理機(jī)重新分配給另一優(yōu)先級(jí)最高的進(jìn)程。用于批處理系統(tǒng)和某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。62023/1/20搶占式優(yōu)先級(jí)調(diào)度算法把處理機(jī)分配給優(yōu)先級(jí)最高的進(jìn)程，使之執(zhí)行。在執(zhí)行期間，只要又出現(xiàn)優(yōu)先級(jí)更高的進(jìn)程，就重新將處理機(jī)分配給新到的優(yōu)先級(jí)最高的進(jìn)程。能更好地滿足緊迫作業(yè)的要求，常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。72023/1/20二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法2、優(yōu)先級(jí)的類型（1）靜態(tài)優(yōu)先級(jí)（2）動(dòng)態(tài)優(yōu)先級(jí)82023/1/20（1）靜態(tài)優(yōu)先級(jí)在創(chuàng)建進(jìn)程時(shí)確定在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，0~7或0~255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法92023/1/20（1）靜態(tài)優(yōu)先級(jí)確定進(jìn)程靜態(tài)優(yōu)先級(jí)的依據(jù)進(jìn)程類型:系統(tǒng)進(jìn)程，用戶進(jìn)程（系統(tǒng)進(jìn)程高于用戶進(jìn)程）進(jìn)程對(duì)資源的需求：要求少的進(jìn)程應(yīng)賦予較高優(yōu)先級(jí)。用戶要求：這是由用戶進(jìn)程的緊迫程度及所付費(fèi)多少來確定。二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法102023/1/20簡單，系統(tǒng)開銷小不精確，僅在要求不高的系統(tǒng)中使用?？赡軙?huì)出現(xiàn)優(yōu)先級(jí)低的進(jìn)程長期沒有被調(diào)度的情況。（1）靜態(tài)優(yōu)先級(jí)靜態(tài)優(yōu)先級(jí)法優(yōu)缺點(diǎn)：二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法112023/1/20進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間靜態(tài)優(yōu)先級(jí)開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均靜態(tài)優(yōu)先級(jí)，非搶占式（1為高優(yōu)先級(jí)）04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法122023/1/20（2）動(dòng)態(tài)優(yōu)先級(jí)在創(chuàng)建之初，先賦予其一個(gè)優(yōu)先級(jí)。隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變，以獲得更好的調(diào)度性能；可規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長，其優(yōu)先級(jí)以速率a提高；當(dāng)采用搶占式優(yōu)先級(jí)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先級(jí)以速率b下降，則可防止一個(gè)長作業(yè)長期地壟斷處理機(jī)。二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法132023/1/203、高響應(yīng)比優(yōu)先調(diào)度算法是FCFS和SJF的結(jié)合，克服了兩種算法的缺點(diǎn)調(diào)度策略：響應(yīng)比最高的作業(yè)優(yōu)先調(diào)度二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法142023/1/20

說明：等待時(shí)間相同，服務(wù)時(shí)間愈短，優(yōu)先級(jí)愈高，服務(wù)時(shí)間相同，等待時(shí)間愈長，優(yōu)先級(jí)愈高，長作業(yè)優(yōu)先級(jí)隨等待時(shí)間的增加而提高，等待時(shí)間足夠長時(shí)，其優(yōu)先級(jí)可升到很高，從而也可獲得處理機(jī)。優(yōu)點(diǎn)：兼顧長短作業(yè)。缺點(diǎn)：由于做相應(yīng)比計(jì)算故增加了系統(tǒng)開銷。二、優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法152023/1/203.3調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法162023/1/20三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1、時(shí)間片輪轉(zhuǎn)法分時(shí)系統(tǒng)中多采用時(shí)間片輪轉(zhuǎn)法把就緒進(jìn)程組織成FIFO隊(duì)列，把CPU分配給隊(duì)首進(jìn)程，規(guī)定它執(zhí)行一個(gè)時(shí)間片。時(shí)間片完時(shí)排在就緒隊(duì)列的末尾，重新把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，也執(zhí)行一個(gè)時(shí)間片。就緒隊(duì)列中的所有進(jìn)程在一給定時(shí)間內(nèi)，均可獲得一個(gè)時(shí)間片的CPU時(shí)間.時(shí)間片的大小從幾ms到幾百ms172023/1/20說明：（1）時(shí)間片選擇問題固定時(shí)間片可變時(shí)間片時(shí)間片大?。?）與時(shí)間片大小有關(guān)的因素系統(tǒng)響應(yīng)時(shí)間就緒進(jìn)程個(gè)數(shù)CPU能力三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法182023/1/20三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法說明：時(shí)間片大小對(duì)系統(tǒng)性能有很大影響：很小，有利于短作業(yè)，因?yàn)樗茉谠摃r(shí)間片內(nèi)完成，但時(shí)間片小，意味著頻繁進(jìn)行進(jìn)程調(diào)度和上下文切換，會(huì)增加系統(tǒng)開銷。如果過大，每個(gè)作業(yè)都可以在一個(gè)時(shí)間片內(nèi)完成，直接褪化為FCFS算法，無法滿足短作業(yè)和交互式作業(yè)的需求。192023/1/20進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A04015153.75B13112113.67C24216143.5D323963E44417133.33平均11.83.46三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法(q=1)202023/1/20進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A040441B134762C2481192.25D321113105E441317133.33平均8.42.5三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法(q=4)212023/1/20為多個(gè)就緒隊(duì)列賦不同的優(yōu)先級(jí)。多級(jí)隊(duì)列：隊(duì)列時(shí)間片長遞增；新進(jìn)程進(jìn)入最上級(jí)隊(duì)列每級(jí)隊(duì)列：先進(jìn)先出，時(shí)間片機(jī)制時(shí)間片完，自動(dòng)降級(jí)上級(jí)隊(duì)列未空，下級(jí)隊(duì)列不能調(diào)度搶占條件：下級(jí)隊(duì)列進(jìn)程運(yùn)行時(shí)，上級(jí)隊(duì)列有新進(jìn)程進(jìn)入，發(fā)生搶占搶占處理：被搶進(jìn)程不降級(jí)，排到隊(duì)列末尾，等待剩余時(shí)間的完成2、多級(jí)反饋隊(duì)列調(diào)度算法三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法222023/1/20就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片：S1＜S2＜S3)2、多級(jí)反饋隊(duì)列調(diào)度算法高低優(yōu)先級(jí)時(shí)間片小大Sn三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法232023/1/203、多級(jí)反饋隊(duì)列調(diào)度算法的性能（1）終端型作業(yè)用戶所提交的作業(yè)屬于交互型作業(yè)，通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成即可；（2）短批處理作業(yè)用戶若在第1隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間；如在第一個(gè)隊(duì)列中不能完成，只需在第2、3隊(duì)列中各執(zhí)行一個(gè)時(shí)間片；三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法242023/1/203、多級(jí)反饋隊(duì)列調(diào)度算法的性能（3）長批處理作業(yè)用戶長作業(yè)將依次在第1，2，3…，n隊(duì)列中執(zhí)行，最終按輪轉(zhuǎn)方式運(yùn)行。三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法252023/1/203.4實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)時(shí)調(diào)度的分類實(shí)時(shí)調(diào)度算法262023/1/20提供必要的信息系統(tǒng)處理能力強(qiáng)采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制一、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的四大基本條件272023/1/201、提供必要的信息（1）就緒時(shí)間（2）開始截止時(shí)間和完成截止時(shí)間（3）處理時(shí)間（4）資源要求（5）優(yōu)先級(jí)一、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件282023/1/202、系統(tǒng)處理能力強(qiáng)假定單處理機(jī)系統(tǒng)中有M個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi。則必須滿足下面的限制條件：

∑Ci/Pi≤1

系統(tǒng)才是可調(diào)度的。一、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件292023/1/202、系統(tǒng)處理能力強(qiáng)例:單處理機(jī)系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是50MS，而每次的處理時(shí)間為10MS，則∑Ci/Pi=6/5>1

所以系統(tǒng)是不可調(diào)度的一、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件302023/1/202、系統(tǒng)處理能力強(qiáng)解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：一、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件312023/1/203、采用搶占式調(diào)度機(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ù)雜。對(duì)于小實(shí)時(shí)系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時(shí)間，則可采用非搶占調(diào)度機(jī)制，以簡化調(diào)度程序和對(duì)任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開銷。但在設(shè)計(jì)這種調(diào)度機(jī)制時(shí)，應(yīng)使所有的實(shí)時(shí)任務(wù)都比較小，在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時(shí)自我阻塞，釋放處理機(jī)，供調(diào)度程序去調(diào)度那種開始截止時(shí)間即將到達(dá)的任務(wù)。一、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件322023/1/204、具有快速切換機(jī)制該機(jī)制應(yīng)具有如下兩方面的能力：

(1)對(duì)外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請(qǐng)求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時(shí)間開銷。一、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件332023/1/20二、實(shí)時(shí)調(diào)度的分類按任務(wù)性質(zhì)硬實(shí)時(shí)調(diào)度算法

軟實(shí)時(shí)調(diào)度算法342023/1/20二、實(shí)時(shí)調(diào)度的分類按調(diào)度方式非搶占調(diào)度算法搶占調(diào)度算法352023/1/201、非搶占式調(diào)度算法算法簡單，用在小型實(shí)時(shí)系統(tǒng)或要求不嚴(yán)的實(shí)時(shí)控制系統(tǒng)中。分兩種：（1）非搶占式輪轉(zhuǎn)調(diào)度算法（2）非搶占式優(yōu)先調(diào)度算法

二、實(shí)時(shí)調(diào)度的分類362023/1/201、非搶占式調(diào)度算法（1）非搶占式輪轉(zhuǎn)調(diào)度算法用于工業(yè)群控系統(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)行。完成后，便把它掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行，這次調(diào)度程序在選擇下一個(gè)（隊(duì)首）任務(wù)運(yùn)行。可獲得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間二、實(shí)時(shí)調(diào)度的分類372023/1/201、非搶占式調(diào)度算法（2）非搶占式優(yōu)先調(diào)度算法針對(duì)有一定要求的系統(tǒng)為實(shí)時(shí)要求高的任務(wù)賦予較高的優(yōu)先級(jí)。優(yōu)先安排在就緒對(duì)列隊(duì)首，待當(dāng)前任務(wù)結(jié)束后，被調(diào)度執(zhí)行。響應(yīng)時(shí)間為數(shù)秒至數(shù)百毫秒二、實(shí)時(shí)調(diào)度的分類382023/1/202、搶占式調(diào)度算法應(yīng)用于響應(yīng)時(shí)間在數(shù)十毫秒以下的系統(tǒng)。根據(jù)搶占發(fā)生時(shí)間不同分類：（1）基于時(shí)鐘中斷的搶占式優(yōu)先級(jí)調(diào)度算法。（2）立即搶占的優(yōu)先級(jí)調(diào)度算法。二、實(shí)時(shí)調(diào)度的分類392023/1/202、搶占式調(diào)度算法

（1）基于時(shí)鐘中斷的優(yōu)先級(jí)調(diào)度算法高優(yōu)先級(jí)的實(shí)時(shí)任務(wù)到達(dá)后不立即搶占，等到時(shí)鐘中斷到來時(shí)再重新分配處理機(jī)。調(diào)度時(shí)間延遲：幾十到幾百毫秒。二、實(shí)時(shí)調(diào)度的分類402023/1/202、搶占式調(diào)度算法

（2）立即搶占的優(yōu)先級(jí)調(diào)度算法高優(yōu)先級(jí)的實(shí)時(shí)任務(wù)到達(dá)后，只要當(dāng)前任務(wù)未處于臨界區(qū)就立即把處理機(jī)分配給它。二、實(shí)時(shí)調(diào)度的分類412023/1/20進(jìn)程1進(jìn)程2……進(jìn)程n實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行非搶占輪轉(zhuǎn)調(diào)度算法調(diào)度時(shí)間二、實(shí)時(shí)調(diào)度的分類422023/1/20

當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度當(dāng)前進(jìn)程完成非搶占優(yōu)先級(jí)調(diào)度算法調(diào)度時(shí)間二、實(shí)時(shí)調(diào)度的分類432023/1/20

當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度時(shí)鐘中斷到來基于時(shí)鐘中斷的搶占式優(yōu)先級(jí)調(diào)度算法調(diào)度時(shí)間二、實(shí)時(shí)調(diào)度的分類442023/1/20

當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度搶占并立即執(zhí)行立即搶占的優(yōu)先級(jí)調(diào)度算法調(diào)度時(shí)間二、實(shí)時(shí)調(diào)度的分類452023/1/20最早截止時(shí)間優(yōu)先算法即EDF算法（EARLIESTDEADLINEFIRST）最低松弛優(yōu)先算法即LLF算法（LEASTLAXITYFIRST）三、常用的幾種實(shí)時(shí)調(diào)度算法462023/1/201、最早截止時(shí)間優(yōu)先調(diào)度算法根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間愈早，其優(yōu)先級(jí)愈高；在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的早晚排序；調(diào)度程序選擇隊(duì)首任務(wù)分配處理機(jī)