實(shí)驗(yàn)三進(jìn)程調(diào)度

1、實(shí)驗(yàn)三進(jìn)程調(diào)度一實(shí)驗(yàn)?zāi)康募由罾斫獠⒛M實(shí)現(xiàn)進(jìn)程（作業(yè)）調(diào)度算法。1）熟悉常用的進(jìn)程調(diào)度算法，如FCFS、SPF、FPF、高響應(yīng)比優(yōu)先、時(shí)間片輪轉(zhuǎn)；2）結(jié)合所學(xué)的數(shù)據(jù)結(jié)構(gòu)及編程知識(shí)，選擇三種進(jìn)程調(diào)度算法予以實(shí)現(xiàn)。二實(shí)驗(yàn)屬性該實(shí)驗(yàn)為設(shè)計(jì)性實(shí)驗(yàn)。三實(shí)驗(yàn)儀器設(shè)備及器材普通PC386以上微機(jī)四實(shí)驗(yàn)要求1） 編程實(shí)現(xiàn)單處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度，要求從FCFS、SPF、FPF、高響應(yīng)比優(yōu)先、時(shí)間片輪轉(zhuǎn)算法中至少選擇三個(gè)；2） 最后編寫主函數(shù)對(duì)所做工作進(jìn)行測(cè)試。實(shí)驗(yàn)前應(yīng)復(fù)習(xí)實(shí)驗(yàn)中所涉及的理論知識(shí)和算法，針對(duì)實(shí)驗(yàn)要求完成基本代碼編寫并完成預(yù)習(xí)報(bào)告、實(shí)驗(yàn)中認(rèn)真調(diào)試所編代碼并進(jìn)行必要的測(cè)試、記錄并分析實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)后

2、認(rèn)真書寫符合規(guī)范格式的實(shí)驗(yàn)報(bào)告（參見附錄A），并要求用正規(guī)的實(shí)驗(yàn)報(bào)告紙和封面裝訂整齊，按時(shí)上交。五、需求分析1、1) 輸入的形式和輸入值的范圍輸入值：進(jìn)程個(gè)數(shù)Num 范圍：0<Num<=100 依次輸入Num個(gè)進(jìn)程的到達(dá)時(shí)間 范圍： 依次輸入Num個(gè)進(jìn)程的服務(wù)時(shí)間 范圍： 輸入要使用的算法（A-FCFS，B-SJF） 2) 程序所能達(dá)到的功能輸入進(jìn)程個(gè)數(shù)Num，每個(gè)進(jìn)程到達(dá)時(shí)間ArrivalTimei，服務(wù)時(shí)間ServiceTimei。采用先來(lái)先服務(wù)FCFS或者短作業(yè)優(yōu)先SJF進(jìn)程調(diào)度算法進(jìn)行調(diào)度，計(jì)算每個(gè)進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，并且統(tǒng)計(jì)Num個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間和

3、平均帶權(quán)周轉(zhuǎn)時(shí)間。2、高優(yōu)先權(quán)優(yōu)先調(diào)度算法1)輸入進(jìn)程數(shù)和進(jìn)程的優(yōu)先權(quán)要求服務(wù)時(shí)間后初始化隊(duì)列。2)W為等待狀態(tài)；R為運(yùn)行狀態(tài)。按照高優(yōu)先權(quán)優(yōu)先原則進(jìn)行進(jìn)程的調(diào)度和執(zhí)行。一步步完成進(jìn)程的調(diào)度和執(zhí)行。六、經(jīng)驗(yàn)和體會(huì)最高優(yōu)先權(quán)優(yōu)先（FPF）調(diào)度算法 此算法常被用在批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度，還可以用于實(shí)時(shí)系統(tǒng)中。當(dāng)其用于作業(yè)調(diào)度， 將后備隊(duì)列中若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)其用于進(jìn)程調(diào)度時(shí)，把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，可以進(jìn)一步把該算法分成以下兩種：非搶占式優(yōu)先權(quán)算法、搶占式優(yōu)先權(quán)調(diào)度算法。非搶占式優(yōu)先權(quán)算法是指一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先

