1、精選優質文檔-傾情為你奉上 采用短作業優先調度算法調度程序學 號： 姓 名： 專 業： 指導老師： 日 期： 專心-專注-專業目錄摘要 在多道程序環境下，主存中有著多個進程，其數目往往多于處理機數目。這就要求系統能按某種算法，動態地把處理機分配給就緒隊列中的一個進程，使之執行。分配處理機的任務是由處理機調度程序完成的。由于處理機是最重要的計算機資源，提高處理機的利用率及改善系統性能（吞吐量、響應時間），在很大程度上取決于處理機調度性能的好壞，因而，處理機調度便成為操作系統設計的中心問題之一。 在多道程序系統中，一個作業被提交后必須經過處理機調度后，方能獲得處理機執行。對于批量型作業而言，通常需

2、要經歷作業調度和進程調度兩個過程后方能獲得處理機。作業調度是對成批進入系統的用戶作業，根據作業控制塊的信息，按一定的策略選取若干個作業使它們可以去獲得處理器運行的一項工作。而對每個用戶來說總希望自己的作業的周轉時間是最小的，短作業優先（SJF）便是其中一種調度方法。 本次課程設計主要是模擬短作業優先(SJF)調度算法。一、實驗題目 采用短作業優先算法的的進程調度程序二、課程設計的目的l 操作系統課程設計是計算機專業重要的教學環節，它為學生提供了一個既動手又動腦，將課本上的理論知識和實際有機的結合一起，獨立分析和解決實際問題的機會。l 進一步鞏固和復習操作系統的基礎知識。l 培養學生結構化程序、

3、模塊化程序設計的方法和能力。l 提高學生調試程序的技巧和軟件設計的能力。l 提高學生分析問題、解決問題以及綜合利用C語言進行程序設計的能力。三、設計內容設計并實現一個采用短作業優先算的進程調度算法演示程序四、設計要求1. 每一個進程有一個PCB，其內容可以根據具體情況設定。 2. 進程數、進入內存時間、要求服務時間、優先級等均可以在界面上設定 3. 可讀取樣例數據（要求存放在外部文件中）進行進程數、進入內存時間、時間片長度、進程優先級的初始化 4. 可以在運行中顯示各進程的狀態：就緒、執行 （由于不要求設置互斥資源與進程間同步關系，故只有兩種狀態） 5. 采用可視化界面，可在進程調度過程中隨時

4、暫停調度，查看當前進程的狀態以及相應的阻塞隊列 五、主要數據結構及其說明算法的基本概念和原理：本次課程設計主要是采用短作業優先算法進程的進程調度過程。短作業優先調度算法，是指對短作業或短進程優先調度的算法。他們可以分別用于作業調度和進程調度，短作業優先的調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將他們調入內存運行。而短進程優先調度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給他，使它立即執行并一直執行到完成，或發生某事件而被阻塞放棄處理機時再度重新調度。本程序采用了非搶占式短作業優先調度。而非搶占式這種方式，一旦把處理機分配給某進程后，便讓該進程一直執行

5、，直至該進程完成或發生某事件而被阻塞時，才再把處理機分配給其它進程，決不允許某進程搶占已經分配出去的處理機。這種調度方式的優點是實現簡單，系統開銷小，適用于大多數的批處理系統環境。但它難以滿足緊急任務的要求立即執行，因而可能造成難以預料的后果。因此，在要求比較嚴格的實時系統中，不宜采用這種調度方式。本課程設計主要是在滿足要求多道單處理機的情況下進行短作業的優先調度。算法的簡要說明：短作業（進程）優先調度算法SJ（P）F，是指對短作業或短進程優先調度的算法。它們可以分別用于作業調度和進程調度。短作業優先（SJF）的調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。

6、而短進程（SPF）調度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行并一直執行到完成，或發生某事件而被阻塞放棄處理機再重新調度。優點是SJ(P)F調度算法能有效地降低作業（進程）的平均等待時間，提高系統吞吐量。缺點是該算法對長作業不利；完全未考慮作業的緊迫程度，因而不能保證緊迫性作業（進程）長期不被調度；由于作業（進程）的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業游戲那調度。 該程序定義了一個進程數據塊(struct Process_)，該數據塊有進程名(name)、到達時

