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

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

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

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

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

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

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