參考程序：處理機低調度模擬系統(tǒng)

1、題目：處理機調度算法的模擬專業(yè)：網(wǎng)絡項目班級：學號：姓名：指導教師：完成日期：一、課程設計目的1、掌握C語言數(shù)組、函數(shù)、指針、結構體的綜合應用。2、掌握使用C語言，進行應用性的開發(fā)。3、掌握系統(tǒng)數(shù)據(jù)結構與算法的設計。二、課程設計內容課程設計題目：處理機低級調度模擬系統(tǒng)課程設計內容：根據(jù)操作系統(tǒng)處理機不同的調度算法，使用C語言模擬實現(xiàn)處理機調度過程。1、系統(tǒng)數(shù)據(jù)結構<1）進程控制塊vpcb）:進程名稱、至U達時間、進程要求運行時間、進程已運行時間、指針、進程狀態(tài)等等 <要根據(jù)不同算法的需要 定義全面的數(shù)據(jù)結構）<2）進程隊列vPQueue :鏈表2、調度算法<1）先來先服

2、務調度vFCFS）:按照進程提交給系統(tǒng)的先后順序 來挑選進程， 先提交的先被挑選。<2）短進程優(yōu)先調度 <SJF）： 是以進入系統(tǒng)的進程所提出的 “執(zhí) 行時間 ”為標準，總是優(yōu)先選取執(zhí)行時間最短的進程。<3）高響應比優(yōu)先調度 <HRN ）：是在每次調度前都要計算所有 被選進程 <在后備隊列中）的響應比，然后選擇響應比最高的進程執(zhí) 行。<4）多級反饋隊列調度（FB，第i級隊列的時間片=2i-1>: <a）應 設置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。<b）當一個新進程進入內存后，首先將它放入第一隊列的末尾，按 FCFS 的原 則排隊等待

3、調度。當輪到該進程執(zhí)行時，如他能在該時間片內完 成，便可準備撤離系統(tǒng)；如果它在一個時間片結束時尚未完成，調 度程序便將該進程轉入第二隊列的末尾，再同樣地按 FCFS 原則等 待調度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再 依次將它放入第三隊列 ，如此下去，當一個長作業(yè)進程從第一 隊列依次降到第 N 隊列后，在第 N 隊列中便采取時間片輪轉的方式 運行。VC ）僅當?shù)谝魂犃锌臻e時，調度程序才調度第二隊列中的進 程運行。三、課程設計的要求1、按照給出的題目內容 <1）完成系統(tǒng)數(shù)據(jù)結構設計與實現(xiàn)、系統(tǒng)算法設計與實現(xiàn)、系統(tǒng)模 塊設計與實現(xiàn)、系統(tǒng)總體的設計與實現(xiàn)。<2）系統(tǒng)需要一

4、個簡單操作界面，例如:1. 先來先服務調度2. 短進程優(yōu)先調度3. 高響應比優(yōu)先調度4. 多級反饋隊列調度5. 退出<按數(shù)字 1、2、 3、 4、5，選擇操作） <3）對每種調度算法都要求輸出每個進程 <進程數(shù)不少于 5）開始運 行時刻、完成時刻、周轉時間，以及這組進程的平均周轉時間。 <4）畫出每種調度算法流程圖。2、寫出課程設計報告，設計報告提交形式：電子文檔提交3、個人獨立完成。4、完成時間 <1 周）四、課程設計過程1、系統(tǒng)中所使用的數(shù)據(jù)結構及說明/ 數(shù)據(jù)結構的定義 /定義進程控制塊 PCBtypedef struct PCBchar PID5。/進程標示

5、符int PRI/進程的優(yōu)先級 （越小越高 >float NeedTime。float StartTime。間float RunBeginTime。float UpTime。float OverTime 。float TurnaroundTime。 float RightTTime 。 struct PCB *next。 PCB,*QueuePtr。 /定義進程隊列 typedef struct QueuePtr front,rear。PQueue。2、系統(tǒng)功能結構/ 進程要求運行時間 （服務時間 > /進程進入就緒隊列的時間 （ 到達時/ 開始運行時間/ 進程已運行時間/ 進程運

