1、進程調(diào)度算法的模擬實現(xiàn)n 實驗?zāi)康?本實驗?zāi)M在單處理機情況下的處理機調(diào)度問題，加深對進程調(diào)度的理解。2利用程序設(shè)計語言編寫算法，模擬實現(xiàn)先到先服務(wù)算法FCFS、輪轉(zhuǎn)調(diào)度算法RR、最短作業(yè)優(yōu)先算法SJF、優(yōu)先級調(diào)度算法PRIOR、最短剩余時間優(yōu)先算法SRTF。3進行算法評價，計算平均等待時間和平均周轉(zhuǎn)時間。n 實驗內(nèi)容及結(jié)果1先來先服務(wù)算法2輪轉(zhuǎn)調(diào)度算法3. 優(yōu)先級調(diào)度算法4. 最短時間優(yōu)先算法5. 最短剩余時間優(yōu)先算法n 實驗總結(jié)在此次模擬過程中，將SRTF單獨拿了出來用指針表示，而其余均用數(shù)組表示。n 完整代碼【Srtf.cpp代碼如下：】/最短剩余時間優(yōu)先算法的實現(xiàn)#include #i

2、nclude #include typedef structint remain_time;/進程剩余執(zhí)行時間int arrive_time;/進程到達時間int Tp;/進入就緒隊列的時間int Tc;/進入執(zhí)行隊列的時間int To;/進程執(zhí)行結(jié)束的時間int number;/進程編號Process_Block;/定義進程模塊typedef struct _QueueProcess_Block PB;struct _Queue *next;_Block,*Process;/定義一個進程模塊隊列中結(jié)點typedef struct Process head;/隊列頭指針Process end;

3、/隊列尾指針Process_Queue;/進程隊列Process_QueuePQ;/定義一個全局隊列變量intt;/全局時間ProcessRun_Now;/當(dāng)前正在運行的進程，作為全局變量void InitQueue(Process_Queue PQ)PQ.head -next = NULL;PQ.end-next = PQ.head;/*初始化隊列*/int IsEmpty(Process_Queue PQ)if(PQ.end-next = PQ.head)return 1;/隊列空的條件為頭指針指向尾指針并且尾指針指向頭指針elsereturn 0;/*判定隊列是否為空隊列*/void E

