概率論文 進程調(diào)度量化分析中的概率模型應(yīng)用

1、概率論文作者:日期:進程調(diào)度量化分析中的概率模型應(yīng)用摘要：進程調(diào)度算法是計算機操作系統(tǒng)核心算法之一。通過簡化進程的狀態(tài)轉(zhuǎn)換關(guān)系及概 率論的相關(guān)理論，在給定了6個假設(shè)條件和2個近似分布的條件下.本文建立了進程調(diào)度的概 率模型，在該模型的指導(dǎo)下，深入分析進程調(diào)度的定量化指標(biāo)。關(guān)鍵詞：概率模型，進程調(diào)度，泊松分布1 .前言進程調(diào)度算法的功能是按一定的調(diào)度策略選擇處于就緒隊列中的進程在處理機上運行。處理 機利用率和系統(tǒng)吞吐量都與進程調(diào)度算法的好壞直接相關(guān)，其算法設(shè)計直接影響操作系統(tǒng) 的整體性能。通過幾個定量指標(biāo)來評價進程調(diào)度性能的重要性也就不言而喻了。進程調(diào)度算法的評價是一個較復(fù)雜的系統(tǒng)工程期。一般有

2、兩類方法。一類是基于具體調(diào) 度算法的性能分析。常見的進程調(diào)度算法有FIFO、SCBF、HPF、RR、HRN和MFQ。這些調(diào)度算 法各有其優(yōu)缺點,一般只從系統(tǒng)吞吐量的高低、周轉(zhuǎn)時間長短等方面做定性的分析。另一類 是基于樣本統(tǒng)計的性能評價方法。這種方法是通過一定數(shù)量的樣本.來定性分析這些調(diào)度算 法的性能。由于具有代表性樣本的設(shè)計難度和樣本數(shù)量的限制，其性能評價具有一定的片面 性。本文將建立一個進程調(diào)度的簡化概率模型，在此基礎(chǔ)上給出六個定量評價指標(biāo)。綜合分 析進程調(diào)度算法的綜合性能。2 .進程調(diào)度的概率模型2. 1進程狀態(tài)分析在多道程序系統(tǒng)中，處理機的分配和調(diào)用都是以進程為單位。進程從創(chuàng)建而產(chǎn)生.由

3、調(diào) 度而執(zhí)行，由撤銷而死亡。在這個過程中，進程表現(xiàn)出了不同的狀態(tài)。進程創(chuàng)建是進程管理 的第一步,是給進程分配除CPU之外的資源的過程。這個階段稱為進程處于建立狀態(tài)。進程 創(chuàng)建完畢后，新進程將被插入就緒隊列等待處理機的調(diào)用。此時,稱該進程處于就緒狀態(tài)。一個就緒進程獲得CPU,稱該進程正處于執(zhí)行態(tài)。進程從就緒態(tài)到執(zhí)行態(tài)的過程就是分派 程序執(zhí)行調(diào)度算法的結(jié)果,進程在執(zhí)行過程中。也有可能由于某事件而暫時無法繼續(xù)執(zhí)行. 不得不放棄CPU。此時,稱進程處于阻塞態(tài)。進程進入執(zhí)行態(tài)除了可能來自就緒態(tài)外，也可能 來自于阻塞態(tài)。進程執(zhí)行完畢后，還得作必要的善后處理工作，稱這種狀態(tài)為終止?fàn)顟B(tài)。圖 I表明了這些狀態(tài)之

4、間的轉(zhuǎn)換關(guān)系。圖1進程五種狀態(tài)轉(zhuǎn)換2. 2模型建立的假設(shè)條件影響進程調(diào)度的因素比較多，為了使得評價模型簡單實用。我們忽略了一些次要因素。 下面是模型建立的假設(shè)條件。(1)本模型僅實用于多道批處理系統(tǒng),不適合分時系統(tǒng)與實時系統(tǒng).(2)所有進程的執(zhí)行都是一次性的，要么不執(zhí)行(等待)，要么一次執(zhí)行完成。(3)所有進程的執(zhí)行過程中都不會出現(xiàn)死鎖現(xiàn)象。(4)所有進程遵循有閑讓進，忙則等待的原則。(5)新進程進入就緒隊列的過程不會停止。(6)系統(tǒng)是單核的，在某一時刻僅有一個進程在執(zhí)行。根據(jù)上述假設(shè),可以將圖2簡化為：圖2進程調(diào)度的簡化模型圖其中：排隊規(guī)則體現(xiàn)了就緒進程按什么方式和順序接受CPU服務(wù)。一般有

5、：先來先服務(wù)、 優(yōu)先權(quán)服務(wù)、短作業(yè)優(yōu)先和隨機服務(wù)等。2. 3進程調(diào)度的概率模型基于以上假設(shè)和大量的統(tǒng)計數(shù)據(jù)表明：一段時問間隔內(nèi)，進入就緒隊列的進程數(shù)近似符 合參數(shù)為人的Poisson分布。如果我們同時假設(shè)每個進程的CPU服務(wù)時問也近似符合負指數(shù)分 布,則根據(jù)排隊論的相關(guān)知識.不難得出：單CPU簡化進程調(diào)度的概率模型就是M/M/ I排隊 模型。具體而言.(1)在時問問隔段t內(nèi)，進入就緒狀態(tài)的進程數(shù)符合參數(shù)為k的Poisson分布。即(Xt)k ”，pN(T) = K = Ve 一"/< = 1,2,3.其中：n(s)表示在時刻s處于就緒狀態(tài)的進程數(shù)，a表示到達率。(2)每個進程的

