操作系統(tǒng)第6講

1、操作系統(tǒng)概念第六講 CPU調(diào)度(1)上章回顧1、產(chǎn)生死鎖的四個(gè)必要條件？如何預(yù)防？本課總體綱要基本概念調(diào)度術(shù)語作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程上下文切換進(jìn)程調(diào)度的性能評(píng)價(jià)調(diào)度算法先到先服務(wù)調(diào)度最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度輪轉(zhuǎn)法調(diào)度基本概念CPU調(diào)度：進(jìn)程調(diào)度程序按照一定的策略，動(dòng)態(tài)的將CPU分配給某個(gè)進(jìn)程，并使之執(zhí)行。目的：以使CPU資源利用率最高。進(jìn)程執(zhí)行由CPU執(zhí)行與IO等待周期組成?；靖拍?CPU區(qū)間時(shí)間直方圖CPU調(diào)度當(dāng)CPU變?yōu)榭臻e時(shí)，操作系統(tǒng)就必須從就緒的隊(duì)列中選擇一個(gè)進(jìn)程來執(zhí)行。系統(tǒng)調(diào)度分為4級(jí)：作業(yè)調(diào)度交換調(diào)度進(jìn)程調(diào)度線程調(diào)度本課總體綱要基本概念調(diào)度術(shù)語作業(yè)調(diào)度進(jìn)

2、程調(diào)度進(jìn)程調(diào)度功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程上下文切換進(jìn)程調(diào)度的性能評(píng)價(jià)調(diào)度算法先到先服務(wù)調(diào)度最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度輪轉(zhuǎn)法調(diào)度調(diào)度術(shù)語CPU利用率：使CPU盡可能忙，實(shí)現(xiàn)高效。吞吐量：(throughput)單位時(shí)間中完成的進(jìn)程周轉(zhuǎn)時(shí)間：運(yùn)行該進(jìn)程所花費(fèi)的時(shí)間等待時(shí)間：在就緒隊(duì)列中等待所花費(fèi)的時(shí)間響應(yīng)時(shí)間：從提交請(qǐng)求到產(chǎn)生第一個(gè)響應(yīng)的時(shí)間CPU作業(yè)調(diào)度作業(yè)調(diào)度功能：記錄系統(tǒng)中作業(yè)的狀況從后備作業(yè)隊(duì)列中挑選一批作業(yè)進(jìn)入執(zhí)行狀態(tài)被選中的作業(yè)分配資源建立進(jìn)程作業(yè)執(zhí)行結(jié)束后釋放所占用的資源作業(yè)調(diào)度目標(biāo)：對(duì)所有作業(yè)應(yīng)該公平合理較高的利用率每天執(zhí)行盡可能多的作業(yè)響應(yīng)時(shí)間快本課總體綱要基本概念調(diào)度術(shù)語作業(yè)調(diào)度進(jìn)

3、程調(diào)度進(jìn)程調(diào)度功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程上下文切換進(jìn)程調(diào)度的性能評(píng)價(jià)調(diào)度算法先到先服務(wù)調(diào)度最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度輪轉(zhuǎn)法調(diào)度進(jìn)程調(diào)度功能功能包括：記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況選擇占有處理機(jī)的進(jìn)程進(jìn)行進(jìn)程上下文切換進(jìn)程調(diào)度時(shí)機(jī)進(jìn)程執(zhí)行完畢進(jìn)入睡眠等待狀態(tài)執(zhí)行進(jìn)程中調(diào)用了P,V原語執(zhí)行中進(jìn)程提出I/O請(qǐng)求分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完系統(tǒng)進(jìn)程執(zhí)行完畢，調(diào)度用戶進(jìn)程就緒隊(duì)列中某進(jìn)程優(yōu)先權(quán)高于當(dāng)前執(zhí)行的進(jìn)程進(jìn)程上下文切換進(jìn)程上下文切換包括四個(gè)步驟：決定是否做上下文切換保存當(dāng)前執(zhí)行的進(jìn)程上下文采用合理的調(diào)度算法，選擇一個(gè)處于就緒狀態(tài)進(jìn)程恢復(fù)所選進(jìn)程的上下文，將控制權(quán)交給所選進(jìn)程 進(jìn)程調(diào)度性能評(píng)價(jià)進(jìn)程調(diào)度性能的衡

4、量是操作系統(tǒng)設(shè)計(jì)的一個(gè)重要指標(biāo)定性：調(diào)度的可靠性、簡(jiǎn)潔性定量：CPU利用率，進(jìn)程的等待/執(zhí)行率方法：對(duì)進(jìn)程調(diào)度的解析是十分困難的，一般采用模擬或測(cè)試系統(tǒng)響應(yīng)時(shí)間的方法本課總體綱要基本概念調(diào)度術(shù)語作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程上下文切換進(jìn)程調(diào)度的性能評(píng)價(jià)調(diào)度算法先到先服務(wù)調(diào)度最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度輪轉(zhuǎn)法調(diào)度調(diào)度算法先到先服務(wù)調(diào)度（FCFS）先請(qǐng)求CPU的進(jìn)程被首先分配到CPU當(dāng)進(jìn)程之間的處理時(shí)間相差較大時(shí)，采用FCFS策略的平均等待時(shí)間較長(zhǎng)。Process Burst TimeP1 24P2 3P3 3 P1P2P32427300P1P3P263300最短作業(yè)優(yōu)先調(diào)度最短作業(yè)

