实验二作业调度模拟程序

实验一、作业调度模拟程序实验

专业：商业软件工程姓名：曾治业学号：201406114235

一、实验目的

（1）加深对作业调度算法的理解；

（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.实验须检查，回答实验相关问题。

注：带**号的条目表示选做内容

三、 实验方法、步骤及结果测试

1. 源程序名：实验二.rar中源程序名 job.c

可执行程序名：job.exe

2. 原理分析及流程图

存储结构：结构体数组，文件读取；

主要算法：先来先服务算法（FCFS）；

最短作业优先算法（SJF）；

最高响应比算法（HRRF）；

关键函数：1. void InputData()//输入数据

1）. void HandworkInputData()//手工输入数据

2）. Pseudo_random_number()//伪随机数输入

3）. void FileInputtData()//文件读取

2. void InsertData()//插入数据

3. void DeleteData()//删除数据

4. void arithmeticmenu()//算法菜单

1）. void FCFS()//先来先服务FCFS

2）. void SJF()//最短作业优先算法SJF

3）. void HRRF()//最高响应比HRRF

3. 主要程序段及其解释：

  1 void FCFS()//先来先服务FCFS
  2 
  3 {
  4 
  5     int i,j;
  6 
  7     float arrtemp,reqtemp;
  8 
  9     float sum=0,sum1=0;
 10 
 11     char nametemp[10];
 12 
 13     //先找到到达系统时间为0的数据，把它放在第一位，因为系统会第一时间执行这个作业
 14 
 15     for(i=0;i<recordjobnum;i++)
 16 
 17     {
 18 
 19            if(job[i].arrtime==0)
 20 
 21            {
 22 
 23                       arrtemp=job[0].arrtime;
 24 
 25                          reqtemp=job[0].reqtime;
 26 
 27                 strcpy(nametemp,job[0].jobname);
 28 
 29                          job[0].arrtime=job[i].arrtime;
 30 
 31                          job[0].reqtime=job[i].reqtime;
 32 
 33                          strcpy(job[0].jobname,job[i].jobname);
 34 
 35                          job[i].arrtime=arrtemp;
 36 
 37                          job[i].reqtime=reqtemp;
 38 
 39                 strcpy(job[i].jobname,nametemp);
 40 
 41            }
 42 
 43     }
 44 
 45     printf("**********先来先服务算法FCFS***************
");
 46 
 47     //从第二位开始根据系统运行时间的长短进行排序，此排序为升序
 48 
 49     for(i=1;i<recordjobnum;i++)
 50 
 51     {
 52 
 53            for(j=i+1;j<recordjobnum;j++)
 54 
 55            {
 56 
 57                   if(job[i].arrtime>job[j].arrtime)
 58 
 59                   {
 60 
 61                          arrtemp=job[i].arrtime;
 62 
 63                          reqtemp=job[i].reqtime;
 64 
 65                 strcpy(nametemp,job[i].jobname);
 66 
 67                          job[i].arrtime=job[j].arrtime;
 68 
 69                          job[i].reqtime=job[j].reqtime;
 70 
 71                          strcpy(job[i].jobname,job[j].jobname);
 72 
 73                          job[j].arrtime=arrtemp;
 74 
 75                          job[j].reqtime=reqtemp;
 76 
 77                 strcpy(job[j].jobname,nametemp);
 78 
 79                   }
 80 
 81            }
 82 
 83     }
 84 
 85    
 86 
 87            printf("
 作业名  作业到达时间   作业运行所需要时间
");
 88 
 89     for(i=0;i<recordjobnum;i++)
 90 
 91        printf("
%3s%12.2f%18.2f",job[i].jobname,job[i].arrtime,job[i].reqtime);
 92 
 93     //计算作业到达系统的时间，作业周转时间，带权作业周转时间
 94 
 95     for(i=0;i<recordjobnum;i++)
 96 
 97     {
 98 
 99            job[i].finishtime=systime+job[i].reqtime;
100 
101            systime=job[i].finishtime;
102 
103            job[i].TAtime=job[i].finishtime-job[i].arrtime;
104 
105            job[i].TAWtime=job[i].TAtime/job[i].reqtime;
106 
107     }
108 
109     printf("
作业名 作业到达时间 作业完成时间 运行时间 作业周转时间 带权作业周转时间
");
110 
111     for(i=0;i<recordjobnum;i++)
112 
113            printf("%4s%12.2f%12.2f%12.2f%12.2f%12.2f
",job[i].jobname,job[i].arrtime,job[i].finishtime,job[i].reqtime,job[i].TAtime,job[i].TAWtime);
114 
115    
116 
117     for(i=0;i<recordjobnum;i++)
118 
119     {
120 
121            sum=sum+job[i].TAtime;//计算作业周转时间的总和
122 
123            sum1=sum1+job[i].TAWtime;//计算作业带权周转时间的总和
124 
125     }
126 
127     tim[recordATA].ATAtime=sum/recordjobnum;//计算该算法所需的平均周转时间
128 
129     tim[recordATA].ATAWtime=sum1/recordjobnum;//计算该算法所需的平均带权周转时间
130 
131     printf("
平均周转时间是=%.2f
",tim[recordATA].ATAtime);
132 
133     printf("平均带权周转时间是=%.2f
",tim[recordATA].ATAWtime);
134 
135     recordATA=recordATA+1;
136 
137     systime=0;
138 
139 }
140 
141  
142 
143 void SJF()//最短作业优先算法SJF
144 
145 {
146 
147     int i,j;
148 
149     float sum=0,sum1=0;
150 
151     float arrtemp,reqtemp;
152 
153     char nametemp[10];
154 
155     for(i=0;i<recordjobnum;i++)
156 
157     {
158 
159            //先找到到达系统时间为0的数据，把它放在第一位，因为系统会第一时间执行这个作业
160 
161            if(job[i].arrtime==0)
162 
163            {
164 
165                       arrtemp=job[0].arrtime;
166 
167                          reqtemp=job[0].reqtime;
168 
169                 strcpy(nametemp,job[0].jobname);
170 
171                          job[0].arrtime=job[i].arrtime;
172 
173                          job[0].reqtime=job[i].reqtime;
174 
175                          strcpy(job[0].jobname,job[i].jobname);
176 
177                          job[i].arrtime=arrtemp;
178 
179                          job[i].reqtime=reqtemp;
180 
181                 strcpy(job[i].jobname,nametemp);
182 
183            }
184 
185     }
186 
187     printf("**********最短作业优先算法SJF*************
");
188 
189     //从第二位开始根据系统运行时间的长短进行排序，此排序为升序
190 
191     for(i=1;i<recordjobnum;i++)
192 
193     {
194 
195            for(j=i+1;j<recordjobnum;j++)
196 
197            {
198 
199                   if(job[i].reqtime>job[j].reqtime)
200 
201                   {
202 
203                          arrtemp=job[i].arrtime;
204 
205                          reqtemp=job[i].reqtime;
206 
207                 strcpy(nametemp,job[i].jobname);
208 
209                          job[i].arrtime=job[j].arrtime;
210 
211                          job[i].reqtime=job[j].reqtime;
212 
213                          strcpy(job[i].jobname,job[j].jobname);
214 
215                          job[j].arrtime=arrtemp;
216 
217                          job[j].reqtime=reqtemp;
218 
219                 strcpy(job[j].jobname,nametemp);
220 
221                   }
222 
223            }
224 
225     }    
226 
227     printf("
 作业名 作业到达时间 作业运行所需要时间
");
228 
229     for(i=0;i<recordjobnum;i++)
230 
231        printf("
%4s%12.2f%12.2f",job[i].jobname,job[i].arrtime,job[i].reqtime);
232 
233     //计算作业到达系统的时间，作业周转时间，带权作业周转时间
234 
235     for(i=0;i<recordjobnum;i++)
236 
237     {
238 
239            job[i].finishtime=systime+job[i].reqtime;
240 
241            systime=job[i].finishtime;
242 
243            job[i].TAtime=job[i].finishtime-job[i].arrtime;
244 
245            job[i].TAWtime=job[i].TAtime/job[i].reqtime;
246 
247     }
248 
249     printf("
作业名 作业到达时间 作业完成时间 运行时间 作业周转时间 带权作业周转时间
");
250 
251     for(i=0;i<recordjobnum;i++)
252 
253            printf("%4s%12.2f%12.2f%12.2f%12.2f%12.2f
",job[i].jobname,job[i].arrtime,job[i].finishtime,job[i].reqtime,job[i].TAtime,job[i].TAWtime);
254 
255    
256 
257     for(i=0;i<recordjobnum;i++)
258 
259     {
260 
261            sum=sum+job[i].TAtime;//计算作业周转时间的总和
262 
263            sum1=sum1+job[i].TAWtime;//计算作业带权周转时间的总和
264 
265     }
266 
267     tim[recordATA].ATAtime=sum/recordjobnum;//计算该算法所需的平均周转时间
268 
269     tim[recordATA].ATAWtime=sum1/recordjobnum;//计算该算法所需的平均带权周转时间
270 
271     printf("
平均周转时间是:%f
",tim[recordATA].ATAtime);
272 
273     printf("平均带权周转时间是:%f
",tim[recordATA].ATAWtime);
274 
275     recordATA=recordATA+1; 
276 
277     systime=0;
278 
279 }
280 
281  
282 
283 void HRRF()//最高响应比HRRF
284 
285 {
286 
287     int i,j;
288 
289     float arrtemp,reqtemp,hrrftemp;
290 
291     float sum=0,sum1=0;
292 
293     char nametemp[10];
294 
295     sort();//根据到达系统时间进行排序
296 
297     printf("
作业名 作业到达时间 作业运行所需要时间
");
298 
299     for(i=0;i<recordjobnum;i++)
300 
301        printf("
%4s%12.2f%12.2f",job[i].jobname,job[i].arrtime,job[i].reqtime);
302 
303     //计算作业的最高响应比
304 
305     for(i=1;i<recordjobnum;i++)
306 
307     {
308 
309            printf("
作业名 最高响应比
");
310 
311            for(j=i;j<recordjobnum;j++)
312 
313            {
314 
315                 job[j].hrrf=1+(job[j-1].reqtime-job[j].arrtime+job[j-1].arrtime)/job[j].reqtime;
316 
317              printf("%4s%12.2f
",job[j].jobname,job[j].hrrf);
318 
319            }
320 
321     }
322 
323     //根据最高响应比进行降序处理
324 
325     for(i=1;i<recordjobnum;i++)
326 
327     {
328 
329            for(j=i+1;j<recordjobnum;j++)
330 
331            {
332 
333                   if(job[i].hrrf<job[j].hrrf)
334 
335                   {
336 
337                          arrtemp=job[i].arrtime;
338 
339                          reqtemp=job[i].reqtime;
340 
341                 strcpy(nametemp,job[i].jobname);
342 
343                 hrrftemp=job[i].hrrf;
344 
345                          job[i].arrtime=job[j].arrtime;
346 
347                          job[i].reqtime=job[j].reqtime;
348 
349                          job[i].hrrf=job[j].hrrf;
350 
351                          strcpy(job[i].jobname,job[j].jobname);
352 
353                          job[j].arrtime=arrtemp;
354 
355                          job[j].reqtime=reqtemp;
356 
357                          job[j].hrrf=hrrftemp;
358 
359                 strcpy(job[j].jobname,nametemp);
360 
361                   }
362 
363            }
364 
365     }
366 
367        //计算作业到达系统的时间，作业周转时间，带权作业周转时间
368 
369     for(i=0;i<recordjobnum;i++)
370 
371     {
372 
373            job[i].finishtime=systime+job[i].reqtime;
374 
375            systime=job[i].finishtime;
376 
377            job[i].TAtime=job[i].finishtime-job[i].arrtime;
378 
379            job[i].TAWtime=job[i].TAtime/job[i].reqtime;
380 
381     }
382 
383     printf("
作业名 作业到达时间 作业完成时间 运行时间 作业周转时间 带权作业周转时间
");
384 
385     for(i=0;i<recordjobnum;i++)
386 
387            printf("%4s%12.2f%12.2f%12.2f%12.2f%12.2f
",job[i].jobname,job[i].arrtime,job[i].finishtime,job[i].reqtime,job[i].TAtime,job[i].TAWtime);
388 
389    
390 
391     for(i=0;i<recordjobnum;i++)
392 
393     {
394 
395            sum=sum+job[i].TAtime;//计算作业周转时间的总和
396 
397            sum1=sum1+job[i].TAWtime;//计算作业带权周转时间的总和
398 
399     }
400 
401     tim[recordATA].ATAtime=sum/recordjobnum;//计算该算法所需的平均周转时间
402 
403     tim[recordATA].ATAWtime=sum1/recordjobnum;//计算该算法所需的平均带权周转时间
404 
405     printf("
平均周转时间是=%.2f
",tim[recordATA].ATAtime);
406 
407     printf("平均带权周转时间是=%.2f
",tim[recordATA].ATAWtime);
408 
409     recordATA=recordATA+1;
410 
411     systime=0;
412 
413 }