1、操 作 系 統課程設計說明書題目:為單道批處理系統設計一個作業調度模擬程序 院 系： 計算機科學與工程學院 專業班級： 計算機 學 號： 學生姓名： 指導教師： 計算機科學與工程學院 計算機科學與技術系 學 號學生姓名專業（班級）計算機09-3班設計題目為單道批處理系統設計一個作業調度模擬程序設計技術參數使用Microsoft Visual C+ 6.0編輯器編寫，利用c語言開發的基于單道批處理系統的一個作業調度模擬程序，完成該課程設計需要掌握先來先服務（FCFS），最短作業優先（SJF）、響應比高者優先（HRN）的調度算法。設計要求作業調度算法分別采用先來先服務（FCFS），最短作業優先（S

2、JF）、響應比高者優先（HRN）的調度算法。對每種調度算法都要求打印每個作業開始運行時刻、完成時刻、周轉時間、帶權周轉時間，以及這組作業的平均周轉時間及帶權平均周轉時間，以比較各種算法的優缺點。工作量1 源代碼程序不少于400行2 附有各種圖示4張3 課程設計任務書不少于3500字工作計劃1.10月23日-10月28日：查詢相關資料，初步確定課程設計的語言，進一步明確其所要實現的功能2.10月29日-11月10日：根據所學知識及搜集的相關信息進行概要設計3.11月11日-11月25日：進行詳細設計，完成相應源代碼的編寫4.11月26日-12月2日：對源代碼進行調試、運行5.12月3日-12月1

3、0日：完善課程設計說明書并提交參考資料1 梁小丹，梁紅兵，哲鳳屏，湯子贏計算機操作系統.第三版西安：西安電子科技大學出版社，200722 袁捷、沈俊、 袁晴晴. 計算機操作系統基礎與應用.第二版.北京： 清華大學出版社，2009.073楊振山、龔培增. 計算機操作系統教程.第三版. 北京：清華大學出版社, 2007.94譚浩強. C程序設計.第四版.北京:清華大學出版社, 2010.065王敬華，林萍，張清國等C語言程序設計教程.第二版北京：清華大學出版社，200910指導教師簽字系主任簽字2011年9月 26日學生姓名： 學號： 專業班級： 計算機09-3班 設計題目： 為單道批處理系統設計

4、一個作業調度模擬程序 指導教師評語：成績： 指導教師： 年 月 日安徽理工大學課程設計（論文）成績評定表摘要 本次課程設計要求用高級語言編寫和調試一個單道批處理系統的作業調度的模擬程序，了解作業調度在操作系統中的作用，以加深對作業調度算法的理解。作業調度算法分別采用先來先服務（FCFS），最短作業優先（SJF）、響應比高者優先（HRN）的調度算法。對每種調度算法都要求打印每個作業開始運行時刻、完成時刻、周轉時間、帶權周轉時間，以及這組作業的平均周轉時間及帶權平均周轉時間，以比較各種算法的優缺點。 關鍵詞：作業調度,先來先服務（FCFS）,最短作業優先（SJF）,響應比高者優先（HRN）目 錄1

5、需求分析11.1問題描述11.2功能分析及描述11.3 開發語言選擇12概要設計22.1功能模塊劃分22.2功能模塊的描述22.3功能模塊結構圖示23詳細設計43.1作業控制塊JCB的數據結構類型43.2先來先服務算法設計43.3最短作業優先算法設計53.4響應比高者優先算法設計64代碼實現84.1高響應比算法84.2最短作業優先算法84.3先來先服務算法95運行結果與分析115.1選擇操作的界面115.2選擇先來先服務算法進行作業調度115.3選擇最短作業優先算法進行作業調度125.4選擇高響應比優先算法進行作業調度136結束語157附錄16參考文獻1需求分析 1.1問題描述為單道批處理系統

6、設計一個作業調度模擬程序。作業調度算法分別采用先來先服務（FCFS），最短作業優先（SJF）、響應比高者優先（HRN）的調度算法。對每種調度算法都要求打印每個作業開始運行時刻、完成時刻、周轉時間、帶權周轉時間，以及這組作業的平均周轉時間及帶權平均周轉時間，以比較各種算法的優缺點。1.2功能分析及描述在批處理系統中，作業進入系統后，先駐留在外存上，通過作業調度算法，將它們分批裝入內存。作業調度程序用于決定把外存上處于后備隊列中的哪些作業調入內存，并為他們創建進程、分配必要的資源，然后，再將新創建的進程加入就緒隊列中，準備執行。應將哪些作業從外存調入內存，取決于所采用的調度算法。最簡單的是先來先服

