操作系統(tǒng)3處理機管理課件

1、第3章 處理機管理本章目錄本章目錄3.1 處理機調(diào)度概述3.1.1 處理機調(diào)度的三個層次3.1.2 進程調(diào)度的功能、時機和基本策略3.2 作業(yè)調(diào)度算法3.2.1 先來先服務(wù)調(diào)度算法3.2.2 短作業(yè)優(yōu)先調(diào)度算法3.5.3 linux的進程調(diào)度算法3.2.3 最短剩余時間優(yōu)先調(diào)度算法3.1.3 調(diào)度算法的性能評價指標(biāo)3.4 實時處理與實時調(diào)度算法3.4.1 實時處理的特征3.4.2 最早截止時間優(yōu)先調(diào)度算法3.4.3 速率單調(diào)調(diào)度算法3.5 linux的處理機調(diào)度3.5.1 涉及調(diào)度的進程分類3.5.2 linux的可運行隊列3.2.4 最高響應(yīng)比調(diào)度算法3.3 進程調(diào)度算法3.3.1 先來先服

2、務(wù)調(diào)度算法3.3.2 輪轉(zhuǎn)調(diào)度算法3.3.3 優(yōu)先級調(diào)度算法3.3.4 多級隊列調(diào)度算法3.3.5 多級反饋隊列調(diào)度算法3.1 處理機調(diào)度概述處理機調(diào)度概述 o3.1.1 處理機調(diào)度的三個層次處理機調(diào)度的三個層次 高級調(diào)度高級調(diào)度 1. 當(dāng)系統(tǒng)決定接納一個作業(yè)時，就要為它開辟一個作業(yè)控制塊（ jcb），以便隨時記錄作業(yè)的信息。 . 被系統(tǒng)接納的作業(yè)，在沒有投入運行前是以“后備作業(yè)”的形式存放在輔存里。所有后備作業(yè)的jcb鏈接在一起，形成“后備作業(yè)隊列”。這些作業(yè)沒有資格參與對處理機的競爭，但系統(tǒng)從它們的里面去挑選參與cpu競爭的作業(yè)。. 高級調(diào)度決定哪個后備作業(yè)可進入系統(tǒng)去接受處理，它控制著多

3、道程序設(shè)計環(huán)境的“度”：進到系統(tǒng)的作業(yè)多，資源的利用率提高了，但每個作業(yè)獲得處理結(jié)果的時間可能會長；進到系統(tǒng)的作業(yè)少，每個作業(yè)很快就得到自己的處理結(jié)果，但資源的利用率可能會下降。 低級調(diào)度低級調(diào)度 2. 低級調(diào)度真正決定cpu下一次執(zhí)行哪一個進程，它將按照一定的算法，從就緒隊列里挑選出可運行的進程投入運行。低級調(diào)度的各種算法，是我們討論的主要目標(biāo)。低級調(diào)度也被稱為“進程調(diào)度” 。中級調(diào)度中級調(diào)度 3. 中級調(diào)度是介于高級調(diào)度和低級調(diào)度之間的一種調(diào)度，如果系統(tǒng)為進程設(shè)置有“掛起”狀態(tài)，那么就會涉及到中級調(diào)度。也就是說，中級調(diào)度與實施進程的內(nèi)、外存交換有關(guān)。 cpu就緒隊列低級調(diào)度釋放中級調(diào)度就緒

4、/掛起隊列時間片到高級調(diào)度阻塞/掛起隊列阻塞隊列中級調(diào)度事件等待事件發(fā)生交互用戶作業(yè)后備作業(yè)隊列. 系統(tǒng)中出現(xiàn)過高并發(fā)度時，就應(yīng)將內(nèi)存中的某些進程暫時換出到外存；系統(tǒng)的并發(fā)度較低時，就應(yīng)該將外存中的某些進程換入到內(nèi)存。進程在內(nèi)、外存間的換出和換入，就是中級調(diào)度承擔(dān)的責(zé)任，通過這種交換，以求達到調(diào)節(jié)和平衡系統(tǒng)“并發(fā)度”的目的。 . 高級調(diào)度執(zhí)行的頻繁程度很低，它只是粗略地決定是否接受一個新進程以及接受哪一個；中級調(diào)度為了實施交換決策，執(zhí)行的頻率相對要頻繁一些；低級調(diào)度要精確地決定執(zhí)行哪一個進程，因此執(zhí)行的頻度為最高。 返回目錄o3.1.2 進程調(diào)度的功能、時機和基本策略進程調(diào)度的功能、時機和基本

