一、目的和要求
1. 实验目的
（1）加深对作业调度算法的理解；
（2）进行程序设计的训练。
2．实验要求
用高级语言编写一个或多个作业调度的模拟程序。
单道批处理系统的作业调度程序。作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所运行的时间等因素。
作业调度算法：
1) 采用先来先服务（FCFS）调度算法，即按作业到达的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。
2) 短作业优先 (SJF) 调度算法，优先调度要求运行时间最短的作业。
3) 响应比高者优先(HRRN)调度算法，为每个作业设置一个优先权(响应比)，调度之前先计算各作业的优先权，优先数高者优先调度。RP (响应比)＝ 作业周转时间 / 作业运行时间=1+作业等待时间/作业运行时间
每个作业由一个作业控制块JCB表示，JCB可以包含以下信息：作业名、提交（到达）时间、所需的运行时间、所需的资源、作业状态、链指针等等。
作业的状态可以是等待W（Wait）、运行R（Run）和完成F（Finish）三种之一。每个作业的最初状态都是等待W。
一、 模拟数据的生成
1． 允许用户指定作业的个数（2-24），默认值为5。
2． 允许用户选择输入每个作业的到达时间和所需运行时间。
3． （**）从文件中读入以上数据。
4． （**）也允许用户选择通过伪随机数指定每个作业的到达时间（0-30）和所需运行时间（1-8）。
二、 模拟程序的功能
1． 按照模拟数据的到达时间和所需运行时间，执行FCFS, SJF和HRRN调度算法，程序计算各作业的开始执行时间，各作业的完成时间，周转时间和带权周转时间（周转系数）。
2． 动态演示每调度一次，更新现在系统时刻，处于运行状态和等待各作业的相应信息（作业名、到达时间、所需的运行时间等）对于HRRN算法，能在每次调度时显示各作业的响应比R情况。
3． （**）允许用户在模拟过程中提交新作业。
4． （**）编写并调度一个多道程序系统的作业调度模拟程序。 只要求作业调度算法：采用基于先来先服务的调度算法。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。
三、 模拟数据结果分析
1． 对同一个模拟数据各算法的平均周转时间，周转系数比较。
2． （**）用曲线图或柱形图表示出以上数据，分析算法的优点和缺点。
四、 实验准备
| 序号 | 准备内容 | 完成情况 |
| 1 | 什么是作业？ | |
| 2 | 一个作业具备什么信息？ | |
| 3 | 为了方便模拟调度过程，作业使用什么方式的数据结构存放和表示？JCB | |
| 4 | 操作系统中，常用的作业调度算法有哪些？ | |
| 5 | 如何编程实现作业调度算法？ | |
| 6 | 模拟程序的输入如何设计更方便、结果输出如何呈现更好？ |
五、 其他要求
1． 完成报告书，内容完整，规格规范。
2． 实验须检查，回答实验相关问题。
注：带**号的条目表示选做内容。
二、实验内容
根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。
三、实验环境
可以采用TC，也可以选用Windows下的利用各种控件较为方便的VB，VC等可视化环境。也可以自主选择其他实验环境。
四、实验原理及核心算法参考程序段
单道FCFS算法：
源代码：
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<time.h>
4 struct jcb{
5 int id;
6 char status;
7
8 int arrtime;
9 int reqtime;
10 int startime;
11 int finitime;
12
13 float TAtime,TAWtime;
14 float prio;
15 } jobarr[24],jobfin[24],job[24];
16 int systime=0;
17
18
19 //主菜单
20 void menu()
21 {
22 printf("\t\t\t***************************************\n");
23 printf("\t\t\t| 作业调度 |\n");
24 printf("\t\t\t|-------------------------------------|\n");
25 printf("\t\t\t| 1.调用文本写入数据 |\n");
26 printf("\t\t\t|-------------------------------------|\n");
27 printf("\t\t\t| 2.调用伪随机数的产生数据 |\n");
28 printf("\t\t\t|-------------------------------------|\n");
29 printf("\t\t\t| 3.自主输入模拟数据 |\n");
30 printf("\t\t\t|**************************************\n");
31 }
32
33
34 //调度算法菜单
35 void menu0()
36 {
37 printf("\n");
38 printf("\n***************************************\n");
39 printf(" 1.FCFS算法调度\n");
40 printf(" 2.SJF算法调度\n");
41 printf(" 3.HRRF算法调度\n");
42 printf(" 4.调用系统清屏\n");
43 printf(" 0.退出算法调度\n");
44 printf("***************************************\n");
45 }
46
47
48 //短作业优先排序
49 void sort(int n)
50 {
51 int i,j;
52 struct jcb temp;
53 for(i=2;i<n;i++)
54 for(j=i+1;j<=n;j++)
55 if(jobarr[i].reqtime>jobarr[j].reqtime) //根据最短的要求服务时间排序
56 {
57 temp=jobarr[i];
58 jobarr[i]=jobarr[j];
59 jobarr[j]=temp;
60 }
61 }
62
63
64 //先到先服务排序
65 void sort0(int n)
66 {
67 int i,j;
68 struct jcb temp;
69 for(i=2;i<n;i++)
70 for(j=i+1;j<=n;j++)
71 if(job[i].arrtime>job[j].arrtime) //根据到达时间排序
72 {
73 temp=job[i];
74 job[i]=job[j];
75 job[j]=temp;
76 }
77 }
78
79
80 //自主输入模拟数据
81 void shoushu()
82 {
83 int n;
84 printf("作业个数:");
85 scanf("%d",&n);
86 for(int i=1;i<=n;i++)
87 {
88 printf("\n第%d个作业:",i);
89 printf("\n请输入作业名:");
90 scanf("%d",&job[i].id);
91 printf("到达时间:");
92 scanf("%d",&job[i].arrtime);
93 printf("要求服务时间:");
94 scanf("%d",&job[i].reqtime);
95 jobarr[i]=job[i];
96 }
97 }
98
99
100 //文本写入数据
101 int ReadFile()
102 {
103 int m=0;
104 int i=1;
105 FILE *fp; //定义文件指针
106 fp=fopen("作业调度.txt","r"); //打开文件
107 if(fp==NULL)
108 {
109 printf("File open error !\n");
110 exit(0);
111 }
112 printf("\n 作业名 作业到达时间 作业运行所需要时间\n");
113 while(!feof(fp))
114 {
115 fscanf(fp,"%d%d%d",&job[i].id,&job[i].arrtime,&job[i].reqtime); //fscanf()函数将数据读入
116 printf("\n%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime); //输出到屏幕
117 i++;
118 };
119
120 if(fclose(fp)) //关闭文件
121 {
122 printf("Can not close the file !\n");
123 exit(0);
124 }
125 m=i-1;
126 return m;
127
128 }
129
130
131 //伪随机数的产生数据
132 int Pseudo_random_number()
133 {
134 int i,n;
135 srand((unsigned)time(0)); //参数seed是rand()的种子，用来初始化rand()的起始值。
136 //输入作业数
137 n=rand()%23+5;
138 for(i=1; i<=n; i++)
139 {
140 job[i].id=i;
141 //作业到达时间
142 job[i].arrtime=rand()%29+1;
143 //作业运行时间
144 job[i].reqtime=rand()%7+1;
145 }
146 printf("\n 作业名 作业到达时间 作业运行所需要时间\n");
147 for(i=1; i<=n; i++)
148 {
149 printf("\n%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);
150 }
151 return n;
152
153 }
154
155
156 //先来先服务算法FCFS
157 void FCFS()
158 {
159 int i=1,j=1;
160 float sumTA=0,sumTAW=0;
161 printf("-----------先来先服务算法FCFS-------------\n");
162 printf("\n 作业名 作业到达时间 作业运行所需要时间\n");
163 while(job[j].id!=NULL)
164 {
165 printf("\n%3d%12d%15d",job[j].id,job[j].arrtime,job[j].reqtime); //输出到屏幕
166 j++;
167 }
168 sort0(j-1);
169 printf("\n\n作业名 作业到达时间 作业完成时间 运行时间 作业周转时间 带权作业周转时间\n");
170 while(job[i].id!=NULL)
171 {
172 if(i==1) //第一个作业先到达，先被调度
173 {
174 job[i].startime=job[i].arrtime;
175 }
176 else //其他作业被调度
177 {
178 if(job[i-1].finitime>=job[i].arrtime) //如果上一个作业的完成时间大于下一个到达时间，则下一个开始时间为上一个作业的完成时间
179 job[i].startime=job[i-1].finitime;
180 else
181 job[i].startime=job[i].arrtime; //否则下一个开始时间即它的到达时间
182 }
183 job[i].finitime=job[i].startime+job[i].reqtime; //计算完成时间
184 job[i].TAtime=job[i].finitime-job[i].arrtime; //计算周转时间
185 job[i].TAWtime=job[i].TAtime/job[i].reqtime; //计算带权周转时间
186 sumTA+=job[i].TAtime;
187 sumTAW+=job[i].TAWtime;
188 printf("\n%3d%12d%13d%14d%12.0lf%14.2lf",job[i].id,job[i].arrtime,job[i].finitime,job[i].reqtime,job[i].TAtime,job[i].TAWtime);
189 i++;
190 }
191 printf("\n平均作业周转时间= %.2lf",sumTA/(i-1));
192 printf("\n平均带权作业周转时间= %.2lf",sumTAW/(i-1));
193 }
194
195
196 //最短作业优先算法SJF
197 void SJF()
198 {
199 int i=1,j=1;
200 float sumTA=0,sumTAW=0;
201 printf("-----------最短作业优先算法SJF-------------\n");
202 printf("\n作业名 作业到达时间 作业运行所需要时间\n");
203 while(job[j].id!=NULL)
204 {
205 printf("\n%3d%12d%15d",job[j].id,job[j].arrtime,job[j].reqtime); //输出到屏幕
206 jobarr[j]=job[j];
207 j++;
208 }
209 sort(j-1);
210 printf("\n\n作业名 作业到达时间 作业完成时间 运行时间 作业周转时间 带权作业周转时间\n");
211 while(jobarr[i].id!=NULL)
212 {
213 if(i==1)
214 {
215 jobarr[i].startime=jobarr[i].arrtime;
216 }
217 else
218 {
219 if(jobarr[i-1].finitime>=jobarr[i].arrtime)
220 jobarr[i].startime=jobarr[i-1].finitime;
221 else
222 jobarr[i].startime=jobarr[i].arrtime;
223 }
224 jobarr[i].finitime=jobarr[i].startime+jobarr[i].reqtime;
225 jobarr[i].TAtime=jobarr[i].finitime-jobarr[i].arrtime;
226 jobarr[i].TAWtime=jobarr[i].TAtime/jobarr[i].reqtime;
227 sumTA+=jobarr[i].TAtime;
228 sumTAW+=jobarr[i].TAWtime;
229 printf("\n%3d%12d%13d%14d%12.0lf%14.2lf",jobarr[i].id,jobarr[i].arrtime,jobarr[i].finitime,jobarr[i].reqtime,jobarr[i].TAtime,jobarr[i].TAWtime);
230 i++;
231 }
232 printf("\n平均作业周转时间= %.2lf",sumTA/(i-1));
233 printf("\n平均带权作业周转时间= %.2lf",sumTAW/(i-1));
234 }
235
236
237 //最高响应比排序
238 void sort1(int n,int k)
239 {
240 int i,j;
241 struct jcb temp;
242 for(i=k;i<n;i++)
243 for(j=i+1;j<=n;j++)
244 if(jobfin[i].prio<jobfin[j].prio)
245 {
246 temp=jobfin[i];
247 jobfin[i]=jobfin[j];
248 jobfin[j]=temp;
249 }
250 }
251
252
253 //响应比最高者优先HRRF算法
254 void HRRF()
255 {
256 int i=1,j=1,k=1;
257 float sumTA=0,sumTAW=0;
258 printf("-----------响应比最高者优先HRRF算法-------------\n");
259 printf("\n作业名 作业到达时间 作业运行所需要时间\n");
260 while(job[j].id!=NULL)
261 {
262 printf("%3d%12d%15d\n",job[j].id,job[j].arrtime,job[j].reqtime); //输出到屏幕
263 jobfin[j]=job[j];
264 j++;
265 }
266 while(jobfin[k].id!=NULL)
267 {
268 i=k;
269 if(k==1)
270 {
271 jobfin[i].startime=jobfin[i].arrtime;
272 jobfin[i].finitime=jobfin[i].startime+jobfin[i].reqtime;
273 jobfin[i].TAtime=jobfin[i].finitime-jobfin[i].arrtime;
274 jobfin[i].TAWtime=jobfin[i].TAtime/jobfin[i].reqtime;
275 }
276 else
277 {
278 printf("\n作业名 最高响应比\n");
279 while(jobfin[i].id!=NULL)
280 {
281 if(jobfin[k-1].finitime>=job[i].arrtime)
282 {
283 jobfin[i].startime=jobfin[k-1].finitime;
284 jobfin[i].prio=(jobfin[i].startime-jobfin[i].arrtime)/(jobfin[i].reqtime/1.0)+1;
285 }
286 else
287 {
288 jobfin[i].startime=0;
289 jobfin[i].prio=0;
290 }
291 i++;
292 }
293 sort1(j-1,k);
294 for(i=k;i<j;i++)
295 printf("%3d%10.2lf\n",jobfin[i].id,jobfin[i].prio);
296 jobfin[k].finitime=jobfin[k-1].finitime+jobfin[k].reqtime;
297 jobfin[k].TAtime=jobfin[k].finitime-jobfin[k].arrtime;
298 jobfin[k].TAWtime=jobfin[k].TAtime/jobfin[k].reqtime;
299 }
300 k++;
301 }
302 printf("\n\n作业名 作业到达时间 作业完成时间 运行时间 作业周转时间 带权作业周转时间\n");
303 for(i=1;i<j;i++)
304 {
305 printf("\n%3d%12d%13d%14d%12.0lf%14.2lf",jobfin[i].id,jobfin[i].arrtime,jobfin[i].finitime,jobfin[i].reqtime,jobfin[i].TAtime,jobfin[i].TAWtime);
306 sumTA+=jobfin[i].TAtime;
307 sumTAW+=jobfin[i].TAWtime;
308 }
309 printf("\n平均作业周转时间= %.2lf",sumTA/(i-1));
310 printf("\n平均带权作业周转时间= %.2lf",sumTAW/(i-1));
311 }
312
313
314 void main0()
315 {
316 int tmp;
317 while(1)
318 {
319 menu0();
320 printf("\n请选择菜单项:");
321 scanf("%d",&tmp);
322 switch (tmp)
323 {
324 case 1:
325 FCFS();
326 break;
327 case 2:
328 SJF();
329 break;
330 case 3:
331 HRRF();
332 break;
333 case 4:
334 system("cls");
335 break;
336 case 0:
337 return;
338 }
339 }
340 }
341
342
343 main()
344 {
345 int tmp;
346 while(1)
347 {
348 menu();
349 printf("\n请选择菜单项:");
350 scanf("%d",&tmp);
351 switch (tmp)
352 {
353 case 1:
354 ReadFile();
355 break;
356 case 2:
357 Pseudo_random_number();
358 break;
359 case 3:
360 shoushu();
361 break;
362 }
363 main0();
364 printf("\n");
365 }
366 } 实验结果：
FCFS：
SJF:
HRRF:
实验总结：
刚开始做这个实验时我觉得很难，有点不知所措，但是通过老师的一些讲解和提供的思路，自己也上网百度了一些不懂的东西，最后成功完成了这个作业调度的一些基本要求，所以我觉得，付出多少，必然有所收获。
学号：201406114214
姓名：冯梓凡