4、權(quán)最高的進(jìn)城后，該進(jìn)程變一直執(zhí)行下去直到完成。這種調(diào)度算法主要用于批處理系統(tǒng)中，也可以用于某些對(duì)實(shí)時(shí)性要求不高的實(shí)時(shí)系統(tǒng)中；而搶占式優(yōu)先權(quán)算法系統(tǒng)將處理機(jī)分配給優(yōu)先權(quán)最高點(diǎn)的進(jìn)程，并執(zhí)行但當(dāng)在執(zhí)行期間遇到另外一個(gè)優(yōu)先權(quán)更高的程序的時(shí)候就會(huì)將處理機(jī)的使用權(quán)給這個(gè)優(yōu)先權(quán)比較高的進(jìn)程，這種調(diào)度算法能夠更好的滿足緊迫作業(yè)的要求，常用在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)找中。通過本次實(shí)驗(yàn)我們深入理解了先來(lái)先服務(wù)和短進(jìn)程優(yōu)先進(jìn)程調(diào)度算法的思想,學(xué)會(huì)高優(yōu)先權(quán)調(diào)度算法的原理和調(diào)度過程、還要能夠熟練運(yùn)用。七、源程序 1、FCFS、SPF#include<iostream>

5、#include<iomanip>using namespace std;static const int Max=100;int ArrivalTimeMax;/到達(dá)時(shí)間int ServiceTimeMax;/服務(wù)時(shí)間int FinishTimeMax;/完成時(shí)間int WholeTimeMax;/周轉(zhuǎn)時(shí)間double WeightWholeTimeMax;/帯權(quán)周莊時(shí)間double AverageWT_FCFS,AverageWT_SJF; /平均周轉(zhuǎn)時(shí)間double AverageWWT_FCFS,AverageWWT_SJF;/平均帯權(quán)周轉(zhuǎn)時(shí)間int ServiceTime

6、_SJFMax;/在SJF算法中使用到int Num=0;int NowTime=0;/記錄當(dāng)前時(shí)間double SumWT=0,SumWWT=0;/SumWT用來(lái)計(jì)算總的周轉(zhuǎn)時(shí)間，SumWWT用來(lái)計(jì)算總的帯權(quán)周轉(zhuǎn)時(shí)間int i;int choice;/記錄選擇 / 先到先服務(wù)算法void FCFS()/找最早到達(dá)的。cout<<"-FCFS-"<<endl;for(i=0;i<Num;i+)if(ArrivalTimei>NowTime)/假如進(jìn)程到達(dá)的時(shí)間比現(xiàn)在已經(jīng)運(yùn)行的時(shí)間NowTime大，說明在NowTime時(shí)刻進(jìn)程未到達(dá) Now

7、Time=ArrivalTimei;/把進(jìn)程的到達(dá)時(shí)間賦給NowTimeNowTime+=ServiceTimei;/把進(jìn)程的服務(wù)時(shí)間加到NowTime上FinishTimei=NowTime;/計(jì)算完成時(shí)間WholeTimei=FinishTimei-ArrivalTimei;/計(jì)算周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間WeightWholeTimei=(double)WholeTimei/ServiceTimei;/計(jì)算帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間SumWT+=WholeTimei;/計(jì)算總的周轉(zhuǎn)時(shí)間SumWWT+=WeightWholeTimei;/計(jì)算總的帯權(quán)周轉(zhuǎn)時(shí)間AverageWT_FC

8、FS=SumWT/Num;/平均周轉(zhuǎn)時(shí)間AverageWWT_FCFS=SumWWT/Num;/平均帯權(quán)周轉(zhuǎn)時(shí)間for(i=0;i<Num;i+)/依次輸出結(jié)果cout<<"時(shí)刻"<<FinishTimei-ServiceTimei<<": 進(jìn)程"<<i+1<<"開始運(yùn)行。"<<" 其完成時(shí)間："<<FinishTimei<<" 周轉(zhuǎn)時(shí)間："<<WholeTimei<<s