5、策略 1. 進程調(diào)度程序的功能進程調(diào)度程序的功能 .保護現(xiàn)場 .挑選運行對象 .恢復(fù)現(xiàn)場 2. 發(fā)生進程調(diào)度的時機發(fā)生進程調(diào)度的時機 當(dāng)某進程正常完成自己的運行或被終止時，為不讓cpu空閑，必須實行調(diào)度，以便從就緒隊列里挑選新的進程投入運行。 . 分時系統(tǒng)中，時鐘中斷處理程序發(fā)現(xiàn)分配給某個進程的時間片用完時，就強制它交出cpu，重新進行cpu調(diào)度。 .運行中的進程提出i/o請求，或要等待別的進程發(fā)來消息，于是自己被阻塞。 .執(zhí)行操作系統(tǒng)提供的某些系統(tǒng)調(diào)用命令，如wait()等。 . 某進程的狀態(tài)從阻塞變?yōu)榫途w時，要由調(diào)度程序決定讓哪一個進程投入運行：是新就緒進程、是正在運行的進程繼續(xù)運行、還是

6、調(diào)度另一個進程運行。 3. 進程調(diào)度的基本策略進程調(diào)度的基本策略 非搶占式：在把cpu分配給某個進程后，就一直讓它使用下去，直到進程完成自己的工作，或因要等待某事件的發(fā)生而交出cpu，否則不允許其他進程奪取cpu。 . 搶占式：在調(diào)度程序把cpu分配給某進程使用后，只要滿足某條件，就允許立即把cpu從運行進程手中奪取過來，分配給滿足條件的進程使用。 返回目錄 特定作業(yè)從提交給系統(tǒng)到獲取結(jié)果所經(jīng)歷的時間間隔。因此，設(shè)作業(yè)i向系統(tǒng)提交的時間為tpi，完成時間是tci，那么它的周轉(zhuǎn)時間ti為：ti = tci - tpi 。o3.1.3 調(diào)度算法的性能評價指標(biāo)調(diào)度算法的性能評價指標(biāo) 1.2.吞吐量吞

7、吐量 周轉(zhuǎn)時間周轉(zhuǎn)時間所謂“吞吐量”，是指單位時間內(nèi)cpu完成作業(yè)的數(shù)量。 . 有的作業(yè)屬于“處理機限制”型的，即需要花費大量的cpu時間，很少輸入/輸出，也稱“cpu繁忙”型；有的屬于“i/o限制”型的，即它在運行期間主要是輸入/輸出，很少進行計算和處理，也稱“i/o繁忙”型。.作業(yè)的周轉(zhuǎn)時間 作業(yè)的周轉(zhuǎn)時間是指作業(yè)的執(zhí)行時間加上作業(yè)的等待時間。設(shè)作業(yè)i的等待時間為twi，執(zhí)行時間為tsi，那么它的周轉(zhuǎn)時間ti為：ti = twi + tsi 。（1）（2）.作業(yè)的平均周轉(zhuǎn)時間 n個作業(yè)，每個作業(yè)的周轉(zhuǎn)時間為ti，那么它們的平均周轉(zhuǎn)時間為：t=(ti )i=1nn1利用平均周轉(zhuǎn)時間，可以基于

8、同一批作業(yè)，來衡量不同調(diào)度算法的調(diào)度性能。 . 作業(yè)的“帶權(quán)周轉(zhuǎn)時間”，指該作業(yè)的周轉(zhuǎn)時間與所需運行時間之比。設(shè)作業(yè)i周轉(zhuǎn)時間為ti，所需執(zhí)行時間為ri，那么它的帶權(quán)周轉(zhuǎn)時間wi為： .作業(yè)的平均帶權(quán)周轉(zhuǎn)時間 （3）n個作業(yè)，每個作業(yè)的帶權(quán)周轉(zhuǎn)時間為wi，那么它們的平均周轉(zhuǎn)時間為： .w=( )tiri1n 利用平均帶權(quán)周轉(zhuǎn)時間，可基于同一調(diào)度算法，對不同批次作業(yè)的調(diào)度性能做出比較。 .cpu的利用率的利用率 3. 所謂“cpu的利用率”，是指在一定的時間區(qū)間內(nèi)，cpu為用戶提供服務(wù)的時間與其總運行時間的比率。 作業(yè)i的cpu利用率ui，是指該作業(yè)的執(zhí)行時間ci與周轉(zhuǎn)時間ti的比率。即： .w

9、i=ti/riui=ci/ti.如果系統(tǒng)內(nèi)有n個作業(yè)，那么整個系統(tǒng)cpu的平均利用率應(yīng)為： u=(ci/ti )i=1nn1 公平性：調(diào)度的設(shè)計，應(yīng)該顧及到所有作業(yè)或進程對cpu的不同需求，盡量做到公平合理，不偏不倚。 設(shè)計目標(biāo)：設(shè)計目標(biāo)是決定算法的主要因素，目標(biāo)不同，要求肯定不一樣。比如批處理系統(tǒng)的調(diào)度，應(yīng)盡量提高各種資源的利用率，以及整個系統(tǒng)的吞吐量；分時系統(tǒng)的調(diào)度，應(yīng)將對用戶提出的請求作出回應(yīng)的速度，控制在用戶能夠容忍的范圍內(nèi)；實時系統(tǒng)的調(diào)度，應(yīng)保證對所發(fā)生的的事件做出及時的響應(yīng)和處理；如此等等。 響應(yīng)比響應(yīng)比 4. 所謂作業(yè)的“響應(yīng)比”，是指一個特定作業(yè)的周轉(zhuǎn)時間與它所需的執(zhí)行時間之比

