锐客网

  1. 首页 > it技术 > >

FCFS，SJF，HRRN算法实现作业调度

【FCFS，SJF，HRRN算法实现作业调度】实验原理
（1）定义程序控制块的结构体和程序工作时间的结构体，JCB可以包含以下信息：作业名、提交（到达）时间、所需的运行时间、所需的资源、作业状态、链指针等等。程序工作时间包括作业运行时刻，作业完成时刻，周转时间，带权周转时间。
（2）主程序默认采用的算法是先来先服务，当选择另外两种算法时通过主程序去调用这种作业调度算法，分别是SJF，HRN。
（3）通过构造进程输入input()，进程运行结果输出output()，disp(),以及使整个程序正常运行的函数块等，通过主函数调用方法函数的想法来实现作业调度。
（4）在对程序控制块的访问和调用通过链表指针的形式，进行调用各种作业调度算法。在作业输入后，会显示输入的内容，并把每一个作业运行的状态都能在程序中体现出来。

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

SJF
FCFS，SJF，HRRN算法实现作业调度
文章图片

HRRN
FCFS，SJF，HRRN算法实现作业调度
文章图片

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

    推荐阅读


    上一篇：如何交叉编译|如何交叉编译 linux kernel 内核

    下一篇：手帐‖我喜欢现在的生活，和那个努力的我