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

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

专业：商业软件工程姓名：黄冠锋学号：201406114134

一、目的和要求

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	模拟程序的输入如何设计更方便、结果输出如何呈现更好？

根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。

三、实验环境

可以采用TC，也可以选用Windows下的利用各种控件较为方便的VB，VC等可视化环境。也可以自主选择其他实验环境。

四、 主要程序和运行结果

FCFS：

void FCFS(struct jcb temp[24],int count)//先到先服务算法
{
    int i=0;
    float averageruntime=0;
    float averageruntimerun=0;
    sort(temp,count);
    temp[i].startime =temp[i].arrtime;
    temp[i].finitime =temp[i].reqtime +temp[i].startime ;
    temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
    temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
    averageruntime=temp[i].TAtime;
    averageruntimerun=temp[i].TAWtime;
    for(i=1;i<count;i++)
    {
        temp[i].startime =temp[i-1].finitime ;
        temp[i].finitime =temp[i].reqtime +temp[i].startime ;
        temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
        temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
        averageruntime+=temp[i].TAtime;
        averageruntimerun+=temp[i].TAWtime;
    }
    printf("作业名 到达时间 开始时间 要求服务时间 调度时间 完成时间 周转时间 带权周转时间
");
    for(i=0;i<count;i++)
    {
        printf("N%d	%s	%d		%d	%d	%d	%0.2f	%0.2f
",i+1,job[i].name ,job[i].arrtime ,job[i].reqtime,job[i].startime ,job[i].finitime ,job[i].TAtime ,job[i].TAWtime  );
    }
    printf("平均周转时间是：%0.2f
",averageruntime/count);
    printf("平均周转时间是：%0.2f
",averageruntimerun/count);
}

SJF：

void SJF(struct jcb temp[24],int count)//短作业优先算法
{
     
    int i=0,j;
    struct jcb t;
    float averageruntime=0;
    float averageruntimerun=0;
    sort(temp,count);
    temp[i].startime =temp[i].arrtime;
    temp[i].finitime =temp[i].reqtime +temp[i].startime ;
    temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
    temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
    averageruntime=temp[i].TAtime;
    averageruntimerun=temp[i].TAWtime;
    for(i=1;i<count-1;i++) 
    {                               
        for(j=i+1;j<count;j++)
        { 
            if(temp[j].reqtime< temp[i].reqtime)
            {
                t=temp[j];
                temp[j]=temp[i];
                temp[i]=t;
            }
        }
    }
    for(i=1;i<count;i++)
    {
        temp[i].startime =temp[i-1].finitime ;
        temp[i].finitime =temp[i].reqtime +temp[i].startime ;
        temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
        temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
        averageruntime+=temp[i].TAtime;
        averageruntimerun+=temp[i].TAWtime;
    }
    printf("作业名 到达时间 开始时间 要求服务时间 调度时间 完成时间 周转时间 带权周转时间
");
    for(i=0;i<count;i++)
    {
        printf("N%d	%s	%d		%d	%d	%d	%0.2f	%0.2f
",i+1,job[i].name ,job[i].arrtime ,job[i].reqtime,job[i].startime ,job[i].finitime ,job[i].TAtime ,job[i].TAWtime  );
    }
    printf("平均周转时间是：%0.2f
",averageruntime/count);
    printf("平均周转时间是：%0.2f
",averageruntimerun/count);
}

HRRN：

void HRRN(struct jcb temp[24],int count)//响应比高者优先算法
{
    int i=0,j;
    struct jcb t;
    float averageruntime=0;
    float averageruntimerun=0;
    sort(temp,count);
    temp[i].startime =temp[i].arrtime;
    temp[i].finitime =temp[i].reqtime +temp[i].startime ;
    temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
    temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
    temp[i].waittime=temp[i].startime-temp[i].arrtime;
    temp[i].rp=temp[i].TAtime/temp[i].reqtime;
    averageruntime=temp[i].TAtime;
    averageruntimerun=temp[i].TAWtime;
    for(i=1;i<count;i++)
    {
        temp[i].startime =temp[i-1].finitime ;
        temp[i].finitime =temp[i].reqtime +temp[i].startime ;
        temp[i].waittime=temp[i].startime-temp[i].arrtime;
        temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
        temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
        temp[i].rp=temp[i].TAtime/temp[i].reqtime;
    }
    for(i=1;i<count-1;i++) 
    {                               
        for(j=i+1;j<count;j++)
        { 
            if(temp[j].rp< temp[i].rp)
            {
                t=temp[j];
                temp[j]=temp[i];
                temp[i]=t;
            }

        }
    }
    for(i=1;i<count;i++)
    {
        temp[i].startime =temp[i-1].finitime ;
        temp[i].finitime =temp[i].reqtime +temp[i].startime ;
        temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
        temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
        averageruntime+=temp[i].TAtime;
        averageruntimerun+=temp[i].TAWtime;
    }
    printf("作业名 到达时间 开始时间 要求服务时间 调度时间 完成时间 周转时间 带权周转时间
");
    for(i=0;i<count;i++)
    {
        printf("N%d	%s	%d		%d	%d	%d	%0.2f	%0.2f
",i+1,job[i].name ,job[i].arrtime ,job[i].reqtime,job[i].startime ,job[i].finitime ,job[i].TAtime ,job[i].TAWtime  );
    }
    printf("平均周转时间是：%0.2f
",averageruntime/count);
    printf("平均周转时间是：%0.2f
",averageruntimerun/count);
}

五、 实验总结

通过这次编写作业调度程序实验，让我充分地了解到系统是如何处理运行作业的，以及加深了对作业调度算法的理解。

全部代码：

  1 #include<stdio.h>
  2 #include<ctype.h>
  3 #include<string.h>
  4 #include <stdlib.h>
  5 #include <time.h>
  6 #include<iostream> 
  7 using namespace std;
  8 
  9 struct jcb
 10 {
 11     char name[10];//作业名         
 12     char status;
 13     
 14 
 15     int arrtime;//到达时间
 16     int reqtime;//要求服务时间
 17     int startime;//调度时间
 18     int finitime;//完成时间
 19     float waittime;//等待时间
 20     float TAtime,TAWtime;//周转时间 带权周转时间
 21     float rp;
 22 }jobarr[24],jobfin[24],job[24];
 23 
 24 int ReadFile()
 25 {
 26     int m=0;
 27     int i=0;
 28     FILE *fp;     //定义文件指针
 29     fp=fopen("3.txt","r");  //打开文件
 30     if(fp==NULL)
 31     {
 32         printf("File open error !
");
 33 //        exit(0);
 34     }
 35     printf("
 id    作业到达时间     作业运行所需要时间
");
 36     while(!feof(fp))
 37     {
 38         fscanf(fp,"%s%d%d",job[i].name,&job[i].arrtime,&job[i].reqtime);  //fscanf()函数将数据读入
 39         printf("
%3s%12d%15d
",job[i].name,job[i].arrtime,job[i].reqtime);  //输出到屏幕
 40         i++;
 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 int Pseudo_random_number()
 52 {
 53     int i,n;
 54     srand((unsigned)time(0));  //参数seed是rand()的种子，用来初始化rand()的起始值。
 55     //输入作业数
 56     n=rand()%23+5;
 57     for(i=0; i<=n; i++)
 58     {
 59       // job[i].name=i;
 60        sprintf(job[i].name,"%d",i);
 61         //作业到达时间
 62         job[i].arrtime=rand()%29+1;
 63         //作业运行时间
 64        job[i].reqtime=rand()%7+1;
 65     }
 66     printf("
 作业名     作业到达时间     作业运行所需要时间");  // id     
 67     for(i=0; i<=n; i++)
 68     {
 69         printf("
  %-d%12d%15d",i+1,job[i].arrtime,job[i].reqtime);    //%3d	        ,job[i].name
 70     }
 71     printf("
");
 72     return n;
 73 }
 74 int own_input()
 75 {
 76         int count,i;
 77         printf("请输入作业个数：");
 78         scanf("%d",&count);
 79         for(i=0;i<count;i++)
 80         {
 81             printf("第%d个作业：
",i+1);
 82             printf("输入作业名：");
 83             scanf("%s",job[i].name);
 84             printf("到达时间：" );
 85             scanf("%d",&job[i].arrtime);
 86             printf("要求服务时间：");
 87             scanf("%d",&job[i].reqtime );
 88             printf("
");
 89         }
 90         return count;
 91 }
 92 void sort(struct jcb temp[24],int count)
 93 {
 94     int i,j;
 95     struct jcb t;
 96     for(i=0;i<count-1;i++) //按进程到达时间的先后排序
 97     {                               //如果两个进程同时到达，按在屏幕先输入的先运行
 98         for(j=i+1;j<count;j++)
 99         { 
100             if(temp[j].arrtime< temp[i].arrtime)
101             {
102                 t=temp[j];
103                 temp[j]=temp[i];
104                 temp[i]=t;
105             }
106 
107         }
108     }
109     
110 }
111 void FCFS(struct jcb temp[24],int count)//先到先服务算法
112 {
113     int i=0;
114     float averageruntime=0;
115     float averageruntimerun=0;
116     sort(temp,count);
117     temp[i].startime =temp[i].arrtime;
118     temp[i].finitime =temp[i].reqtime +temp[i].startime ;
119     temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
120     temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
121     averageruntime=temp[i].TAtime;
122     averageruntimerun=temp[i].TAWtime;
123     for(i=1;i<count;i++)
124     {
125         temp[i].startime =temp[i-1].finitime ;
126         temp[i].finitime =temp[i].reqtime +temp[i].startime ;
127         temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
128         temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
129         averageruntime+=temp[i].TAtime;
130         averageruntimerun+=temp[i].TAWtime;
131     }
132     printf("作业名 到达时间 开始时间 要求服务时间 调度时间 完成时间 周转时间 带权周转时间
");
133     for(i=0;i<count;i++)
134     {
135         printf("N%d	%s	%d		%d	%d	%d	%0.2f	%0.2f
",i+1,job[i].name ,job[i].arrtime ,job[i].reqtime,job[i].startime ,job[i].finitime ,job[i].TAtime ,job[i].TAWtime  );
136     }
137     printf("平均周转时间是：%0.2f
",averageruntime/count);
138     printf("平均周转时间是：%0.2f
",averageruntimerun/count);
139 }
140 
141 void SJF(struct jcb temp[24],int count)//短作业优先算法
142 {
143      
144     int i=0,j;
145     struct jcb t;
146     float averageruntime=0;
147     float averageruntimerun=0;
148     sort(temp,count);
149     temp[i].startime =temp[i].arrtime;
150     temp[i].finitime =temp[i].reqtime +temp[i].startime ;
151     temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
152     temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
153     averageruntime=temp[i].TAtime;
154     averageruntimerun=temp[i].TAWtime;
155     for(i=1;i<count-1;i++) 
156     {                               
157         for(j=i+1;j<count;j++)
158         { 
159             if(temp[j].reqtime< temp[i].reqtime)
160             {
161                 t=temp[j];
162                 temp[j]=temp[i];
163                 temp[i]=t;
164             }
165         }
166     }
167     for(i=1;i<count;i++)
168     {
169         temp[i].startime =temp[i-1].finitime ;
170         temp[i].finitime =temp[i].reqtime +temp[i].startime ;
171         temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
172         temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
173         averageruntime+=temp[i].TAtime;
174         averageruntimerun+=temp[i].TAWtime;
175     }
176     printf("作业名 到达时间 开始时间 要求服务时间 调度时间 完成时间 周转时间 带权周转时间
");
177     for(i=0;i<count;i++)
178     {
179         printf("N%d	%s	%d		%d	%d	%d	%0.2f	%0.2f
",i+1,job[i].name ,job[i].arrtime ,job[i].reqtime,job[i].startime ,job[i].finitime ,job[i].TAtime ,job[i].TAWtime  );
180     }
181     printf("平均周转时间是：%0.2f
",averageruntime/count);
182     printf("平均周转时间是：%0.2f
",averageruntimerun/count);
183 }
184 
185 void HRRN(struct jcb temp[24],int count)//响应比高者优先算法
186 {
187     int i=0,j;
188     struct jcb t;
189     float averageruntime=0;
190     float averageruntimerun=0;
191     sort(temp,count);
192     temp[i].startime =temp[i].arrtime;
193     temp[i].finitime =temp[i].reqtime +temp[i].startime ;
194     temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
195     temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
196     temp[i].waittime=temp[i].startime-temp[i].arrtime;
197     temp[i].rp=temp[i].TAtime/temp[i].reqtime;
198     averageruntime=temp[i].TAtime;
199     averageruntimerun=temp[i].TAWtime;
200     for(i=1;i<count;i++)
201     {
202         temp[i].startime =temp[i-1].finitime ;
203         temp[i].finitime =temp[i].reqtime +temp[i].startime ;
204         temp[i].waittime=temp[i].startime-temp[i].arrtime;
205         temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
206         temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
207         temp[i].rp=temp[i].TAtime/temp[i].reqtime;
208     }
209     for(i=1;i<count-1;i++) 
210     {                               
211         for(j=i+1;j<count;j++)
212         { 
213             if(temp[j].rp< temp[i].rp)
214             {
215                 t=temp[j];
216                 temp[j]=temp[i];
217                 temp[i]=t;
218             }
219 
220         }
221     }
222     for(i=1;i<count;i++)
223     {
224         temp[i].startime =temp[i-1].finitime ;
225         temp[i].finitime =temp[i].reqtime +temp[i].startime ;
226         temp[i].TAtime =temp[i].finitime -temp[i].arrtime ;
227         temp[i].TAWtime =temp[i].TAtime/temp[i].reqtime;
228         averageruntime+=temp[i].TAtime;
229         averageruntimerun+=temp[i].TAWtime;
230     }
231     printf("作业名 到达时间 开始时间 要求服务时间 调度时间 完成时间 周转时间 带权周转时间
");
232     for(i=0;i<count;i++)
233     {
234         printf("N%d	%s	%d		%d	%d	%d	%0.2f	%0.2f
",i+1,job[i].name ,job[i].arrtime ,job[i].reqtime,job[i].startime ,job[i].finitime ,job[i].TAtime ,job[i].TAWtime  );
235     }
236     printf("平均周转时间是：%0.2f
",averageruntime/count);
237     printf("平均周转时间是：%0.2f
",averageruntimerun/count);
238 }
239 
240 int main()
241 { 
242     int i,count,select,s,sel;
243     printf("************************************
");
244     printf("   1.调用文本写入数据
");
245     printf("   2.调用伪随机数的产生数据
");
246     printf("   3.调用自己输入模拟数据
");
247     printf("************************************

");
248     printf("请选择菜单项：
");
249     scanf("%d",&s);
250     if(s==1)
251         ReadFile();
252     else if(s==2)
253         Pseudo_random_number();
254     else if(s==3)
255         own_input();
256     printf("作业的数目：");
257     scanf("%d",&count);
258     do{
259     printf("-----------------请选择作业调度算法------------------
");
260     printf("1:采用先来先服务 (FCFS) 调度算法
2:采用短作业优先 (SJF) 调度算法
3:采用响应比高者优先 (HRRN) 调度算法
");
261     printf("请选择：");
262     scanf("%d",&select);
263 
264     while(select<1||select>3)
265     {
266         printf("输入有误，请重新输入:");
267         scanf("%d",&select);
268         
269     }
270     printf("
经按到达时间排序后，未达到队列是
");
271     printf("	作业名	到达时间	要求服务时间
");
272     for(i=0;i<count;i++)
273     {
274         printf("N%d	%s	%d		%d
",i+1,job[i].name ,job[i].arrtime ,job[i].reqtime);
275     }
276     
277    
278     if(select==1)
279     {
280            printf("------先来先服务 (FCFS) 调度算法------
");
281         FCFS(job,count);
282 
283     }
284     else if(select==2)
285     {
286             printf("------短作业优先 (SJF)调度算法------
");
287             SJF(job,count);
288        
289     }
290     else if(select==3)
291     {
292         printf("------响应比高者优先 (HRRN)调度算法------
");
293         HRRN(job,count);
294        
295     }
296     printf("1.继续作业调度算法  0.结束
");
297     printf("请选择1或0：");
298     scanf("%d",&sel);
299     }while(sel==1);
300  
301     return 0;
302 }

View Code