中北大學
中北大學軟體學院
實訓說明書
實訓名稱作業系統課程設計
題目名稱：基於linux的模擬程序排程演算法的實現
專業班級12210a03班
小組成員
學號： 1221010821 姓名：__嚴晗成績：
學號： 1221010916 姓名： 許鈺成績：
學號： 1221011024 姓名： 張悅成績：
指導教師
2015 年 1 月
1 需求分析
在作業系統中，程序排程實際就是給程序分配記憶體資源，隨著計算機系統的發展，為了更充分的利用系統資源以及提高計算機的執行效率，因此需要在不同的環境下採用不同的排程演算法，使得系統具有合理的響應時間，就要求系統能按照某種演算法，動態的把處理機分配給就緒佇列中的乙個程序，使之執行。因此，就需要設計出幾種不同的演算法，通過比較，選出一種最優的。
本程式主要實現基於linux的程序排程演算法的實現。共實現了三種不同的排程演算法，分別是：先來先服務排程演算法，短作業優先排程，高響應比排程演算法。
在程式的執行過程中，可以自主輸入程序的個數以及程序必要的資訊，如：程序的建立時間，服務時間等，然後通過不同的排程演算法實現程序的排程，每一種演算法都能動態的演示程序排程的過程，時間間隔為一秒鐘，並且可以計算出每種排程演算法下的平均周轉時間和平均帶權周轉時間，通過排序比較各種排程演算法的優劣。
2 總體設計
本程式主要分為四大模組：
1. 建立程序：可以手動建立程序，使用者可以自主決定程序的個數，並且在建立程序時自主決定程序名，程序的建立時間以及執行時間。
2. 幾種不同的排程演算法：分別是先來先服務排程演算法，短作業優先排程和高響應比排程演算法。
3. 顯示結果函式：在各個排程演算法中，每一步執行完後都會以**的形式顯示出程序的資訊，包括：程序名，建立時間，服務時間，開始執行時間，完成時間，周轉時間，帶權周轉時間。
4. 比較各演算法的優劣：對平均周轉時間和平均帶權周轉時間按照由小到大的順序進行排序比較。
程式中採用結構體來儲存程序資訊，其中包括：程序名，程序的建立時間，服務時間，執行時間，完成時間，周轉時間，帶權周轉時間，等待時間，優先權，時候完成等，各個程序共同組成乙個結構體陣列。
結構圖如下：
資料結構如下：
struct pro//程序排程資訊結構體
;3．詳細設計
先來先服務fcfs是最簡單的排程演算法，按先後順序進行排程。按照作業提交或程序變為就緒狀態的先後次序，分派cpu。當前作業或程序占用cpu，直到執行完或阻塞，才出讓cpu（非搶占方式）。
在作業或程序喚醒後（如i/o完成），並不立即恢復執行通常等到當前作業或程序出讓cpu。
根據先來先服務的演算法，作業a開始時間為0，需要4個單位時間才能完成，作業a開始執行之後，隨後到的作業，誰先來誰排在前面，當a執行完畢之後即執行其次到達的作業，即b到達的時間是1，b執行時c才到達，所以c在b之後執行……依次執行下去，直到全部完成為止，這個演算法和作業執行所需時間的長短沒有關係，只和作業到達的先後順序有關係，先到達的作業先被執行，這就是先來先服務演算法的核心思想。
短作業優先sjf又稱為「短程序優先」；這是對fcfs演算法的改進，其目標是減少平均周轉時間。對預計執行時間短的作業（程序）優先分派處理機。通常後來的短作業不搶先正在執行的作業。
短作業優先排程演算法，是指對短作業或短程序優先排程的演算法。他們可以分別用於作業排程和程序排程，短作業優先的排程演算法是從後備佇列中選擇乙個或若干個估計執行時間最短的作業，將他們調入記憶體執行。而短程序優先排程演算法則是從就緒佇列中選出乙個估計執行時間最短的程序，將處理機分配給他，使它立即執行並一直執行到完成，或發生某事件而被阻塞放棄處理機時再度重新排程。
最高響應比優先法（hrrn）是對fcfs方式和sjf 方式的一種綜合平衡。hrrn排程策略同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選出響應比最高的作業投入執行。
響應比r定義如下： r=(w+t)/t=1+w/t 其中t為該作業估計需要的執行時間，w為作業在後備狀態佇列中的等待時間。 每當要進行作業排程時，系統計算每個作業的響應比，選擇其中r最大者投入執行。
這樣，即使是長作業，隨著它等待時間的增加，w/t也就隨著增加，也就有機會獲得排程執行。這種演算法是介於fcfs和sjf 之間的一種折中演算法。由於長作業也有機會投入執行，在同一時間內處理的作業數顯然要少於sjf 法，從而採用hrrn 方式時其吞吐量將小於採用sjf 法時的吞吐量。
另外，由於每次排程前要計算響應比，系統開銷也要相應增加。
核心**：
#include<>
#include<>
struct pro//程序排程資訊結構體
;float pjzhou_time,pjd_time; //平均周轉時間和平均帶權時間
float s,t; //分別儲存周轉時間和帶權時間的和
float fs,ft,ss,st,hs,ht; //分別儲存各演算法中的平均周轉時間和平均帶權時間
void display(struct pro a,int n) ;//顯示函式
void count(struct pro a,int n);//計算函式
void fcfs(struct pro a,int n)//fcfs演算法
a[min].excute_time=a[temp].finish_time;
a[min].finish_time=a[min].excute_time+a[min].serve_time;
a[min].zhou_time=a[min].finish_time-a[min].creat_time;//周轉時間=完成時間-建立時間
a[min].d_time=a[min].zhou_time/a[min].serve_time;//帶權周轉時間=周轉時間/服務時間;
temp=min;
printf("\n\n");
printf("fcfs:\n");
display(a,n);
sleep(1);
}count(a,n);
fs=pjzhou_time;
ft=pjd_time;
printf("\n");
printf("平均周轉時間 t=%5.3f\n平均帶權周轉時間 w=%5.3f\n",pjzhou_time,pjd_time);
printf("\n");
printf("\n");
}void sjf(struct pro a,int n) //sjf演算法
{ int i,j;
int min=1;
int max=1;
int temp=0;
a[0].excute_time=a[0].creat_time;
a[0].finish_time=a[0].excute_time+a[0].serve_time;
a[0].zhou_time=a[0].finish_time-a[0].creat_time;
a[0].d_time=a[0].zhou_time/a[0].serve_time;
作業系統程序排程實驗報告
實驗一程序排程實驗 專業 xx 學號 xx 姓名 實驗日期 20xx年xx月xx日 一 實驗目的 通過對程序排程演算法的模擬加深對程序概念和程序排程演算法的理解。二 實驗要求 編寫程式實現對5個程序的排程模擬，要求至少採用兩種不同的排程演算法分別進行模擬排程。三 實驗方法內容 1.演算法設計思路 將...
作業系統程序排程實驗報告
哈爾濱工業大學電腦科學與技術學院 實驗報告 課程名稱 作業系統 課程型別 必修 實驗專案名稱 程序排程 實驗題目 先來先服務和優先順序排程的實現 班級 學號 姓名 一 實驗目的 二 實驗要求及實驗環境 由於在多道程式或多個任務系統中，系統同時處於就緒狀態的程序有若干個，即能執行的程序數遠大於處理機個...
作業系統實驗報告 程序排程 作業排程等
作業系統實驗報告 1 程序排程 2 作業排程 3 主存空間的分配和 4 檔案系統 學生學院 計算機學院 專業班級 網路工程 3 班 學號 3107007062 學生姓名 張菲 指導教師 胡欣如 2009 年 12 月 20 日 計算機學院網路工程專業 3 班 組 學號 3107007062 姓名張菲...