10、。 . 作業(yè)i的等待時間為twi，執(zhí)行時間為tsi，那么該作業(yè)的響應(yīng)比rri是： rri = ( twi + tsi ) / tsi影響調(diào)度算法設(shè)計的因素 .（1）（2）（3） 均衡性：調(diào)度算法應(yīng)考慮資源使用的均衡性，使系統(tǒng)中的各種資源都能得到充分地利用。比如，把“處理機限制”和“i/o限制”作業(yè)搭配，就有可能收到良好的效果。 （4） 兼顧性：調(diào)度算法應(yīng)既考慮長作業(yè)的要求，也考慮短作業(yè)的要求；既考慮高優(yōu)先級進程的要求，也要顧及低優(yōu)先級進程的利益。只偏袒某一方，所造成的后果有可能是嚴重的，甚至是無法彌補的。 返回目錄 右示三個作業(yè)，按1、2、3的順序提交給系統(tǒng)，采用fcfs調(diào)度算法。畫出它們的“

11、甘特圖”，計算每個作業(yè)的周轉(zhuǎn)時間及平均周轉(zhuǎn)時間。（忽略系統(tǒng)調(diào)度所需額外的時間開銷） 作業(yè)1第1個被作業(yè)調(diào)度程序選中運行，花費24個cpu時間運行完畢，故周轉(zhuǎn)時間是：t1=24-0=24；作業(yè)2等待24個cpu時間后被調(diào)度運行，花費3個cpu時間運行完畢，故周轉(zhuǎn)時間是：t2=27-0=27；作業(yè)3的周轉(zhuǎn)時間是：t3=30-0=30。這三個作業(yè)的平均周轉(zhuǎn)時間為(24+27+30)/3=27。 o3.2.1 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法 3.2 作業(yè)調(diào)度算法作業(yè)調(diào)度算法 先來先服務(wù)（fcfs）作業(yè)調(diào)度算法，基于作業(yè)到達后備隊列的先后次序以及作業(yè)對系統(tǒng)資源的需求，從中挑選進入內(nèi)存、成為參與cp

12、u競爭的作業(yè)對象。有時也稱為先進先出（fifo）作業(yè)調(diào)度算法。 .例例3-1 ：作業(yè)所需cpu時間1232433解解： 作業(yè)1作業(yè)2作業(yè)32433.所謂“甘特圖”，即是指能夠反映作業(yè)調(diào)度順序及占用cpu時間的一種進度圖。 右示五個作業(yè)，采用fcfs 作業(yè)和進程調(diào)度算法，可供5個作業(yè) 使用的內(nèi)存空間為100kb，需要時按 序分配。作業(yè)進入內(nèi)存后，不許在內(nèi) 存中移動。計算每個作業(yè)的周轉(zhuǎn)時間和平均周轉(zhuǎn)時間。（忽略系統(tǒng)調(diào)度時間，作業(yè)都沒有輸入/輸出請求）例例3-2 ：作業(yè)所需cpu時間1234510.110.310.510.610.7到達時間所需內(nèi)存量0.70.50.40.40.215kb70kb50

13、kb20kb10kb解解： .各作業(yè)的周轉(zhuǎn)時間裝入內(nèi)存時間完成時間10.110.311.311.310.7開始運行時間周轉(zhuǎn)時間10.811.311.912.311.50.71.01.41.70.810.110.811.511.910.3.作業(yè)運行時的內(nèi)存分配情況作業(yè)1(15kb)作業(yè)2(70kb)作業(yè)5(10kb)空閑(5kb)(a)到10.7時 內(nèi)存情形空閑(15kb)作業(yè)2(70kb)作業(yè)5(10kb)空閑(5kb)(b)到10.8作業(yè)1 完成時內(nèi)存情形作業(yè)3(50kb)作業(yè)4(20kb)作業(yè)5(10kb)空閑(5kb)(c) 到11.3作業(yè)2 完成時內(nèi)存情形空閑(15kb) 這批作業(yè)的調(diào)

14、度順序是： 12534， 系統(tǒng)的平均作業(yè)周轉(zhuǎn)時間為： (0.7+1.0+1.4+1.7+0.8) / 5 = 1.12.返回目錄 各自的開始運行時間、完成時間、周轉(zhuǎn)時間以及帶權(quán)周轉(zhuǎn)時間如下所示。五個作業(yè)的調(diào)度順序是abecd。 有5個作業(yè)ae，情況如表所示，按照sjf進行作業(yè)調(diào)度。計算它們各自的開始運行時間、完成時間、周轉(zhuǎn)時間以及帶權(quán)周轉(zhuǎn)時間。 短作業(yè)優(yōu)先（sjf）調(diào)度算法，總是在作業(yè)后備隊列里選擇要求運行時間最短的、滿足其資源需要的作業(yè)進入內(nèi)存，參與對cpu的競爭。 o3.2.2 短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法.例例3-4 ：作業(yè)所需cpu時間abcde02468到達時間36452解解

