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

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

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

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

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

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

7、使該算法不一定能真正做到短作業游戲那調度。該程序定義了一個進程數據塊(struct process_)，該數據塊有進程名(name)、到達時間(arrivetime)、服務時間(servicetime)、開始執行時間(starttime)、完成時間(finishtime)、周轉時間(zztime)、帶權周轉時間(dqzztime)、執行順序（order）。用到的公式有：完成時間=到達時間+服務時間；周轉時間=完成時間+到達時間； 帶權周轉時間=周轉時間/服務時間；(第一次執行的進程的完成時間=該進程的 到達時間；下一個進程的開始執行時間=上一個進程的完成時間)。運行進程的順序需要對進程的到達時

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

9、程設計還增加了阻塞時間和被阻塞時間來對個進程的運行加以控制。 此次課程設計的總體流程圖如下：r結束輸出最后信息：output()開 始輸入進程的個數:numsort()輸入進程的信息:namestarttimeservicetime隊列中是否只有一個進程？ny執行時間處理函數：time()執行判斷函數：run()八、源程序文件#include #define maxnum 100 using namespace std; struct process_structintnumber;/進程編號char namemaxnum;/進程名稱intarrivaltime;/到達時間intservice

10、time;/開始運行時間intfinishtime;/運行結束時間intwholetime;/運行時間 int run_flag;/調度標志int order;/運行次序doubleweightwholetime;/周轉時間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

11、number_schedul,temp_counter;/進程編號，當前已執行進程個數float run_time;run_time=processi.wholetime; j=1;while(jn)&(processi.arrivaltime=processj.arrivaltime)/判斷是否有兩個進程同時到達if(processj.wholetimeprocessi.wholetime) j+;run_time=processi.wholetime; i=j;/查找下一個被調度的進程/對找到的下一個被調度的進程求相應的參數number_schedul=i;processnumber_sc

12、hedul.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;/查找下一個被調度的進程/對找到的下一個被調度的進程求相應的參數proc

14、essnumber_schedul.servicetime=temp_time;processnumber_schedul.finishtime=processnumber_schedul.servicetime+p rocessnumber_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); break;case 1:printf(對進程用短作業優先調度。nn); pinput();sjf();poutput(); break;int pinput()/進程參數輸入int i;printf(請輸入進程

16、個數: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.ord

17、er=0; processi.run_flag=0;system(cls);return 0;int poutput()/調度結果輸出int i;float turn_round_time=0,f1,w=0;printf(進程名稱 到達 t 運行 t 開始運行 t 結束 t 執行順序 周轉 t帶權周轉 tn);for(i=0;in;i+)processi.weightwholetime=processi.finishtime-processi.arrivaltime; f1=processi.weightwholetime/processi.wholetime; turn_round_time

18、+=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.serv icetime,processi.finishtime,processi.order,processi.weightwholetime,f1);printf(average_turn_round_timer=%fn,turn_round_time/

19、n); printf(weight_average_turn_round_timer=%fn,w/n);return 0;九、實驗體會通過本次課程設計，使我對計算機操作系統短作業優先調度算法這一節的知識有了更深的了解 。短作業優先調度算法易于實現，并且效率很高，但是短作業只考慮到短作業的利益，而不顧長作業，這樣就可能會使得長作業 一直處于等待狀態而不能運行。所以，短作業優先算法適用于系統中短作業 較多的情況。此外，通過本次實驗，進一步鞏固和復習操作系統的基礎知識， 更進一步的了解了結構化模塊化程序設計的方法，提高了調試程序的技巧， 提高了自己的動手能力我對操作系統中的作業調度模擬和短作業優先算

20、法有 了更深的認識。并且發現，只看課本上的知識遠遠不夠，只一味學習也根本 沒用，必須要動手親自實踐，才能真正掌握所學的東西。雖然在這次課程 設計過程中，我們也遇到了很多問題，但我們都能保持一個良好的心態，不 急不躁，并且能通過請教老師，與同學們積極討論，查看課外資料，反復實 驗，反復檢查，將問題一個個解答，并最終成功的完成本次課程設計。課程 設計結束了，在這次的課程設計中不僅檢驗了我所學習的知識，也培養了我 如何去做一件事情，又如何完成一件事情的能力。通過模擬進程的調度問題，更加深了我對于操作系統理論的理解，在自己的動手操作過程中，能夠體會成功的喜悅和遇到問題自己解決的能力， 對于我來說是一次提高，讓自己多多的在實踐中可以加深對理論的理解，也讓我明白了以后應該如何更好，更高效的學習，在以后，我會更加努力?？傊?，本次課程設計讓我們學到了很多東西，包括課本上的和課外的， 是一個非常有意義的課程設計。十、參考文獻1） 宗大華，宗濤，陳吉人著 操作系統北京：人民郵電出版社，20092） 李愛華，程磊著面相對象程序設計（c+語言） 北京: 清華大學出版社，20103） 宋曉宇 ， windows 操作系統核心編程實驗教程 中國鐵道出版社4） 張麗芬 劉利雄 王金玉編著 操作系統實驗教程清華大學出版社“”“”at the