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

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

1、《計算機(jī)操作系統(tǒng)》課程設(shè)計題目：13采用高響應(yīng)比算法的進(jìn)程調(diào)度程序班級：小組成員：指導(dǎo)教師：時間：2013.6.24—2013.7.30地點：7b3122013年6月21目錄工作進(jìn)度表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參考文獻(xiàn)2121工作進(jìn)度表時間完成工作完成人周一完成課程設(shè)計的需求分析周二編寫代碼測試代碼周三編寫代碼測試代碼周四編寫代碼測試代碼周五完善

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

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

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

5、高而優(yōu)先獲得處理機(jī)，此即FCFS算法。若所有的就緒隊列進(jìn)程具有各不相同的優(yōu)先權(quán)初始值，那么，對于優(yōu)先權(quán)初始值低的進(jìn)程，在等待足夠的時間后，其優(yōu)先權(quán)便可能升為最高從而獲得處理機(jī)。而采用搶占式調(diào)度算法時，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機(jī)。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)要進(jìn)行作業(yè)調(diào)度時，系統(tǒng)計算每個作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。這樣，即使是長作業(yè)，隨著它等待時間的增加，W/T也就隨著增加，也就有機(jī)會獲得調(diào)度執(zhí)行。這種算法是介于FCFS和SJF?之間的一種折中算法。由于長作業(yè)也有機(jī)會投入運(yùn)行，在同一時間內(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è)到達(dá)時間floatinputtime[];////輸入時間floatcputime[];

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