操作系統(tǒng)原理短作業(yè)優(yōu)先算法報告附源代碼

1、中國地質(zhì)大學(xué)（北京）操作系統(tǒng)原理實習報告實習題目： 1、 2、 實習人員： 學(xué)號 姓名（組長） 學(xué)號 姓名 一、題目分析在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運行得不到保證。于是我們想到了一種辦法解決這個問題，就是引用動態(tài)優(yōu)先權(quán)、并使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a提高，長作業(yè)在等待一定的時間后，必然有機會分配到處理機，這樣長作業(yè)也得到了運行。設(shè)計并實現(xiàn)一個采用高響應(yīng)比算法的進程調(diào)度演示程序，響應(yīng)比 R 定義如下：RWT/T1W/T 其中 T 為該作業(yè)估計需要的執(zhí)行時間， 為作業(yè)在后備狀態(tài)隊列中的等待時 W間。 每當要進行作業(yè)調(diào)度時，系統(tǒng)計算每個作

2、業(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)增加。二、數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)體數(shù)組pathk 實現(xiàn)對進程響應(yīng)比的計算 Pathmax 實現(xiàn)對進程響應(yīng)比的排序 Pathii 實現(xiàn)程序的各階段運行狀況的輸出三、算法流程圖程序設(shè)計流程圖開始讀取進程判斷進程是否進入內(nèi)存對響應(yīng)比排序

3、高的進程先運行等待結(jié)束是是高響應(yīng)比函數(shù)執(zhí)行過程流程圖開 始 當前作業(yè)為依編號找到的第一個還未執(zhí)行的作業(yè) 當前作業(yè)是最后一個作業(yè) 當前作業(yè)和下一個還沒執(zhí)行的作業(yè)比較 當前作業(yè)在上次作業(yè)被執(zhí)行完之前到達 同時到達 當前作業(yè)取較早達到且響應(yīng)比較高的一個 當前作業(yè)取較早到達的一個 當前作業(yè)取相應(yīng)比較高的一個 返回這一次要執(zhí)行的作業(yè)四、重難點分析計算每一個進程的動態(tài)優(yōu)先權(quán)，需要在每執(zhí)行一個進程之后計算一遍未執(zhí)行進程的優(yōu)先權(quán)，從中選出優(yōu)先權(quán)最高的一個執(zhí)行。五、運行測試（截圖）六、分工編碼 ：實驗報告： 七、總結(jié)本次演算實驗主要對最高響應(yīng)比算法的理解和對進程調(diào)度的功能以及進程調(diào)度算法有了深入的理解。在這次的

4、課程設(shè)計中，計算每一個進程的動態(tài)優(yōu)先權(quán)，需要在每執(zhí)行一個進程之后計算一遍未執(zhí)行進程的優(yōu)先權(quán)，從中選出優(yōu)先權(quán)最高的一個執(zhí)行，因為疏忽導(dǎo)致了響應(yīng)比的計算錯誤，從而加大了完成代碼的時間量。對于這次出現(xiàn)的這個問題，使我有了對程序設(shè)計的嚴謹性，課本基礎(chǔ)知識的理解程度上有了更深刻的認識，也讓我明白到了基礎(chǔ)知識的重要性。完成此次課程實際之后，我對進程調(diào)度模擬設(shè)計的各種算法有了更進一步的理解，在編寫程序中所遇到的問題讓我有了對操作系統(tǒng)有了迫切要更深層次的掌握，并且感受到操作系統(tǒng)這門課程實在是很重要的一門課程。通過本次實驗對用高響應(yīng)比算法的優(yōu)先調(diào)度算法有了更深入的理解和掌握，進一步鞏固和復(fù)習操作系統(tǒng)的基礎(chǔ)知識，

5、更進一步的了解了結(jié)構(gòu)化模塊化程序設(shè)計的方法，提高了調(diào)試程序的技巧。八、附件：源代碼#include <iostream>#include <cstring>#include <algorithm>#define MAXN 1500using namespace std;struct node bool vis;/是否已執(zhí)行 char name;/進程名稱 int come;/到達時間 int ser;/服務(wù)時間 int st;/開始時間 int end;/結(jié)束時間 int zhouzhuan;/周轉(zhuǎn)時間 double right, youxianji;/帶全

6、周轉(zhuǎn)時間，動態(tài)優(yōu)先權(quán), pathMAXN;int main() int n; int ansMAXN; cout << "請輸入進程的數(shù)目: " cin >> n; cout << "請依次輸入每個進程的名字、到達時間、服務(wù)時間: " << endl; for(int i = 0; i < n; +i) cin >> >> e >> pathi.ser; pathi.vis = false; double sum = 0; i

7、nt inde = 0; int now = 0; for(int i = 0; i < n; +i) int j; for(j = 0; j < n; +j) if(e > now && pathj.vis = false) break; double MAX = -9999; int max; for(int k = 0; k < j; +k) if(pathk.vis = false) pathk.youxianji = (now - e + pathk.ser)/(1.0 * pathk.ser); if(MA

8、X < pathk.youxianji) MAX = pathk.youxianji; max = k; pathmax.st = now; now += pathmax.ser; pathmax.end = now; pathmax.zhouzhuan = (pathmax.end - e); pathmax.right = (pathmax.zhouzhuan*1.0/ pathmax.ser); ansinde+ = max; pathmax.vis = true; cout << "進程 開始時間 結(jié)束時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間" << endl; for(int i = 0; i < n; +i) sum += pathi.right; cout << << " " << pathi.st << " " << pathi.end << " " <<