7、間(arrivetime)、服務時間(servicetime)、開始執行時間(starttime)、完成時間(finishtime)、周轉時間(zztime)、帶權周轉時間(dqzztime)、執行順序（order）。用到的公式有：完成時間=到達時間+服務時間；周轉時間=完成時間+到達時間；帶權周轉時間=周轉時間/服務時間；(第一次執行的進程的完成時間=該進程的到達時間；下一個進程的開始執行時間=上一個進程的完成時間)。運行進程的順序需要對進程的到達時間和服務時間進行比較。如果某一進程是從0時刻到達的，那么首先執行該進程；之后就比較進程的服務時間，誰的服務時間短就先執行誰（如果服務時間相同則看

8、它們的到達時間，到達時間短的先執行）；如果到達時間和服務時間相同，則按先來先服務算法執行。六、程序運行結果1 進入操作界面如下2輸入進程的信息3 各時刻進程的狀態4 進程信息5 平均帶權周轉時間界面七、流程圖本次課程設計主要是通過比較各個進程的優先級以及各進程所需要占用的CPU時間來確定哪個作業優先運行，短作業優先調度算法除了能保證優先級更高的作業優先運行外，還能使相同優先級的前提下，所需CPU時間最短的那個作業優先運行，次外，本次課程設計還增加了阻塞時間和被阻塞時間來對個進程的運行加以控制。 此次課程設計的總體流程圖如下：開 始輸入進程的個數:numr隊列中是否只有一個進程？執行時間處理函數

9、：Time()Y 結 束Sort()輸入進程的信息:name starttime servicetimeN執行判斷函數：Run()輸出最后信息：Output()八、源程序文件#include<iostream>#define MaxNum 100using namespace std; struct Process_structint Number; /進程編號char NameMaxNum; /進程名稱 int ArrivalTime; /到達時間int ServiceTime; /開始運行時間int FinishTime; /運行結束時間int WholeTime; /運行時間

10、 int run_flag; /調度標志int order; /運行次序double WeightWholeTime; /周轉時間double AverageWT_FCFS,AverageWT_SJF; /平均周轉時間 double AverageWWT_FCFS,AverageWWT_SJF; /平均帶權周轉時間ProcessMaxNum;int N; /實際進程個數int SJF(); /短作業優先int SJF() /短作業優先算法int temp_time=0; /當期那時間int i=0,j;int number_schedul,temp_counter; /進程編號，當前已執行進程

11、個數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+;/查找下一個被調度的進程/對找到的下一個被調度的進程求相應的參數number_schedul=i;Processnumber_schedul.ServiceTime=Processn

12、umber_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_counter<N)for(j=0;j<N;j+)if(Processj

13、.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)run_time=Processj.WholeTime;number_schedul=j;/查找下一個被調度的進程/對找到的下一個被調度的進程求

14、相應的參數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_counter+;Processnumber_schedul.order=temp_counter;return 0;int Pinput()

15、; /進程參數輸入int Poutput(); /調度結果輸出void main()int option;printf(" *主菜單*n");printf(" * 1 使用短作業優先 *n");printf(" * 0 退出 *n");printf(" *n");/system("cls");system("color 1f");scanf("%d",&option);switch(option)case 0:printf("運行結束。n

16、");break;case 1:printf("對進程用短作業優先調度。nn"); Pinput();SJF();Poutput();break;int Pinput() /進程參數輸入int i;printf("請輸入進程個數:n");scanf("%d",&N);for(i=0;i<N;i+)printf("*n");printf("請輸入一個進程:n",i+1);printf("請輸入進程名稱:n");scanf("%s",P

17、rocessi.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;Processi.run_flag=0;system("cls"

18、);return 0;int Poutput() /調度結果輸出int i;float turn_round_time=0,f1,w=0;printf(" 進程名稱 到達T 運行T 開始運行T 結束T 執行順序 周轉T 帶權周轉Tn");for(i=0;i<N;i+)Processi.WeightWholeTime=Processi.FinishTime-Processi.ArrivalTime;f1=Processi.WeightWholeTime/Processi.WholeTime;turn_round_time+=Processi.WeightWholeTim

19、e;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;九、實驗體會通過本次課程設計，使我對計算機操作系統短作業優先調度算法這一節的知識有了更深的了解 。短作業優先調度算法易于實現，并且效率很高，但是短作業只考慮到短作業的利益，而不顧長作業，這樣就可能會使得長作業一直處于等待狀態而不能運行。所以，短作業優先