動態(tài)優(yōu)先級算法

《動態(tài)優(yōu)先級算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、《計算機操作系統(tǒng)》課程設(shè)計題目：13采用高響應(yīng)比算法的進程調(diào)度程序班級：小組成員：指導(dǎo)教師：時間：2013.6.24—2013.7.30地點：7b3122013年6月21目錄工作進度表2組員分工21.目的及意義32.課程設(shè)計任務(wù)及要求42.1設(shè)計任務(wù)42.2設(shè)計要求43.算法及數(shù)據(jù)結(jié)構(gòu)53.1算法總體設(shè)計思想53.2動態(tài)優(yōu)先級算法54.程序設(shè)計與實現(xiàn)104.1系統(tǒng)流程圖104.2程序代碼104.3實驗結(jié)果185.結(jié)論206.收獲、體會和建議21參考文獻2121工作進度表時間完成工作完成人周一完成課程設(shè)計的需求分析周二編寫代碼測試代碼周三編寫代碼測試代碼周四編寫代碼測試代碼周五完善

2、程序周六完成設(shè)計報告組員分工（組長）2011XXXX1、設(shè)計并編寫界面部分代碼；?2、將代碼運行并調(diào)試；3、編寫課程設(shè)計報告和心得體會；1、畫算法的程序流程圖；2、編寫課程設(shè)計報告和心得體會；211.目的及意義本課程設(shè)計主要任務(wù)就是在多用戶操作系統(tǒng)支持下建立多用戶多級文件系統(tǒng)的設(shè)計。具體說來，主要是為了達到下述實驗?zāi)康模海?）了解并掌握文件系統(tǒng)中用于管理所必須的數(shù)據(jù)結(jié)構(gòu)。（2）了解并掌握主要的文件操作命令的實現(xiàn)方法。（3）通過課程實踐掌握課程設(shè)計的方法和流程，并總結(jié)設(shè)計經(jīng)驗，提出更好的改進方法。212.課程設(shè)計任務(wù)及要求2.1設(shè)計任務(wù)在多道程序和多任務(wù)系統(tǒng)中，系統(tǒng)內(nèi)同時處于就緒狀

3、態(tài)的進程可能有若干個，且進程之間也存在著同步與互斥的關(guān)系，要求采用指定的調(diào)度策略，使系統(tǒng)中的進程有條不紊地工作，通過觀察諸進程的運行過程，以鞏固和加深處理機調(diào)度的概念2.2設(shè)計要求每一個進程有一個PCB，其內(nèi)容可以根據(jù)具體情況設(shè)定?？梢栽诮缑嬖O(shè)定的互斥資源（包括兩種：輸入設(shè)備與輸出設(shè)備）的數(shù)目進程數(shù)、進入內(nèi)存時間、要求服務(wù)時間可以在界面上進行設(shè)定進程之間存在一定的同步與互斥關(guān)系，可以通過界面進行設(shè)定，其表示方法如下：進程的服務(wù)時間由三段組成：I2C10O5（表示進程的服務(wù)時間由2個時間片的輸入，10個時間片的計算，5個時間片的輸出）進程間的同步關(guān)系用一個段表示：W2，表示該進程先

4、要等待P2進程執(zhí)行結(jié)束后才可以運行因此，進程間的同步與互斥關(guān)系、服務(wù)時間可以統(tǒng)一用四段表示為：I2C10O5W2可以在運行中顯示各進程的狀態(tài)：就緒、阻塞、執(zhí)行采用可視化界面，可在進程調(diào)度過程中隨時暫停調(diào)度，查看當(dāng)前進程的狀態(tài)以及相應(yīng)的阻塞隊列具有一定的數(shù)據(jù)容錯性213.算法及數(shù)據(jù)結(jié)構(gòu)3.1算法總體設(shè)計思想動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是可以隨進程的推進或隨其等待時間的增加而改變，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進程都有相同的優(yōu)先權(quán)初始值則顯然是最先進入就緒隊列的進程將因其動態(tài)優(yōu)先權(quán)變得最

5、高而優(yōu)先獲得處理機，此即FCFS算法。若所有的就緒隊列進程具有各不相同的優(yōu)先權(quán)初始值，那么，對于優(yōu)先權(quán)初始值低的進程，在等待足夠的時間后，其優(yōu)先權(quán)便可能升為最高從而獲得處理機。而采用搶占式調(diào)度算法時，如果再規(guī)定當(dāng)前進程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機。3.2動態(tài)優(yōu)先級算法3.2.1功能最高響應(yīng)比優(yōu)先法（HRRN）是對FCFS方式和SJF?方式的一種綜合平衡。HRRN調(diào)度策略同時考慮每個作業(yè)的等待時間長短和估計需要的執(zhí)行時間長短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。??響應(yīng)比R定義如下：?R=(W+T)/T=1+W/T??其中T為該作業(yè)估計需要的執(zhí)行時間，W為

6、作業(yè)在后備狀態(tài)隊列中的等待時間。??每當(dāng)要進行作業(yè)調(diào)度時，系統(tǒng)計算每個作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。這樣，即使是長作業(yè)，隨著它等待時間的增加，W/T也就隨著增加，也就有機會獲得調(diào)度執(zhí)行。這種算法是介于FCFS和SJF?之間的一種折中算法。由于長作業(yè)也有機會投入運行，在同一時間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF?法，從而采用HRRN?方式時其吞吐量將小于采用SJF?法時的吞吐量。另外，由于每次調(diào)度前要計算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。3.2.2數(shù)據(jù)結(jié)構(gòu)floatarrtime[];//作業(yè)到達時間floatinputtime[];////輸入時間floatcputime[];

7、//CPU運行時間floatoutputtime[];//輸出時間floatwaittime[];//等待時間21floatinstatime[];//開始運行時間floatcpustatime[];//CPU開始時間floatoutstatime[];//輸出開始時間floatfintime[];//結(jié)束運行時間floatprio[];//優(yōu)先權(quán)Stringstate[];//是否已經(jīng)完成intarrival[];//是否到達intinputdone[];//是否輸入完成int