處理機(jī)調(diào)度算法的比較

《處理機(jī)調(diào)度算法的比較》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、處理機(jī)調(diào)度算法的比較計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)2009摘要：處理機(jī)調(diào)度基本概念、調(diào)度算法優(yōu)劣的評(píng)價(jià)準(zhǔn)則、多種處理機(jī)調(diào)度算法的介紹引言操作系統(tǒng)是處理計(jì)算機(jī)硬件的一層軟件和作為計(jì)算機(jī)用戶與計(jì)算機(jī)硬件的中間的協(xié)調(diào)者。操作系統(tǒng)的CPU調(diào)度器負(fù)責(zé)給各個(gè)任務(wù)分發(fā)CPU帶寬資源。調(diào)度算法負(fù)責(zé)管理當(dāng)前執(zhí)行任務(wù)等額順序和性能3內(nèi)容：3.1處理機(jī)調(diào)度的基本概念高/中/低級(jí)調(diào)度1.高級(jí)調(diào)度（作業(yè)調(diào)度）決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，準(zhǔn)備執(zhí)行。2.低級(jí)調(diào)度（進(jìn)程調(diào)度）決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)

2、分配給該進(jìn)程的具體操作。非搶占方式和搶占方式3.中級(jí)調(diào)度決定把又具備運(yùn)行條件的掛起進(jìn)程重新調(diào)入內(nèi)存，掛到就緒隊(duì)列上，準(zhǔn)備執(zhí)行。3.2調(diào)度算法優(yōu)劣的評(píng)價(jià)準(zhǔn)則衡量和比較調(diào)度算法性能優(yōu)劣主要有一下幾個(gè)因素：　　（1）CPU利用率。CPU是計(jì)算機(jī)系統(tǒng)中最重要的資源，所以應(yīng)盡可能使CPU保持忙，使這一資源利用率最高?！　。?）吞吐量。CPU運(yùn)行時(shí)表示系統(tǒng)正處于工作狀態(tài)，工作量的大小是以每單位時(shí)間所完成的作業(yè)數(shù)目來描述的，這就叫吞吐量。　?。?）周轉(zhuǎn)時(shí)間。指從作業(yè)提交到作業(yè)完成所經(jīng)過的時(shí)間，包括作業(yè)等待，在就緒隊(duì)列中排隊(duì)，在處理機(jī)上運(yùn)行以及進(jìn)行輸入/輸出操作所花時(shí)間的總和

3、?！　。?）等待時(shí)間。處理機(jī)調(diào)度算法實(shí)際上并不影響作業(yè)執(zhí)行或輸入/輸出操作的時(shí)間，只影響作業(yè)在就緒隊(duì)列中等待所花的時(shí)間。因此，衡量一個(gè)調(diào)度算法優(yōu)劣常常簡(jiǎn)單的考察等待時(shí)間。（5）響應(yīng)時(shí)間。指從作業(yè)提交到系統(tǒng)作出相應(yīng)所經(jīng)過的時(shí)間。在交互式系統(tǒng)中，作業(yè)的周轉(zhuǎn)時(shí)間并不一定是最好的衡量準(zhǔn)則，因此，常常使用另一種度量準(zhǔn)則，即相應(yīng)時(shí)間。從用戶觀點(diǎn)看，響應(yīng)時(shí)間應(yīng)該快一點(diǎn)好，但這常常要犧牲系統(tǒng)資源利用率為代價(jià)。（6）公平性——確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的CPU份額或其他資源份額，不會(huì)出現(xiàn)餓死情況。當(dāng)然，這些目標(biāo)本身就存在著矛盾之處，操作系統(tǒng)在設(shè)計(jì)時(shí)必須根據(jù)其類型的不同進(jìn)行權(quán)衡

