一、實驗目的

1、?對作業(yè)調(diào)度的相關內(nèi)容作進一步的理解。

2、?明白作業(yè)調(diào)度的主要任務。

3、?通過編程掌握作業(yè)調(diào)度的主要算法。

二、實驗內(nèi)容及要求

1、對于給定的一組作業(yè), 給出其到達時間和運行時間，例如下表所示：

2、分別用先來先服務算法、短作業(yè)優(yōu)先和響應比高者優(yōu)先三種算法給出作業(yè)的調(diào)度順序。

3、計算每一種算法的平均周轉(zhuǎn)時間及平均帶權(quán)周轉(zhuǎn)時間并比較不同算法的優(yōu)劣。

?

三、實驗過程

1、程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明

進程結(jié)構(gòu)體

{‘作業(yè)名’:’A’,’到達時間’:0,’服務時間’:6,’結(jié)束時間’:0,’周轉(zhuǎn)時間’:0,’帶權(quán)周轉(zhuǎn)時間’:0}

2、實驗程序：

#include<iostream>

using namespace std;

struct works

{

char name;//作業(yè)名

double ctime;//到達時間

double stime;//服務時間

double ftime;//完成時間

double ztime;//周轉(zhuǎn)時間

double dtime;//帶權(quán)周轉(zhuǎn)時間

double wtime;//等待時間

double rratio;//響應比

};

double sumztime,sumdtime;

double avgztime,avgdtime;

void input(works *p,int n);//輸入

void output(works *p,int n);//輸出

void datap(works *p,int n);//數(shù)據(jù)處理

void sort(works *p,int n);//按到達時間排序

void fcfs(works *p,int n);//先來先服務

void sjf(works *p,int n);//短作業(yè)優(yōu)先

void hrf(works *p,int n);//高響應比優(yōu)先

?

int main()

{

int n;

cout<<"輸入作業(yè)數(shù)目: ";

cin>>n;

works *a=new works[n];

input(a,n);

fcfs(a,n);

cout<<"\n";

sjf(a,n);

cout<<"\n";

hrf(a,n);

delete a;

return 0;

}

void input(works *p,int n)

{

cout<<"請輸入作業(yè)信息: "<<endl<<endl;

for(int i=0;i<n;i++)

{

cout<<"作業(yè)名: ";

cin>>p[i].name ;

cout<<"到達時間: ";

cin>>p[i].ctime ;

cout<<"服務時間: ";

cin>>p[i].stime ;

cout<<"\n";

}

?

}

?

void datap(works *p,int n)

{

sumztime=sumdtime=0;

p[0].ftime =p[0].ctime +p[0].stime ;

for(int i=1;i<n;i++)

{

p[i].ftime=p[i-1].ftime+p[i].stime;

}

for(int j=0;j<n;j++)

{

p[j].ztime =p[j].ftime -p[j].ctime ;

p[j].dtime =p[j].ztime /p[j].stime ;

sumztime+=p[j].ztime;

sumdtime+=p[j].dtime;

}

avgztime=sumztime/n;

avgdtime=sumdtime/n;

}

?

void output(works *p,int n)

{

cout<<"作業(yè)調(diào)度順序: ";

for(int k=0;k<n;k++)

{

cout<<p[k].name ?<<" ";

}

cout<<"\n";

cout<<"平均周轉(zhuǎn)時間="<<avgztime<<endl;

cout<<"平均帶權(quán)周轉(zhuǎn)時間="<<avgdtime<<endl;

}

?

void sort(works *p,int n)

{

for(int i=n-1;i>=1;i--)

for(int j=0;j<i;j++)

if(p[j].ctime >p[j+1].ctime )

{

works temp;

temp=p[j];

p[j]=p[j+1];

p[j+1]=temp;

}

}

?

void fcfs(works *p,int n)

{

sort(p,n);

datap(p,n);

cout<<"先來先服務算法"<<endl;

output(p,n);

?

}

?

void sjf(works *p,int n)

{

sort(p,n);

for(int i=0;i<n-1;i++)

{

int k=0;

if(i==0)

p[i].ftime =p[i].ctime +p[i].stime ;

else

p[i].ftime =p[i].stime +p[i-1].ftime ;

for(int j=i+1;j<n;j++)

{

if(p[j].ctime<=p[i].ftime )

k++;

}

double minstime=p[i+1].stime ;

int ps=i+1;

for(int m=i+1;m<i+k;m++)

{

if(p[m+1].stime <minstime)

{

minstime=p[m+1].stime ;

ps=m+1;

}

}

works temp;

temp=p[i+1];

p[i+1]=p[ps];

p[ps]=temp;

}

datap(p,n);

cout<<"短作業(yè)優(yōu)先算法: "<<endl;

output(p,n);

}

?

void hrf(works *p,int n)

{

sort(p,n);

for(int i=0;i<n-1;i++)

{

int k=0;

if(i==0)

p[i].ftime =p[i].ctime +p[i].stime ;

?

else

p[i].ftime =p[i].stime +p[i-1].ftime ;

for(int j=i+1;j<n;j++)

{

if(p[j].ctime <=p[i].ftime )

k++;

}

double maxrratio=(p[i].ftime -p[i+1].ctime )/p[i+1].stime ;

int ps=i+1;

for(int m=i+1;m<i+k;m++)

{

if((p[i].ftime -p[m+1].ctime)/p[m+1].stime >=maxrratio)

{

maxrratio=(p[i].ftime -p[m+1].ctime)/p[m+1].stime;

ps=m+1;

}

}

works temp;

temp=p[i+1];

p[i+1]=p[ps];

p[ps]=temp;

}

datap(p,n);

cout<<"高響應比優(yōu)先算法: "<<endl;

output(p,n);

}

3、給出測試數(shù)據(jù)和運行結(jié)果

workA={'作業(yè)名':'A','到達時間':0,'服務時間':6}

workB={'作業(yè)名':'B','到達時間':2,'服務時間':50}

workC={'作業(yè)名':'C','到達時間':5,'服務時間':20}

workD={'作業(yè)名':'D','到達時間':5,'服務時間':10}?

workE={'作業(yè)名':'E','到達時間':12,'服務時間':40}

workF={'作業(yè)名':'F','到達時間':15,'服務時間':8}

先來先服務算法

調(diào)度順序:['A',?'B',?'C',?'D',?'E',?'F']?周轉(zhuǎn)時間:74.1667?帶權(quán)周轉(zhuǎn)時間:5.2425

短作業(yè)優(yōu)先算法

調(diào)度順序:['A',?'D',?'F',?'C',?'E',?'B']?周轉(zhuǎn)時間:44.8333?帶權(quán)周轉(zhuǎn)時間:1.16025

高響應比優(yōu)先算法