作业调度

实验二作业调度模拟程序

一、目的和要求

　　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 struct jcb{
  3     char name[10];
  4     char status;
  5     
  6     int id;
  7     int arrtime;//到达时间
  8     int reqtime;//需求时间
  9     int startime;//开始时间
 10     int waittime;//等待时间
 11     int finitime;//结束时间
 12     
 13     float  responseratio; //响应比
 14     float TAtime,TAWtime;//周转时间，带权周转时间
 15     float prio;
 16 }   jobarr[24],jobfin[24],job[24];
 17 
 18 void fcfs(int n); 
 19 void fcfs2(int n); 
 20 void sjf(int n);
 21 void sjf2(int n);
 22 void hrrn(int n);
 23 void hrrn2(int n);
 24 void result(int n); 
 25 void result2(int n); 
 26 
 27 int systime=0;
 28 int intarr,intfin,intjob;  /*到达作业个数，完成作业个数，未到达作业个数*/
 29 int n;
 30 void sort(){
 31     struct jcb p;
 32     int n;
 33     int j;
 34     int i;
 35     printf("经按到达时间排序后，未达到队列是
");
 36     printf("        作业名    到达时间  要求服务时间
");
 37     for(i=0;i<n-1;i++)
 38     {
 39         for(j=i+1;j<n;j++)
 40         {
 41             if(job[i].arrtime>job[j].arrtime)
 42             {
 43                 p=job[i];
 44                 job[i]=job[j];
 45                 job[j]=p;
 46             }
 47         }
 48     }
 49     for(i=0;i<n;i++)
 50     {
 51         printf("N %s     %d         %d         %d
",i+1,job[i].name,job[i].arrtime,job[i].reqtime);
 52     }
 53     
 54     printf("
                  现在系统时间 %d:
",systime);
 55 }
 56 void main(){
 57     int a,b;//输入的选择
 58     
 59     struct jcb p;
 60     int j;
 61     int i;
 62     //printf("1:采用先来先服务 (FCFS) 调度算法
2:采用短作业优先 (SJF) 调度算法
3:采用响应比高者优先 (HRRN) 调度算法
");
 63    // scanf("%d",&a);
 64     while(1){
 65     printf("	***************************************
");
 66     printf("	1.调用文本写入数据
");
 67     printf("	2.调用伪随机数的产生数据
");
 68     printf("	3.调用自己输入模拟数据
");
 69     printf("	***************************************
");
 70     printf("
	请选择菜单项:");
 71     scanf("%d",&a);
 72     switch(a){
 73     case 1:
 74     ReadFile();
 75     break;
 76     case 2:
 77     Pseudo_random_number();
 78     break;
 79     case 3:
 80     WriteFile();
 81     break;
 82     default:
 83     printf("error
");
 84     break;
 85     }
 86 
 87     }
 88 }
 89 void fcfs(int n){ 
 90     struct jcb p;
 91     int j;
 92     int i;
 93     for(i=0;i<n-1;i++)
 94     {
 95         for(j=i+1;j<n;j++)
 96         {
 97             if(job[i].arrtime>job[j].arrtime)
 98             {
 99                 p=job[i];
100                 job[i]=job[j];
101                 job[j]=p;
102             }
103         }
104     }
105     for(i=0;i<n;i++){ 
106         if(i==0){ //第一个进程 
107         job[i].TAtime=job[i].reqtime; 
108         job[i].finitime=job[i].arrtime+job[i].reqtime; 
109         } 
110         else if(job[i].arrtime>job[i-1].finitime){//第i个进程到达系统时，第i-1个进程已运行完毕 
111         job[i].TAtime=job[i].reqtime; 
112         job[i].finitime=job[i].arrtime+job[i].reqtime; 
113         } 
114         else{//第i个进程到达系统时，第i-1个进程未运行完毕 
115         job[i].TAtime=job[i].reqtime+job[i-1].finitime-job[i].arrtime; 
116         job[i].finitime=job[i].arrtime+job[i].TAtime; 
117         } 
118         job[i].TAWtime=job[i].TAtime*1.0/job[i].reqtime; 
119     } 
120    
121 } 
122 void fcfs2(int n){
123    struct jcb p;
124     int j;
125     int i;
126     for(i=0;i<n-1;i++)
127     {
128         for(j=i+1;j<n;j++)
129         {
130             if(job[i].arrtime>job[j].arrtime)
131             {
132                 p=job[i];
133                 job[i]=job[j];
134                 job[j]=p;
135             }
136         }
137     }
138     for(i=0;i<n+1;i++){ 
139         if(i==0){ //第一个进程 
140         job[i].TAtime=job[i].reqtime; 
141         job[i].finitime=job[i].arrtime+job[i].reqtime; 
142         } 
143         else if(job[i].arrtime>job[i-1].finitime){//第i个进程到达系统时，第i-1个进程已运行完毕 
144         job[i].TAtime=job[i].reqtime; 
145         job[i].finitime=job[i].arrtime+job[i].reqtime; 
146         } 
147         else{//第i个进程到达系统时，第i-1个进程未运行完毕 
148         job[i].TAtime=job[i].reqtime+job[i-1].finitime-job[i].arrtime; 
149         job[i].finitime=job[i].arrtime+job[i].TAtime; 
150         } 
151         job[i].TAWtime=job[i].TAtime*1.0/job[i].reqtime; 
152     } 
153 }
154 
155 void sjf(int n){
156   int i; 
157   int j;
158   struct jcb p;
159    for(i=0;i<n-1;i++)
160     {
161         for(j=i+1;j<n;j++)
162         {
163             if(job[i].reqtime>job[j].reqtime)
164             {
165                 p=job[i];
166                 job[i]=job[j];
167                 job[j]=p;
168             }
169         }
170     }
171     for(i=0;i<n;i++){ 
172         if(i==0){ //第一个进程 
173         job[i].TAtime=job[i].reqtime; 
174         job[i].finitime=job[i].arrtime+job[i].reqtime; 
175         } 
176         else if(job[i].arrtime>job[i-1].finitime){//第i个进程到达系统时，第i-1个进程已运行完毕 
177         job[i].TAtime=job[i].reqtime; 
178         job[i].finitime=job[i].arrtime+job[i].reqtime; 
179         } 
180         else{//第i个进程到达系统时，第i-1个进程未运行完毕 
181         job[i].TAtime=job[i].reqtime+job[i-1].finitime-job[i].arrtime; 
182         job[i].finitime=job[i].arrtime+job[i].TAtime; 
183         } 
184         job[i].TAWtime=job[i].TAtime*1.0/job[i].reqtime; 
185     } 
186 }
187 void sjf2(int n){
188   int i; 
189   int j;
190   struct jcb p;
191    for(i=0;i<n;i++)
192     {
193         for(j=i+1;j<n+1;j++)
194         {
195             if(job[i].reqtime>job[j].reqtime)
196             {
197                 p=job[i];
198                 job[i]=job[j];
199                 job[j]=p;
200             }
201         }
202     }
203     for(i=0;i<n+1;i++){ 
204         if(i==0){ //第一个进程 
205         job[i].TAtime=job[i].reqtime; 
206         job[i].finitime=job[i].arrtime+job[i].reqtime; 
207         } 
208         else if(job[i].arrtime>job[i-1].finitime){//第i个进程到达系统时，第i-1个进程已运行完毕 
209         job[i].TAtime=job[i].reqtime; 
210         job[i].finitime=job[i].arrtime+job[i].reqtime; 
211         } 
212         else{//第i个进程到达系统时，第i-1个进程未运行完毕 
213         job[i].TAtime=job[i].reqtime+job[i-1].finitime-job[i].arrtime; 
214         job[i].finitime=job[i].arrtime+job[i].TAtime; 
215         } 
216         job[i].TAWtime=job[i].TAtime*1.0/job[i].reqtime; 
217     } 
218 }
219 void hrrn(int n)
220 {
221 int i; 
222   int j;
223   struct jcb p;
224    for(i=0;i<n-1;i++)
225     {
226         for(j=i+1;j<n;j++)
227         {
228             if(job[i].arrtime>job[j].arrtime)
229             {
230                 p=job[i];
231                 job[i]=job[j];
232                 job[j]=p;
233             }
234         }
235    }     
236    for(i=0;i<n;i++){
237        job[0].startime=job[0].arrtime;
238        job[i].finitime=job[i].startime+job[i].reqtime;//结束时间    
239        job[i+1].startime=job[i].finitime;
240        job[i].waittime=job[i].startime-job[i].arrtime;//等待时间
241        job[i].TAtime=job[i].finitime-job[i].arrtime;//周转时间
242        job[i].responseratio=job[i].TAtime/job[i].reqtime;//响应比
243        job[i].TAWtime=job[i].TAtime*1.0/job[i].reqtime;
244    } 
245    for(i=1;i<n-1;i++)
246    {
247        for(j=i+1;j<n;j++)
248           {
249              if(job[i].responseratio<job[j].responseratio)//比较后面来的作业的响应比
250              {
251                  p=job[i];
252                  job[i]=job[j];
253                  job[j]=p;
254              }
255           }
256    }
257 
258 }
259 void hrrn2(int n)
260 {
261 int i; 
262   int j;
263   struct jcb p;
264    for(i=0;i<n;i++)
265     {
266         for(j=i+1;j<n+1;j++)
267         {
268             if(job[i].arrtime>job[j].arrtime)
269             {
270                 p=job[i];
271                 job[i]=job[j];
272                 job[j]=p;
273             }
274         }
275    }     
276    for(i=0;i<n+1;i++){
277        job[0].startime=job[0].arrtime;
278        job[i].finitime=job[i].startime+job[i].reqtime;//结束时间    
279        job[i+1].startime=job[i].finitime;
280        job[i].waittime=job[i].startime-job[i].arrtime;//等待时间
281        job[i].TAtime=job[i].finitime-job[i].arrtime;//周转时间
282        job[i].responseratio=job[i].TAtime/job[i].reqtime;//响应比
283        job[i].TAWtime=job[i].TAtime*1.0/job[i].reqtime;
284    } 
285    for(i=1;i<n-1;i++)
286    {
287        for(j=i+1;j<n;j++)
288           {
289              if(job[i].responseratio<job[j].responseratio)//比较后面来的作业的响应比
290              {
291                  p=job[i];
292                  job[i]=job[j];
293                  job[j]=p;
294              }
295           }
296    }
297 
298 }
299 void result(int n){ 
300     int i; 
301     float averTAtime; 
302     float averTAWtime; 
303     int sum_TAtime=0; 
304     float sum_TAWtime=0.00; 
305     printf("
作业名	到达系统时间	CPU所需时间/h	结束时间	周转时间/h
"); 
306     for(i=0;i<n;i++){ 
307     printf("%s  	%d     		%d   		%d       	%.2f
",job[i].name,job[i].arrtime,job[i].reqtime,job[i].finitime,job[i].TAtime); 
308        
309     sum_TAtime=sum_TAtime+job[i].TAtime; 
310     sum_TAWtime=sum_TAWtime+job[i].TAWtime; 
311     } 
312     averTAtime=sum_TAtime*1.0/n; 
313     averTAWtime=sum_TAWtime*1.00/n; 
314     printf("
平均周转时间：%.2f
",averTAtime); 
315     printf("平均带权周转时间：%.2f
",averTAWtime); 
316 } 
317 void result2(int n){
318         int i; 
319     float averTAtime; 
320     float averTAWtime; 
321     int sum_TAtime=0; 
322     float sum_TAWtime=0.00; 
323     printf("
作业名	到达系统时间	CPU所需时间/h	结束时间	周转时间/h
"); 
324     for(i=1;i<n+1;i++){ 
325     printf("%s  	%d     		%d   		%d       	%.2f
",job[i].name,job[i].arrtime,job[i].reqtime,job[i].finitime,job[i].TAtime); 
326        
327     sum_TAtime=sum_TAtime+job[i].TAtime; 
328     sum_TAWtime=sum_TAWtime+job[i].TAWtime; 
329     } 
330     averTAtime=sum_TAtime*1.0/n; 
331     averTAWtime=sum_TAWtime*1.00/n; 
332     printf("
平均周转时间：%.2f
",averTAtime); 
333     printf("平均带权周转时间：%.2f
",averTAWtime); 
334 }
335 int ReadFile()
336 {
337     int b;
338     int n=0;
339     int i=1;
340     FILE *fp;     //定义文件指针
341     fp=fopen("3.txt","r");  //打开文件
342     if(fp==NULL)
343     {
344         printf("File open error !
");
345         exit(0);
346     }
347     printf("
 id    作业到达时间     作业运行所需要时间
");
348     while(!feof(fp))
349     {
350         fscanf(fp,"%s%d%d",&job[i].name,&job[i].arrtime,&job[i].reqtime);  //fscanf()函数将数据读入
351         printf("%s%12d%15d
",job[i].name,job[i].arrtime,job[i].reqtime);  //输出到屏幕
352         i++;
353     };
354 
355     if(fclose(fp))     //关闭文件
356     {
357         printf("Can not close the file !
");
358         exit(0);
359     }
360     n=i-1;
361     printf("
**********************************");
362     printf("
1:采用先来先服务 (FCFS) 调度算法
2:采用短作业优先 (SJF) 调度算法
3:采用响应比高者优先 (HRRN) 调度算法
");
363     scanf("%d",&b);
364     switch(b){
365     case 1:
366     //    sort(n);
367         fcfs2(n);
368         result2(n);
369         break;
370     case 2:
371         sjf2(n);
372         result2(n);
373         break;
374     case 3:
375         hrrn2(n);
376         result2(n);
377         break;
378     }
379    return 0;
380 }
381 
382 //伪随机数产生器
383 int Pseudo_random_number()
384 {
385     int i,n,b;
386     srand((unsigned)time(0));  //参数seed是rand()的种子，用来初始化rand()的起始值。
387     //输入作业数
388     n=rand()%23+5;
389     for(i=1; i<=n; i++)
390     {
391         job[i].id=i;
392         //作业到达时间
393         job[i].arrtime=rand()%29+1;
394         //作业运行时间
395         job[i].reqtime=rand()%7+1;
396     }
397     printf("
 id    作业到达时间     作业运行所需要时间
");
398     for(i=1; i<=n; i++)
399     {
400         printf("
%d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);
401     }
402     return n;
403     printf("
**********************************");
404     printf("
1:采用先来先服务 (FCFS) 调度算法
2:采用短作业优先 (SJF) 调度算法
3:采用响应比高者优先 (HRRN) 调度算法
");
405     scanf("%d",&b);
406     switch(b){
407     case 1:
408         fcfs2(n);
409         result2(n);
410         break;
411     case 2:
412         sjf2(n);
413         result2(n);
414         break;
415     case 3:
416         hrrn2(n);
417         result2(n);
418         break;
419     }
420     return 0;
421 }
422 int WriteFile(){
423     int n;
424     int b;
425     struct jcb p;
426     int j;
427     int i;
428     printf("请输入作业个数:");
429     scanf("%d",&n);
430     for(i=0;i<n;i++)
431     {
432         printf("
");
433         printf("第%d个作业:
",i+1);
434         printf("输入作业名:",i+1);
435         scanf("%s",&job[i].name);
436         printf("到达时间:",i+1);
437         scanf("%d",&job[i].arrtime);
438         printf("要求服务时间:",i+1);
439         scanf("%d",&job[i].reqtime);
440     }
441 
442     printf("1:采用先来先服务 (FCFS) 调度算法
2:采用短作业优先 (SJF) 调度算法
3:采用响应比高者优先 (HRRN) 调度算法
");
443     scanf("%d",&b);
444     if(b==1){
445     fcfs(n);
446     result(n);
447     }
448     if(b==2){
449     sjf(n);
450     result(n);
451     }
452     if(b==3){
453     hrrn(n);
454     result(n);
455     }
456 }