作業(yè)調(diào)度實(shí)驗(yàn)報(bào)告

1、一、實(shí)驗(yàn)名稱(chēng)作業(yè)調(diào)度算法實(shí)驗(yàn)。二、實(shí)驗(yàn)?zāi)繕?biāo)已知 n 個(gè)作業(yè)的進(jìn)入時(shí)間和估計(jì)運(yùn)行時(shí)間（以分鐘計(jì)）（1 ）單道環(huán)境下，分別用先來(lái)先服務(wù)調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法、響應(yīng)比高者優(yōu)先調(diào)度算法，求出批作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間； 在多道環(huán)境（如 2 道）下，求出這些作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間（2 ）就同一批次作業(yè)，分別討論這些算法的優(yōu)劣；（3 ）衡量同一調(diào)度算法對(duì)不同作業(yè)流的性能。三、實(shí)驗(yàn)環(huán)境要求1.PC 機(jī)。2.Windows環(huán)境。3.CodeBlocks四、實(shí)驗(yàn)基本原理（ 1 ）先來(lái)先服務(wù)算法： 按照作業(yè)提交給系統(tǒng)的先后順序來(lái)挑選作業(yè)，先提交的先被挑選。（ 2 ）最短作業(yè)優(yōu)先算法

2、：是以進(jìn)入系統(tǒng)的作業(yè)所提出的“執(zhí)行時(shí)間”為標(biāo)準(zhǔn)，總是優(yōu)先選取執(zhí)行時(shí)間最短的作業(yè)。（ 3 ）響應(yīng)比高者優(yōu)先算法：是在每次調(diào)度前都要計(jì)算所有被選作業(yè)（在后備隊(duì)列中）的響應(yīng)比，然后選擇響應(yīng)比最高的作業(yè)執(zhí)行。（4 ）兩道批處理系統(tǒng)中最短作業(yè)優(yōu)先調(diào)度算法：內(nèi)存中可以進(jìn)入兩個(gè)作業(yè)，這兩個(gè)作業(yè)按照最短作業(yè)優(yōu)先調(diào)度算法調(diào)整作業(yè)執(zhí)行的次序。五、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)使用一維數(shù)組來(lái)保存多個(gè)作業(yè)Job job20;，采用的是順序存儲(chǔ)。使用 queue<Jcb *> q保存調(diào)度隊(duì)列里的作業(yè)指針。struct Date/時(shí)間結(jié)構(gòu)體int hour;/時(shí)間的小時(shí)int minute;/時(shí)間的分鐘;struct Jcb/

3、作業(yè)結(jié)構(gòu)體，用來(lái)描述作業(yè)int no;/作業(yè)編號(hào)Date enter;/進(jìn)入時(shí)間int operation;/估計(jì)運(yùn)行時(shí)間Date start;/開(kāi)始時(shí)間Date over;/結(jié)束時(shí)間intturnover;/周轉(zhuǎn)時(shí)間double weighted;/帶權(quán)周轉(zhuǎn)時(shí)間int state=0;/標(biāo)記改作業(yè)是否進(jìn)入運(yùn)行狀態(tài);六、流程圖單道環(huán)境下算法流程圖先來(lái)先服務(wù)調(diào)度開(kāi)始最高響應(yīng)比優(yōu)先服務(wù)最短作業(yè)優(yōu)先服務(wù)將JCB 按作業(yè)提交的時(shí)刻的先后順序排隊(duì)No將作業(yè)一入調(diào)度隊(duì)列，不斷從就緒隊(duì)列中選擇 state=0，且處理時(shí)間最短的作業(yè)放入調(diào)度隊(duì)列中，直到所有作業(yè)都進(jìn)入調(diào)度隊(duì)列調(diào)用 runing 函數(shù)處理調(diào)度隊(duì)列