15、： 作業(yè)調(diào)度的gantt圖 ：作業(yè)a作業(yè)b作業(yè)c作業(yè)e作業(yè)d36425.開始運行時間 帶權(quán)周轉(zhuǎn)時間 0311159完成時間 周轉(zhuǎn)時間371114311.172.752.801.5039152011返回目錄o3.2.3 最短剩余時間優(yōu)先調(diào)度算法最短剩余時間優(yōu)先調(diào)度算法 . 最短剩余時間優(yōu)先（srtf）作業(yè)調(diào)度算法，是在調(diào)度時從后備作業(yè)隊列里挑選所需運行時間最短的作業(yè)投入運行。運行過程中，若有運行時間更短的作業(yè)達到，那么它就搶占cpu，讓當(dāng)前正在運行的作業(yè)暫停執(zhí)行。 例例3-5 ： 有5個作業(yè)ae，情況如表所示，按照srtf進行作業(yè)調(diào)度。計算它們的開始運行時間、完成時間、周轉(zhuǎn)時間以及帶權(quán)周轉(zhuǎn)時間。

16、作業(yè)所需cpu時間abcde02468到達時間36452解解： . 各自的開始運行時間、完成時間、周轉(zhuǎn)時間以及帶權(quán)周轉(zhuǎn)時間如下所示。五個作業(yè)的調(diào)度順序是：abcebd 。 .作業(yè)調(diào)度的gantt圖 ：.開始運行時間 帶權(quán)周轉(zhuǎn)時間 034158完成時間 周轉(zhuǎn)時間313414212.171.02.801.031582010abcebd0348101520時間e到達d到達c到達b到達a到達62返回目錄 各自的開始運行時間、完成時間、周轉(zhuǎn)時間以及帶權(quán)周轉(zhuǎn)時間如下所示。 有5個作業(yè)ae，情況如表所示，按照hrrn進行作業(yè)調(diào)度。計算它們的開始運行時間、完成時間、周轉(zhuǎn)時間以及帶權(quán)周轉(zhuǎn)時間。 最高響應(yīng)比（hr

17、rn）調(diào)度算法，是在進行新一次調(diào)度時，計算后備作業(yè)隊列里所有作業(yè)當(dāng)前的響應(yīng)比rr，挑選出響應(yīng)比最高者參與對cpu的競爭。 o3.2.4 最高響應(yīng)比調(diào)度算法最高響應(yīng)比調(diào)度算法 .例例3-6 ：作業(yè)所需cpu時間abcde02468到達時間36452解解： .開始運行時間 帶權(quán)周轉(zhuǎn)時間 0391513完成時間 周轉(zhuǎn)時間37914711.172.252.803.539132015作業(yè)調(diào)度的gantt圖 ：.作業(yè)a作業(yè)b作業(yè)c作業(yè)e作業(yè)d36425. 時刻9作業(yè)b完成后，作業(yè)c、d、e都到 達系統(tǒng)。計算它們?nèi)齻€的響應(yīng)比，即： rrc = (9-4) + 4)/4=2.25 rrd = (9-6) +

18、5)/5=1.6 rre = (9-8) + 2)/2=1.5 比較后知，這時作業(yè)c的響應(yīng)比最高，所以應(yīng)調(diào)度它運行。五個作業(yè)調(diào)度順序是：abced。 返回目錄3.3 進程調(diào)度算法進程調(diào)度算法 o3.3.1 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法 進程的先來先服務(wù)調(diào)度算法作用在就緒隊列上。進程就緒時，將pcb插入到就緒隊列尾部；調(diào)度時，總是把cpu分配給就緒隊列之首的進程使用。它一直占用cpu，除非運行結(jié)束自愿釋放，或因等待某事件的發(fā)生交出cpu。這是一種非搶占式的調(diào)度算法。 .o3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法 系統(tǒng)時鐘周期性地產(chǎn)生中斷。中斷發(fā)生時，迫使當(dāng)前正在運行的進程中止運行，到就緒隊列

19、里排隊，調(diào)度程序按fcfs從就緒隊列里選擇就緒進程投入運行。因此每個運行進程在被搶占前，最多運行一個規(guī)定的時間長度，這個時間長度被稱為“時間片”。 .分配給進程a的一個時間片q分配給進程b的一個時間片q分配給進程a的另一個時間片q時鐘中斷時鐘中斷時鐘中斷用戶a一次交互結(jié)束. rr調(diào)度算法的關(guān)鍵是時間片設(shè)置的大小。若時間片q設(shè)置得小，那么長作業(yè)可能需要經(jīng)若干個時間片才能完成一次交互活動，從而增加了系統(tǒng)在進程間切換時的開銷；若時間片q設(shè)置得長，長到每個交互只需要一個時間片就能夠完成時，那么rr就成fcfs了。所以，時間片的尺寸最好是略大于一次典型交互活動所需的時間。 q=4 時，五個進程的調(diào)度順序

