实验二作业调度模拟程序

一、目的和要求

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 #include "h.h"
  2 
  3 struct job
  4 {
  5     char name[10];
  6     char status;
  7 
  8     int id;
  9     int arrtime;
 10     int reqtime;
 11     int startime;
 12     int finitime;
 13     int waittime;
 14 
 15     int TAtime;
 16     float TAWtime;
 17     float prio;
 18 }jobarr[24], jobfin[24], job[24];
 19 
 20 int systime = 0;
 21 int intarr, intfin, intjob;
 22 
 23 int readFile()
 24 {
 25     int m=0;
 26     int i=0;
 27     FILE *fp;     //定义文件指针
 28     fp=fopen("3.txt","r");  //打开文件
 29     if(fp==NULL)
 30     {
 31         printf("File open error !
");
 32         exit(0);
 33     }
 34     printf("
 id    作业到达时间     作业运行所需要时间
");
 35     while(!feof(fp))
 36     {
 37         fscanf(fp,"%d%d%d",&job[i].id,&job[i].arrtime,&job[i].reqtime);  //fscanf()函数将数据读入
 38         printf("
%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);  //输出到屏幕
 39         i++;
 40     };
 41 
 42     if(fclose(fp))     //关闭文件
 43     {
 44         printf("Can not close the file !
");
 45         exit(0);
 46     }
 47     m=i-1;
 48     return m;
 49 
 50 }
 51 
 52 //伪随机数产生器
 53 int randNumber()
 54 {
 55     int i,n;
 56   //  srand((unsigned)time(0));  //参数seed是rand()的种子，用来初始化rand()的起始值。
 57     //输入作业数
 58     n=rand()%23+5;
 59     for(i=0; i<=n; i++)
 60     {
 61         job[i].id=i;
 62         //作业到达时间
 63         job[i].arrtime=rand()%29+1;
 64         //作业运行时间
 65         job[i].reqtime=rand()%7+1;
 66     }
 67     printf("
 id    作业到达时间     作业运行所需要时间
");
 68     for(i=0; i<=n; i++)
 69     {
 70         printf("
%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);
 71     }
 72     return n;
 73 
 74 }
 75 
 76 void sort(int n, int x)
 77 {
 78     int i, j;
 79     for(i = 0 + x; i <= n; i++)
 80     {
 81         for(j = i+1; j <= n; j++)
 82         {
 83             if(job[i].arrtime > job[j].arrtime)
 84             {
 85                 struct job tmp = job[i];
 86                 job[i] = job[j];
 87                 job[j] = tmp;
 88             }
 89         }
 90     }
 91 }
 92 
 93 void show(int n)
 94 {
 95     int i = 0;
 96 
 97     
 98     
 99     printf("
 id    作业到达时间     作业完成时间    运行时间    作业周转时间    带权周转时间
");
100     for(i=0; i<=n; i++)
101     {
102         printf("
%3d%12d%15d%15d%15d%15.2f",job[i].id, job[i].arrtime, job[i].finitime, job[i].reqtime, job[i].TAtime, job[i].TAWtime);
103     }
104 
105     int allTAtime = 0;
106     float allTAWtime = 0;
107     for(i = n; i <= n; i++)
108     {
109         allTAtime += job[i].TAtime;
110         allTAWtime += job[i].TAWtime;
111     }
112 
113     printf("
平均作业周转时间：%0.2f", (float)allTAtime / n);
114     printf("
平均作业带权周转时间：%0.2f
", allTAWtime / n);
115 }
116 
117 void FCFS(int n)
118 {
119     int i;
120 
121     printf("
		**********先来先服务FCFS***********

");
122     sort(n, 0);
123 
124     printf("
 id    作业到达时间     作业运行所需要时间
");
125 
126     for(i = 0; i <= n; i++)
127     {
128             printf("
%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);
129     }
130 
131     for(i = 0; i <= n; i++)
132             {
133                 if(i == 0 || job[i-1].finitime < job[i].arrtime)
134                 {
135                     job[i].finitime = job[i].arrtime + job[i].reqtime;
136                     job[i].TAtime = job[i].finitime - job[i].arrtime;
137                     job[i].TAWtime = (float)job[i].TAtime / job[i].reqtime;
138                 }
139                 else
140                 {
141                     job[i].finitime = job[i-1].finitime + job[i].reqtime;
142                     job[i].TAtime = job[i].finitime - job[i].arrtime;
143                     job[i].TAWtime = (float)job[i].TAtime / job[i].reqtime;
144                 }
145             }
146 
147     show(n);
148 
149 }
150 
151 void SJF(int n)
152 {
153     int i = 0, j = 0, x = 0;
154 
155     printf("
		**********短作业优先SJF***********

");
156 
157     for(x = 0; x <= n; x++)
158     {
159         if(x == 0)
160         {
161             sort(n, 0);
162             printf("
 id    作业到达时间     作业运行所需要时间
");
163 
164             for(i = 0; i <= n; i++)
165             {
166                 printf("
%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);
167             }
168 
169             for(i = 0; i <= n; i++)
170             {
171                 if(i == 0 || job[i-1].finitime < job[i].arrtime)
172                 {
173                     job[i].finitime = job[i].arrtime + job[i].reqtime;
174                     job[i].TAtime = job[i].finitime - job[i].arrtime;
175                     job[i].TAWtime = (float)job[i].TAtime / job[i].reqtime;
176                 }
177                 else
178                 {
179                     job[i].finitime = job[i-1].finitime + job[i].reqtime;
180                     job[i].TAtime = job[i].finitime - job[i].arrtime;
181                     job[i].TAWtime = (float)job[i].TAtime / job[i].reqtime;
182                 }
183             }
184 
185         }
186         else if(job[x-1].finitime <= job[x].arrtime)
187         {
188             sort(n, x);
189         }
190         else
191         {
192             for(i = x; i <= n; i++)
193                 {
194                     for(j = i+1; j <= n; j++)
195                     {
196                         if(job[i].reqtime > job[j].reqtime)
197                         {
198                             struct job tmp = job[i];
199                             job[i] = job[j];
200                             job[j] = tmp;
201                         }
202                     }
203                 }
204         }
205     }
206 
207     show(n);
208 
209 }
210 
211 void HRRF(int n)
212 {
213     int i,  x;
214 
215     printf("
		**********响应比最高者优先HRRF算法***********

");
216 
217     for(x = 0; x <= n; x++)
218     {
219         if(x == 0)
220         {
221             sort(n, 0);
222             printf("
 id    作业到达时间     作业运行所需要时间
");
223 
224             for(i = 0; i <= n; i++)
225             {
226                 printf("
%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);
227             }
228 
229             for(i = 0; i <= n; i++)
230             {
231                 if(i == 0 || job[i-1].finitime < job[i].arrtime)
232                 {
233                     job[i].finitime = job[i].arrtime + job[i].reqtime;
234                     job[i].TAtime = job[i].finitime - job[i].arrtime;
235                     job[i].TAWtime = (float)job[i].TAtime / job[i].reqtime;
236                 }
237                 else
238                 {
239                     job[i].finitime = job[i-1].finitime + job[i].reqtime;
240                     job[i].TAtime = job[i].finitime - job[i].arrtime;
241                     job[i].TAWtime = (float)job[i].TAtime / job[i].reqtime;
242                 }
243             }
244 
245             for(i = x; i <= n; i++)
246             {
247                 job[i].waittime = job[x-1].finitime - job[i].arrtime;
248                 job[i].prio = 1 + (float)job[i].waittime / (float)job[i].reqtime;
249 
250             }
251 
252             for(i = x; i <= n; i++)
253             {
254                 for(int j = i+1; j <= n; j++)
255                 {
256                     if(job[i].prio < job[j].prio)
257                     {
258                         struct job tmp = job[i];
259                         job[i] = job[j];
260                         job[j] = tmp;
261                     }
262                 }
263             }
264 
265         }
266         else if(job[x-1].finitime <= job[x].arrtime)
267         {
268             sort(n, x);
269         }
270         else
271         {
272             for(i = x; i <= n; i++)
273             {
274                 job[i].waittime = job[x-1].finitime - job[i].arrtime;
275                 job[i].prio = 1 + (float)job[i].waittime / (float)job[i].reqtime;
276 
277             }
278 
279             printf("  
id    最高响应比
");
280             for(i = x; i <= n; i++)
281                 printf("%3d%12.2f
", job[i].id, job[i].prio);
282         }
283     }
284 
285     show(n);
286 }

 1 #include "h.h"
 2 
 3 int main(void)
 4 {
 5     int n = 0;
 6     int option = 0;
 7 
 8     printf("		********************************
");
 9     printf("		    1. 调用文本写入数据
");
10     printf("		    2. 调用随机数产生的数据
");
11     printf("		    3. 调用自己填入模拟数据
");
12     printf("		********************************

");
13 
14     printf("	请选择菜单项：");
15     scanf("%d", &option);
16     switch(option)
17     {
18     case 1:
19         n = readFile();
20         break;
21     case 2:
22         n = randNumber();
23         break;
24     case 3:
25         break;
26     }
27 
28     printf("


		********************************
");
29     printf("		    1. FCFS算法调度
");
30     printf("		    2. SJF算法调度
");
31     printf("		    3. HRRF算法调度
");
32     printf("		    4. 调用系统清屏
");
33     printf("		    0. 退出算法调度
");
34     printf("		********************************

");
35 
36     printf("	请选择菜单项：");
37     scanf("%d", &option);
38     switch(option)
39     {
40     case 1:
41         FCFS(n);
42         break;
43     case 2:
44         SJF(n);
45         break;
46     case 3:
47         HRRF(n);
48         break;
49     }
50 
51     
52 
53     return 0;
54 }

#ifndef H_H

#define H_H

#include <stdio.h>
#include <stdlib.h>

int readFile();
int randNumber();
void FCFS(int n);
void SJF(int n);
void HRRF(int n);

#endif H_H