FCFS，SJF，HRRN算法实现作业调度
实验原理
（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(" 作业号No.%d:\n",i); 183 p=getpch(JCB); 184 printf(" 输入作业名:"); 185 scanf("%s",p->name); 186 printf(" 输入作业到达时刻:"); 187 scanf("%f",&p->arrivetime); 188 printf(" 输入作业运行时间:"); 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 free(p); 228 return(1); 229 } 230 231 void check(int select) 232 { 233 JCB* jr; 234 printf(" 是 :%s",p->name);//当前执行的作业是 235 disp(p,select); 236 jr=ready; 237 destroy(); 238 } 239 240 void running(JCB* jr) 241 { 242 if (T>=jr->arrivetime) jr->wt.Tb=T; 243 else jr->wt.Tb=jr->arrivetime; 244 jr->wt.Tc=jr->wt.Tb+jr->runtime; 245 jr->wt.Ti=jr->wt.Tc-jr->arrivetime; 246 jr->wt.Wi=jr->wt.Ti/jr->runtime; 247 T=jr->wt.Tc; 248 } 249 250 int main() 251 { 252 int select=0,len,h=0; 253 float sumTi=0,sumWi=0; 254 printf("请选择作业调度算法的方式:\n"); 255 printf("\t1.FCFS 2.SJF 3.HRN \n"); 256 printf("请输入作业调度算法序号(1-3):"); 257 scanf("%d",&select); 258 259 input(); //调用输入函数 260 len=space(); 261 262 263 while((len!=0)&&(ready!=NULL)) 264 { 265 h++; 266 printf(" 第%d个执行作业 ",h); 267 p=ready; 268 ready=p->link; 269 p->link=NULL; 270 p->state=\'R\'; 271 running(p); 272 sumTi+=p->wt.Ti; 273 sumWi+=p->wt.Wi; 274 check(select); //与所选择的算法比较，调用void check(int select) 275 if (select==2&&h<len-1) SJFget(); 276 if (select==3&&h<len-1) HRNget(); 277 getchar(); 278 getchar(); 279 } 280 printf(" 作业已经完成.\n"); 281 printf("\t 此组作业的平均周转时间：%.2f\n",sumTi/h); 282 printf("\t 此组作业的带权平均周转时间：%.2f\n",sumWi/h); 283 getchar(); 284 }
程序运行结果 FCFS
SJF
HRRN
总结与体会
通过本次实验，感觉自己对之前数据结构的算法和语法掌握得不是很好，虽然会定义结构体比较熟练，但是对于在程序中调用结构体就不太理解，导致多次出错，并通过查阅相关资料，然后不断修改，由于之前的数据结构学得不扎实，所以写代码遇到很多困难，往后要多回顾旧知识，特别是语法结构和新接触的几种作业调度的算法思想。
版权声明：本文为clcbk原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。