一、目的和要求
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 | 由作业说明书在系统中生成一个称为作业控制块(job control block，JCB)的表格。该表格登记该作业所要求的资源情况、预计执行时间和执行优先级等。从而，操作系统通过该表了解到作业要求，并分配资源和控制作业中程序和数据的编译、链接、装入和执行等。 |
| 4 | 操作系统中，常用的作业调度算法有哪些？ | 先来先服务、轮转法、多级反馈队列列算法、优先级法、短作业优先法、最高响应 |
| 5 | 如何编程实现作业调度算法？ | |
| 6 | 模拟程序的输入如何设计更方便、结果输出如何呈现更好？ | |
五、 其他要求
1． 完成报告书，内容完整，规格规范。
2． 实验须检查，回答实验相关问题。
注：带**号的条目表示选做内容。
二、实验内容
根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。
三、实验环境
可以采用TC，也可以选用Windows下的利用各种控件较为方便的VB，VC等可视化环境。也可以自主选择其他实验环境。
四、实验原理及核心算法参考程序段
单道FCFS算法：
1 #include<stdio.h>
2 #include<string.h>
3 void shuru();
4 void readfiles();
5 void ran();
6 typedef struct jcb
7 {
8 char name[10];
9 char status; //状态：开始s，等待d，就绪j
10 int id;
11 int arrtime; //到达时间
12 int reqtime; //要求服务时间
13 int startime; //开始时间
14 int finitime; //完成时间
15
16 float TAtime,TAWtime; //周转时间、带权周转时间
17 float prio; //优先级
18 float HRRF; //响应比
19
20 }jcb;
21
22
23
24 jcb jcbs[100]; //最多100个作业
25 int systime=0,bfsum,add,del;
26 int intarr,infin,intjob,sumjcb;
27 char T='A'; //T的默认值是A
28
29 void sort(int choose) //排序
30 {
31 int i,j;
32 jcb temp;
33 for(i=1;i<=sumjcb;i++)
34 {
35 for(j=i+1;j<=sumjcb;j++)
36 {
37 if(choose==1)
38 {
39 if(jcbs[i].arrtime>jcbs[j].arrtime)
40 {
41 strcpy(temp.name,jcbs[i].name);
42 temp.status=jcbs[i].status;
43 temp.arrtime=jcbs[i].arrtime;
44 temp.reqtime=jcbs[i].reqtime;
45 temp.startime=jcbs[i].startime;
46 temp.finitime=jcbs[i].finitime;
47 temp.TAtime=jcbs[i].TAtime;
48 temp.TAWtime=jcbs[i].TAWtime;
49 temp.prio=jcbs[i].prio;
50 temp.id=jcbs[i].id;
51 temp.HRRF=jcbs[i].HRRF;
52
53 strcpy(jcbs[i].name,jcbs[j].name);
54 jcbs[i].status=jcbs[j].status;
55 jcbs[i].arrtime=jcbs[j].arrtime;
56 jcbs[i].reqtime=jcbs[j].reqtime;
57 jcbs[i].startime=jcbs[j].startime;
58 jcbs[i].finitime=jcbs[j].finitime;
59 jcbs[i].TAtime=jcbs[j].TAtime;
60 jcbs[i].TAWtime=jcbs[j].TAWtime;
61 jcbs[i].prio=jcbs[j].prio;
62 jcbs[i].id=jcbs[j].id;
63 jcbs[i].HRRF=jcbs[j].HRRF;
64
65 strcpy(jcbs[j].name,temp.name);
66 jcbs[j].status=temp.status;
67 jcbs[j].arrtime=temp.arrtime;
68 jcbs[j].reqtime=temp.reqtime;
69 jcbs[j].startime=temp.startime;
70 jcbs[j].finitime=temp.finitime;
71 jcbs[j].TAtime=temp.TAtime;
72 jcbs[j].TAWtime=temp.TAWtime;
73 jcbs[j].prio=temp.prio;
74 jcbs[j].id=temp.id;
75 jcbs[j].HRRF=temp.HRRF;
76 }
77 }
78 else if(choose==2)
79 {
80 if(jcbs[i].reqtime>jcbs[j].reqtime)
81 {
82 strcpy(temp.name,jcbs[i].name);
83 temp.status=jcbs[i].status;
84 temp.arrtime=jcbs[i].arrtime;
85 temp.reqtime=jcbs[i].reqtime;
86 temp.startime=jcbs[i].startime;
87 temp.finitime=jcbs[i].finitime;
88 temp.TAtime=jcbs[i].TAtime;
89 temp.TAWtime=jcbs[i].TAWtime;
90 temp.prio=jcbs[i].prio;
91 temp.id=jcbs[i].id;
92 temp.HRRF=jcbs[i].HRRF;
93
94 strcpy(jcbs[i].name,jcbs[j].name);
95 jcbs[i].status=jcbs[j].status;
96 jcbs[i].arrtime=jcbs[j].arrtime;
97 jcbs[i].reqtime=jcbs[j].reqtime;
98 jcbs[i].startime=jcbs[j].startime;
99 jcbs[i].finitime=jcbs[j].finitime;
100 jcbs[i].TAtime=jcbs[j].TAtime;
101 jcbs[i].TAWtime=jcbs[j].TAWtime;
102 jcbs[i].prio=jcbs[j].prio;
103 jcbs[i].id=jcbs[j].id;
104 jcbs[i].HRRF=jcbs[j].HRRF;
105
106 strcpy(jcbs[j].name,temp.name);
107 jcbs[j].status=temp.status;
108 jcbs[j].arrtime=temp.arrtime;
109 jcbs[j].reqtime=temp.reqtime;
110 jcbs[j].startime=temp.startime;
111 jcbs[j].finitime=temp.finitime;
112 jcbs[j].TAtime=temp.TAtime;
113 jcbs[j].TAWtime=temp.TAWtime;
114 jcbs[j].prio=temp.prio;
115 jcbs[j].id=temp.id;
116 jcbs[j].HRRF=temp.HRRF;
117 }
118 }
119 else if(choose==3)
120 {
121 if(jcbs[i].HRRF<jcbs[j].HRRF)
122 {
123 strcpy(temp.name,jcbs[i].name);
124 temp.status=jcbs[i].status;
125 temp.arrtime=jcbs[i].arrtime;
126 temp.reqtime=jcbs[i].reqtime;
127 temp.startime=jcbs[i].startime;
128 temp.finitime=jcbs[i].finitime;
129 temp.TAtime=jcbs[i].TAtime;
130 temp.TAWtime=jcbs[i].TAWtime;
131 temp.prio=jcbs[i].prio;
132 temp.id=jcbs[i].id;
133 temp.HRRF=jcbs[i].HRRF;
134
135 strcpy(jcbs[i].name,jcbs[j].name);
136 jcbs[i].status=jcbs[j].status;
137 jcbs[i].arrtime=jcbs[j].arrtime;
138 jcbs[i].reqtime=jcbs[j].reqtime;
139 jcbs[i].startime=jcbs[j].startime;
140 jcbs[i].finitime=jcbs[j].finitime;
141 jcbs[i].TAtime=jcbs[j].TAtime;
142 jcbs[i].TAWtime=jcbs[j].TAWtime;
143 jcbs[i].prio=jcbs[j].prio;
144 jcbs[i].id=jcbs[j].id;
145 jcbs[i].HRRF=jcbs[j].HRRF;
146
147 strcpy(jcbs[j].name,temp.name);
148 jcbs[j].status=temp.status;
149 jcbs[j].arrtime=temp.arrtime;
150 jcbs[j].reqtime=temp.reqtime;
151 jcbs[j].startime=temp.startime;
152 jcbs[j].finitime=temp.finitime;
153 jcbs[j].TAtime=temp.TAtime;
154 jcbs[j].TAWtime=temp.TAWtime;
155 jcbs[j].prio=temp.prio;
156 jcbs[j].id=temp.id;
157 jcbs[j].HRRF=temp.HRRF;
158 }
159 }
160 else
161 printf("Error!\n");
162 }
163 }
164 }
165 void ins() //插入
166 {
167 int i;
168 while(T!='E'&&T!='e')
169 {
170 printf("'I'nsert or 'D'elete or 'E'xit?\n");
171 getchar();
172 scanf("%c",&T);
173 if(T=='I'||T=='i')
174 {
175 printf("你想插入多少个作业?\n");
176 scanf("%d",&add);
177 bfsum=sumjcb;
178 sumjcb=sumjcb+add;
179 for(i=bfsum+1;i<=sumjcb;i++)
180 {
181 printf("\n第%d个作业:\n",i);
182 getchar();
183 printf("输入作业名:\n");
184 gets(jcbs[i].name);
185 printf("到达时间:\n");
186 scanf("%d",&jcbs[i].arrtime);
187 printf("要求服务时间:\n");
188 scanf("%d",&jcbs[i].reqtime);
189 }
190 }
191 else if(T=='D'||T=='d')
192 {
193 printf("你想删除第几组?");
194 scanf("%d",&del);
195 for(i=del;i<=sumjcb-1;i++)
196 {
197 strcpy(jcbs[i].name,jcbs[i+1].name);
198 jcbs[i].arrtime=jcbs[i+1].arrtime;
199 jcbs[i].reqtime=jcbs[i+1].reqtime;
200 }
201 sumjcb--;
202 }
203 }
204 }
205
206
207 void printarr() //打印
208 {
209 int i;
210 printf("\t\tname\tartime\trqtime\n");
211 for(i=1;i<=sumjcb;i++)
212 {
213 printf("N %d\t",i);
214 printf("\t%s",jcbs[i].name);
215 printf("\t%d",jcbs[i].arrtime);
216 printf("\t%d\n",jcbs[i].reqtime);
217 }
218 printf("\t\t\t\t\t\t现在系统时间%d\n",systime);
219
220 }
221 void printz()
222 {
223 int i;
224 float sum1=0,sum2=0; //计算平均周转时间、平均带权周转时间
225 printf("\t\tname\tartime\trqtime\tstime\tftime\tTAtime\t\tTAWtime\n");
226 for(i=1;i<=sumjcb;i++)
227 {
228 printf("N %d\t",i);
229 printf("\t%s",jcbs[i].name);
230 printf("\t%d",jcbs[i].arrtime);
231 printf("\t%d",jcbs[i].reqtime);
232 printf("\t%d",jcbs[i].startime);
233 printf("\t%d",jcbs[i].finitime);
234 printf("\t%f",jcbs[i].TAtime);
235 printf("\t%f\n",jcbs[i].TAWtime);
236 }
237 for(i=1;i<=sumjcb;i++)
238 {
239 sum1=sum1+jcbs[i].TAtime;
240 }
241 for(i=1;i<=sumjcb;i++)
242 {
243 sum2=sum2+jcbs[i].TAWtime;
244 }
245 printf("\n平均周转时间=%f\n",sum1/sumjcb);
246 printf("\n平均带权周转时间=%f\n",sum2/sumjcb);
247 printf("\t\t\t\t\t\t现在系统时间%d\n",systime);
248 }
249 void sumofthey()
250 {
251 int i;
252 jcbs[1].startime=jcbs[1].arrtime;
253 jcbs[1].finitime=jcbs[1].arrtime+jcbs[1].reqtime;
254 jcbs[1].TAtime=(float)(jcbs[1].finitime-jcbs[1].arrtime);
255 jcbs[1].TAWtime=(float)(jcbs[1].TAtime/jcbs[1].reqtime);
256 jcbs[1].HRRF=(float)(jcbs[1].TAtime/jcbs[1].reqtime);
257 for(i=2;i<=sumjcb;i++)
258 {
259 jcbs[i].startime=jcbs[i-1].finitime;
260 jcbs[i].finitime=jcbs[i].startime+jcbs[i].reqtime;
261 jcbs[i].TAtime=(float)(jcbs[i].finitime-jcbs[i].arrtime);
262 jcbs[i].TAWtime=(float)(jcbs[i].TAtime/jcbs[i].reqtime);
263 jcbs[i].HRRF=(float)(jcbs[i].TAtime/jcbs[i].reqtime);
264 }
265 }
266 void startit()
267 {
268 int n;
269 printf("\n");
270 printf("\t\t\t**************************\n");
271 printf("\t\t\t**1.调用文本写入数据******\n");
272 printf("\t\t\t**2.调用伪随机数产生数据**\n");
273 printf("\t\t\t**3.调用自己输入模拟数据**\n");
274 printf("\t\t\t**************************\n");
275 scanf("%d",&n);
276 switch(n)
277 {
278 case 1:
279 readfiles();
280 sumofthey();
281 break;
282 case 2:
283 ran();
284 sumofthey();
285 break;
286 case 3:
287 shuru();
288 sumofthey();
289 break;
290 default:
291 {
292 printf("输入有误，请重新输入");
293 break;
294 }
295 }
296 }
297 void ran()
298 {
299 int i;
300 srand((unsigned)time(0)); //参数seed是rand()的种子，用来初始化rand()的起始值。
301 sumjcb=rand()%23+5;
302 for(i=1;i<=sumjcb;i++)
303 {
304 itoa(i,jcbs[i].name, 2);
305
306 jcbs[i].arrtime=rand()%29+1;
307
308 jcbs[i].reqtime=rand()%7+1;
309 }
310 printf("\n \tid \t作业到达时间 \t作业运行所需要时间\n");
311 for(i=1; i<=sumjcb; i++)
312 {
313 printf("\n\t%s\t%12d\t%15d",jcbs[i].name,jcbs[i].arrtime,jcbs[i].reqtime);
314 }
315 printf("\n");
316 }
317
318 void readfiles()
319 {
320 char szTest[1000] = {0};int i=0,n;
321 FILE *fp=fopen("D:\\File1.txt","r");
322 //FILE *fout=fopen("D:\\File2.txt","w");
323 if(fp == NULL)
324 {
325 printf("ERROR!\n");
326 exit(0);
327 }
328 //fscanf(fp,"jcbsum=%d\n",%n);
329 while(!feof(fp))
330 {
331 fscanf(fp,"%d%d%d",&jcbs[i].id,&jcbs[i].arrtime,&jcbs[i].reqtime); //fscanf()函数将数据读入
332 printf("\n%3d%12d%15d\n",jcbs[i].id,jcbs[i].arrtime,jcbs[i].reqtime); //输出到屏幕
333 itoa(jcbs[i].id,jcbs[i].name,10);
334 i++;
335 /*memset(szTest, 0, sizeof(szTest));
336 fscanf(fp,"@id=%d|",&i);
337 fgets(fp,"name=%s|",jcbs[i].name);
338 fscanf(fp,"arrtime=%d|reqtime=%d\n",&jcbs[i].arrtime,&jcbs[i].reqtime);
339 */
340 //fscanf(fp,"%d",)
341 }
342 sumjcb=i;
343 fclose(fp);
344 }
345 void shuru()
346 {
347 int i;
348 printf("作业个数:\n");
349 scanf("%d",&sumjcb);
350 for(i=1;i<=sumjcb;i++)
351 {
352 printf("\n第%d个作业:\n",i);
353 getchar();
354 printf("输入作业名:\n");
355 gets(jcbs[i].name);
356 printf("到达时间:\n");
357 scanf("%d",&jcbs[i].arrtime);
358 printf("要求服务时间:\n");
359 scanf("%d",&jcbs[i].reqtime);
360 }
361 sumofthey();
362 }
363 void choosesort()
364 {
365 int n;
366 printf("\t\t\t*****************************\n");
367 printf("\t\t\t*******1.FCFS算法调度********\n");
368 printf("\t\t\t*******2.SJF算法调度*********\n");
369 printf("\t\t\t*******3.HRRF算法调度********\n");
370 printf("\t\t\t*******4.调用系统清屏********\n");
371 printf("\t\t\t*******5.退出算法调度********\n");
372 printf("\t\t\t*****************************\n");
373 scanf("%d",&n);
374 switch(n)
375 {
376 case 1:
377 printf("运行先来先服务算法FCFS\n");
378 sort(1);
379 printf("\n经按到达时间排序后，未达到队列是\n");
380 printz();
381 break;
382 case 2:
383 printf("运行最短作业优先算法FJS\n");
384 sort(2);
385 printf("\n经按到达时间排序后，未达到队列是\n");
386 printz();
387 break;
388 case 3:
389 printf("运行最高响应比优先算法HRRF\n");
390 sort(3);
391 printf("\n经按到达时间排序后，未达到队列是\n");
392 printz();
393 break;
394 case 4:
395 system("cls");
396 break;
397 case 5:
398 exit(0);
399 break;
400 }
401 }
402 void main()
403 {
404 startit();
405 choosesort();
406
407
408 }