7、務調度算法，這是指講最早進入外存的作業最先調入內存；較常用的一種是短作業優先調度算法，這是將外存上最短的作業最先調入內存；此外，還有基于響應比高者優先的調度算法，根據作業的等待時間和要求服務時間的和與要求服務時間之比可計算出響應比。1.3 開發語言選擇 本課程設計采用C語言實現。2概要設計 2.1功能模塊劃分根據功能描述，單道批處理程序作業調度的模擬程序要求實現如下功能：建立作業、選擇作業、運行作業、計算作業周轉時間和帶權周轉時間，以及這組作業的平均周轉時間和帶權平均周轉時間、顯示運行結果（包括每個作業開始運行時刻、完成時刻、周轉時間、帶權周轉時間，以及這組作業的平均周轉時間及帶權平均周轉時間

8、等）、退出程序。 2.2功能模塊的描述各模塊的功能介紹如下：（1）建立作業：輸入作業數，建立一組作業，并對所建立的這組作業進行初始化，用以模擬作業調度。初始化的內容包括作業名，作業要求運行的時間，其中，作業進入系統的時間由系統默認設置。（2）選擇作業：程序通過先來先服務調度算法、短作業優先調度算法和高響應比優先調度算法對建立的一組作業進行選擇，決定把哪個作業從外存調入內存中。（3）運行作業：根據初始化中設置的作業要求運行時間來模擬作業的運行。（4）計算：作業完成計算作業周轉時間和帶權周轉時間，以及這組作業的平均周轉時間和帶權平均周轉時間。（5）顯示結果：將計算所得的結果輸出。（6）退出程序：當

9、實驗結束，不再需要模擬作業調度的時候，用來退出程序。2.3功能模塊結構圖示作業調度模擬程序的系統功能結構如圖2-1所示。作 業 調 度 系 統 退出程序高響應比優先算短作業優先算法先來先服務算法輸出運行結果運行作業初始化初始化運行作業輸出運行結果初始化運行作業輸出運行結果 圖2-1 作業調度模擬程序系統功能結構圖3詳細設計 3.1作業控制塊JCB的數據結構類型由于在單道批處理系統中，不必考慮作業所需要的資源是否得到滿足，它所占用的 CPU時限等因素。每個作業由一個作業控制塊JCB表示，JCB可以包含如下信息：作業名、提交時間、所需的服務時間、所需的資源、作業狀態、鏈指針等等。作業的狀態可以是等

10、待W(Wait)、運行R(Run)和完成F(Finish)三種狀態之一。每個作業的最初狀態總是等待W。對每種調度算法都要求輸出每個作業開始運行時刻、完成時刻、周轉時間、帶權周轉時間，以及這組作業的平均周轉時間及帶權平均周轉時間。從以上分析可見，在這個模擬程序中作業控制塊JCB的數據結構類型可定義為：struct jcb /作業控制塊 char name10; /作業名 int reachtime; /作業到達時間 int starttime; /作業開始時間 int needtime; /作業需要運行的時間 float super; /作業的響應比 int finishtime; /作業完成時

11、間 float cycletime; /作業周轉時間 float cltime; /作業帶權周轉時間 char state; /作業狀態 struct jcb *next; /結構體指針*ready=NULL,*p,*q; typedef struct jcb JCB; 3.2先來先服務算法設計先來先服務算法：按照作業提交給系統的先后順序來挑選作業，先提交的先被執行。流程圖如圖3-1所示。空結 束計算并打印這組作業的平均周轉時間及帶權平均周轉時間等待隊列空？更改時間量times的值；times:=times+服務時間計算并打印運行作業i的完成時刻finishtime，周轉時間cycletime

12、，帶權周轉時間cltime;完成時間：=開始運行時間+服務時間周轉時間：=完成時間到達時間帶權周轉時間：=周轉時間/服務時間調度隊首的作業投入運行；更改隊首指針，使作業的狀態為R，記住作業運行的時刻starttime等初始化所有的JBC使JBC按作業提交的時刻的先后順序排隊時間量times:=0開 始不空圖3-1 先來先服務調度算法流程圖3.3最短作業優先算法設計最短作業優先算法：是以進入系統的作業所要求的服務時間為標準，總是優先選取執行時間最短的作業。流程圖如圖3-2所示。空結 束計算并打印這組作業的平均周轉時間及帶權平均周轉時間等待隊列空？更改時間量times的值；times:=times

13、+服務時間計算并打印運行作業i的完成時刻finishtime，周轉時間cycletime，帶權周轉時間cltime;完成時間：=開始運行時間+服務時間周轉時間：=完成時間到達時間帶權周轉時間：=周轉時間/服務時間調度隊首的作業投入運行；更改隊首指針，使所要求服務時間最短的作業排在隊首，使作業的狀態為R，記住作業運行的時刻starttime等初始化所有的JBC使JBC按作業提交的時刻的先后順序排隊時間量times:=0開 始不空圖3-2 短作業優先調度算法流程圖 3.4響應比高者優先算法設計響應比高者優先算法：是在每次調度前都要計算所有被選作業（在后備隊列中）的響應比，然后選擇響應比最高的作業執

