作业调度

实验原理

（1）定义程序控制块的结构体和程序工作时间的结构体，JCB可以包含以下信息：作业名、提交（到达）时间、所需的运行时间、所需的资源、作业状态、链指针等等。程序工作时间包括作业运行时刻，作业完成时刻，周转时间，带权周转时间。

（2）主程序默认采用的算法是先来先服务，当选择另外两种算法时通过主程序去调用这种作业调度算法，分别是SJF，HRN。

（3）通过构造进程输入input()，进程运行结果输出output()，disp(),以及使整个程序正常运行的函数块等，通过主函数调用方法函数的想法来实现作业调度。

（4）在对程序控制块的访问和调用通过链表指针的形式，进行调用各种作业调度算法。在作业输入后，会显示输入的内容，并把每一个作业运行的状态都能在程序中体现出来。

  1 #include<stdio.h>
  2 #include <stdlib.h>
  3 #include <conio.h>
  4 #define getpch(type) (type*)malloc(sizeof(type))    //为进程创建一个空间
  5  
  6 struct worktime{
  7     float Tb;             //作业运行时刻
  8     float Tc;             //作业完成时刻
  9     float Ti;             //周转时间
 10     float Wi;            //带权周转时间
 11 };
 12  
 13 struct jcb {              
 14     char name[10];        //作业名
 15     float arrivetime;        //作业到达时间
 16     float runtime;        //作业所需的运行时间
 17     char resource;        //所需资源
 18     float Rp;             //后备作业响应比
 19     char state;           //作业状态
 20     int worked_time;      //已运行时间   
 21     struct worktime wt;
 22     int need_time;       //要求运行时间
 23     int flag;             //进程结束标志
 24     struct jcb* link;     //链指针
 25 }*ready=NULL,*p;
 26  
 27 typedef struct jcb JCB;//重命名结构体
 28 float T=0;
 29 int N;
 30 JCB *front,*rear;       
 31  
 32 void sort()     
 33 {
 34     JCB *first, *second;
 35     int insert=0;  //插入数
 36     if((ready==NULL)||((p->arrivetime)<(ready->arrivetime)))  
 37     {
 38         p->link=ready;
 39         ready=p;
 40         T=p->arrivetime;
 41         p->Rp=1;
 42     }
 43     else
 44     {
 45         first=ready;
 46         second=first->link;
 47         while(second!=NULL)
 48         {
 49             if((p->arrivetime)<(second->arrivetime))
 50             {
 51                 p->link=second;
 52                 first->link=p;
 53                 second=NULL;
 54                 insert=1;
 55             }
 56             else
 57             {
 58                 first=first->link;
 59                 second=second->link;
 60             }
 61         }
 62         if (insert==0) first->link=p;
 63     }
 64 }
 65  
 66 void SJFget()
 67 {
 68     JCB *front,*mintime,*rear;
 69     int ipmove=0;
 70     mintime=ready;
 71     rear=mintime->link;
 72     while(rear!=NULL)
 73     {
 74         if ((rear!=NULL)&&(T>=rear->arrivetime)&&(mintime->runtime)>(rear->runtime))
 75         {
 76             front=mintime;
 77             mintime=rear;
 78             rear=rear->link;
 79             ipmove=1;
 80         }
 81         else
 82             rear=rear->link;
 83     }
 84     if (ipmove==1)
 85     {
 86         front->link=mintime->link;
 87         mintime->link=ready;
 88     }
 89     ready=mintime;
 90 }
 91  
 92 void HRNget()
 93 {
 94     JCB *front,*mintime,*rear;
 95     int ipmove=0;
 96     mintime=ready;
 97     rear=mintime->link;
 98     while(rear!=NULL)
 99         if ((rear!=NULL)&&(T>=rear->arrivetime)&&(mintime->Rp)<(rear->Rp))
100         {
101             front=mintime;
102             mintime=rear;
103             rear=rear->link;
104             ipmove=1;
105         }
106         else
107             rear=rear->link;
108     if (ipmove==1){
109         front->link=mintime->link;
110         mintime->link=ready;
111     }
112     ready=mintime;
113 }
114  
115 void creatJCB() //为每个作业创建一个JCB并初始化形成一个循环链队列
116 {   
117     JCB *p,*l;
118     int i=0;
119     l = (JCB *)malloc(sizeof(JCB));
120     printf("\n 请输入作业的个数:");
121     scanf("%d",&N);
122     printf("\n 作业号No.%d:\n",i);
123     printf("\n请输入作业的名字:");
124     scanf("%s",l->name);
125     printf("\n请输入作业的时间:");
126     scanf("%d",&l->need_time);
127     l->state = 'r';          //作业初始状态为就绪(即准备状态)
128     l->worked_time = 0;
129     l->link=NULL;
130     l->flag=0;
131     front=l;
132     for(i =1;i<N;i++)
133     {
134         p = (JCB *)malloc(sizeof(JCB));
135         printf("\n 作业号No.%d:\n",i);
136         printf("\n请输入作业的名字:");
137         scanf("%s",p->name);
138         printf("\n请输入作业的时间:");
139         scanf("%d",&p->need_time);
140         p->state='r';
141         p->worked_time=0;
142         p->flag=0;
143         l->link=p;
144         l=l->link;
145     }
146     rear=l;rear->link=front;
147 }  
148  
149 void output()//进程输出函数
150 {  
151     int j;
152     printf("name runtime needtime state\n");
153     for(j=1;j<=N;j++)
154     {   printf(" %-4s\t%-4d\t%-4d\t%-c\n",front->name,front->worked_time,front->need_time,front->state);
155         front=front->link;
156     }
157     printf("\n");
158 }
159  
160 int judge(JCB *p) //判断所有进程运行结束
161 {
162     int flag=1,i;
163     for(i=0;i<N;i++)
164     {
165         if(p->state!='e')
166         {
167             flag = 0;
168             break;}
169         p=p->link;
170     }
171     return flag;
172 }
173  
174 //作业输入 
175 void input()
176 {
177     int i,num;
178     printf("\n 请输入作业的个数:");
179     scanf("%d",&num);
180     for(i=0;i<num;i++)
181     {
182         printf("\n 作业号No.%d:\n",i);
183         p=getpch(JCB);
184         printf("\n 输入作业名:");
185         scanf("%s",p->name);
186         printf("\n 输入作业到达时刻:");
187         scanf("%f",&p->arrivetime);
188         printf("\n 输入作业运行时间:");
189         scanf("%f",&p->runtime);
190         printf("\n");
191         p->state='w';
192         p->link=NULL;
193         sort();
194     }
195 }
196  
197 int space()
198 {
199     int l=0; JCB* jr=ready;
200     while(jr!=NULL)
201     {
202         l++;
203         jr=jr->link;
204     }
205     return(l);
206 }
207  
208 void disp(JCB* jr,int select)
209 {
210     if (select==3) printf("\n 作业   到达时间   服务时间   响应比   运行时刻   完成时刻   周转时间  带权周转时间 \n");
211     else printf("\n 作业   到达时间   服务时间   运行时刻   完成时刻   周转时间  带权周转时间 \n");
212     printf(" %s\t",jr->name);
213     printf(" %.2f\t  ",jr->arrivetime);
214     printf("  %.2f\t",jr->runtime);
215     if (select==3&&p==jr) printf("|%.2f    ",jr->Rp);
216     if (p==jr){
217         printf("%.2f\t ",jr->wt.Tb);
218         printf("  %.2f   ",jr->wt.Tc);
219         printf("  %.2f\t",jr->wt.Ti);
220         printf("  %.2f",jr->wt.Wi);
221     }
222     printf("\n");
223 }
224  
225 int destroy()
226 {
227     printf("\n 作业 [%s] 已完成.\n",p->name);
228     free(p);
229     return(1);
230 }
231  
232 void check(int select)
233 {
234     JCB* jr;
235     printf("\n **** 当前正在运行的作业是:%s",p->name);
236     disp(p,select);
237     jr=ready;
238     printf("\n ****当前就绪队列状态为:");
239     while(jr!=NULL)
240     {
241         jr->Rp=(jr->runtime+T-jr->arrivetime)/jr->runtime;
242         disp(jr,select);
243         jr=jr->link;
244     }
245     destroy();
246 }
247  
248 void running(JCB* jr)
249 {
250     if (T>=jr->arrivetime) jr->wt.Tb=T;
251     else jr->wt.Tb=jr->arrivetime;
252     jr->wt.Tc=jr->wt.Tb+jr->runtime;
253     jr->wt.Ti=jr->wt.Tc-jr->arrivetime;
254     jr->wt.Wi=jr->wt.Ti/jr->runtime;
255     T=jr->wt.Tc;
256 }
257  
258 int main()
259 {
260     int select=0,len,h=0;
261     float sumTi=0,sumWi=0;
262     printf("\t---*****************---\n");
263     printf("请选择作业调度算法的方式:\n");
264     printf("\t1.FCFS 2.SJF 3.HRN \n");
265     printf("\t---*****************---\n");
266     printf("请输入作业调度算法序号(1-3):");
267     scanf("%d",&select);
268 
269     input();   //调用输入函数
270     len=space();
271    
272      
273     while((len!=0)&&(ready!=NULL))
274     {
275         h++;
276         printf(" 执行第%d个作业 \n",h);
277         p=ready;
278         ready=p->link;
279         p->link=NULL;
280         p->state='R';
281         running(p);
282         sumTi+=p->wt.Ti;
283         sumWi+=p->wt.Wi;
284         check(select); //与所选择的算法比较，调用void check(int select)
285         if (select==2&&h<len-1) SJFget();
286         if (select==3&&h<len-1) HRNget();
287         printf("\n 按任意一键继续......");
288         getchar();
289         getchar();
290     }
291     printf("\n 作业已经完成.\n");
292     printf("\t 此组作业的平均周转时间：%.2f\n",sumTi/h);
293     printf("\t 此组作业的带权平均周转时间：%.2f\n",sumWi/h);
294     getchar();
295 }

程序运行结果

总结与体会

通过本次实验，感觉自己对之前数据结构的算法和语法掌握得不是很好，虽然会定义结构体比较熟练，但是对于在程序中调用结构体就不太理解，导致多次出错，并通过查阅相关资料，然后不断修改，由于之前的数据结构学得不扎实，所以写代码遇到很多困难，往后要多回顾旧知识，特别是语法结构和新接触的几种作业调度的算法思想。