OS短作業(yè)優(yōu)先調(diào)度算法C語言

1、 采用短作業(yè)優(yōu)先調(diào)度算法調(diào)度程序?qū)W 號： 姓 名： 專 業(yè)： 指導老師： 日 期： 目錄一、實驗題目3二、課程設計的目的3三、設計內(nèi)容3四、設計要求3五、主要數(shù)據(jù)結(jié)構(gòu)及其說明4六、程序運行結(jié)果5七、流程圖7八、源程序文件9九、實驗體會13十、參考文獻13摘要 在多道程序環(huán)境下，主存中有著多個進程，其數(shù)目往往多于處理機數(shù)目。這就要求系統(tǒng)能按某種算法，動態(tài)地把處理機分配給就緒隊列中的一個進程，使之執(zhí)行。分配處理機的任務是由處理機調(diào)度程序完成的。由于處理機是最重要的計算機資源，提高處理機的利用率及改善系統(tǒng)性能（吞吐量、響應時間），在很大程度上取決于處理機調(diào)度性能的好壞，因而，處理機調(diào)度便成為操作系統(tǒng)

2、設計的中心問題之一。 在多道程序系統(tǒng)中，一個作業(yè)被提交后必須經(jīng)過處理機調(diào)度后，方能獲得處理機執(zhí)行。對于批量型作業(yè)而言，通常需要經(jīng)歷作業(yè)調(diào)度和進程調(diào)度兩個過程后方能獲得處理機。作業(yè)調(diào)度是對成批進入系統(tǒng)的用戶作業(yè)，根據(jù)作業(yè)控制塊的信息，按一定的策略選取若干個作業(yè)使它們可以去獲得處理器運行的一項工作。而對每個用戶來說總希望自己的作業(yè)的周轉(zhuǎn)時間是最小的，短作業(yè)優(yōu)先（SJF）便是其中一種調(diào)度方法。 本次課程設計主要是模擬短作業(yè)優(yōu)先(SJF)調(diào)度算法。一、實驗題目 采用短作業(yè)優(yōu)先算法的的進程調(diào)度程序二、課程設計的目的l 操作系統(tǒng)課程設計是計算機專業(yè)重要的教學環(huán)節(jié)，它為學生提供了一個既動手又動腦，將課本上的

3、理論知識和實際有機的結(jié)合一起，獨立分析和解決實際問題的機會。l 進一步鞏固和復習操作系統(tǒng)的基礎(chǔ)知識。l 培養(yǎng)學生結(jié)構(gòu)化程序、模塊化程序設計的方法和能力。l 提高學生調(diào)試程序的技巧和軟件設計的能力。l 提高學生分析問題、解決問題以及綜合利用C語言進行程序設計的能力。三、設計內(nèi)容設計并實現(xiàn)一個采用短作業(yè)優(yōu)先算的進程調(diào)度算法演示程序四、設計要求1. 每一個進程有一個PCB，其內(nèi)容可以根據(jù)具體情況設定。 2. 進程數(shù)、進入內(nèi)存時間、要求服務時間、優(yōu)先級等均可以在界面上設定 3. 可讀取樣例數(shù)據(jù)（要求存放在外部文件中）進行進程數(shù)、進入內(nèi)存時間、時間片長度、進程優(yōu)先級的初始化 4. 可以在運行中顯示各進程

4、的狀態(tài)：就緒、執(zhí)行 （由于不要求設置互斥資源與進程間同步關(guān)系，故只有兩種狀態(tài)） 5. 采用可視化界面，可在進程調(diào)度過程中隨時暫停調(diào)度，查看當前進程的狀態(tài)以及相應的阻塞隊列 五、主要數(shù)據(jù)結(jié)構(gòu)及其說明算法的基本概念和原理：本次課程設計主要是采用短作業(yè)優(yōu)先算法進程的進程調(diào)度過程。短作業(yè)優(yōu)先調(diào)度算法，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。他們可以分別用于作業(yè)調(diào)度和進程調(diào)度，短作業(yè)優(yōu)先的調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將他們調(diào)入內(nèi)存運行。而短進程優(yōu)先調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給他，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄

5、處理機時再度重新調(diào)度。本程序采用了非搶占式短作業(yè)優(yōu)先調(diào)度。而非搶占式這種方式，一旦把處理機分配給某進程后，便讓該進程一直執(zhí)行，直至該進程完成或發(fā)生某事件而被阻塞時，才再把處理機分配給其它進程，決不允許某進程搶占已經(jīng)分配出去的處理機。這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務的要求立即執(zhí)行，因而可能造成難以預料的后果。因此，在要求比較嚴格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。本課程設計主要是在滿足要求多道單處理機的情況下進行短作業(yè)的優(yōu)先調(diào)度。算法的簡要說明：短作業(yè)（進程）優(yōu)先調(diào)度算法SJ（P）F，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別用于

6、作業(yè)調(diào)度和進程調(diào)度。短作業(yè)優(yōu)先（SJF）的調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程（SPF）調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機再重新調(diào)度。優(yōu)點是SJ(P)F調(diào)度算法能有效地降低作業(yè)（進程）的平均等待時間，提高系統(tǒng)吞吐量。缺點是該算法對長作業(yè)不利；完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進程）長期不被調(diào)度；由于作業(yè)（進程）的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真

7、正做到短作業(yè)游戲那調(diào)度。 該程序定義了一個進程數(shù)據(jù)塊(struct Process_)，該數(shù)據(jù)塊有進程名(name)、到達時間(arrivetime)、服務時間(servicetime)、開始執(zhí)行時間(starttime)、完成時間(finishtime)、周轉(zhuǎn)時間(zztime)、帶權(quán)周轉(zhuǎn)時間(dqzztime)、執(zhí)行順序（order）。用到的公式有：完成時間=到達時間+服務時間；周轉(zhuǎn)時間=完成時間+到達時間；帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務時間；(第一次執(zhí)行的進程的完成時間=該進程的到達時間；下一個進程的開始執(zhí)行時間=上一個進程的完成時間)。運行進程的順序需要對進程的到達時間和服務時間進行比較

8、。如果某一進程是從0時刻到達的，那么首先執(zhí)行該進程；之后就比較進程的服務時間，誰的服務時間短就先執(zhí)行誰（如果服務時間相同則看它們的到達時間，到達時間短的先執(zhí)行）；如果到達時間和服務時間相同，則按先來先服務算法執(zhí)行。六、程序運行結(jié)果1 進入操作界面如下2輸入進程的信息3 各時刻進程的狀態(tài)4 進程信息5 平均帶權(quán)周轉(zhuǎn)時間界面七、流程圖本次課程設計主要是通過比較各個進程的優(yōu)先級以及各進程所需要占用的CPU時間來確定哪個作業(yè)優(yōu)先運行，短作業(yè)優(yōu)先調(diào)度算法除了能保證優(yōu)先級更高的作業(yè)優(yōu)先運行外，還能使相同優(yōu)先級的前提下，所需CPU時間最短的那個作業(yè)優(yōu)先運行，次外，本次課程設計還增加了阻塞時間和被阻塞時間來對

9、個進程的運行加以控制。 此次課程設計的總體流程圖如下：開 始輸入進程的個數(shù):numr隊列中是否只有一個進程？執(zhí)行時間處理函數(shù)：Time()Y 結(jié) 束Sort()輸入進程的信息:name starttime servicetimeN執(zhí)行判斷函數(shù)：Run()輸出最后信息：Output()八、源程序文件#include#define MaxNum 100using namespace std; struct Process_structint Number; /進程編號char NameMaxNum; /進程名稱 int ArrivalTime; /到達時間int ServiceTime; /開始運

10、行時間int FinishTime; /運行結(jié)束時間int WholeTime; /運行時間 int run_flag; /調(diào)度標志int order; /運行次序double WeightWholeTime; /周轉(zhuǎn)時間double AverageWT_FCFS,AverageWT_SJF; /平均周轉(zhuǎn)時間 double AverageWWT_FCFS,AverageWWT_SJF; /平均帶權(quán)周轉(zhuǎn)時間ProcessMaxNum;int N; /實際進程個數(shù)int SJF(); /短作業(yè)優(yōu)先int SJF() /短作業(yè)優(yōu)先算法int temp_time=0; /當期那時間int i=0,j;