5、優(yōu)先調(diào)度（SJF）將每個(gè)進(jìn)程與其下一個(gè)CUP區(qū)間段相關(guān)聯(lián)，當(dāng)CPU可用時(shí)，它會(huì)賦給具有最短后續(xù)CPU區(qū)間的進(jìn)程兩種方法非搶占性一旦一個(gè)進(jìn)程開始執(zhí)行就需完成該次任務(wù)搶占性如果新來的進(jìn)程CPU區(qū)間段比當(dāng)前進(jìn)程的時(shí)間段小，則優(yōu)先選擇新進(jìn)程。稱為SRTF(Shorest Remaining Time First)SJF算法是最優(yōu)的。最短作業(yè)優(yōu)先調(diào)度 進(jìn)程 到達(dá)時(shí)間區(qū)間時(shí)間P10.07P22.04P34.01P45.04SJF (非搶占性)SJF平均等待時(shí)間 = (0 + (7-4)+(8-2) +(12-5)/4 =4msFCFS平均等待時(shí)間（0(7-2)(11-4)(12-5)/4=4.75msP1

6、P3P273160P4812最短作業(yè)優(yōu)先調(diào)度 ProcessArrival TimeBurst TimeP10.07P22.04P34.01P45.04SJF (搶占性)P1P3P242110P457P2P116平均等待時(shí)間 = (9 + 1 + 0 +2)/4 = 3最短作業(yè)優(yōu)先調(diào)度如何決定下一個(gè)CPU區(qū)間的長(zhǎng)度用前一個(gè)CPU區(qū)間的長(zhǎng)度估計(jì)下一個(gè)CPU區(qū)間的長(zhǎng)度最短作業(yè)優(yōu)先調(diào)度 =0n+1 = nRecent history does not count =1 n+1 = tn實(shí)際最后一個(gè)CPU區(qū)間記數(shù)。n+1 = tn+(1 - ) tn -1 + +(1 - )j tn -j + +(1

7、 - )n +1 0因?yàn)?and (1 - ) 小于或等于 1,所以后面項(xiàng)的權(quán)比前面項(xiàng)權(quán)要小。最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度每個(gè)進(jìn)程都有優(yōu)先權(quán)具有最高優(yōu)先權(quán)的進(jìn)程分配給CPUSJF算法作為優(yōu)先權(quán)算法的特例。優(yōu)先權(quán)為下一個(gè)CPU區(qū)間的倒數(shù)。CPU區(qū)間越大，優(yōu)先權(quán)越小導(dǎo)致的問題：饑餓（starvation)低優(yōu)先權(quán)的進(jìn)程可能永遠(yuǎn)也不會(huì)運(yùn)行。（無窮阻塞）解決方案：老化(aging)逐漸增加在系統(tǒng)中等待很長(zhǎng)時(shí)間的進(jìn)程的優(yōu)先權(quán)。輪轉(zhuǎn)法調(diào)度（Round-Robin)輪轉(zhuǎn)法調(diào)度：專門為分時(shí)系統(tǒng)設(shè)計(jì)的。每個(gè)進(jìn)程得到一個(gè)較小的時(shí)間單元時(shí)間片（time quantum），時(shí)間片通常（10ms100ms)。系統(tǒng)給每個(gè)進(jìn)

8、程分配若干個(gè)時(shí)間片，被調(diào)度的進(jìn)程運(yùn)行完時(shí)間片后，系統(tǒng)就發(fā)生調(diào)度。如果有n個(gè)進(jìn)程，q個(gè)時(shí)間片，那么每個(gè)進(jìn)程會(huì)得到1/n的CPU時(shí)間，每個(gè)長(zhǎng)度不超過q時(shí)間單元。每個(gè)進(jìn)程必須等待CPU的時(shí)間不會(huì)超過（n-1）q個(gè)時(shí)間單元，直到下一個(gè)時(shí)間片為止。兩種情況：CPU區(qū)間小于時(shí)間片CPU區(qū)間大于時(shí)間片輪轉(zhuǎn)法調(diào)度ProcessBurst TimeP153P2 17P368P4 24甘特圖為（時(shí)間片q20ms): 特點(diǎn)：平均等待時(shí)間較高，但響應(yīng)較好P1P2P3P4P1P3P4P1P3P302037577797117121134154162輪轉(zhuǎn)法調(diào)度時(shí)間片與上下文時(shí)間的關(guān)系輪轉(zhuǎn)法調(diào)度不同時(shí)間片的平均等待時(shí)間統(tǒng)計(jì)輪轉(zhuǎn)法性能