20、是：abcdbed q=1 時，五個進程的調(diào)度順序是：aaabbcbdcbedcbedcbdd 五個作業(yè)ae的情況如右所示，對進程實施兩次rr調(diào)度算法，時間片分別為1個cpu時間單位和4個cpu時間單位。求各進程的開始運行時間、完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間以及帶權(quán)平均周轉(zhuǎn)時間。 . rr進程調(diào)度是個多路開關(guān)，通過它把一個cpu分配給多個進程使用，產(chǎn)生出有多個邏輯cpu的空幻印象，只是每個邏輯cpu的運行速度要比真正的物理cpu來得慢罷了。 02051015abcde輪轉(zhuǎn)q=1(rr)abcde輪轉(zhuǎn)q=4(rr)02051015進程b到達進程a到達進程c到達進程d到達進程e到達

21、例例3-7 ：作業(yè)所需cpu時間abcde02468到達時間36452.解解： 返回目錄 就緒隊列里有如右所示五個進程p1p5 ，實施hpf調(diào)度算法，試計算平均等待時間。o3.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法 . 優(yōu)先級調(diào)度（hpf）算法，是基于進程優(yōu)先級進行的調(diào)度算法。在需要調(diào)度時，hpf算法總是從就緒隊列里挑選優(yōu)先級最高者投入運行。 進程的pcb里，都會記錄進程的優(yōu)先級。優(yōu)先級常用數(shù)字表示，比如07，或04095。不過，數(shù)字0到底表示最高還是最低，各個操作系統(tǒng)不盡相同。有的系統(tǒng)以數(shù)字越小表示優(yōu)先級越高，有的則以數(shù)字越大表示優(yōu)先級越高。本書規(guī)定數(shù)字越小優(yōu)先級越高。 .例例3-8 ：進程所

22、需cpu時間p1p2p3p4p5101215優(yōu)先級31452它們的調(diào)度順序是：p2p5p1p3p4 。.解解： .相應(yīng)的gantt圖如下所示。p2p5p1p3p40161618 19 搶占式優(yōu)先級調(diào)度算法：一個新進程抵達就緒隊列時，若優(yōu)先級高于當(dāng)前運行進程，那就讓當(dāng)前進程暫停運行進入就緒隊列，把cpu分配給新進程使用，實現(xiàn)搶占。. 非搶占式優(yōu)先級調(diào)度算法：就緒隊列基于進程優(yōu)先級進行排隊，優(yōu)先級高的排在前面，優(yōu)先級低的排在后面。調(diào)度時，總是把就緒隊列的首進程作為分配cpu的對象。.確定進程優(yōu)先級的因素 根據(jù)進程的類型。比如由于系統(tǒng)進程完成的任務(wù)是提供系統(tǒng)服務(wù)，分配系統(tǒng)資源，因此給予系統(tǒng)進程較高的

23、優(yōu)先級，不僅合乎情理，而且也能夠提高系統(tǒng)的工作效率。 (1)(2) 根據(jù)進程執(zhí)行任務(wù)的重要性。每個進程所完成的任務(wù)，其重要性和緊迫性肯定是不一樣的。比如，賦予報警進程高的優(yōu)先級，一旦緊急事件發(fā)生時，讓它立即搶占cpu投入運行，這是理所當(dāng)然的事情。 (3) 根據(jù)進程程序的性質(zhì)。一個“處理機限制”進程，由于需占用較長的運行時間，影響系統(tǒng)整體效率的發(fā)揮，因此只能給予較低的優(yōu)先級；一個“i/o限制”進程，給予它較高的優(yōu)先級后，就能充分發(fā)揮cpu和外部設(shè)備之間的并行工作能力。 (4) 根據(jù)對資源的要求。系統(tǒng)資源有處理機、內(nèi)存儲器、外部設(shè)備等?？砂凑找粋€進程所需資源的類型和數(shù)量，確定它的優(yōu)先級。比如給予占

24、用cpu時間短或內(nèi)存容量少的進程以較高的優(yōu)先級，這樣可以提高系統(tǒng)的吞吐量。 (5) 根據(jù)用戶的請求。系統(tǒng)可以根據(jù)用戶的請求，給予它的作業(yè)及其相應(yīng)進程很高的優(yōu)先級，作“加急”處理。 . 進程優(yōu)先級的分類：所謂“靜態(tài)”優(yōu)先級，即指在進程的整個生命期內(nèi)優(yōu)先數(shù)保持不變；所謂“動態(tài)”優(yōu)先級，是指在進程的整個生命期內(nèi)可隨時修正它的優(yōu)先級別，以適應(yīng)系統(tǒng)環(huán)境和條件的變化。 返回目錄o3.3.4 多級隊列調(diào)度算法多級隊列調(diào)度算法 . 多級隊列（mq）調(diào)度算法，是把就緒進程按不同的性質(zhì)組合成若干個就緒隊列，每個隊列實行不同的進程調(diào)度算法。 系統(tǒng)進程就緒隊列實時進程就緒隊列交互進程就緒隊列批處理進程就緒隊列優(yōu)先級高