14、行。流程圖如圖3-3所示。空結 束計算并打印這組作業的平均周轉時間及帶權平均周轉時間等待隊列空？更改時間量times的值；times:=times+服務時間計算并打印運行作業i的完成時刻finishtime，周轉時間cycletime，帶權周轉時間cltime;完成時間：=開始運行時間+服務時間周轉時間：=完成時間到達時間帶權周轉時間：=周轉時間/服務時間先計算隊列中所有作業的響應比，總是選擇響應比最高的走也作為此刻要運行的作業，并修改相應的指針，記下starttime等初始化所有的JBC使JBC按作業提交的時刻的先后順序排隊時間量times:=0開 始不空 圖3-3響應比高者優先算法流程圖4

15、代碼實現4.1高響應比算法void hrn(int m) /高響應比算法 JCB *min; int i,iden; system("cls"); inital(); for(i=0;i<n;i+) p=min=ready;iden=1; super(); do if(p->state='W'&&p->reachtime<=times) if(iden) min=p;iden=0; else if(p->super>min->super) min=p; p=p->next; while(p!=N

16、ULL); if(iden) i-;times+; /printf("ntime=%d:tno JCB submib.wait.",time); if(times>1000)printf("nruntime is too long.error.");getch(); else running(min,m); /調用running()函數 /for final(); /調用running()函數4.2最短作業優先算法void sjf(int m) / 最短作業優先算法 JCB *min; int i,iden; system("cls&qu

17、ot;); inital(); for(i=0;i<n;i+) p=min=ready;iden=1; do if(p->state='W'&&p->reachtime<=times) if(iden) min=p;iden=0; else if(p->needtime<min->needtime) min=p; p=p->next; while(p!=NULL) ; if(iden) i-; /printf("ntime=%d:tno JCB submib.wait.",time); time

18、s+; if(times>100)printf("nruntime is too long.error");getch(); else running(min,m); /調用running()函數 /for final(); /調用running()函數4.3先來先服務算法void fcfs(int m) /先來先服務算法 int i,iden; system("cls"); inital(); for(i=0;i<n;i+) p=ready;iden=1; do if(p->state='W'&&p-&

19、gt;reachtime<=times) iden=0; if(iden)p=p->next; while(p!=NULL&&iden) ; if(iden) i-; printf("n沒有滿足要求的進程,需等待"); times+; if(times>100)printf("n時間過長");getch(); else running(p,m); /調用running()函數 final(); /調用running()函數5運行結果與分析5.1選擇操作的界面如圖5-1所示。圖5-1 選擇操作的界面5.2選擇先來先服務算法

20、進行作業調度輸入操作初始信息，建立一組作業，由4個作業組成，作業名分別為a，b，c，d。如圖5-2所示。圖5-2 初始化調度順序為abcd。運行結果如圖5-3、圖5-4、圖5-5所示。 圖5-3 先來先服務算法調度 圖5-4先來先服務算法調度圖5-5先來先服務算法調度5.3選擇最短作業優先算法進行作業調度調度順序:acdb。運行結果如圖5-6、圖5-7、圖5-8所示。 圖5-6 最短作業優先算法調度 圖5-7 最短作業優先算法調度圖5-8最短作業優先算法調度5.4選擇高響應比優先算法進行作業調度調度順序:acbd。運行結果如圖5-9、圖5-10、圖5-11所示。 圖5-9響應比高者優先算法調度

21、 圖5-10響應比高者優先算法調度圖5-11 響應比高者優先算法調度6結束語當今，計算機技術在各個方面都極大地影響了人們的生活。操作系統作為一門計算機的基礎課程，無論是對計算機等信息技術專業的學生活研究人員，還是對一般計算機應用人員，都是非常有益和重要的。通過本次課程設計我對在課堂上所學的有關操作系統的知識有了更加深刻的理解和掌握，尤其是單道批處理系統。進一步了解了該系統的主要特征：自動性，順序性，單道性。批處理系統能提高系統資的利源用率和系統吞吐量。通過對三種調度算法的模擬程序設計，對先來先服務調度算法、短作業優先調度算法以及高響應比優先調度算法的基本概念、實現過程以及各個算法的優缺點有的了

22、深刻的了解，知道了不同的算法類型適合不同的作業類型。本次課程設計結合了C語言程序設計語言，通過對作業調度模擬程序的設計，積累了程序設計的實戰經驗，鍛煉了程序設計能力。通過這次課程設計，我學到了很多知識，拓寬了知識面，鍛煉了能力，綜合素質得到較大提高，把所學課程及相關知識加以融會貫通，理解了操作系統工作的方法，為今后的學習、工作打下了堅實的基礎。7附錄源程序：#include <stdio.h>#include <stdlib.h> #include <conio.h> #define getpch(type) (type*)malloc(sizeof(typ

