一、实验目的
1、 对作业调度的相关内容作进一步的理解。
2、 理解作业调度的主要任务。
3、 通过编程掌握作业调度的主要算法。
二、实验内容及要求
1、 对于给定的一组作业, 给出其到达时间和运行时间，数据要求通过键盘输入。
例如下表所示：,
|
作业名 |
A |
B |
C |
D |
E |
F |
|
到达时间 |
0 |
2 |
5 |
5 |
12 |
15 |
|
服务时间 |
6 |
50 |
20 |
10 |
40 |
8 |
2、分别用先来先服务算法、短作业优先和响应比高者优先三种算法给出作业的调度顺序。
3、计算每一种算法的平均周转时间及平均带权周转时间并比较不同算法的优劣。
三、实验报告
1、程序中使用的数据结构及符号说明。
2、给出主要算法的流程图。
3、给出程序清单并附上注释。
4、给出测试数据和运行结果。
代码如下
1 #include<iostream>
2 using namespace std;
3 struct works
4 {
5 char name; //作业名
6 double ctime; //到达时间
7 double stime; //服务时间
8 double ftime; //完成时间
9 double ztime; //周转时间
10 double dtime; //带权周转时间
11 double wtime; //等待时间
12 double rratio; //响应比
13 };
14 double sumztime,sumdtime;
15 double avgztime,avgdtime;
16 void input(works *p,int n); //输入
17 void output(works *p,int n);//输出
18 void datap(works *p,int n);//数据处理
19 void sort(works *p,int n); //按到达时间排序
20 void fcfs(works *p,int n); //先来先服务
21 void sjf(works *p,int n); //短作业优先
22 void hrf(works *p,int n); //高响应比优先
23
24 int main()
25 {
26 int n;
27 cout<<"输入作业数目：";
28 cin>>n;
29 works *a=new works[n];
30 input(a,n);
31 fcfs(a,n);
32 cout<<"\n";
33 sjf(a,n);
34 cout<<"\n";
35 hrf(a,n);
36 delete a;
37 return 0;
38 }
39 void input(works *p,int n)
40 {
41 cout<<"请输入作业信息："<<endl<<endl;
42 for(int i=0;i<n;i++)
43 {
44 cout<<"作业名：";
45 cin>>p[i].name ;
46 cout<<"到达时间：";
47 cin>>p[i].ctime ;
48 cout<<"服务时间：";
49 cin>>p[i].stime ;
50 cout<<"\n";
51 }
52
53 }
54
55 void datap(works *p,int n)
56 {
57 sumztime=sumdtime=0;
58 p[0].ftime =p[0].ctime +p[0].stime ;
59 for(int i=1;i<n;i++)
60 {
61 p[i].ftime=p[i-1].ftime+p[i].stime;
62 }
63 for(int j=0;j<n;j++)
64 {
65 p[j].ztime =p[j].ftime -p[j].ctime ;
66 p[j].dtime =p[j].ztime /p[j].stime ;
67 sumztime+=p[j].ztime;
68 sumdtime+=p[j].dtime;
69 }
70 avgztime=sumztime/n;
71 avgdtime=sumdtime/n;
72 }
73
74 void output(works *p,int n)
75 {
76 cout<<"作业调度顺序：";
77 for(int k=0;k<n;k++)
78 {
79 cout<<p[k].name <<" ";
80 }
81 cout<<"\n";
82 cout<<"平均周转时间="<<avgztime<<endl;
83 cout<<"平均带权周转时间="<<avgdtime<<endl;
84
85 }
86
87 void sort(works *p,int n)
88 {
89 for(int i=n-1;i>=1;i--)
90 for(int j=0;j<i;j++)
91 if(p[j].ctime >p[j+1].ctime )
92 {
93 works temp;
94 temp=p[j];
95 p[j]=p[j+1];
96 p[j+1]=temp;
97 }
98
99
100 }
101
102 void fcfs(works *p,int n)
103 {
104 sort(p,n);
105 datap(p,n);
106 cout<<"先来先服务算法"<<endl;
107 output(p,n);
108
109 }
110
111 void sjf(works *p,int n)
112 {
113 sort(p,n);
114 for(int i=0;i<n-1;i++)
115 {
116 int k=0;
117 if(i==0)
118 p[i].ftime =p[i].ctime +p[i].stime ;
119 else
120 p[i].ftime =p[i].stime +p[i-1].ftime ;
121 for(int j=i+1;j<n;j++)
122 {
123 if(p[j].ctime<=p[i].ftime )
124 k++;
125 }
126 double minstime=p[i+1].stime ;
127 int ps=i+1;
128 for(int m=i+1;m<i+k;m++)
129 {
130 if(p[m+1].stime <minstime)
131 {
132 minstime=p[m+1].stime ;
133 ps=m+1;
134 }
135 }
136 works temp;
137 temp=p[i+1];
138 p[i+1]=p[ps];
139 p[ps]=temp;
140 }
141 datap(p,n);
142 cout<<"短作业优先算法："<<endl;
143 output(p,n);
144 }
145
146 void hrf(works *p,int n)
147 {
148 sort(p,n);
149 for(int i=0;i<n-1;i++)
150 {
151 int k=0;
152 if(i==0)
153 p[i].ftime =p[i].ctime +p[i].stime ;
154
155 else
156 p[i].ftime =p[i].stime +p[i-1].ftime ;
157 for(int j=i+1;j<n;j++)
158 {
159 if(p[j].ctime <=p[i].ftime )
160 k++;
161 }
162 double maxrratio=(p[i].ftime -p[i+1].ctime )/p[i+1].stime ;
163 int ps=i+1;
164 for(int m=i+1;m<i+k;m++)
165 {
166 if((p[i].ftime -p[m+1].ctime)/p[m+1].stime >=maxrratio)
167 {
168 maxrratio=(p[i].ftime -p[m+1].ctime)/p[m+1].stime;
169 ps=m+1;
170 }
171 }
172 works temp;
173 temp=p[i+1];
174 p[i+1]=p[ps];
175 p[ps]=temp;
176 }
177 datap(p,n);
178 cout<<"高响应比优先算法："<<endl;
179 output(p,n);
180 }
181
2 using namespace std;
3 struct works
4 {
5 char name; //作业名
6 double ctime; //到达时间
7 double stime; //服务时间
8 double ftime; //完成时间
9 double ztime; //周转时间
10 double dtime; //带权周转时间
11 double wtime; //等待时间
12 double rratio; //响应比
13 };
14 double sumztime,sumdtime;
15 double avgztime,avgdtime;
16 void input(works *p,int n); //输入
17 void output(works *p,int n);//输出
18 void datap(works *p,int n);//数据处理
19 void sort(works *p,int n); //按到达时间排序
20 void fcfs(works *p,int n); //先来先服务
21 void sjf(works *p,int n); //短作业优先
22 void hrf(works *p,int n); //高响应比优先
23
24 int main()
25 {
26 int n;
27 cout<<"输入作业数目：";
28 cin>>n;
29 works *a=new works[n];
30 input(a,n);
31 fcfs(a,n);
32 cout<<"\n";
33 sjf(a,n);
34 cout<<"\n";
35 hrf(a,n);
36 delete a;
37 return 0;
38 }
39 void input(works *p,int n)
40 {
41 cout<<"请输入作业信息："<<endl<<endl;
42 for(int i=0;i<n;i++)
43 {
44 cout<<"作业名：";
45 cin>>p[i].name ;
46 cout<<"到达时间：";
47 cin>>p[i].ctime ;
48 cout<<"服务时间：";
49 cin>>p[i].stime ;
50 cout<<"\n";
51 }
52
53 }
54
55 void datap(works *p,int n)
56 {
57 sumztime=sumdtime=0;
58 p[0].ftime =p[0].ctime +p[0].stime ;
59 for(int i=1;i<n;i++)
60 {
61 p[i].ftime=p[i-1].ftime+p[i].stime;
62 }
63 for(int j=0;j<n;j++)
64 {
65 p[j].ztime =p[j].ftime -p[j].ctime ;
66 p[j].dtime =p[j].ztime /p[j].stime ;
67 sumztime+=p[j].ztime;
68 sumdtime+=p[j].dtime;
69 }
70 avgztime=sumztime/n;
71 avgdtime=sumdtime/n;
72 }
73
74 void output(works *p,int n)
75 {
76 cout<<"作业调度顺序：";
77 for(int k=0;k<n;k++)
78 {
79 cout<<p[k].name <<" ";
80 }
81 cout<<"\n";
82 cout<<"平均周转时间="<<avgztime<<endl;
83 cout<<"平均带权周转时间="<<avgdtime<<endl;
84
85 }
86
87 void sort(works *p,int n)
88 {
89 for(int i=n-1;i>=1;i--)
90 for(int j=0;j<i;j++)
91 if(p[j].ctime >p[j+1].ctime )
92 {
93 works temp;
94 temp=p[j];
95 p[j]=p[j+1];
96 p[j+1]=temp;
97 }
98
99
100 }
101
102 void fcfs(works *p,int n)
103 {
104 sort(p,n);
105 datap(p,n);
106 cout<<"先来先服务算法"<<endl;
107 output(p,n);
108
109 }
110
111 void sjf(works *p,int n)
112 {
113 sort(p,n);
114 for(int i=0;i<n-1;i++)
115 {
116 int k=0;
117 if(i==0)
118 p[i].ftime =p[i].ctime +p[i].stime ;
119 else
120 p[i].ftime =p[i].stime +p[i-1].ftime ;
121 for(int j=i+1;j<n;j++)
122 {
123 if(p[j].ctime<=p[i].ftime )
124 k++;
125 }
126 double minstime=p[i+1].stime ;
127 int ps=i+1;
128 for(int m=i+1;m<i+k;m++)
129 {
130 if(p[m+1].stime <minstime)
131 {
132 minstime=p[m+1].stime ;
133 ps=m+1;
134 }
135 }
136 works temp;
137 temp=p[i+1];
138 p[i+1]=p[ps];
139 p[ps]=temp;
140 }
141 datap(p,n);
142 cout<<"短作业优先算法："<<endl;
143 output(p,n);
144 }
145
146 void hrf(works *p,int n)
147 {
148 sort(p,n);
149 for(int i=0;i<n-1;i++)
150 {
151 int k=0;
152 if(i==0)
153 p[i].ftime =p[i].ctime +p[i].stime ;
154
155 else
156 p[i].ftime =p[i].stime +p[i-1].ftime ;
157 for(int j=i+1;j<n;j++)
158 {
159 if(p[j].ctime <=p[i].ftime )
160 k++;
161 }
162 double maxrratio=(p[i].ftime -p[i+1].ctime )/p[i+1].stime ;
163 int ps=i+1;
164 for(int m=i+1;m<i+k;m++)
165 {
166 if((p[i].ftime -p[m+1].ctime)/p[m+1].stime >=maxrratio)
167 {
168 maxrratio=(p[i].ftime -p[m+1].ctime)/p[m+1].stime;
169 ps=m+1;
170 }
171 }
172 works temp;
173 temp=p[i+1];
174 p[i+1]=p[ps];
175 p[ps]=temp;
176 }
177 datap(p,n);
178 cout<<"高响应比优先算法："<<endl;
179 output(p,n);
180 }
181