25、低. 可按進程的類型組建各種就緒隊列：系統(tǒng)進程就緒隊列、實時進程就緒隊列、交互進程就緒隊列、批處理進程就緒隊列等。每個隊列都執(zhí)行自己的調(diào)度算法。 . 兩個隊列間獲得cpu的權(quán)利要有先后次序。比如，根據(jù)每個隊列的優(yōu)先級不同，越往上的隊列，獲得cpu的優(yōu)先級越高；越往下的隊列，獲得cpu的優(yōu)先級越低。這樣，只有在系統(tǒng)進程就緒隊列和實時進程就緒隊列為空的前提下，才能夠去調(diào)度交互進程就緒隊列里的進程；當(dāng)一個批處理進程執(zhí)行時，若有一個交互進程抵達了就緒隊列，那么批處理進程就將被搶占，把cpu讓給交互進程使用。返回目錄 系統(tǒng)從第1個隊列開始調(diào)度；只有在前i-1個隊列都空時，才調(diào)度第i個隊列里的進程。當(dāng)更高

26、級別的隊列到達進程時，系統(tǒng)將立即轉(zhuǎn)去運行級別高的那個進程。 系統(tǒng)設(shè)多個就緒隊列，有自己的優(yōu)先級，第1個隊列的優(yōu)先級最高，越往下隊列的優(yōu)先級依次降低。 多級反饋隊列（mfq）調(diào)度算法，是在多級隊列調(diào)度算法基礎(chǔ)上加入隊列間的反饋措施構(gòu)成的，它允許進程在不同的就緒隊列里移動?！胺答仭?，是依據(jù)進程使用cpu的時間長短進行的。 .o3.3.5 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法 cpu調(diào)度阻塞，就緒時間片到cpu調(diào)度阻塞，就緒完成完成時間片到cpu調(diào)度阻塞，就緒時間片到完成到達級1(先來先服務(wù))級2(先來先服務(wù))級n(輪轉(zhuǎn)或先來先服務(wù)).多級反饋隊列的做法(1)(2) 為就緒隊列分配不同時間片，在

27、優(yōu)先級高的隊列里的進程，獲得的cpu服務(wù)時間短；在優(yōu)先級低的隊列里的進程，獲得的cpu服務(wù)時間長。 (3) n個隊列都實施fcfs調(diào)度算法，最后一個隊列也可實施rr調(diào)度算法。新進程抵達時，先進入第1個就緒隊列。進程在某個隊列里獲得時間片后，若用完時間片前被阻塞，仍回原隊列末尾排隊；若耗盡時間片后仍未做完工作，則將其移入低一級就緒隊列排隊，直至隊列n。 (4)返回目錄 所謂“任務(wù)速率”，是該任務(wù)周期t（單位為秒）的倒數(shù)。比如，如果一個任務(wù)的周期是50ms，那么它的速率是20次/秒。一個任務(wù)的“執(zhí)行時間”c，是指該任務(wù)所需要的cpu時間總量。在單處理器系統(tǒng)中，任務(wù)的執(zhí)行時間c必須小于它的周期t。一

28、個任務(wù)如果在執(zhí)行期間沒被打斷，那么它的cpu利用率應(yīng)該是u=c/t。比如說，一個任務(wù)的周期是80ms，執(zhí)行時間是55ms，那么它的cpu利用率為55/80=0.6875。 3.4 實時處理與實時調(diào)度算法實時處理與實時調(diào)度算法 o3.4.1 實時處理的特征實時處理的特征 1. 實時處理的特征實時處理的特征 “時限性”：每個實時任務(wù)都有一個期限，指明任務(wù)的開始時間或結(jié)束時間，也就是最晚何時須開始（最早截止時間），或最晚何時候須完成（最晚截止時間）。根據(jù)時限要求，可分為“硬實時任務(wù)”和 “軟實時任務(wù)”兩類。 (1)(2) “周期性”： “周期性任務(wù)”是指一個任務(wù)過一定的時間間隔t就做一次（稱一個“實

29、例”）。也就是說，每隔t個cpu單位時間做一次。所謂“非周期性任務(wù)”，是指那些只有開始或結(jié)束的時限約束的任務(wù)。 任務(wù)p任務(wù)p的一個周期任務(wù)p任務(wù)p的一個周期任務(wù)p空閑空閑時間一個實例一個實例(3)2. 實時進程的幾種處理方式實時進程的幾種處理方式 . 時間片輪轉(zhuǎn)的搶占式調(diào)度：出現(xiàn)對實時進程的請求時，該進程被添加到就緒隊列等待它時間片的到來。這種調(diào)度對于實時進程來說，通常是難以接受的。 當(dāng)前進程進程1進程n實時進程來自實時進程的請求實時進程被添加到就緒隊列中，等待它的下一個時間片調(diào)度時間進程2就緒隊列. 優(yōu)先級非搶占式調(diào)度：出現(xiàn)對實時進程的請求時，賦予它最高的優(yōu)先級。這樣，只要當(dāng)前進程阻塞或完成