4、，以達(dá)到較好的效果。下面著重看一下批處理系統(tǒng)的調(diào)度性能指標(biāo)。批處理系統(tǒng)的調(diào)度性能主要用作業(yè)周轉(zhuǎn)時(shí)間和作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間來衡量，此時(shí)間越短，則系統(tǒng)效率越高，作業(yè)吞吐能率越強(qiáng)。如果作業(yè)i提交給系統(tǒng)的時(shí)刻是ts，完成時(shí)刻是tf，那么，作業(yè)的周轉(zhuǎn)時(shí)間ti為：ti=tf-ts實(shí)際上，它是作業(yè)在系統(tǒng)里的等待時(shí)間與運(yùn)行時(shí)間之和。從操作系統(tǒng)來說，為了提高系統(tǒng)的性能，要讓若干個(gè)用戶的平均作業(yè)周轉(zhuǎn)時(shí)間和平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間最小。平均作業(yè)周轉(zhuǎn)時(shí)間T=（Σti）/n如果作業(yè)i的周轉(zhuǎn)時(shí)間為ti，所需運(yùn)行時(shí)間為tk，則稱wi=ti/tk為該作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間。因?yàn)?，ti是等待時(shí)間與運(yùn)行時(shí)間

5、之和，故帶權(quán)周轉(zhuǎn)時(shí)間總大于1。平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=（Σwi）/n通常，用平均作業(yè)周轉(zhuǎn)時(shí)間來衡量對(duì)同一作業(yè)流施行不同作業(yè)調(diào)度算法時(shí)，它們呈現(xiàn)的調(diào)度性能；用平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間來衡量對(duì)不同作業(yè)流施行同一作業(yè)調(diào)度算法時(shí)，它們呈現(xiàn)的調(diào)度性能。這兩個(gè)數(shù)值均越小越好。3.3幾種處理機(jī)調(diào)度算法詳細(xì)介紹3.3.1作業(yè)調(diào)度1、先來先服務(wù)算法先來先服務(wù)FCFS（FirstCome，F(xiàn)irstServed）算法是按照作業(yè)進(jìn)入系統(tǒng)的作業(yè)后備隊(duì)列的先后次序來挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。這是一種非剝奪式算法，容易實(shí)現(xiàn)，但效率不高，只顧及到作業(yè)等候時(shí)間，而沒考慮作業(yè)要求服務(wù)時(shí)

6、間的長(zhǎng)短。顯然這不利于短作業(yè)而優(yōu)待了長(zhǎng)作業(yè)，或者說有利于CPU繁忙型作業(yè)而不利于I/O繁忙型作業(yè)。有時(shí)為了等待長(zhǎng)作業(yè)的執(zhí)行，而使短作業(yè)的周轉(zhuǎn)時(shí)間變得很大。從而，平均周轉(zhuǎn)時(shí)間也變大。2、最短作業(yè)優(yōu)先算法最短作業(yè)優(yōu)先SJF（ShortestJobFirst）算法是以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時(shí)間長(zhǎng)短為標(biāo)準(zhǔn)，總是選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。這是一種非剝奪式調(diào)度算法，它克服了FCFS偏愛長(zhǎng)作業(yè)的缺點(diǎn)，易于實(shí)現(xiàn)，但效率也不高。它的主要弱點(diǎn)：一是需要預(yù)先知道作業(yè)所需的CPU時(shí)間，這個(gè)估計(jì)值很難精確，如果程序員估計(jì)過低，系統(tǒng)就可能提前終止該作業(yè)；二是忽視了作業(yè)等待

7、時(shí)間，由于系統(tǒng)不斷地接受新作業(yè)，而作業(yè)調(diào)度又總是選擇計(jì)算時(shí)間短的作業(yè)投入運(yùn)行，因此，使進(jìn)入系統(tǒng)時(shí)間早但計(jì)算時(shí)間長(zhǎng)的作業(yè)等待時(shí)間過長(zhǎng)，會(huì)出現(xiàn)饑餓現(xiàn)象；三是盡管減少了對(duì)長(zhǎng)作業(yè)的偏愛，但由于缺少剝奪機(jī)制，對(duì)分時(shí)、實(shí)時(shí)處理仍然很不理想。3、響應(yīng)比最高者優(yōu)先（HRRF）算法先來先服務(wù)算法與最短作業(yè)優(yōu)先算法都是比較片面的調(diào)度算法。先來先服務(wù)算法只考慮作業(yè)的等候時(shí)間而忽視了作業(yè)的計(jì)算時(shí)間，而最短作業(yè)優(yōu)先算法恰好與之相反，它只考慮用戶估計(jì)的作業(yè)計(jì)算時(shí)間而忽視了作業(yè)的等待時(shí)間。響應(yīng)比最高者優(yōu)先算法（HighestResponseRatioFirst）是介乎這兩種算法之間的一種折

8、衷的策略，既考慮作業(yè)等待時(shí)間，又考慮作