操作系统作业调度--操作系统

一、目的和要求

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 #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 void menu()
 19 {
 20     printf("__________***************_________
");
 21     printf("|     1.调用文本写入数据         |
");
 22     printf("|________________________________|
");
 23     printf("|     2.调用伪随机数的产生数据   |
");
 24     printf("|________________________________|
");
 25     printf("|     3.调用自己输入模拟数据     |
");
 26     printf("__________***************_________
");
 27 }
 28 //调度算法菜单
 29 void menu0()
 30 {
 31    printf("
________********_______
");
 32     printf("|      1.FCFS算法调度   |
");
 33     printf("|_______________________|
");
 34     printf("|      2.SJF算法调度    |
");
 35     printf("|_______________________|
");
 36     printf("|      3.HRRF算法调度   |
");
 37     printf("|_______________________|
");
 38     printf("|      0.退出算法调度   |
");
 39     printf("________********_______
");
 40 }
 41 //短作业优先排序
 42 void sort(int n)
 43 {
 44     int i,j; 
 45     struct jcb temp;
 46     for(i=2;i<n;i++) 
 47     for(j=i+1;j<=n;j++) 
 48     if(jobarr[i].reqtime>jobarr[j].reqtime) //根据最短的要求服务时间排序
 49     { 
 50        temp=jobarr[i]; 
 51        jobarr[i]=jobarr[j]; 
 52        jobarr[j]=temp; 
 53     } 
 54 }
 55 //先到先服务排序
 56 void sort0(int n)
 57 {
 58     int i,j; 
 59     struct jcb temp;
 60     for(i=2;i<n;i++) 
 61     for(j=i+1;j<=n;j++) 
 62     if(job[i].arrtime>job[j].arrtime) //根据到达时间排序
 63     { 
 64        temp=job[i]; 
 65        job[i]=job[j]; 
 66        job[j]=temp; 
 67     } 
 68 }
 69 //自己输入模拟数据
 70 void shoushu()
 71 {
 72         int n;
 73     printf("作业个数:");
 74     scanf("%d",&n);
 75     for(int i=1;i<=n;i++)
 76     {
 77         printf("
第%d个作业:",i+1);
 78         printf("
输入id:");
 79         scanf("%d",&job[i].id);
 80         printf("到达时间:");
 81         scanf("%d",&job[i].arrtime);
 82         printf("要求服务时间:");
 83         scanf("%d",&job[i].reqtime);
 84         jobarr[i]=job[i];
 85     }
 86 }
 87 //文本写入数据
 88 int ReadFile()
 89 {
 90     int m=0;
 91     int i=1;
 92     FILE *fp;     //定义文件指针
 93     fp=fopen("4.txt","r");  //打开文件
 94     if(fp==NULL)
 95     {
 96         printf("File open error !
");
 97         exit(0);
 98     }
 99     printf("
 id    作业到达时间     作业运行所需要时间
");
100     while(!feof(fp))
101     {
102         fscanf(fp,"%d%d%d",&job[i].id,&job[i].arrtime,&job[i].reqtime);  //fscanf()函数将数据读入
103         printf("
%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);  //输出到屏幕
104         i++;
105     };
106 
107     if(fclose(fp))     //关闭文件
108     {
109         printf("Can not close the file !
");
110         exit(0);
111     }
112     m=i-1;
113     return m;
114 
115 }
116 //伪随机数的产生数据
117 int Pseudo_random_number()
118 {
119     int i,n;
120     srand((unsigned)time(0));  //参数seed是rand()的种子，用来初始化rand()的起始值。
121     //输入作业数
122     n=rand()%23+5;
123     for(i=1; i<=n; i++)
124     {
125         job[i].id=i;
126         //作业到达时间
127         job[i].arrtime=rand()%29+1;
128         //作业运行时间
129         job[i].reqtime=rand()%7+1;
130     }
131     printf("
 id    作业到达时间     作业运行所需要时间
");
132     for(i=1; i<=n; i++)
133     {
134         printf("
%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);
135     }
136     return n;
137 
138 }
139 //先来先服务算法FCFS
140 void FCFS()
141 {
142     int i=1,j=1;
143     float sumTA=0,sumTAW=0;
144     printf("-----------先来先服务算法FCFS-------------
");
145     printf("
 id    作业到达时间     作业运行所需要时间
");
146     while(job[j].id!=NULL)
147     {
148         printf("
%3d%12d%15d",job[j].id,job[j].arrtime,job[j].reqtime);  //输出到屏幕
149         j++;
150     }
151     sort0(j-1);
152         printf("

 id    作业到达时间   作业完成时间   运行时间  作业周转时间  带权作业周转时间
");
153         while(job[i].id!=NULL)
154     {
155         if(i==1)  //第一个作业先到达，先被调度
156         {
157             job[i].startime=job[i].arrtime;
158         }
159         else   //其他作业被调度
160         {
161             if(job[i-1].finitime>=job[i].arrtime)  //如果上一个作业的完成时间大于下一个到达时间，则下一个开始时间为上一个作业的完成时间
162                 job[i].startime=job[i-1].finitime;
163             else
164                 job[i].startime=job[i].arrtime;   //否则下一个开始时间即它的到达时间
165         }
166         job[i].finitime=job[i].startime+job[i].reqtime; //计算完成时间
167         job[i].TAtime=job[i].finitime-job[i].arrtime; //计算周转时间
168         job[i].TAWtime=job[i].TAtime/job[i].reqtime;   //计算带权周转时间
169         sumTA+=job[i].TAtime;
170         sumTAW+=job[i].TAWtime;
171         printf("
%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); 
172         i++;
173     }
174         printf("
平均作业周转时间= %.2lf",sumTA/(i-1));
175         printf("
平均带权作业周转时间= %.2lf",sumTAW/(i-1));
176 }
177 //最短作业优先算法SJF
178 void SJF()
179 {
180     int i=1,j=1;
181     float sumTA=0,sumTAW=0;
182     printf("-----------最短作业优先算法SJF-------------
");
183     printf("
 id    作业到达时间     作业运行所需要时间
");
184     while(job[j].id!=NULL)
185     {
186         printf("
%3d%12d%15d",job[j].id,job[j].arrtime,job[j].reqtime);  //输出到屏幕
187         jobarr[j]=job[j];
188         j++;
189     }
190     sort(j-1);
191     printf("

 id    作业到达时间   作业完成时间   运行时间  作业周转时间  带权作业周转时间
");
192     while(jobarr[i].id!=NULL)
193     {
194         if(i==1)
195         {
196             jobarr[i].startime=jobarr[i].arrtime;
197         }
198         else
199         {
200             if(jobarr[i-1].finitime>=jobarr[i].arrtime)
201                 jobarr[i].startime=jobarr[i-1].finitime;
202             else
203                 jobarr[i].startime=jobarr[i].arrtime;
204         }
205         jobarr[i].finitime=jobarr[i].startime+jobarr[i].reqtime;
206         jobarr[i].TAtime=jobarr[i].finitime-jobarr[i].arrtime;
207         jobarr[i].TAWtime=jobarr[i].TAtime/jobarr[i].reqtime;
208         sumTA+=jobarr[i].TAtime;
209         sumTAW+=jobarr[i].TAWtime;
210         printf("
%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); 
211         i++;
212     }
213         printf("
平均作业周转时间= %.2lf",sumTA/(i-1));
214         printf("
平均带权作业周转时间= %.2lf",sumTAW/(i-1));
215 }
216 //最高响应比排序
217 void sort1(int n,int k)
218 {
219     int i,j; 
220     struct jcb temp;
221     for(i=k;i<n;i++) 
222     for(j=i+1;j<=n;j++) 
223     if(jobfin[i].prio<jobfin[j].prio) 
224     { 
225        temp=jobfin[i]; 
226        jobfin[i]=jobfin[j]; 
227        jobfin[j]=temp; 
228     } 
229 }
230 //响应比最高者优先HRRF算法
231 void HRRF()
232 {
233     int i=1,j=1,k=1;
234     float sumTA=0,sumTAW=0;
235     printf("-----------响应比最高者优先HRRF算法-------------
");
236     printf("
 id    作业到达时间     作业运行所需要时间
");
237     while(job[j].id!=NULL)
238     {
239         printf("%3d%12d%15d
",job[j].id,job[j].arrtime,job[j].reqtime);  //输出到屏幕
240         jobfin[j]=job[j];
241         j++;
242     }
243     while(jobfin[k].id!=NULL)
244     {
245         i=k;  
246         if(k==1)
247         {
248             jobfin[i].startime=jobfin[i].arrtime;
249             jobfin[i].finitime=jobfin[i].startime+jobfin[i].reqtime;
250             jobfin[i].TAtime=jobfin[i].finitime-jobfin[i].arrtime;
251             jobfin[i].TAWtime=jobfin[i].TAtime/jobfin[i].reqtime;
252         }
253         else
254         {
255         printf("
id   最高响应比
");
256         while(jobfin[i].id!=NULL)
257         {
258             if(jobfin[k-1].finitime>=job[i].arrtime)
259             {
260                 jobfin[i].startime=jobfin[k-1].finitime;
261                 jobfin[i].prio=(jobfin[i].startime-jobfin[i].arrtime)/(jobfin[i].reqtime/1.0)+1;
262             }
263             else
264             {
265                 jobfin[i].startime=0;    
266                   jobfin[i].prio=0;
267             }
268             i++;
269         }
270         sort1(j-1,k);
271         for(i=k;i<j;i++)
272             printf("%3d%10.2lf
",jobfin[i].id,jobfin[i].prio);
273         jobfin[k].finitime=jobfin[k-1].finitime+jobfin[k].reqtime;
274         jobfin[k].TAtime=jobfin[k].finitime-jobfin[k].arrtime;
275         jobfin[k].TAWtime=jobfin[k].TAtime/jobfin[k].reqtime;
276         }
277         k++;
278     }
279         printf("

 id    作业到达时间   作业完成时间   运行时间  作业周转时间  带权作业周转时间
");
280         for(i=1;i<j;i++)
281         {
282             printf("
%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); 
283             sumTA+=jobfin[i].TAtime;
284             sumTAW+=jobfin[i].TAWtime;
285         }
286         printf("
平均作业周转时间= %.2lf",sumTA/(i-1));
287         printf("
平均带权作业周转时间= %.2lf",sumTAW/(i-1));
288 }
289 void main0()
290 {
291     int tmp;
292     while(1)
293     {
294     menu0();
295     printf("
请选择菜单项:");
296     scanf("%d",&tmp);
297     switch (tmp)
298     {
299     case 1:
300         FCFS();
301         break;
302     case 2:
303         SJF();
304         break;
305     case 3:
306         HRRF();
307         break;
308     case 0:
309         return;
310     }
311     }
312 }
313 main()
314 {
315     int tmp;
316     while(1)
317     {
318     menu();
319     printf("
请选择菜单项:");
320     scanf("%d",&tmp);
321     switch (tmp)
322     {
323     case 1:
324         ReadFile();
325         break;
326     case 2:
327         Pseudo_random_number();
328         break;
329     case 3:    
330         shoushu();
331         break;
332     }
333     main0();
334     printf("
");
335     }
336 }

View Code