30、，實時進程就可獲得cpu。 當(dāng)前進程來自實時進程的請求進程1實時進程實時進程被添加到就緒隊列首調(diào)度時間就緒隊列當(dāng)前進程阻塞或完成. 基于優(yōu)先級和時鐘中斷相結(jié)合的調(diào)度算法：通過時鐘按照規(guī)則產(chǎn)生搶占點。在到達一個搶占點時，如果有更高優(yōu)先級的進程在等待，那么就進行對cpu的搶占。 當(dāng)前進程來自實時進程的請求進程1實時進程等待下一個搶占點調(diào)度時間下一個搶占點就緒隊列當(dāng)前進程來自實時進程的請求進程1實時進程實時進程搶占當(dāng)前進程立即運行. 立即搶占調(diào)度算法：操作系統(tǒng)幾乎是立即響應(yīng)來自對實時進程的請求，以使調(diào)度的延遲時間降到最小。 返回目錄 有三個都已就緒的實時任務(wù)a、b、c，利用最早截止時間優(yōu)先（edf）

31、調(diào)度算法對它們實施調(diào)度。 o3.4.2 最早截止時間優(yōu)先調(diào)度算法最早截止時間優(yōu)先調(diào)度算法 . 最早截止時間優(yōu)先（edf）算法，是通過任務(wù)最早截止時間所確定的優(yōu)先級來進行調(diào)度，截止時間越早，其優(yōu)先級就越高。 . 調(diào)度具體做法 ：記錄每個任務(wù)每一次的最早截止時間；到達某任務(wù)的最早截止時間時，就產(chǎn)生該任務(wù)的一個實例，并進入就緒隊列；有新任務(wù)進入就緒隊列時，按照各任務(wù)當(dāng)時的最早截止時間進行優(yōu)先調(diào)度。 020406080100120140a1b1c1a2a3a4a5b2b3b4c2c3a1截止時間b1截止時間c1截止時間a2截止時間b2截止時間a3截止時間c2截止時間a4、b3截止時間a1b1c1 a2

32、b2c2 a3a4c3a5b4時間(ms)時間(ms)a1、b1、c1開始時間1030507090110130基本信息最早截止時間優(yōu)先(edf)b3例例3-11 ：實時任務(wù)所需執(zhí)行時間abc10ms15ms5ms周期30ms40ms50ms解：解：返回目錄o3.4.3 速率單調(diào)調(diào)度算法速率單調(diào)調(diào)度算法 . 速率單調(diào)調(diào)度（rms）算法，基于任務(wù)的周期確定出任務(wù)的優(yōu)先級，然后根據(jù)優(yōu)先級進行調(diào)度。周期越短，優(yōu)先級越高。 . 調(diào)度具體做法 ：將任務(wù)的周期轉(zhuǎn)化成它的速率，成為該任務(wù)的靜態(tài)優(yōu)先級；到達某個任務(wù)的最早截止時間時，產(chǎn)生該任務(wù)的一個實例，并進入就緒隊列；有新任務(wù)進入就緒隊列時，按照各個任務(wù)的優(yōu)先

33、級實施調(diào)度。 有三個都已就緒的實時任務(wù)a、b、c，利用速率單調(diào)調(diào)度（rms）算法對它們實施調(diào)度。例例3-12 ：解：解：實時任務(wù)所需執(zhí)行時間abc10ms15ms5ms周期30ms40ms50ms020406080100120140a1b1c1a2a3a4a5b2b3b4c2c3a1截止時間b1截止時間c1截止時間a2截止時間b2截止時間a3截止時間c2截止時間a4、b3截止時間a1b1c1 a2b2c2 a3a4c3a5b4時間(ms)時間(ms)a1、b1、c1開始時間1030507090110130基本信息速率單調(diào)調(diào)度(rms)b3b3返回目錄 實時進程：那些需要極快得到響應(yīng)、有很強調(diào)度

34、要求的進程為實時進程。這些進程如果得不到很快的響應(yīng)，就可能會產(chǎn)生不可預(yù)料的后果。3.5 linux的處理機調(diào)度的處理機調(diào)度 o3.5.1 涉及調(diào)度的進程分類涉及調(diào)度的進程分類1. 根據(jù)性質(zhì)分類根據(jù)性質(zhì)分類 交互式進程：那些經(jīng)常要與用戶進行交互會話的進程為交互式進程。特點是要花費很多時間等待用戶在鍵盤和鼠標(biāo)上進行的操作；接收到用戶的輸入后，應(yīng)在50150ms之間喚醒進程，并對用戶做出回應(yīng)，否則就超出了用戶的忍耐度。 . 批處理進程：那些無需與用戶進行交互、經(jīng)常被安排在后臺運行的進程為批處理進程 。 .2. 根據(jù)使用根據(jù)使用cpu的情況分類的情況分類 . 活動進程：上次沒有使用完自己的時間片的那些