4、作業(yè)調(diào)度隊(duì)首的作業(yè)投入運(yùn)行調(diào)度隊(duì)列為空？Yes調(diào)用 display函數(shù)，計(jì)算這組作業(yè)的平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間，并作業(yè)處理輸出結(jié)果不斷從就緒隊(duì)列中選擇 state=0，且響應(yīng)比最高的作業(yè)放入到調(diào)度隊(duì)列中，直到所有作業(yè)都進(jìn)入調(diào)度隊(duì)列。結(jié)束多道環(huán)境下的兩道批處理系統(tǒng)中最短作業(yè)優(yōu)先作業(yè)調(diào)度算法的流程圖。開(kāi)始初始化作業(yè)在內(nèi)存中停留時(shí)間數(shù)組 op, 是每個(gè)作業(yè)的停留時(shí)間設(shè)為將要運(yùn)行的時(shí)間，即opi=Ji.operation.將最先進(jìn)入的 2個(gè)作業(yè)調(diào)入到內(nèi)存，work1=0,work2=1; 并改變標(biāo)記狀態(tài) state=1，作業(yè)處理個(gè)數(shù)記為t=2作業(yè)總數(shù) n>=t?No處理 work1YesWor

5、k1 的預(yù)計(jì)運(yùn)行時(shí)間計(jì)算平均周轉(zhuǎn)時(shí)間和平均<work2 的預(yù)計(jì)運(yùn)行時(shí)帶權(quán)周轉(zhuǎn)時(shí)間， 輸出作間？業(yè)處理后的結(jié)果。YesNo結(jié)束處理work1 ，處理 work2 ，work1=work2,Opwork1+=opwork2.Work2=-1,Work2=-1,從剩余到達(dá)的作業(yè)中選出預(yù)計(jì)處理時(shí)間最短的作業(yè) i ,t+,work2=i七、源代碼#include<iostream>#include<stdio.h>#include<cstring>#include<algorithm>#include<queue>using namesp

6、ace std;struct Date/時(shí)間結(jié)構(gòu)體int hour;/時(shí)間的小時(shí)int minute;/時(shí)間的分鐘;struct Jcb/作業(yè)結(jié)構(gòu)體，用來(lái)描述作業(yè)int no;/作業(yè)編號(hào)Date enter;/進(jìn)入時(shí)間int operation;/估計(jì)運(yùn)行時(shí)間Date start;/開(kāi)始時(shí)間Date over;/結(jié)束時(shí)間intturnover;/周轉(zhuǎn)時(shí)間double weighted;/帶權(quán)周轉(zhuǎn)時(shí)間int state=0;/標(biāo)記改作業(yè)是否進(jìn)入運(yùn)行狀態(tài);/ 函數(shù)聲明void display(Jcb J,int n);/輸出void runing( queue<Jcb *> q,int

7、 n);/根據(jù)算法將就緒隊(duì)列排好隊(duì)后的單道作業(yè)的運(yùn)行主體void fcfs( Jcb J,int n);/先來(lái)先服務(wù)作業(yè)調(diào)度void sfc(Jcb J,int n);/最短作業(yè)優(yōu)先作業(yè)調(diào)度void hrfc(Jcb J,int n);/最高響應(yīng)比作業(yè)調(diào)度void text(void (*dispatch)(JcbJ,int n),Jcb J,int n,JcbJ1,int n1, Jcb J2,int n2);/測(cè)試單道環(huán)境，不同批次作業(yè)，相同算法void mulfc(Jcb J,int n);/兩道環(huán)境，內(nèi)存中可以用兩個(gè)作業(yè)，內(nèi)存中的這兩個(gè)作業(yè)按照作業(yè)長(zhǎng)短調(diào)整作業(yè)執(zhí)行的次序。/ 主函數(shù)，（