9、etprecision(3)<<" 帯權(quán)周轉(zhuǎn)時(shí)間："<<WeightWholeTimei<<setprecision(3)<<endl;cout<<"平均周轉(zhuǎn)時(shí)間："<<AverageWT_FCFS<<endl;cout<<"平均帯權(quán)周轉(zhuǎn)時(shí)間："<<AverageWWT_FCFS<<endl; / 短進(jìn)程優(yōu)先算法void SJF()/找已經(jīng)到達(dá)的且服務(wù)時(shí)間最短的進(jìn)程（假定輸入的進(jìn)程是按照到達(dá)時(shí)間先后輸入的）cout&

10、lt;<"-SJF-"<<endl;int min=0;NowTime=ArrivalTime0+ServiceTime0;/計(jì)算第一次的NowTImeFinishTime0=NowTime;/計(jì)算第一個(gè)進(jìn)程的完成時(shí)間ServiceTime_SJF0=1000;/賦初值。cout<<"時(shí)刻"<<FinishTime0-ServiceTime0<<": 進(jìn)程"<<1<<"開始運(yùn)行。"int allin=0,j,k;for(i=1;i<

11、Num;i+)/進(jìn)入循環(huán)，從第二個(gè)到達(dá)的進(jìn)程開始k=1;min=0;if(allin=0)/找到已經(jīng)到達(dá)的進(jìn)程個(gè)數(shù)j=0;while(ArrivalTimej<=NowTime && j<Num)/已經(jīng)到達(dá)的進(jìn)程j+;if(j>=Num)allin=1;else j=Num;j=j-1;/j是已經(jīng)到達(dá)的進(jìn)程數(shù)while(k<=j)/從已經(jīng)到達(dá)的進(jìn)程里找到服務(wù)時(shí)間最短的進(jìn)程if(ServiceTime_SJFk=0)/進(jìn)程的服務(wù)時(shí)間如果等于0，則跳過該進(jìn)程k+;else if(ServiceTime_SJFmin>ServiceTime_SJFk)/

12、比較，找到服務(wù)時(shí)間最短的進(jìn)程min=k;k+;ServiceTime_SJFmin=0;/找完后置零，便于下一次循環(huán)時(shí)使用NowTime+=ServiceTimemin;/累加當(dāng)前時(shí)間FinishTimemin=NowTime;/完成時(shí)間for(i=0;i<Num;i+)/計(jì)算周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間，總的周轉(zhuǎn)時(shí)間和總的帶權(quán)周轉(zhuǎn)時(shí)間WholeTimei=FinishTimei-ArrivalTimei;WeightWholeTimei=(double)WholeTimei/ServiceTimei;SumWT+=WholeTimei;SumWWT+=WeightWholeTimei;Ave

13、rageWT_SJF=SumWT/Num;/平均周轉(zhuǎn)時(shí)間AverageWWT_SJF=SumWWT/Num;/平均帶權(quán)周轉(zhuǎn)時(shí)間cout<<" 其完成時(shí)間："<<FinishTime0<<" 周轉(zhuǎn)時(shí)間："<<WholeTime0<<setprecision(3)<<" 帯權(quán)周轉(zhuǎn)時(shí)間："<<WeightWholeTime0<<setprecision(3)<<endl;for(i=1;i<Num;i+)/輸出結(jié)果cout<

14、;<"時(shí)刻"<<FinishTimei-ServiceTimei<<": 進(jìn)程"<<i+1<<"開始運(yùn)行。"<<" 其完成時(shí)間："<<FinishTimei<<" 周轉(zhuǎn)時(shí)間："<<WholeTimei<<setprecision(3)<<" 帯權(quán)周轉(zhuǎn)時(shí)間："<<WeightWholeTimei<<setprecision(3)&

15、lt;<endl;cout<<"平均周轉(zhuǎn)時(shí)間："<<AverageWT_SJF<<endl;cout<<"平均帯權(quán)周轉(zhuǎn)時(shí)間："<<AverageWWT_SJF<<endl;void input() / 輸入函數(shù)cout<<"請(qǐng)輸入進(jìn)程個(gè)數(shù)："cin>>Num;while(Num>100|Num<=0)cout<<"進(jìn)程個(gè)數(shù)必須大于0且小于等于100！請(qǐng)重新輸入進(jìn)程個(gè)數(shù)："cin>>

