處理機(jī)調(diào)度算法詳解

1、1關(guān)于處理機(jī)調(diào)度算法關(guān)于處理機(jī)調(diào)度算法《操作系統(tǒng)》教材中，介紹了常用的作業(yè)調(diào)度算法和進(jìn)程調(diào)度算法。其中先來(lái)先服務(wù)法（FCFS）和優(yōu)先級(jí)法對(duì)作業(yè)調(diào)度和進(jìn)程調(diào)度都適用，時(shí)間片輪轉(zhuǎn)法（RR）適用于進(jìn)程調(diào)度。此外，還介紹了其他調(diào)度算法，如短作業(yè)優(yōu)先法、最短剩余時(shí)間優(yōu)先法、多級(jí)隊(duì)列法和多級(jí)反饋隊(duì)列法，這4個(gè)算法不是課程的重點(diǎn)內(nèi)容，不作為考核要求。需要指出的是：（1）在作業(yè)調(diào)度和進(jìn)程調(diào)度中同時(shí)出現(xiàn)的算法，如FCFS、優(yōu)先級(jí)法，其使用原理是基本相同的

2、；（2）作業(yè)調(diào)度算法和進(jìn)程調(diào)度算法應(yīng)嚴(yán)格與存儲(chǔ)管理中的“請(qǐng)求淘汰換頁(yè)算法”相區(qū)別，注意不要混淆。下面，結(jié)合具體的例題，詳解調(diào)度算法：1.先來(lái)先服務(wù)法（先來(lái)先服務(wù)法（FCFS）算法描述：每次調(diào)度時(shí)，從后備作業(yè)隊(duì)列或就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的作業(yè)或進(jìn)程。【例1】下表給出作業(yè)l，2，3的到達(dá)時(shí)間和運(yùn)行時(shí)間。采用先來(lái)先服務(wù)調(diào)度算法，試問作業(yè)調(diào)度的次序和平均周轉(zhuǎn)時(shí)間各為多少？（時(shí)間單位：小時(shí)，以十進(jìn)制進(jìn)行計(jì)算。）作業(yè)號(hào)到達(dá)時(shí)間運(yùn)行時(shí)間12

3、30.00.41.08.04.01.0分析分析解題關(guān)鍵是要根據(jù)系統(tǒng)采用的調(diào)度算法，弄清系統(tǒng)中各道作業(yè)隨時(shí)間的推進(jìn)情況。我們可以用一個(gè)作業(yè)執(zhí)行時(shí)間圖來(lái)形象地表示作業(yè)的執(zhí)行情況，幫助我們理解此題。先來(lái)先服務(wù)調(diào)度算法是按照作業(yè)到達(dá)的先后次序挑選作業(yè)，先進(jìn)入的作業(yè)優(yōu)先被挑選。即按照“排隊(duì)買票”的辦法，依次選擇作業(yè)。其作業(yè)執(zhí)行時(shí)間圖如下：或者簡(jiǎn)化為下圖：作業(yè)1作業(yè)2作業(yè)3||||時(shí)間081213由于作業(yè)1，2，3是依次到來(lái)的，所以剛開始時(shí)系統(tǒng)中只

4、有作業(yè)1，于是作業(yè)1被選中。在8.0時(shí)刻，作業(yè)1運(yùn)行完成，這時(shí)作業(yè)2和作業(yè)3已經(jīng)到達(dá)，都在系統(tǒng)中等待調(diào)度，按照先來(lái)先服務(wù)法的規(guī)定，每次調(diào)度最先進(jìn)入就緒隊(duì)列中的作業(yè)，由于作業(yè)2比作業(yè)3先到達(dá)，于是作業(yè)2被優(yōu)先選中運(yùn)行。待作業(yè)2運(yùn)行完畢，最后運(yùn)行作業(yè)3。因此，作業(yè)調(diào)作業(yè)作業(yè)3作業(yè)2作業(yè)100.41.08.012.013.0時(shí)間作業(yè)提交時(shí)間各作業(yè)陸續(xù)完成時(shí)間3根據(jù)執(zhí)行時(shí)間圖就可以計(jì)算各個(gè)進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間了。這里要注意的是，

5、要記住帶權(quán)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間的算術(shù)公式：帶權(quán)周轉(zhuǎn)時(shí)間W，即：W=RT其中T為周轉(zhuǎn)時(shí)間，R為實(shí)際運(yùn)行時(shí)間。平均帶權(quán)周轉(zhuǎn)時(shí)間為：nRTnWWniiinii1111????????????????????????解：解：采用時(shí)間片輪轉(zhuǎn)法進(jìn)行調(diào)度，算法的性能指標(biāo)如下：到達(dá)時(shí)間進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A020050502.5B010134343.4C015245453.0D05320204.0時(shí)間片=1平

6、均周轉(zhuǎn)時(shí)間=37.25平均帶權(quán)周轉(zhuǎn)時(shí)間=3.225TWA020050502.5B010530303.0C0151045453.0D051520204.0時(shí)間片=5平均周轉(zhuǎn)時(shí)間=36.25平均帶權(quán)周轉(zhuǎn)時(shí)間=3.125TW感興趣的同學(xué)還可以根據(jù)時(shí)間片從1~10的變化，多計(jì)算幾次，并分析每次計(jì)算得到的平均周轉(zhuǎn)時(shí)間，做一條平均周轉(zhuǎn)時(shí)間隨時(shí)間片變化的曲線，來(lái)體會(huì)時(shí)間片的變化對(duì)平均周轉(zhuǎn)時(shí)間的影響，并分析原因。05101520253035404550