作业调度算法.docx

作业调度算法操作系统实验报告 题目：作业调度算法班级：网络工程姓名：朱锦涛学号： E31314037 一、实验目的 用代码实现页面调度算法，即先来先服务调度算法 、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = /要求服务时间 三、实验内容 源程序： #include<stdio.h> #include<stdlib.h> #include<time.h> struct work int id; intarrive_time; intwork_time; int wait; float priority; ; typedefstructsjf_work struct work s_work; /数据域 structsjf_work * pNext; /指针域 NODE,*PNODE; void FCFS; void SJF; voidshowmenu; boolIs_empty(PNODE pHead); intcnt_work(PNODE pHead); PNODE do_work(PNODE pHead,int *w_finish_time,inti); void show(int *w_finish_time,inti,PNODEq,int *w_rel_time); void HRRN; PNODE priorit(PNODE pHead); void do_work_1(PNODE pHead,int *w_finish_time,inti); int main int choice; /设置选择数 showmenu; /显示菜单 scanf("%d",&choice); while(choice != 0) /选择算法 switch(choice) case 1 : printf("您选择的是先来先服务算法:n"); FCFS; break; case 2 : printf("您选择的是短作业优先算法:n"); SJF; break; case 3 : printf("您选择的是高响应比优先调度算法n"); HRRN; break; default: printf("请重新选择！"); break; printf("n"); printf("下面是菜单，请继续，或者按0退出"); showmenu; scanf("%d",&choice); printf("感谢您使用本系统，再见！"); return 0; void FCFS intj,k; intw_rel_time5; intw_finish_time5; floatrel_time = 0; struct work temp; inti; struct work w5; srand(time(0); for(i=0;i<5;i+) wi.id = rand%10; wi.arrive_time = rand%10; wi.work_time = rand%10+1; for(j=0;j<5;j+) printf("第%d个作业的编号是：%dt",j+1,wj.id); printf("第%d个作业到达时间：%dt",j+1,wj.arrive_time); printf("第%d个作业服务时间：%dt",j+1,wj.work_time); printf("n"); for(j=1;j<5;j+) for(k=0;k<5-j;k+) if(wk.arrive_time> wk+1.arrive_time) temp = wk; wk = wk+1; wk+1 = temp; printf("n"); w_finish_time0 = w0.arrive_time + w0.work_time; for(j=0;j<5;j+) if(w_finish_timej < wj+1.arrive_time) w_finish_timej+1 = wj+1.arrive_time + wj+1.work_time; else w_finish_timej+1 = w_finish_timej + wj+1.work_time; for(j=0;j<5;j+) w_rel_timej = w_finish_timej - wj.arrive_time; for(j=0;j<5;j+) rel_time += w_rel_timej; for(j=0;j<5;j+) printf("第%d个系统执行的作业到达时间：%d ",j+1,wj.arrive_time); printf("编号是：%d ",wj.id); printf("服务时间是：%d ",wj.work_time); printf("完成时间是：%d ",w_finish_timej); printf("周转时间是：%d ",w_rel_timej); printf("n"); printf("平均周转时间：%fn",rel_time/5); void SJF intw_rel_time10; intw_finish_time10; floatrel_time = 0; srand(time(0); inti; int j = 0; PNODE pHead = (PNODE)malloc(sizeof(NODE); if (NULL = pHead) printf("分配失败, 程序终止!n"); exit(-1); PNODE pTail = pHead; pTail->pNext = NULL; /定义该链表有头结点，且第一个节点初始化为空 for(i=0;i<10;i+) PNODE pNew = (PNODE)malloc(sizeof(NODE); if (NULL = pNew) printf("分配失败, 程序终止!n"); exit(-1); pNew->s_work.id = rand%100; pNew->s_work.arrive_time = rand%10; pNew->s_work.work_time = rand%10+1; pTail->pNext = pNew; pNew->pNext = NULL; pTail = pNew; PNODE p = pHead->pNext; /p指向第一个节点 while (NULL != p) printf("第%d个作业的编号是：%dt",j+1,p->s_work.id); printf("第%d个作业到达时间：%dt",j+1,p->s_work.arrive_time); printf("第%d个作业服务时间：%dt",j+1,p->s_work.work_time); printf("n"); p = p->pNext; printf("n"); j+; p = pHead->pNext; PNODE q = p; /p,q都指向第一个节点 p = p->pNext; while(p != NULL) if(p->s_work.arrive_time< q->s_work.arrive_time) q = p; p = p->pNext; PNODE r = pHead->pNext; /r也指向第一个节点 intcnt = 0; /记录所有节点数据域中到达时间最短且相等的个数 while(r!= NULL) if( r->s_work.arrive_time = q->s_work.arrive_time ) cnt+; r = r->pNext; p = pHead->pNext; while(p != NULL) /在相等到达时间的作业中找服务时间最短的作业 if(cnt> 1) if( p->s_work.arrive_time = q->s_work.arrive_time ) if( p->s_work.work_time< q->s_work.work_time ) q = p; p = p->pNext; else p =NULL; /确定q所指作业最先到达且服务时间最短 w_finish_time0 = q->s_work.arrive_time + q->s_work.work_time; w_rel_time0 = w_finish_time0 - q->s_work.arrive_time; printf("第1个系统执行的作业到达时间：%d ",q->s_work.arrive_time); printf("编号是：%d ",q->s_work.id); printf("服务时间是：%d n",q->s_work.work_time); printf("完成时间是：%d ",w_finish_time0); printf("周转时间是：%d n",w_rel_time0); p = pHead; /寻找q的前一个节点，方便删掉q节点 while( p->pNext != q ) p = p->pNext; p->pNext = q->pNext; free(q); q = NULL; for(i=0;i<9&&!Is_empty(pHead);i+) printf("现在系统还剩%d个作业！n",cnt_work(pHead); q = do_work(pHead,w_finish_time,i); show(w_finish_time,i,q,w_rel_time); p = pHead; /寻找q的前一个节点，方便删掉 while( p->pNext != q ) p = p->pNext; p->pNext = q->pNext; free(q); q = NULL; for(j=0;j<10;j+) rel_time += w_rel_timej; q节点 printf("平均周转时间：%fn",rel_time/10); bool Is_empty(PNODE pHead) /判断作业是否做完 PNODE p; p = pHead->pNext; intlen = 0; while(p != NULL) len+; p = p->pNext; if(len = 0) return true; /当没有作业时，返回为真 else return false; intcnt_work(PNODE pHead) / PNODE p; p = pHead->pNext; intlen = 0; while(p != NULL) len+; p = p->pNext; returnlen; 计算当前还剩多少作业 PNODE do_work(PNODE pHead,int *w_finish_time,inti) PNODE p,q; intcnt = 0; /计数器清0，计算当前作业完成时，系统中有多少个作业已经到达 p = pHead->pNext; q = p; while(p != NULL) if( p->s_work.arrive_time<= w_finish_timei ) cnt +; q = p; p = p->pNext; else p = p->pNext; /q指向当前到达时间小于刚刚完成的作业，但不一定是服务时间最短的(如果有的话) printf("系统中有%d个作业在当前作业完成时已经到达！n",cnt); p = pHead->pNext; while(p != NULL) if(cnt>1) /执行此次判断后，q现在指向所有条件都满足的作业 if( p->s_work.arrive_time<= w_finish_timei ) if( p->s_work.work_time< q->s_work.work_time ) q = p; p = p->pNext; else p = p->pNext; else p = p->pNext; else /当前作业完成时，没有作业到达的情况 p = p->pNext; /用q来接收最先到达的，用p来遍历 while( p != NULL ) if( p->s_work.arrive_time< q->s_work.arrive_time ) q = p; p = p->pNext; w_finish_timei+1 = q->s_work.arrive_time + q->s_work.work_time; w_finish_timei+1 = w_finish_timei + q->s_work.work_time; return q; void show(int *w_finish_time,inti,PNODEq,int *w_rel_time) w_finish_timei+1 = w_finish_timei + q->s_work.work_time; w_rel_timei+1 = w_finish_timei+1 - q->s_work.arrive_time; printf("第%d个系统执行的作业到达时间：%d ",i+2,q->s_work.arrive_time); printf("编号是：%d ",q->s_work.id); printf("服务时间是：%dn",q->s_work.work_time); printf("完成时间是：%d ",w_finish_timei+1); printf("周转时间是：%d n",w_rel_timei+1); voidshowmenu printf("*n"); printf("请选择你要执行的命令: n"); printf("1：先来先服务算法n"); printf("2：短作业优先算法n"); printf("3: 高响应比优先算法n"); printf("0: 退出菜单n"); printf("*n"); void HRRN intw_rel_time10; intw_finish_time10; floatrel_time = 0; float priority; /计算优先权 srand(time(0); inti; int j = 0; PNODE pHead = (PNODE)malloc(sizeof(NODE); if (NULL = pHead) printf("分配失败, 程序终止!n"); exit(-1); PNODE pTail = pHead; pTail->pNext = NULL; /定义该链表有头结点，且第一个节点初始化为空 for(i=0;i<10;i+) /定义了十个进程 PNODE pNew = (PNODE)malloc(sizeof(NODE); if (NULL = pNew) printf("分配失败, 程序终止!n"); exit(-1); pNew->s_work.id = rand%100; pNew->s_work.arrive_time = rand%10; pNew->s_work.work_time = rand%10+1; pTail->pNext = pNew; pNew->pNext = NULL; pTail = pNew; PNODE p = pHead->pNext; /p指向第一个节点 while (NULL != p) printf("第%d个作业的编号是：%dt",j+1,p->s_work.id); printf("第%d个作业到达时间：%dt",j+1,p->s_work.arrive_time); printf("第%d个作业服务时间：%dt",j+1,p->s_work.work_time); printf("n"); p = p->pNext; printf("n"); j+; p = pHead->pNext; PNODE q = p; /p,q都指向第一个节点 p = p->pNext; while(p != NULL) if(p->s_work.arrive_time< q->s_work.arrive_time) q = p; p = p->pNext; PNODE r = pHead->pNext; /r也指向第一个节点 intcnt = 0; /记录所有节点数据域中到达时间最短且相等的个数 while(r!= NULL) if( r->s_work.arrive_time = q->s_work.arrive_time ) cnt+; r = r->pNext; p = pHead->pNext; while(p != NULL) /在相等到达时间的作业中找服务时间最短的作业 if(cnt> 1) if( p->s_work.arrive_time = q->s_work.arrive_time ) if( p->s_work.work_time< q->s_work.work_time ) q = p; p = p->pNext; else p =NULL; /确定q所指作业最先到达且服务时间最短 w_finish_time0 = q->s_work.arrive_time + q->s_work.work_time; w_rel_time0 = w_finish_time0 - q->s_work.arrive_time; printf("第1个系统执行的作业到达时间：%d ",q->s_work.arrive_time); printf("编号是：%d ",q->s_work.id); printf("服务时间是：%d n",q->s_work.work_time); printf("完成时间是：%d ",w_finish_time0); printf("周转时间是：%d n",w_rel_time0); p = pHead; /寻找q的前一个节点，方便删掉q节点 while( p->pNext != q ) p = p->pNext; p->pNext = q->pNext; free(q); q = NULL; /已经找到并执行第一个进程，执行完之后又将其删除了 for(i=0;i<9&&!Is_empty(pHead);i+) printf("现在系统还剩%d个作业！n",cnt_work(pHead); do_work_1(pHead,w_finish_time,i); q = priorit(pHead); show(w_finish_time,i,q,w_rel_time); p = pHead; /寻找q的前一个节点，方便删掉q节点 while( p->pNext != q ) p = p->pNext; p->pNext = q->pNext; free(q); q = NULL; for(j=0;j<10;j+) rel_time += w_rel_timej; printf("平均周转时间：%fn",rel_time/10); void do_work_1(PNODE pHead,int *w_finish_time,inti) PNODE p,q; intcnt = 0; /计数器清0，计算当前作业完成时，系统中有多少个作业已经到达 p = pHead->pNext; q = p; while(p != NULL) if( p->s_work.arrive_time<= w_finish_timei ) cnt +; q = p; p = p->pNext; else p = p->pNext; /q指向当前到达时间小于刚刚完成的作业，但有可能有另外几个进程也已经到达了，所以要进行下面的判断 printf("系统中有%d个作业在当前作业完成时已经到达！n",cnt); p = pHead->pNext; while(p != NULL) if(cnt>1) /说明此时有好几个都已经到达了 if(p->s_work.arrive_time<= w_finish_timei) p->s_work.wait = w_finish_timei - p->s_work.arrive_time; p = p->pNext; else p->s_work.wait = 0; p = p->pNext; else /当前作业完成时，没有作业到达的情况 p = p->pNext; /此时p指向第一个节点，q指向第二个节点，还是找最先到达的 while( p != NULL ) if( p->s_work.arrive_time< q->s_work.arrive_time ) q = p; p = p->pNext; w_finish_timei+1 = q->s_work.arrive_time + q->s_work.work_time; return; w_finish_timei+1 = w_finish_timei + q->s_work.work_time; PNODE priorit(PNODE pHead) PNODE p = pHead->pNext; while(p != NULL) if(p->s_work.wait> 0) p->s_work.priority = (p->s_work.wait + p->s_work.work_time) / p->s_work.work_time; /一个已经等待的进程的优先等级 p = p->pNext; 计算每 else p = p->pNext; p = pHead->pNext; PNODE q; q = p; p = p->pNext; /p已经指向第二个节点 while(p != NULL) if(p->s_work.wait> 0) if(p->s_work.priority> q->s_work.priority) q = p; p = p->pNext; else p = p->pNext; else p = p->pNext; printf("该进程优先级最高，为：%fn",q->s_work.priority); return q; 实验结果： 系统自动为每个算法模拟分配五个作业，同时随机生成作业的编号，作业的到达时间，作业估计运行的时间。 1.先来先服务算法 该算法严格按照各作业到达时间来为其分配进程和资源，实验的结果见截图，最后算出该算法五个作业的平均周转时间。 2.短作业优先 短作业优先算法考虑的比较多，系统先找出最先到达的作业，若有多个相同时间到达的作业，则按照其运行时间长短先为时间短的服务。 3.高响应比优先算法 代码中主要运用PNODE priorit(PNODE pHead)函数计算作业的优先权。 四.实验小结 通过的代码的实现，对三种作业调度算法有了更深的理解。短作业优先算法要考虑的是后备队列