作业调度算法(先来先服务算法,短作业算法)

..《操作系统》实验报告题目：作业调度算法班级：网络工程姓名：朱锦涛学号：E31314037一、实验目的用代码实现页面调度算法,即先来先服务〔FCFS调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现,加深对算法的核心的理解。二、实验原理1.先来先服务〔FCFS调度算法FCFS是最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,系统将按照作业到达的先后次序来进行调度,或者说它是优先考虑在系统中等待时间最长的作业,而不管该作业所需执行的时间的长短,从后备作业队列中选择几个最先进入该队列的作业,将它们调入内存,为它们分配资源和创建进程。然后把它放入就绪队列。2.短作业优先算法SJF算法是以作业的长短来计算优先级,作业越短,其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时,它将从外存的作业后备队列中选择若干个估计运行时间最短的作业,优先将它们调入内存。3、高响应比优先调度算法高响应比优先调度算法则是既考虑了作业的等待时间,又考虑了作业的运行时间的算法,因此既照顾了短作业,又不致使长作业等待的时间过长,从而改善了处理机调度的性能。如果我们引入一个动态优先级,即优先级是可以改变的令它随等待的时间的延长而增加,这将使长作业的优先级在等待期间不断地增加,等到足够的时间后,必然有机会获得处理机。该优先级的变化规律可以描述为：优先权=〔等待时间+要求服务时间/要求服务时间三、实验内容源程序：#include<stdio.h>#include<stdlib.h>#include<time.h>structwork{ intid; intarrive_time; intwork_time; intwait; floatpriority;};typedefstructsjf_work{ structworks_work;//数据域 structsjf_work*pNext;//指针域}NODE,*PNODE;voidFCFS<>;voidSJF<>;voidshowmenu<>;boolIs_empty<PNODEpHead>;intcnt_work<PNODEpHead>;PNODEdo_work<PNODEpHead,int*w_finish_time,inti>;voidshow<int*w_finish_time,inti,PNODEq,int*w_rel_time>;voidHRRN<>;PNODEpriorit<PNODEpHead>;voiddo_work_1<PNODEpHead,int*w_finish_time,inti>;intmain<>{ intchoice;//设置选择数 showmenu<>;//显示菜单 scanf<"%d",&choice>; while<choice!=0>//选择算法 { switch<choice> { case1: printf<"您选择的是先来先服务算法:\n">; FCFS<>; break; case2: printf<"您选择的是短作业优先算法:\n">; SJF<>; break; case3: printf<"您选择的是高响应比优先调度算法\n">; HRRN<>; break; default: printf<"请重新选择！">; break; } printf<"\n">; printf<"下面是菜单,请继续,或者按‘0’退出">; showmenu<>; scanf<"%d",&choice>; } printf<"感谢您使用本系统,再见！">; return0;}voidFCFS<>{ intj,k; intw_rel_time[5]; intw_finish_time[5]; floatrel_time=0;structworktemp; inti; structworkw[5]; srand<time<0>>; for<i=0;i<5;i++> { w[i].id=rand<>%10; w[i].arrive_time=rand<>%10; w[i].work_time=rand<>%10+1; } for<j=0;j<5;j++> { printf<"第%d个作业的编号是：%d\t",j+1,w[j].id>; printf<"第%d个作业到达时间：%d\t",j+1,w[j].arrive_time>; printf<"第%d个作业服务时间：%d\t",j+1,w[j].work_time>; printf<"\n">; } for<j=1;j<5;j++> for<k=0;k<5-j;k++> { if<w[k].arrive_time>w[k+1].arrive_time> { temp=w[k]; w[k]=w[k+1]; w[k+1]=temp; } } printf<"\n">; w_finish_time[0]=w[0].arrive_time+w[0].work_time; for<j=0;j<5;j++> { if<w_finish_time[j]<w[j+1].arrive_time> { w_finish_time[j+1]=w[j+1].arrive_time+w[j+1].work_time; } else w_finish_time[j+1]=w_finish_time[j]+w[j+1].work_time; } for<j=0;j<5;j++> w_rel_time[j]=w_finish_time[j]-w[j].arrive_time; for<j=0;j<5;j++> { rel_time+=w_rel_time[j]; } for<j=0;j<5;j++> { printf<"第%d个系统执行的作业到达时间：%d",j+1,w[j].arrive_time>; printf<"编号是：%d",w[j].id>; printf<"服务时间是：%d",w[j].work_time>; printf<"完成时间是：%d",w_finish_time[j]>; printf<"周转时间是：%d",w_rel_time[j]>; printf<"\n">; }printf<"平均周转时间：%f\n",rel_time/5>;}voidSJF<>{ intw_rel_time[10]; intw_finish_time[10]; floatrel_time=0; srand<time<0>>; inti; intj=0; PNODEpHead=<PNODE>malloc<sizeof<NODE>>; if<NULL==pHead> { printf<"分配失败,程序终止!\n">; exit<-1>; } PNODEpTail=pHead; pTail->pNext=NULL;//定义该链表有头结点,且第一个节点初始化为空 for<i=0;i<10;i++> { PNODEpNew=<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; } PNODEp=pHead->pNext;//p指向第一个节点 while<NULL!=p> { printf<"第%d个作业的编号是：%d\t",j+1,p->s_work.id>; printf<"第%d个作业到达时间：%d\t",j+1,p->s_work.arrive_time>; printf<"第%d个作业服务时间：%d\t",j+1,p->s_work.work_time>; printf<"\n">; p=p->pNext; printf<"\n">; j++; } p=pHead->pNext; PNODEq=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; } PNODEr=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_time[0]=q->s_work.arrive_time+q->s_work.work_time; w_rel_time[0]=w_finish_time[0]-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_time[0]>; printf<"周转时间是：%d\n",w_rel_time[0]>; 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的前一个节点,方便删掉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_time[j]; } printf<"平均周转时间：%f\n",rel_time/10>;}boolIs_empty<PNODEpHead>//判断作业是否做完{ PNODEp; p=pHead->pNext; intlen=0; while<p!=NULL> { len++; p=p->pNext; } if<len==0> returntrue;//当没有作业时,返回为真 else returnfalse;}intcnt_work<PNODEpHead>//计算当前还剩多少作业{ PNODEp; p=pHead->pNext; intlen=0; while<p!=NULL> { len++; p=p->pNext; } returnlen;}PNODEdo_work<PNODEpHead,int*w_finish_time,inti>{ PNODEp,q; intcnt=0;//计数器清0,计算当前作业完成时,系统中有多少个作业已经到达p=pHead->pNext; q=p; while<p!=NULL> { if<p->s_work.arrive_time<=w_finish_time[i]> { 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_time[i]> { 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_time[i+1]=q->s_work.arrive_time+q->s_work.work_time; } } w_finish_time[i+1]=w_finish_time[i]+q->s_work.work_time; returnq;}voidshow<int*w_finish_time,inti,PNODEq,int*w_rel_time>{ w_finish_time[i+1]=w_finish_time[i]+q->s_work.work_time; w_rel_time[i+1]=w_finish_time[i+1]-q->s_work.arrive_time; printf<"第%d个系统执行的作业到达时间：%d",i+2,q->s_work.arrive_time>; printf<"编号是：%d",q->s_work.id>; printf<"服务时间是：%d\n",q->s_work.work_time>; printf<"完成时间是：%d",w_finish_time[i+1]>; printf<"周转时间是：%d\n",w_rel_time[i+1]>;}voidshowmenu<>{printf<"**********************************\n">; printf<"请选择你要执行的命令~:\n">; printf<"1：先来先服务算法\n">; printf<"2：短作业优先算法\n">; printf<"3:高响应比优先算法\n">; printf<"0:退出菜单\n">; printf<"**********************************\n">;}voidHRRN<>{ intw_rel_time[10]; intw_finish_time[10]; floatrel_time=0; floatpriority;//计算优先权 srand<time<0>>; inti; intj=0; PNODEpHead=<PNODE>malloc<sizeof<NODE>>; if<NULL==pHead> { printf<"分配失败,程序终止!\n">; exit<-1>; } PNODEpTail=pHead; pTail->pNext=NULL;//定义该链表有头结点,且第一个节点初始化为空 for<i=0;i<10;i++>//定义了十个进程 { PNODEpNew=<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; } PNODEp=pHead->pNext;//p指向第一个节点 while<NULL!=p> { printf<"第%d个作业的编号是：%d\t",j+1,p->s_work.id>; printf<"第%d个作业到达时间：%d\t",j+1,p->s_work.arrive_time>; printf<"第%d个作业服务时间：%d\t",j+1,p->s_work.work_time>; printf<"\n">; p=p->pNext; printf<"\n">; j++; } p=pHead->pNext; PNODEq=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; } PNODEr=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_time[0]=q->s_work.arrive_time+q->s_work.work_time; w_rel_time[0]=w_finish_time[0]-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_time[0]>; printf<"周转时间是：%d\n",w_rel_time[0]>; 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_time[j]; } printf<"平均周转时间：%f\n",rel_time/10>;}voiddo_work_1<PNODEpHead,int*w_finish_time,inti>{ PNODEp,q; intcnt=0;//计数器清0,计算当前作业完成时,系统中有多少个作业已经到达p=pHead->pNext; q=p; while<p!=NULL> { if<p->s_work.arrive_time<=w_finish_time[i]> { 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_time[i]> { p->s_work.wait=w_finish_time[i]-p->s_work.arrive_time; p=p->pNext; } else { p->s_work.wait=0; p=p->pNext; } } else//当前作业完成时,没有作业到达的情况 { p=p->pNext;