23、e) #define NULL 0int n;float T1=0,T2=0;int times=0;struct jcb /作業控制塊 char name10; /作業名 int reachtime; /作業到達時間 int starttime; /作業開始時間 int needtime; /作業需要運行的時間 float super; /作業的響應比 int finishtime; /作業完成時間 float cycletime; /作業周轉時間 float cltime; /作業帶權周轉時間 char state; /作業狀態 struct jcb *next; /結構體指針*ready

24、=NULL,*p,*q;typedef struct jcb JCB; void inital() /建立作業控制塊隊列,先將其排成先來先服務的模式隊列int i;printf("n輸入作業數:");scanf("%d",&n);for(i=0;i<n;i+) p=getpch(JCB); printf("n輸入作業名:"); scanf("%s",p->name); getch(); p->reachtime=i; printf("作業默認到達時間:%d",i); p

25、rintf("n輸入作業要運行的時間:"); scanf("%d",&p->needtime); p->state='W' p->next=NULL; if(ready=NULL) ready=q=p; else q->next=p; q=p; void disp(JCB* q,int m) /顯示作業運行后的周轉時間及帶權周轉時間等 if(m=3) /顯示高響應比算法調度作業后的運行情況 printf("n作業%s正在運行，估計其運行情況：n",q->name); printf(

26、"開始運行時刻：%dn",q->starttime); printf("完成時刻：%dn",q->finishtime); printf("周轉時間：%fn",q->cycletime); printf("帶權周轉時間：%fn",q->cltime); printf("相應比:%fn",q->super); getch(); else / 顯示先來先服務,最短作業優先算法調度后作業的運行情況 printf("n作業%s正在運行，估計其運行情況：n"

27、;,q->name); printf("開始運行時刻：%dn",q->starttime); printf("完成時刻：%dn",q->finishtime); printf("周轉時間：%fn",q->cycletime); printf("帶權周轉時間：%fn",q->cltime); getch(); void running(JCB *p,int m) /運行作業 if(p=ready) /先將要運行的作業從隊列中分離出來 ready=p->next; p->nex

28、t=NULL; else q=ready; while(q->next!=p) q=q->next; q->next=p->next; p->starttime=times; /計算作業運行后的完成時間,周轉時間等等 p->state='R' p->finishtime=p->starttime+p->needtime; p->cycletime=(float)(p->finishtime-p->reachtime); p->cltime=(float)(p->cycletime/p->n

29、eedtime); T1+=p->cycletime; T2+=p->cltime; disp(p,m); /調用disp()函數,顯示作業運行情況 times+=p->needtime; p->state='F' printf("n%s has been finished!npress any key to continue.n",p->name); free(p); /釋放運行后的作業 getch();void super() /計算隊列中作業的高響應比 JCB *padv; padv=ready; do if(padv-&

30、gt;state='W'&&padv->reachtime<=times) padv->super=(float)(times-padv->reachtime+padv->needtime)/padv->needtime; padv=padv->next; while(padv!=NULL);void final() /最后打印作業的平均周轉時間,平均帶權周轉時間 float s,t; t=T1/n; s=T2/n; getch(); printf("nn作業已經全部完成!"); printf(&qu

31、ot;n%d個作業的平均周轉時間是：%f",n,t); printf("n%d個作業的平均帶權周轉時間是%f：nnn",n,s); void hrn(int m) /高響應比算法 JCB *min; int i,iden; system("cls"); inital(); for(i=0;i<n;i+) p=min=ready;iden=1; super(); do if(p->state='W'&&p->reachtime<=times) if(iden) min=p;iden=0; e

32、lse if(p->super>min->super) min=p; p=p->next; while(p!=NULL); if(iden) i-;times+; /printf("ntime=%d:tno JCB submib.wait.",time); if(times>1000)printf("nruntime is too long.error.");getch(); else running(min,m); /調用running()函數 /for final(); /調用running()函數void sjf(in

33、t m) / 最短作業優先算法 JCB *min; int i,iden; system("cls"); inital(); for(i=0;i<n;i+) p=min=ready;iden=1; do if(p->state='W'&&p->reachtime<=times) if(iden) min=p;iden=0; else if(p->needtime<min->needtime) min=p; p=p->next; while(p!=NULL) ; if(iden) i-; /pri

34、ntf("ntime=%d:tno JCB submib.wait.",time); times+; if(times>100)printf("nruntime is too long.error");getch(); else running(min,m); /調用running()函數 /for final(); /調用running()函數void fcfs(int m) /先來先服務算法 int i,iden; system("cls"); inital(); for(i=0;i<n;i+) p=ready;iden=1; do if(p->state='W'&&p->reachtime<=times)