16、;Num;for(i=0;i<Num;i+)cout<<"第"<<i+1<<"個(gè)進(jìn)程的到達(dá)時(shí)間："cin>>ArrivalTimei;for(i=0;i<Num;i+)int data=0;cout<<"第"<<i+1<<"個(gè)進(jìn)程的服務(wù)時(shí)間："cin>>data;ServiceTimei=data;ServiceTime_SJFi=data;cout<<"-"<<e

17、ndl;cout<<"請(qǐng)選擇要使用的算法(1-FCFS,2-SJF): "cin>>choice;void main()char flag='y'Loop:NowTime=0;SumWT=0;SumWWT=0;/參數(shù)初始化 input();/輸入if(choice=1)FCFS();/調(diào)用FCFS算法else if(choice=2)SJF();/調(diào)用SJF算法else/輸入有誤，則重新選擇while(1) cout<<"您的選擇有誤!請(qǐng)重新選擇!"<<endl;cout<<&q

18、uot;請(qǐng)選擇要使用的算法(1-FCFS,2-SJF): "cin>>choice;if(choice=1)FCFS();break;else if(choice=2)SJF();break;cout<<endl<<"是否繼續(xù)使用該程序，按'y'或'Y'鍵繼續(xù)，按其他任意鍵退出："cin>>flag;if(flag='y' | flag='Y')goto Loop;2、高優(yōu)先權(quán)優(yōu)先調(diào)度算法#include "stdio.h" #inc

19、lude "stdlib.h" #define getpch(type) new typestruct pcb /* 定義進(jìn)程控制塊PCB */ char name10; /進(jìn)程名 char state; /狀態(tài) int super; /優(yōu)先級(jí) int ntime; /要求服務(wù)時(shí)間 int rtime; /已運(yùn)行時(shí)間 struct pcb* next; *ready=NULL,*p;typedef struct pcb PCB;void sort(PCB *a) /* 建立對(duì)進(jìn)程進(jìn)行優(yōu)先級(jí)排列函數(shù)*/ PCB *first, *second; int insert=0; i

20、f(ready=NULL)|(a->super)>(ready->super) /*優(yōu)先級(jí)最大者,插入隊(duì)首*/ a->next=ready; ready=a; else /* 進(jìn)程比較優(yōu)先級(jí),插入適當(dāng)?shù)奈恢弥?/ first=ready; second=first->next; while(second!=NULL) if(a->super)>(second->super) /*若插入進(jìn)程比當(dāng)前進(jìn)程優(yōu)先數(shù)大,插入到當(dāng)前進(jìn)程前面*/a->next=second; first->next=a; second=NULL; insert=1;

21、 else /*指針后移，尋找插入點(diǎn)*/ first=first->next; second=second->next; if(insert=0) first->next=a;/* 插入進(jìn)程優(yōu)先數(shù)最低,則插入到隊(duì)尾*/ void createpcb() /* 建立進(jìn)程控制塊函數(shù)*/ int i,num; printf("ttt最高優(yōu)先權(quán)優(yōu)先調(diào)度算法模擬tn"); printf("n 請(qǐng)輸入進(jìn)程數(shù)目:"); scanf("%d",&num); for(i=0;i<num;i+) p=getpch(PCB)

22、; printf("n 第%d個(gè)進(jìn)程的名字、優(yōu)先數(shù)及該進(jìn)程要求服務(wù)的時(shí)間:",i+1); scanf("%s%d%d",p->name,&p->super,&p->ntime); p->rtime=0; p->state='w' p->next=NULL; sort(p); void display1() /*建立進(jìn)程顯示函數(shù),用于顯示當(dāng)前進(jìn)程*/ printf("n進(jìn)程名 狀態(tài) 優(yōu)先數(shù) 要求服務(wù)的時(shí)間 已運(yùn)行時(shí)間 n"); void display2(PCB * p

23、r) printf("%3.5s %7c %6d %12d %10d",pr->name,pr->state,pr->super,pr->ntime,pr->rtime); printf("n"); void check() /* 建立進(jìn)程查看函數(shù) */ PCB *pr; printf("n"); printf("n");printf("n * 當(dāng)前正在運(yùn)行的進(jìn)程是%s的狀態(tài)如下:n",p->name); display1(); display2(p); pr=read