6、行完成的時間/周轉時間/ 帶權周轉時間/隊頭、隊尾指針本系統(tǒng)是處理機低級調度模擬系統(tǒng)，主要通過模擬來實現(xiàn)處理機調度，調度方式有先來先服務調度VFCFS）、短進程優(yōu)先調度<SJF）、高響應比優(yōu)先調度<HRN）、多級反饋隊列調度 （FB>四種 調度方式。系統(tǒng)運行過程如下：輸入進程個數(shù)，輸入進程詳細信息，通過簡單操作界面來選擇調度方式，調度的過程和結果，重新選擇調度方式或者選擇結束開始3、調度算法流程圖 如下圖所示）開始輸入進程個 數(shù)和進程詳 細信息找到第一個到達的進程并排在隊首以后到達的進程按到達時間和服務時間進行綜合排序令p為隊首的進程計算p的開始運行時間，結束運行時間，周轉時

7、間和帶權周轉時間p=p_>next輸出進程 相關信息NOYES p!=NULL?>輸出平均周轉 時間和平均帶 權周轉時間計算平均周轉時間和平均帶權周轉時間結束輸入進程個數(shù)和進程詳細信息找到第一個到達的進程并排在隊首以后到達的進程按響應比大小進行排序令P為隊首的進程計算P的開始運行時間，結束運行時間，周轉時間和帶權周轉時間輸出進程 相關信息p=p_>nextYESp!=NULL? ii計算平均周轉 時間和平均帶權周轉時間輸出平均周轉 時間和平均帶 權周轉時間結束開始輸入進程個 數(shù)和進程詳細信息對進程按FCFS序 并保存在隊列Q中設置第一隊列Q、第二隊列M、第三隊列N的時間片T1

8、、T2、T3的大?。?i-1）NOYES第一隊列Q為空？ 令p為隊列Q的頭結點YES一 第二隊列M為空？、二;NOYES叩->n ext這個進程的<=T1？服務時間*計算p->next的已運 行時間，結束運行 時間，周轉時間和 帶權周轉時間輸出進程詳 細運行信息NO令P-> next的已運行時間為T1輸出進程詳 細運行信息將進程插入隊列M中> p=p->next "<YE乞：p->next!=NULL? 一：；-結束令p為隊列 M的頭結點YESNO_.”P>next這個進程的""耳 服務時間<=T2?&g

9、t;計算p-> next的已運行時間，結束運行 時間，周轉時間和帶權周轉時間YES "、*-第三隊列N為空?令P-> next的已運行時間為T1+T2輸出進程詳 細運行信息輸出進程詳 細運行信息將進程插入隊列N中Hp=p->nextp->next!=NULL?NO令p為隊列N的頭結點計算p-> next的已運行時間，結束運行時間，周轉時間和帶權周轉時間輸出進程詳 細運行信息YESp=p->nextNOYES,p-> next!=NULL?4、程序清單及其描述#include<stdio.h>#include<stdlib.h

10、>#include<math.h>#include<malloc.h>#include<process.h>#include<stdlib.h>#define NULL 0int ProcessNum。/進程個數(shù)float AverageTurnoverTime。 /平均周轉時間float AverageRightTTime。 /平均帶權周轉時間/ 函數(shù)結果狀態(tài)代碼 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0/ 數(shù)據(jù)結構的定義 /定義進程控制塊 PCBtypedef st

11、ruct PCBchar PID5。/進程標示符char Name10。/進程名稱int PRI/進程的優(yōu)先級 （越小越高 >/進程要求運行時間 （服務時間 > /進程進入就緒隊列的時間 （到達時間 >/開始運行時間/進程已運行時間/進程運行完成的時間/周轉時間/帶權周轉時間/隊頭、隊尾指針float NeedTime。 float StartTime。float RunBeginTime。float UpTime。 float OverTime 。float TurnaroundTime。 float RightTTime 。 struct PCB *next。PCB,*Q