8、 1 ）同一批次作業(yè)，分別用先來(lái)先服務(wù)調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法、 響應(yīng)比高者優(yōu)先調(diào)度算法， 得到批作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間； （2 ）同一調(diào)度算法對(duì)不同作業(yè)流的調(diào)度。int main()int n,n1,n2;Jcb job20,job120,job220;FILE*p=fopen("example1.txt", "r");fscanf(p, "%d", &n);/ 批次一作業(yè)for(int i=0;i<n;i+)jobi.no=i+1;fscanf(p, "%d%d%d", &

9、;jobi.enter.hour, &jobi.enter.minute, &jobi.operation);/ 批次二作業(yè)fscanf(p, "%d", &n1);for(int i=0;i<n1;i+)job1i.no=i+1;fscanf(p, "%d%d%d", &job1i.enter.hour, &job1i.enter.minute, &job1i.operation);/ 批次三作業(yè)fscanf(p, "%d", &n2);for(int i=0;i<

10、n2;i+)job2i.no=i+1;fscanf(p, "%d%d%d", &job2i.enter.hour, &job2i.enter.minute, &job2i.operation);fclose(p);printf("n-單道環(huán)境, 同一批次作業(yè),不同算法-n");cout<<" 先來(lái)先服務(wù)作業(yè)調(diào)度： "<<endl;fcfs(job,n);cout<<" 最短時(shí)間優(yōu)先服務(wù)作業(yè)調(diào)度："<<endl;sfc(job,n);cout&l

11、t;<" 最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法"<<endl;hrfc(job,n);printf("nn");printf("-單道環(huán)境，不同批次作業(yè)，同一算法-n");cout<<".先來(lái)先服務(wù)作業(yè)調(diào)度."<<endl;text(fcfs, job,n,job1,n1,job2,n2);cout<<".最短優(yōu)先服務(wù)作業(yè)調(diào)度."<<endl;text(sfc, job,n,job1,n1,job2,n2);cout<<&quo

12、t;.最高響應(yīng)比優(yōu)先服務(wù)作業(yè)調(diào)度:."<<endl;text(hrfc, job,n,job1,n1,job2,n2);printf("-兩道環(huán)境-n");mulfc(job1,n);printf("-n");return 0;/ 單道環(huán)境，不同批次作業(yè)，同一算法voidtext(void(*dispatch)(JcbJ,intn),JcbJ,intn,JcbJ1,int n1, Jcb J2,int n2)/ 單道環(huán)境，不同批次作業(yè)，同一算法cout<<" 批次一作業(yè) :"<<endl;

13、dispatch(J,n);cout<<" 批次二作業(yè) :"<<endl;dispatch(J1,n1);cout<<" 批次三作業(yè) :"<<endl;dispatch(J2,n2);/ 輸出void display(Jcb J,int n)double T=0,W=0;printf(" 作業(yè) 進(jìn)入時(shí)間 估計(jì)運(yùn)行時(shí)間 (分鐘 ) 開(kāi)始時(shí)間 結(jié)束時(shí)間 周轉(zhuǎn)時(shí)間 (分鐘 ) 帶權(quán)周轉(zhuǎn)時(shí)間 n");for(int i=0;i<n;i+)Ji.turnover=(Ji.over.hour*

14、60 + Ji.over.minute)-(Ji.enter.hour*60+Ji.enter.minute);T+=Ji.turnover;Ji.weighted=Ji.turnover/(double)Ji.operation;W+=Ji.weighted;printf("Job%2dt %2d:%02dt %-14dt %2d:%02dt%2d:%02dt%-6dt%-5.2ftn",Ji.no,Ji.enter.hour,Ji.enter.minute,Ji.operation,Ji.start.hour,Ji.start.minute,Ji.over.hour,

15、Ji.over.minute, Ji.turnover,Ji.weighted );T/=n;W/=n;printf(" 作業(yè)平均周轉(zhuǎn)時(shí)間T=%.2lf分鐘 n", T);printf(" 作業(yè)帶權(quán)平均周轉(zhuǎn)時(shí)間W=%.3lfnnn",W);/ 根據(jù)算法將就緒隊(duì)列排好隊(duì)后的單道作業(yè)的運(yùn)行主體void runing( queue<Jcb *> q,int n)Jcb *j;int h,m;j=q.front();h=j->enter.hour;m=j->enter.minute;while (!q.empty()j=q.front()

16、;q.pop();j->start.hour=h;j->start.minute=m;j->over.hour=j->start.hour+(j->start.minute+j->operation)/6 0;j->over.minute=(j->start.minute+j->operation)%60;j->turnover=(j->over.hour*60+j->over.minute)-(j->enter.hour*60+j->enter.minute);j->weighted=j->tur

17、nover/(double)j->operation;h=j->over.hour;m=j->over.minute;/ display(J,t);/ 最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法void hrfc(Jcb J,int n)/最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法queue<Jcb *> qjob;int flag20;for(int j=0;j<n;j+)flagj=0;qjob.push(&J0);doublewait=J0.operation+J0.enter.hour*60+J0.enter.minute;/記錄作業(yè)流已經(jīng)執(zhí)行的時(shí)間int t=n-1;fl

18、ag0=1;while(t)int i=1;while(flagi)i+;for(int j=i; j<n ;j+)if(Jj.enter.hour*60+Jj.enter.minute)>wait)break;/如果這個(gè)作業(yè)還沒(méi)來(lái)到，則停止繼續(xù)比較 ,只考慮已經(jīng)進(jìn)入就緒隊(duì)列的作業(yè)if(flagj=0 )doublewaiti=wait-Ji.enter.hour*60-Ji.enter.minute;/作業(yè)Ji 的等待時(shí)間doublewaitj=wait-Jj.enter.hour*60-Jj.enter.minute;if(waiti/Ji.operation)<(wai

19、tj/Jj.operation)i=j;qjob.push(&Ji);flagi=1;wait+=Ji.operation;t-;runing(qjob,n);display(J,n);void fcfs( Jcb J,int n)/先來(lái)先服務(wù)作業(yè)調(diào)度算法queue<Jcb *> qjob;for(int i=0;i<n;i+)qjob.push(&Ji);runing(qjob,n);display(J,n);/ 最短作業(yè)優(yōu)先作業(yè)調(diào)度算法void sfc(Jcb J,int n)/最短作業(yè)優(yōu)先作業(yè)調(diào)度算法queue<Jcb *> qjob;qjo