11、int number_schedul,temp_counter; /進程編號，當前已執(zhí)行進程個數(shù)float run_time;run_time=Processi.WholeTime;j=1;while(jN)&(Processi.ArrivalTime=Processj.ArrivalTime) /判斷是否有兩個進程同時到達if(Processj.WholeTimeProcessi.WholeTime)run_time=Processi.WholeTime;i=j;j+;/查找下一個被調(diào)度的進程/對找到的下一個被調(diào)度的進程求相應的參數(shù)number_schedul=i;Processnumber

12、_schedul.ServiceTime=Processnumber_schedul.ArrivalTime;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Processnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1;temp_time=Processnumber_schedul.FinishTime; Processnumber_schedul.order=1;temp_counter=1;while(temp_counterN)for(

13、j=0;jN;j+)if(Processj.ArrivalTime=temp_time)&(!Processj.run_flag)run_time=Processj.WholeTime;number_schedul=j;break;for(j=0;jN;j+)if(Processj.ArrivalTime=temp_time)&(!Processj.run_flag)if(Processj.WholeTimerun_time)run_time=Processj.WholeTime;number_schedul=j;/查找下一個被調(diào)度的進程/對找到的下一個被調(diào)度的進程求相應的參數(shù)Processn

14、umber_schedul.ServiceTime=temp_time;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Processnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1;temp_time=Processnumber_schedul.FinishTime;temp_counter+;Processnumber_schedul.order=temp_counter;return 0;int Pinput(); /進程參數(shù)輸入int

15、Poutput(); /調(diào)度結(jié)果輸出void main()int option;printf( *主菜單*n);printf( * 1 使用短作業(yè)優(yōu)先 *n);printf( * 0 退出 *n);printf( *n);/system(cls);system(color 1f);scanf(%d,&option);switch(option)case 0:printf(運行結(jié)束。n);break;case 1:printf(對進程用短作業(yè)優(yōu)先調(diào)度。nn); Pinput();SJF();Poutput();break;int Pinput() /進程參數(shù)輸入int i;printf(請輸入進

16、程個數(shù):n);scanf(%d,&N);for(i=0;iN;i+)printf(*n);printf(請輸入一個進程:n,i+1);printf(請輸入進程名稱:n);scanf(%s,Processi.Name); printf(請輸入到達時間:n);scanf(%d,&Processi.ArrivalTime);printf(請輸入服務時間:n);scanf(%d,&Processi.WholeTime);Processi.ServiceTime=0;Processi.FinishTime=0;Processi.WeightWholeTime=0;Processi.order=0;Pro

17、cessi.run_flag=0;system(cls);return 0;int Poutput() /調(diào)度結(jié)果輸出int i;float turn_round_time=0,f1,w=0;printf( 進程名稱 到達T 運行T 開始運行T 結(jié)束T 執(zhí)行順序 周轉(zhuǎn)T 帶權(quán)周轉(zhuǎn)Tn);for(i=0;iN;i+)Processi.WeightWholeTime=Processi.FinishTime-Processi.ArrivalTime;f1=Processi.WeightWholeTime/Processi.WholeTime;turn_round_time+=Processi.Wei

18、ghtWholeTime;w+=f1;printf(時刻%d :,Processi.ServiceTime,Processi.Name);printf( %s %d %d %d %d %d %f %fn,Processi.Name,Processi.ArrivalTime,Processi.WholeTime,Processi.ServiceTime,Processi.FinishTime,Processi.order,Processi.WeightWholeTime,f1);printf(average_turn_round_timer=%fn,turn_round_time/N);printf(weight_average_turn_round_timer=%fn,w/N);return 0;九、實驗體會通過本次課程設計，使我對計算機操作系統(tǒng)短作業(yè)優(yōu)先調(diào)度算法這一節(jié)的知識有了更深的了解 。短作業(yè)優(yōu)先調(diào)度算法易于實現(xiàn)，并且效率很高，但是短作業(yè)只考慮到短作業(yè)的利益，而不顧長作業(yè)，這樣就可能會使得長作業(yè)一直處于等待狀態(tài)而不能運行。所以，短作業(yè)優(yōu)先算法適用于系統(tǒng)中短作業(yè)較多的情況。此外，通過本次實驗，進一步鞏固和復