6、CPU服務(wù)時間Vn相互獨立,具有相同的負指數(shù)分布：p(vn<t) 1_e-Rtt<0 t>02. 4 M/M/I排隊模型任何一個排隊過程都包括以下三個過程：到達過程；排隊過程；服務(wù)過程。如果一個排 隊系統(tǒng)僅有一個服務(wù)系統(tǒng)，到達顧客數(shù)服從泊松分布，服務(wù)時間服從負指數(shù)分布和FIFO排隊 過程，則該排隊系統(tǒng)被稱為M/M/ I系統(tǒng)。2. 4. 1建模FCFS調(diào)度算法是最簡單的進程調(diào)度算法。算法描述：當(dāng)一個進程處于就緒狀態(tài)，就進入 就緒隊列。當(dāng)前進程停止運行時，就從就緒隊列中選等待時間最長的進程運行。將FCFS調(diào)度算法的處理過程模擬如圖3所示的服務(wù)摸型，該模型由一個隊列和單CPU組 成

7、。假設(shè)進程到達就緒隊列的過程是速率為人的泊松流，CPU的服務(wù)時聞服從負指數(shù)分布， 服務(wù)速率為操作系統(tǒng)中處予就緒狀態(tài)的進程數(shù)目是有限的并且棚對比較小，CPU的服務(wù) 速率U較大。因此FCFS服務(wù)模型可以認為是一個M/M / I隨機服務(wù)模型。ArrivingProcessesDepartingProcesses圖3 FCFS服務(wù)模型2. 4. 2 FCFS算法平均響應(yīng)時間分析對于交互式系統(tǒng)或者實時系統(tǒng)，響應(yīng)時間是用戶所關(guān)心的。特別是當(dāng)系統(tǒng)中有大量進程 共存時，仍要保證每個用戶都有可以接受響應(yīng)的速度而并不感到明顯的延遲。根據(jù)測定，當(dāng) 這種延遲超過150ms時，使用者就會明顯地感覺到°響應(yīng)時間

8、是評價算法的一個重要標(biāo)準(zhǔn)，所以響應(yīng)時間越小越好。根據(jù)公式，如果U越大, 入越小，T越小。這與直覺一樣，如果人不變，進程平均服務(wù)時間I / U越短，則就緒隊列中 進程的等待時間就越短，平均響應(yīng)時間就越短。如果U二入，則T將趨于無窮大，此時系統(tǒng)性 能是最差的。3. 5基于概率模型的進程調(diào)度評估基于M/M/1排隊模型，我們可以得到進程調(diào)度算法的定量指標(biāo)。見表1：指標(biāo)定義數(shù)值說明A平均到達率單位時間內(nèi)到達就 緒排隊列的進程數(shù)平均服務(wù)率單位時間內(nèi)CPU執(zhí)行 的進程數(shù)1 A進程到達就緒隊列 的時間均值1每個CPU的平均執(zhí)行 時間PCPU的利用率入口當(dāng)人CPU處于不斷忙碌中Lq就緒隊列長度均值入2 m-A)

9、Lq _與CPU利用率相關(guān)Wq進程在就緒隊列中 的等待時間均值入R（M -入）該指標(biāo)也可以理解 為進程在就緒隊列 中的平均響應(yīng)時間，Wq = pWw進程逗留時間均值1 p - A不考慮在外存后被 隊列的等待時間表1定量指標(biāo)表從上表不難看出.進程調(diào)度性能僅僅與平均到達率和平均服務(wù)有關(guān)。而由于平均到達率 是不可控的，提高性能就轉(zhuǎn)移到提高平均服務(wù)率上面。平均服務(wù)率是單位時間內(nèi)CPU執(zhí)行的 進程數(shù).與CPU的性能和每個進程需要CPU服務(wù)時間的長短有關(guān)。假定CPU性能一定.如果執(zhí) 行的進程需要CPU服務(wù)的時間越少.那么平均服務(wù)率就越大。從而進程逗留時間均值和進程 在就緒隊列中的等待時間均值越少?；谂抨?/p>

10、規(guī)則而產(chǎn)生的不同算法.如先來先服務(wù)、優(yōu)先 權(quán)服務(wù)、短作業(yè)優(yōu)先和隨機服務(wù)等.必然導(dǎo)致單位時間內(nèi)CPU執(zhí)行的進程數(shù)的不同。顯然.一 段時間間隔內(nèi)短作業(yè)優(yōu)先算法的CPU平均服務(wù)率最高。先來先服務(wù)算法優(yōu)先考慮的是等待時 間最短的進程，而優(yōu)先權(quán)服務(wù)則優(yōu)先考慮的是優(yōu)先權(quán)大的進程，隨機服務(wù)算法是隨機選擇進 程。這三種算法的不同主要體現(xiàn)在優(yōu)先考慮對象的不同，對單個進程有較強的意義”，4. 討論為了使得進程調(diào)度的概率模型簡單和易于建立.我們給出了6個假設(shè)條件和兩個近似分 布。其中第6個假設(shè)條件可以去掉.那么我們所對應(yīng)系統(tǒng)就是多處理機系統(tǒng)。建立的模型就 是M / M / 1排隊模型。兩個近似分布即Poisson分布和負指數(shù)分布也僅僅是我們的參考結(jié)果。 迄今為止，還沒有發(fā)現(xiàn)嚴格的證明。因此本文所闡述的模型也僅僅是一個理論上粗糙的近似。 相關(guān)參數(shù)的確定需要進一步細致的研究。參考文獻(11任泰明.如何用數(shù)學(xué)模型定量評價進程調(diào)度算法的性能。蘭州石化職業(yè)技術(shù)學(xué)院學(xué)報, 2001, I (1) ； 792 Diml tr i Bertsekas. Robert Ga I lager. Data Networks. 2nd E