20、b.push(&J0);inttime=J0.enter.hour*60+J0.enter.minute+J0.operation;/ 上一個(gè)作業(yè)的結(jié)束時(shí)間J0.state=1;int t=n-1;while(t)int i=1;while(Ji.state)i+;for(int j=i;j<n;j+)if(Jj.enter.hour*60+Jj.enter.minute)>time)break;/如果這個(gè)作業(yè)還沒(méi)來(lái)到，則停止繼續(xù)比較 ,只考慮已經(jīng)進(jìn)入就緒隊(duì)列的作業(yè)if(Jj.state=0 && (Ji.operation>Jj.operation)

21、i=j;qjob.push(&Ji);Ji.state=1;time+=Ji.operation;t-;runing(qjob,n);display(J,n);/ 兩道環(huán)境，內(nèi)存中可以用兩個(gè)作業(yè)，內(nèi)存中的這兩個(gè)作業(yè)按照作業(yè)void mulfc(Jcb J,int n)/兩道環(huán)境，內(nèi)存中可以用兩個(gè)作業(yè)，內(nèi)存中的這兩個(gè)作業(yè)按照作業(yè)長(zhǎng)短調(diào)整作業(yè)執(zhí)行的次序。/ 至少有兩個(gè)作業(yè)。cout<<"兩 道 批 處 理 系統(tǒng) 中 最 短 作業(yè) 優(yōu) 先 作 業(yè) 調(diào)度 算 法"<<endl;int op20;inti,work1=-1,work2=-1;/work

22、1是先開(kāi)始執(zhí)行的作業(yè)，work2是后來(lái)進(jìn)入內(nèi)存的作業(yè)for(i=0;i<n;i+)opi=Ji.operation;Ji.state=0;work1=0;J0.state=1;J0.start.hour=J0.enter.hour;J0.start.minute=J0.enter.minute;work2=1;int h=J0.enter.hour;int m=J0.enter.minute;int work=work1;int time;int t=2;while(t<=n)if(Jwork1.operation>Jwork2.operation)/第二個(gè) work2進(jìn)入內(nèi)

23、存的作業(yè)的執(zhí)行時(shí)間短于work1 ，就暫停執(zhí)行 work1, 轉(zhuǎn)而執(zhí)行 work2.opwork1+=Jwork2.operation;if(t=2)/第二個(gè)進(jìn)入內(nèi)存的， 且運(yùn)行時(shí)間較已在內(nèi)存中的短，則作業(yè)開(kāi)始時(shí)間為進(jìn)入的時(shí)間Jwork2.start.hour=Jwork2.enter.hour;Jwork2.start.minute=Jwork2.enter.minute;else/從第三個(gè)進(jìn)入內(nèi)存的作業(yè)，且執(zhí)行時(shí)間比當(dāng)前在內(nèi)存中的執(zhí)行時(shí)間短，則開(kāi)始時(shí)間為上一個(gè)作業(yè)的結(jié)束時(shí)間Jwork2.start.hour=h;Jwork2.start.minute=m;Jwork2.over.hour=

24、Jwork2.start.hour+(Jwork2.start.minute+opwork2)/60;Jwork2.over.minute=(Jwork2.start.minute+opwork2)%60;h=Jwork2.over.hour;m=Jwork2.over.minute;time=h*60+m;work2=-1;/改作業(yè)執(zhí)行完畢else/第二個(gè) work2進(jìn)入內(nèi)存的作業(yè)的執(zhí)行時(shí)間較長(zhǎng)， 所以仍然執(zhí)行開(kāi)始就在內(nèi)存的作業(yè)work1, 知道 work1執(zhí)行完畢Jwork1.over.hour=Jwork1.start.hour+(Jwork1.start.minute+opwork1)

25、/60;Jwork1.over.minute=(Jwork1.start.minute+opwork1)%60;h=Jwork2.over.hour;m=Jwork2.over.minute;time=h*60+m;Jwork2.start.hour=h;Jwork2.start.minute=m;work1=work2;work2=-1;int w;int i=1;while(Ji.state=1)i+;w=i;for(int j=w; j<n;j+)if(Jj.enter.hour*60+Jj.enter.minute)>time)break;/如果這個(gè)作業(yè)還沒(méi)來(lái)到，則停止繼續(xù)