35、進程被視為活動進程。既然上次沒有使用完一個時間片，表明該進程是i/o繁忙的，因此應(yīng)該盡快讓它投入運行。. 過期進程：上次使用完了屬于自己的時間片的那些進程被視為過期進程。既然上次使用完了時間片，表明該進程是cpu繁忙的。為能夠獲得更長的cpu服務(wù)時間，它就必須投入更長時間的等待，等到所有活動進程都過期時才得以運行。返回目錄 policy：指明對進程實行的調(diào)度類型，如sched_fifo（先進先出的實時進程調(diào)度）； sched_rr（時間片輪轉(zhuǎn)的實時進程調(diào)度）； sched_normal（普通的分時進程調(diào)度）。 time_slice：記錄進程時間片中還剩余的時鐘節(jié)拍數(shù)。o3.5.2 linux的

36、可運行隊列的可運行隊列1. pcb中與調(diào)度程序相關(guān)的字段中與調(diào)度程序相關(guān)的字段 state：記錄每個進程的當(dāng)前狀態(tài) 。 static_prio：靜態(tài)優(yōu)先級，取值范圍100（最高優(yōu)先級）139（最低優(yōu)先級）。新進程創(chuàng)建時，總是繼承父進程的靜態(tài)優(yōu)先級。用戶可以通過系統(tǒng)調(diào)用，改變自己的靜態(tài)優(yōu)先級。 (1)(2) prio ：動態(tài)優(yōu)先級，取值范圍100（最高優(yōu)先級）139（最低優(yōu)先級）。系統(tǒng)將根據(jù)進程的靜態(tài)優(yōu)先級、睡眠（等待）時間，計算出它的動態(tài)優(yōu)先級。(3)(4)next_run：指向進程所屬運行隊列鏈表中的下一個進程。 (5)prev_run：指向進程所屬運行隊列鏈表中的前一個進程。(6)arra

37、y：指向進程所在運行隊列的prio_array_t結(jié)構(gòu)。(7)sleep_avg：進程的平均睡眠時間。(8)(9)(10) rt_priority：記錄進程的實時優(yōu)先級 ，每個實時進程都與一個范圍從1（最高優(yōu)先級）99（最低優(yōu)先級）的實時優(yōu)先級數(shù)值相關(guān)。 2. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)prio_array_t 為提高調(diào)度效率， linux為活動和過期進程 各維護一個可運行進程 鏈表，每個鏈表按進程的優(yōu)先級（0139），開設(shè)140個可運行隊列?？蛇\行進程的pcb，通過pcb里的next_run和prev_run兩個字段鏈接在這樣的隊列里，成為140個雙向隊列。 . 通過prio_array_t型數(shù)據(jù)結(jié)構(gòu)

38、，形成兩個可運行鏈表、每個里面有140個可運行隊列。 prio_array_t各字段的內(nèi)容與含義 .32位/字5個字bitmap位圖111012139127優(yōu)先級0優(yōu)先級2優(yōu)先級127pcbpcbpcbpcbpcbpcb(1) nr_active：鏈表中pcb的個數(shù)；(2) bitmap：由字長32位的、5個字組成的優(yōu)先級位圖，當(dāng)且僅當(dāng)某個優(yōu)先級的進程隊列不空時，對應(yīng)的標(biāo)志位為1；(3) queue：140個優(yōu)先級隊列的頭結(jié)點數(shù)組。queue arrays：有兩個元素的數(shù)組，一個是活動進程的可運行鏈表（由active指向），一個是過期進程的可運行鏈表（由expired指向）。 3. 數(shù)據(jù)結(jié)構(gòu)數(shù)

39、據(jù)結(jié)構(gòu)runqueue runqueueactiveexpiredarrays0arrays1一個prio_array_t一個prio_array_tpcbpcbpcbpcbpcbpcbpcbpcbpcbpcb優(yōu)先級0優(yōu)先級0優(yōu)先級139優(yōu)先級139 runqueue是調(diào)度程序中最重要的數(shù)據(jù)結(jié)構(gòu)，它維護著活動進程和過期進程的可運行進程鏈表，隨時記錄著系統(tǒng)調(diào)度時所需的各種信息。 .runqueue里涉及可運行進程的有關(guān)字段如下 ：(1) curr：指向當(dāng)前正在運行進程的pcb。 (2) active：指向活動進程的可運行鏈表指針。 (3) expired：指向過期進程的可運行鏈表指針。 (4). runqueue與prio_array_t 之間的關(guān)系，如圖示。 返回目錄 一