操作系統(tǒng)短作業(yè)優(yōu)先調(diào)度算法

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

2、度便成為操作系統(tǒng)設(shè)計的中心問題之一。 在多道程序系統(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)度方法。 本次課程設(shè)計主要是模擬短作業(yè)優(yōu)先(SJF)調(diào)度算法。一、實驗題目 采用短作業(yè)優(yōu)先算法的的進程調(diào)度程序二、課程設(shè)計的目的l 操作系統(tǒng)課程設(shè)計是計算機專業(yè)重要的教學環(huán)節(jié)，它為學生提供了一個既動手又

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

4、運行中顯示各進程的狀態(tài)：就緒、執(zhí)行 （由于不要求設(shè)置互斥資源與進程間同步關(guān)系，故只有兩種狀態(tài)） 5. 采用可視化界面，可在進程調(diào)度過程中隨時暫停調(diào)度，查看當前進程的狀態(tài)以及相應(yīng)的阻塞隊列 五、主要數(shù)據(jù)結(jié)構(gòu)及其說明算法的基本概念和原理：本次課程設(shè)計主要是采用短作業(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)境。但它難以滿足緊急任務(wù)的要求立即執(zhí)行，因而可能造成難以預料的后果。因此，在要求比較嚴格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。本課程設(shè)計主要是在滿足要求多道單處理機的情況下進行短作業(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)、服務(wù)時間(servicetime)、開始執(zhí)行時間(starttime)、完成時間(finishtime)、周轉(zhuǎn)時間(zztime)、帶權(quán)周轉(zhuǎn)時間(dqzztime)、執(zhí)行順序（order）。用到的公式有：完成時間=到達時間+服務(wù)時間；周轉(zhuǎn)時間=完成時間+到達時間；帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間；(第一次執(zhí)行的進程的完成時間=該進程的到達時間；下一個進程的開始執(zhí)行時間=上一個進程的完成時間)。運行進程的順序需要對進程的到達時間和

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

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

10、達時間int ServiceTime; /開始運行時間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_

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

12、調(diào)度的進程求相應(yīng)的參數(shù)number_schedul=i;Processnumber_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=

13、1;temp_counter=1;while(temp_counter<N)for(j=0;j<N;j+)if(Processj.ArrivalTime<=temp_time)&&(!Processj.run_flag)run_time=Processj.WholeTime;number_schedul=j;break;for(j=0;j<N;j+)if(Processj.ArrivalTime<=temp_time)&&(!Processj.run_flag)if(Processj.WholeTime<run_time)ru

14、n_time=Processj.WholeTime;number_schedul=j;/查找下一個被調(diào)度的進程/對找到的下一個被調(diào)度的進程求相應(yīng)的參數(shù)Processnumber_schedul.ServiceTime=temp_time;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Processnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1;temp_time=Processnumber_schedul.FinishTime;temp_c

15、ounter+;Processnumber_schedul.order=temp_counter;return 0;int Pinput(); /進程參數(shù)輸入int 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");scan

16、f("%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("請輸入進程個數(shù):n");scanf("%d",&N);for(i=0;i<N;i+)printf("*n");printf("請輸入

17、一個進程:n",i+1);printf("請輸入進程名稱:n");scanf("%s",Processi.Name); printf("請輸入到達時間:n");scanf("%d",&Processi.ArrivalTime);printf("請輸入服務(wù)時間:n");scanf("%d",&Processi.WholeTime);Processi.ServiceTime=0;Processi.FinishTime=0;Processi.WeightW

18、holeTime=0;Processi.order=0;Processi.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;i<N;i+)Processi.WeightWholeTime=Processi.FinishTime-Processi.ArrivalTime;f1=Processi.Weigh

19、tWholeTime/Processi.WholeTime;turn_round_time+=Processi.WeightWholeTime;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;九、實驗體會通過本次課程設(shè)計，使我對計算機操作系統(tǒng)短作業(yè)優(yōu)先調(diào)度算法這一節(jié)的知識有了更深的了解 。短作業(yè)優(yōu)先調(diào)度算法易于實現(xiàn)，并且效率很高，但是短作業(yè)只考慮到短作業(yè)的利益，而不顧長作業(yè)，這樣就可能會使得長作業(yè)一直處于等待狀態(tài)而不能運行。所以，