12、ueuePtr。 /定義進程隊列 typedef structQueuePtr front,rear。PQueue。/ 函數(shù)的申明int InitQueue(PQueue &Q。 int EnQueue(PQueue &Q。int QueueEmpty(PQueue Q。 回 1,否則返回 0 void PoolQueue(PQueue *Q。 int print(PQueue Q。/構造一個空隊列/插入一個新的進程到隊尾隊列判空，若Q為空隊列，則返/建立后備隊列/進程隊列輸出void FCFSsort(PQueue &Q>。 進行排序void SPFsort(P

13、Queue &Q>。進行排序void HRNsort(PQueue &Q>。 間進行排序void Dispatcher(PQueue &Q>。void FB(PQueue &Q>。/先來先服務調度的對到達時間/短進程優(yōu)先調度的對服務時間/高響應比優(yōu)先調度的對服務時/先來先服務調度/多級反饋隊列調度void ManagesChooses(PQueue &Q。 / 調度方式選擇/ 函數(shù)的定義 / 構造一個空隊列 int InitQueue(PQueue &Q>Q.front=Q.rear=(QueuePtr>mal

14、loc(sizeof(PCB>>。 if(!Q.front>exit(0> 。Q.front->next=NULL 。return 1。/ 插入一個新的進程到隊尾 int EnQueue(PQueue &Q>QueuePtr p。if(!(p=(QueuePtr>malloc(sizeof(PCB>>>>/存儲分配失敗exit(0> 。 scanf("%s",p->PID>。/輸入進程標示符 scanf("%s",p->Name>。/輸入進程名scan

15、f("%d %f %f",&p->PRI,&p->NeedTime,&p->StartTime>。 /輸入進程優(yōu)先級、要求運行時間、到達時間 p->next=NULL 。Q.rear->next=p。Q.rear=p。return 1。/ 隊列判空， 若 Q 為空隊列 ,則返回 1,否則返回 0int QueueEmpty(PQueue Q>/若Q為空隊列，則返回1,否則返回0if(Q.front=Q.rear>return 1。elsereturn 0。/ 建立后備隊列 void PoolQueue(

16、PQueue *Qint i 。printf(" 請輸入進程的個數(shù)： "。 scanf("%d",&ProcessNum。printf("請輸入d個進程的信息T代表時間)n標示符 程名 優(yōu)先級 服務 T 到達 Tn",ProcessNum。for(i=1。i二ProcessNum。i+ EnQueue(*Q。/ 進程隊列輸出 int print(PQueue QQueuePtr p。if(Q.front=Q.rearreturn 0。p=Q.front-next。printf("<T 代表時間) n 標示符 進

17、程名 優(yōu)先級 服 務 T 到達 Tn"> 。while (p!=NULL>/當隊列不空printf("%st%st%dt%4.3ft%4.3fn",p->PID,p->Name,p- >PRI,p->NeedTime,p->StartTime>。p=p->next。/ 先來先服務調度的對到達時間進行排序 void FCFSsort(PQueue &Q>QueuePtr tail,p=Q.front。QueuePtr q=p->next。tail=NULL 。for(。p->next-&

18、gt;next!二tail。p=Q.front,q=p->next>/選擇排序if(p->next->StartTime > q->next->StartTime> p->next=q->next。q->next=q->next->next。p->next->next=q。p=p->next。q=p->next。tail=q 。/ 短進程優(yōu)先調度的對服務時間進行排序 void SPFsort(PQueue &Q>/deltaT 是時間float deltaT,Time=0。差Qu

19、euePtr temp1,temp2,tail,p=Q.fro n。QueuePtr q=p->next。tail=NULL 。一個到達而且服務時間最少的進程if(p->next->StartTime > q->next->StartTime>temp1=p->next。temp2=q->next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。elseq=q->next。if(p->next->StartTime > Time

20、>Time=p->StartTime。Time=Time+p->next->NeedTime。for(p=p->next,q=p->next 。 p->next->next!=tail 。 p=p->next,q=p->next>/對隊列按到達時間與服務時間長短進行選擇排序<從第二個元素開始)while(q->next!=tail>if(p->next->StartTime <= Time>>if(q->next->StartTime <= Time>&am

21、p;&(p->next- >NeedTime > q->next->NeedTime>>temp1=p->next。temp2=q->next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。elseq=q->next。else if(p->next->StartTime > Time>&&(q->next- >StartTime <= Time>>temp2=q-&g

22、t;next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。elseq=q->next。if(p->next->StartTime > Time>deltaT=p->StartTime-Time。Time=Time+deltaT。Time=Time+p->next->NeedTime。/ 高響應比優(yōu)先調度的對服務時間進行排序 - void HRNsort(PQueue &Q>float deltaT,PResp on seRatio,QRes

23、p on seRatio,Time=0/deltaT是時間差,PResponseRatio QResponseRatic是響應比QueuePtr temp1,temp2,tail,p=Q.fro n。QueuePtr q=p->next。tail=NULL 。for(。 q->next!=tail 。 >/找出第一個到達而且服務時間最少的進程if(p->next->StartTime > q->next->StartTime>temp1=p->next。temp2=q->next。p->next=temp2。q->n

24、ext=temp2->next。p->next->next=temp1。elseq=q->next。if(p->next->StartTime > Time>Time=p->StartTime。Time=Time+p->next->NeedTime。for(p=p->next,q=p->next 。 p->next->next!=tail 。 p=p->next,q=p- >next>/對隊列按響應比大小排序 <從第二個元素開始)while(q->next!=tail>

25、if(p->next->StartTime <= Time>&&(q->next->StartTime <= Time>>PResponseRatio=(Time-p->next- >StartTime>+p->next->NeedTime>/(p->next->NeedTime>>。QResponseRatio=(Time-q->next->StartTime>+q->next->NeedTime>/(q->next-&g

26、t;NeedTime>>。 if(PResponseRatio<QResponseRatio> temp1=p->next。temp2=q->next。p->next=temp2。 q->next=temp2->next。 p->next->next=temp1。elseq=q->next。else if(p->next->StartTime > Time>&&(q->next- >StartTime <= Time>>temp1=p->next。

27、temp2=q->next。p->next=temp2。q->next=temp2->next。 p->next->next=temp1。elseq=q->next。if(p->next->StartTime > Time>Time=Time+deltaT。Time=Time+p->next->NeedTime。/ 調度 void Dispatcher（PQueue &Q>float SumTurnaroundTime=0。 /定義周轉時間總和并賦值 0float SumRightTTime=0。/定義

28、帶權周轉時間總和并賦值 0float deltaT,Time=0。/deltaT 是時間差QueuePtr p=Q.front->next。printf（"<T 代表時間） n 標示符進程名 到達 T務 T 開始 T 完成 T 周轉 T 帶權周轉 Tn"> 。for（。p!二NULL。p=p->next>if（p->StartTime>Time>Time=deltaT。p->RunBeginTime=Time。p->OverTime=Time+p->NeedTime。p->TurnaroundTime=

29、p->OverTime-p->StartTime。 p->RightTTime=p->TurnaroundTime/p->NeedTime。printf("%st%st%4.3ft%4.3ft%4.3ft%4.3ft%4.3ft%4.3fn",p->PID,p->Name,p->StartTime,p->NeedTime,p->RunBeginTime,p->OverTime,p->TurnaroundTime,p->RightTTime>。Time=p->OverTime。for(p

30、二Q.front->next。p!二NULL。p=p->next>/計算平均周轉時間和平均帶權周轉時間SumTurnaroundTime=SumTurnaroundTime+p->TurnaroundTime。SumRightTTime=SumRightTTime+p->RightTTime 。 AverageTurnoverTime=SumTurnaroundTime/ProcessNum。AverageRightTTime=SumRightTTime/ProcessNum。printf("此調度方式的平均周轉時間為 4.3f,平均帶權周轉時間為 4.

31、3fn",AverageTurnoverTime,AverageRightTTime。/多級反饋隊列調度 void FB(PQueue &QPQueue M,N。InitQueue(M。/初始化第二隊列InitQueue(N。/初始化第三隊列FCFSsort(Q。printf(" 調度前進程排列如下 :n"。print(Q。QueuePtr p,q,r。q=M.front。r=N.front。float i,deltaT,Time=0。/deltaT是時間差float T1,T2,T3。T1=2*1-1 。第一隊列Q的時間片T2=2*2-1 。/第二隊列

32、M 的時間片T3=2*3-1 。/第三隊列 M 的時間片 printf("n 調度過程如下 :n"> 。for(p二Q.front。p->next!二NULL。p=p->next>/第一隊列的調度if(p->next->StartTime>Time>for(i=Time+1 。 i<=p->next->StartTime。 i+> printf("第4.3f時刻，等待隊列到來！ n",i>。deltaT=p->next->StartTime-Time。Time=Ti

33、me+deltaT。p->next->RunBeginTime=Time。 if(p->next->NeedTime<=T1>p->next->OverTime=Time+p->next->NeedTime。 p->next->UpTime=p->next->NeedTime。>next->StartTime。p->next->RightTTime=p->next->TurnaroundTime/p->next->NeedTime。for(i二Time+1。i&l

34、t;p->next->OverTime。i+>printf("第4.3f時刻，進程標示符 st進程 名 %s 運行中,已運行了 %4.3f 時刻！ n",i,p->next->PID,p->next- >Name,i-Time>。printf("第%4.3f時刻，進程標示符 %st進程名%s 運行完成！ n",i,p->next->PID,p->next->Name>。Time=p->next->OverTime。elsep->next->UpTime=

35、T1 。for(i=1 。 i<=T1 。 i+>printf("第%4.3f時刻，進程標示符 %st進程 名 %s 運行中，已運行了 %4.3f 時刻！ n",p->next->RunBeginTime+i,p- >next->PID,p->next->Name,i>。q->next=p->next。q=q->next。Time=Time+T1 。q->next=NULL 。for(p=M.front。p->next!二NULL。p=p->next>/第二隊列的調度if(p-&

36、gt;next->NeedTime-p->next->UpTime><=T2>p->next->OverTime=Time+p->next->NeedTime-p- >next->UpTime。p->next->TurnaroundTime=p->next->OverTime-p- >next->StartTime。p->next->RightTTime=p->next->TurnaroundTime/p- >next->NeedTime。for(i=

37、Time+1 。 i<p->next->OverTime。 i+>printf("第4.3f時刻，進程標示符 st進程 名 %s 運行中,已運行了 %4.3f 時刻！ n",i,p->next->PID,p->next- >Name,p->next->UpTime+i-Time> 。printf("第%4.3f時刻，進程標示符 %st進程名%s 運行完成！ n",i,p->next->PID,p->next->Name>。p->next->UpTi

38、me=p->next->NeedTime。elsefor(i=1。i<=T2。i+>printf("第4.3f時刻，進程標示符 st進程 名 %s 運行中,已運行了 %4.3f 時刻！ n",Time+i,p->next->PID,p- >next->Name,i+p->next->UpTime>。r->next=p->next。r=r->next。 p->next->UpTime=p->next->UpTime+T2 。 Time=Time+T2。r->nex

39、t=NULL 。for(p=N.front。 p->next!=NULL 。 p=p->next>/第三隊列的調度 p->next->OverTime=Time+p->next->NeedTime-p->next- >UpTime。p->next->TurnaroundTime=p->next->OverTime-p->next- >StartTime。>NeedTime。for(i二Time+1。i<p->next->OverTime。i+>printf("第4.

40、3f時刻，進程標示符 st進程名%s 運行中，已運行了 %4.3f 時刻！ n",i,p->next->PID,p->next->Name,p- >next->UpTime+i-Time> 。printf("第%4.3f時刻，進程標示符%st進程名%s運行完 成！ n",i,p->next->PID,p->next->Name> 。p->next->UpTime=p->next->NeedTime。 Time=p->next->OverTime。/ 調度方式

41、選擇 void ManagesChooses(PQueue &Q>int i 。printf("nnnt 請選擇調度方式： n">。 printf("=n"> 。printf("1.先來先服務調度 n">。printf("2.短進程優(yōu)先調度 n">。printf("3.高響應比優(yōu)先調度 n">。printf("4.多級反饋隊列調度 n">。prin tf(" 5.退出 n">。printf("

42、;< 按數(shù)字 1、2、3、4、5,選擇操作)n">。n">printf(" scanf("%d",&i 。switch(icase 1:FCFSsort(Q。printf(" 先來先服務調度的對到達時間進行排序的排序 結果如下 :n" 。print(Q 。printf("n 調度后的結果如下 :n" 。Dispatcher(Q。Man agesChooses(Qbreak。case 2:SPFsort(Q。printf(" 短進程優(yōu)先調度的對服務時間進行排序的排序 結果

43、如下 :n"。print(Q。printf("n 調度后的結果如下 :n" 。Dispatcher(Q。ManagesChooses(Q 。break。case 3:HRNsort(Q。printf(" 高響應比優(yōu)先調度的對服務時間進行排序的排序結果如下 :n">print(Q 。printf("n 調度后的結果如下 :n" 。 Dispatcher(Q。Man agesChooses(Qbreak。case 4:FB(Q。ManagesChooses(Q 。break。case 5:break。/ 主函數(shù) void

44、main(int n。PQueue Q。InitQueue(Q。/初始化后備隊列PoolQueue(&Q。/ 進程插入后備隊列中并返回進程個數(shù)printf("n 輸入的進程情況如下 :n"。print(Q。Man agesChooses(Q>3、系統(tǒng)運行結果"E:M SDev98MyProjectsll 冃 2 了曰 iDe bugl 1月對曰己.exe"g無口王 哥一 5 方入符 圍幕1;4 5呈名E標示符123標手符123A間T夷服4代優(yōu)魏1234請選擇調度方式:度度、衛(wèi) 度度調調亦 調調先列 桑優(yōu)隊4饋冬 先程應反 、 盍高多退12

45、3 4服務T4. HUB3.0005 B0Q2.BB04.000到達T0.0001.3002*0004*盹0優(yōu)救12服務T4- dt)03-AO05- 0002.00040附到達T0.0001-Q902.B&&3.0004,000訓痘后的結果如下:撕軀名1Ab B司）到達T0.000l.oee2.see3.000 4.000服務T4.0003.0005.0002.004.B00開始T0.0004.0007,000 12.000 丄4B00完成T4.00012.00014.B0018.000周轉T4.QQQJ 00010.00011 14,000帶權周轉T1.0002.&

46、Q&2.8005.5003.590此調度方式的平均周轉時間為以込平均帶權周轉時間為“翻先程應反 盡響番 奩高多退4度度 度度調調 調調先列 務先優(yōu)隊度的對展務時間迸行排序的排序結果如下)呈名優(yōu)先級服務T到達T14.0000.00042.0003 00023.0001 00054.0004.00035.0002 000到達T0 000服務T4 000開始T0 000完成T4 000周轉T4.000帶權周轉T1.0004D3.0002.0004.0006.0003.00012B1.0003.0006.0009.0008.00025E4.0004.0009.00013.0009.00023C2.0005.0001