4、nQueue(Process_Queue PQ,Process P)Process temp =(Process)malloc(sizeof(_Block);temp = PQ.end;temp-next-next = P;PQ.end-next = P;/*插入隊列操作*/Process DeQueue(Process_Queue PQ)if(IsEmpty(PQ)return NULL;Process temp = PQ.head-next;PQ.head-next= temp -next;if(PQ.end-next = temp)PQ.end-next = PQ.head;return

5、 temp;/*出列操作*/Process ShortestProcess(Process_Queue PQ)if(IsEmpty(PQ)/如果隊列為空，返回if(!Run_Now)return NULL;elsereturn Run_Now;Process temp,shortest,prev;int min_time;if(Run_Now)/如果當(dāng)前有進程正在執(zhí)行，shortest = Run_Now; /那么最短進程初始化為當(dāng)前正在執(zhí)行的進程，min_time = Run_Now-PB.remain_time;else/如果當(dāng)前沒有進程執(zhí)行，shortest = PQ.head-next

6、;/則最短進程初始化為隊列中第一個進程min_time = PQ.head-next-PB.remain_time;temp = PQ.head;prev = temp;while(temp-next)if(temp-next-PB.remain_time next;/則保存當(dāng)前進程，min_time = shortest-PB.remain_time;prev=temp;/及其前驅(qū)temp=temp-next;if(shortest = PQ.end-next)/如果最短剩余時間進程是隊列中最后一個進程，PQ.end-next = prev;/則需要修改尾指針指向其前驅(qū)prev-next =

7、 shortest-next;/修改指針將最短剩余時間進程插入到隊頭return shortest;/*調(diào)度最短剩余時間的進程至隊頭*/void Run()Run_Now-PB.remain_time-;/某一時間運行它的剩余時間減return;/*運行函數(shù)*/void Wait()return ;int sum(int array,int n)int i,sum=0;for(i=0;in;i+)sum+=arrayi;return sum;int main()PQ.head= (Process)malloc(sizeof(_Block);PQ.end= (Process)malloc(siz

8、eof(_Block);Run_Now= (Process)malloc(sizeof(_Block);Run_Now=NULL;InitQueue(PQ);int i,N,Total_Time=0;/Total_Time為所有進程的執(zhí)行時間之和printf(請輸入計算機中的進程數(shù)目:n);scanf(%d,&N);Process *P,temp;P = (Process*)malloc(N*sizeof(Process);int *wt,*circle_t;wt=(int*)malloc(N*sizeof(int);circle_t=(int*)malloc(N*sizeof(int);fo

9、r(i=0;iPB.number=i+1;Pi-next=NULL;wti=0;circle_ti=0;printf(輸入第%d個進程的到達時間及剩余執(zhí)行時間:n,i+1);scanf(%d %d,&Pi-PB.arrive_time,&Pi-PB.remain_time);for(i=0;iPB.remain_time;printf(n進程按順序運行依次為:n);i=0;int k=0;for(t=0;t+)if(Run_Now)/如果當(dāng)前有進程正在執(zhí)行Run();if(t = Pi-PB.arrive_time)/如果當(dāng)前時間正好有進程進入if(Pi-PB.remain_time PB.r

10、emain_time)temp= Pi;Pi= Run_Now;Run_Now = temp;/則調(diào)度它至運行隊列中，Run_Now-PB.Tp=t;Run_Now-PB.Tc=t;wtRun_Now-PB.number-1+=Run_Now-PB.Tc-Run_Now-PB.Tp;printf(%d ,Run_Now-PB.number);EnQueue(PQ,Pi);/并將當(dāng)前運行進程重新插入隊列中Pi-PB.Tp=t;k+;i=(i+1)(N-1)?(N-1):(i+1);if(Run_Now-PB.remain_time = 0)/如果當(dāng)前進程運行結(jié)束，Run_Now-PB.To=t;

11、/進程運行結(jié)束的時間circle_tRun_Now-PB.number-1 +=t-Run_Now-PB.arrive_time;free(Run_Now);/則將它所占資源釋放掉，Run_Now =NULL;/并修改Run_Now為NULLRun_Now = ShortestProcess(PQ);/從就緒隊列中調(diào)出最短剩余時間進程至隊頭，if(!Run_Now)/如果隊列為空，轉(zhuǎn)為等待狀態(tài)if(IsEmpty(PQ) & k = N) break;Wait();continue;elseRun_Now-PB.Tc=t;wtRun_Now-PB.number-1+=Run_Now-PB.Tc

12、-Run_Now-PB.Tp;printf(%d ,Run_Now-PB.number);else/如果當(dāng)前運行進程為空，那么if(t = Pi-PB.arrive_time)/如果正好這時有進程入隊k+;EnQueue(PQ,Pi);Run_Now = DeQueue(PQ);/則直接被調(diào)入運行隊列中Run_Now-PB.Tp=t;Run_Now-PB.Tc=t;printf(%d ,Run_Now-PB.number);i=(i+1)(N-1)?(N-1):(i+1);elseWait();continue;printf(n);printf(平均等待時間是:n%fn,(float)sum(

13、wt,N)/N);printf(平均周轉(zhuǎn)時間是:n%fn,(float)sum(circle_t,N)/N);return 0;/【Process.cpp代碼如下：】#include#includeusing namespace std;class Processpublic:string ProcessName; / 進程名字 int Time; / 進程需要時間 int leval; / 進程優(yōu)先級 int LeftTime; / 進程運行一段時間后還需要的時間; void Copy ( Process proc1, Process proc2); / 把proc2賦值給proc1void

14、 Sort( Process pr, int size) ; / 此排序后按優(yōu)先級從大到小排列void sort1(Process pr, int size) ; / 此排序后按需要的cpu時間從小到大排列void Fcfs( Process pr, int num, int Timepice); / 先來先服務(wù)算法void TimeTurn( Process process, int num, int Timepice); / 時間片輪轉(zhuǎn)算法void Priority( Process process, int num, int Timepice); / 優(yōu)先級算法void main() i

15、nt a; coutendl; cout 選擇調(diào)度算法：endl; cout 1: FCFS 2: 時間片輪換 3: 優(yōu)先級調(diào)度 4: 最短作業(yè)優(yōu)先 5: 最短剩余時間優(yōu)先a; const int Size =30; Process processSize ; int num; int TimePice; cout 輸入進程個數(shù):num; cout 輸入此進程時間片大小: TimePice;for( int i=0; i num; i+) string name; int CpuTime; int Leval; cout 輸入第 i+1 個進程的名字、cpu時間和優(yōu)先級:name; cin C

16、puTimeLeval; processi.ProcessName =name; processi.Time =CpuTime; processi.leval =Leval; coutendl;for ( int k=0;knum;k+) processk.LeftTime=processk.Time ;/對進程剩余時間初始化 cout ( 說明: 在本程序所列進程信息中，優(yōu)先級一項是指進程運行后的優(yōu)先級! ); coutendl; coutendl; cout進程名字共需占用CPU時間 還需要占用時間 優(yōu)先級 狀態(tài)endl;if(a=1) Fcfs(process,num,TimePice)

17、;else if(a=2) TimeTurn( process, num, TimePice);else if(a=3) Sort( process, num); Priority( process , num, TimePice); else / 最短作業(yè)算法，先按時間從小到大排序，再調(diào)用Fcfs算法即可 sort1(process,num); Fcfs(process,num,TimePice); void Copy ( Process proc1, Process proc2) proc1.leval =proc2.leval ; proc1.ProcessName =proc2.Pro

18、cessName ; proc1.Time =proc2.Time ;void Sort( Process pr, int size) /以進程優(yōu)先級高低排序/ 直接插入排序 for( int i=1;i0 & temp.levalsize/2;d-) Process temp; temp=pr d; pr d = pr size-d-1; pr size-d-1=temp; / 此排序后按優(yōu)先級從大到小排列/* 最短作業(yè)優(yōu)先算法的實現(xiàn)*/void sort1 ( Process pr, int size) / 以進程時間從低到高排序/ 直接插入排序 for( int i=1;i0 & tem

19、p.Time prj-1.Time ) prj = prj-1; j-; prj = temp; /* 先來先服務(wù)算法的實現(xiàn)*/void Fcfs( Process process, int num, int Timepice) / process 是輸入的進程，num是進程的數(shù)目，Timepice是時間片大小while(true) if(num=0) cout 所有進程都已經(jīng)執(zhí)行完畢!endl; exit(1); if(process0.LeftTime=0) cout 進程process0.ProcessName 已經(jīng)執(zhí)行完畢!endl; for (int i=0;inum;i+) pro

20、cessi=processi+1; num-; else if(processnum-1.LeftTime=0) cout 進程processnum-1.ProcessName 已經(jīng)執(zhí)行完畢!endl; num-; else coutendl; /輸出正在運行的進程 process0.LeftTime=process0.LeftTime- Timepice; process0.leval =process0.leval-1; cout process0.ProcessName process0.Time ; coutprocess0.LeftTime process0.leval 運行; co

21、utendl; for(int s=1;snum;s+) cout processs.ProcessName processs.Time ; coutprocesss.LeftTime processs.leval 等待endl; ; / else coutendl; system( pause); coutendl; / while /* 時間片輪轉(zhuǎn)調(diào)度算法實現(xiàn)*/void TimeTurn( Process process, int num, int Timepice)while(true) if(num=0) cout 所有進程都已經(jīng)執(zhí)行完畢!endl; exit(1); if(proc

22、ess0.LeftTime=0) cout 進程process0.ProcessName 已經(jīng)執(zhí)行完畢!endl; for (int i=0;inum;i+) processi=processi+1; num-; if( processnum-1.LeftTime =0 ) cout 進程 processnum-1.ProcessName 已經(jīng)執(zhí)行完畢! 0) coutendl; /輸出正在運行的進程 process0.LeftTime=process0.LeftTime- Timepice; process0.leval =process0.leval-1; cout process0.Pr

23、ocessName process0.Time ; coutprocess0.LeftTime process0.leval 運行; coutendl; for(int s=1;snum;s+) cout processs.ProcessName processs.Time ; coutprocesss.LeftTime processs.leval; if(s=1) cout 就緒endl; else cout 等待endl; Process temp; temp = process0; for( int j=0;jnum;j+) processj = processj+1; processnum-1 = temp; / else coutendl; system( pause); coutendl; / while