26、比較 ,只考慮已經(jīng)進(jìn)入就緒隊(duì)列的作業(yè)if(Jj.state=0 && (Jw.operation > Jj.operation)w=j;work2=w;/第二個(gè)進(jìn)入內(nèi)存的作業(yè)t+;Jwork2.state=1;/ 最后剩下 work1 作業(yè)Jwork1.over.hour=Jwork1.start.hour+(Jwork1.start.minute+opwork1)/60;Jwork1.over.minute=(Jwork1.start.minute+opwork1)%60;display(J,n);八、實(shí)驗(yàn)結(jié)果（1 ）在單道環(huán)境下，已知n 個(gè)作業(yè)的進(jìn)入時(shí)間和估計(jì)運(yùn)行時(shí)間

27、（以分鐘計(jì)），得到的每一個(gè)作業(yè)的開(kāi)始時(shí)間、結(jié)束時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間，以及這些作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間；（ 2 ）同一調(diào)度算法對(duì)不同作業(yè)流的性能，每個(gè)算法有三個(gè)測(cè)試作業(yè)流先來(lái)先服務(wù)作業(yè)調(diào)度最短優(yōu)先服務(wù)作業(yè)調(diào)度最高響應(yīng)比優(yōu)先服務(wù)作業(yè)調(diào)度（ 3 ）在 2 道環(huán)境下，已知 n 個(gè)作業(yè)的進(jìn)入時(shí)間和估計(jì)運(yùn)行時(shí)間（以分鐘計(jì)），得到的每一個(gè)作業(yè)的開(kāi)始時(shí)間、結(jié)束時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間，以及這些作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。九、結(jié)果分析（1 ）單道環(huán)境下，對(duì)于批次一作業(yè)流。先來(lái)先服務(wù)的作業(yè)調(diào)度的作業(yè)平均周轉(zhuǎn)時(shí)間 T=112.5 分鐘最短作業(yè)優(yōu)先服務(wù)作業(yè)調(diào)度的作業(yè)平均周轉(zhuǎn)時(shí)間 T=90 分鐘最高相應(yīng)比優(yōu)先服務(wù)作業(yè)調(diào)度的作業(yè)平均周轉(zhuǎn)時(shí)間T=102.5分鐘 .可見(jiàn)對(duì)于批次一作業(yè)，最短作業(yè)優(yōu)先作業(yè)調(diào)度算法效率最高。（2 ）單道環(huán)境下。2