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

《作业调度算法(先来先服务算法,短作业算法)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

《操作系统》实验报告题目：作业调度算法班级：网络工程姓名：朱锦涛学号：E31314037 一、实验目的用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。二、实验原理1.先来先服务（FCFS）调度算法FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。2.短作业优先算法SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为：优先权=（等待时间+要求服务时间）/要求服务时间三、实验内容源程序：#include#include#includestructwork{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("您选择的是先来先服务算法: "); FCFS();break;case2:printf("您选择的是短作业优先算法: ");SJF();break;case3:printf("您选择的是高响应比优先调度算法 ");HRRN();break;default:printf("请重新选择！");break;}printf(" ");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个作业的编号是：%dt",j+1,w[j].id);printf("第%d个作业到达时间：%dt",j+1,w[j].arrive_time);printf("第%d个作业服务时间：%dt",j+1,w[j].work_time);printf(" ");} 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(" ");w_finish_time[0]=w[0].arrive_time+w[0].work_time;for(j=0;j<5;j++){ if(w_finish_time[j]pNext=NULL;//定义该链表有头结点，且第一个节点初始化为空 for(i=0;i<10;i++){PNODEpNew=(PNODE)malloc(sizeof(NODE));if(NULL==pNew){printf("分配失败,程序终止! ");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个作业的编号是：%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(" ");p=p->pNext;printf(" ");j++;}p=pHead->pNext;PNODEq=p;//p,q都指向第一个节点 p=p->pNext;while(p!=NULL){if(p->s_work.arrive_times_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_times_work.work_time)q=p;p=p->pNext;}elsep=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 ",q->s_work.work_time);printf("完成时间是：%d",w_finish_time[0]);printf("周转时间是：%d ",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个作业！ ",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 ",rel_time/10);}boolIs_empty(PNODEpHead)//判断作业是否做完{PNODEp;p=pHead->pNext;intlen=0;while(p!=NULL){len++;p=p->pNext;} if(len==0)returntrue;//当没有作业时，返回为真elsereturnfalse;}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个作业在当前作业完成时已经到达！ ",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_times_work.work_time) {q=p;p=p->pNext;}elsep=p->pNext;}elsep=p->pNext;}else//当前作业完成时，没有作业到达的情况{p=p->pNext;//用q来接收最先到达的，用p来遍历while(p!=NULL){if(p->s_work.arrive_times_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 ",q->s_work.work_time);printf("完成时间是：%d",w_finish_time[i+1]);printf("周转时间是：%d ",w_rel_time[i+1]);}voidshowmenu(){printf("********************************** ");printf("请选择你要执行的命令~: ");printf("1：先来先服务算法 "); printf("2：短作业优先算法 ");printf("3:高响应比优先算法 ");printf("0:退出菜单 ");printf("********************************** ");}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("分配失败,程序终止! ");exit(-1);}PNODEpTail=pHead;pTail->pNext=NULL;//定义该链表有头结点，且第一个节点初始化为空for(i=0;i<10;i++)//定义了十个进程{PNODEpNew=(PNODE)malloc(sizeof(NODE));if(NULL==pNew){printf("分配失败,程序终止! ");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个作业的编号是：%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(" "); p=p->pNext;printf(" ");j++;}p=pHead->pNext;PNODEq=p;//p,q都指向第一个节点p=p->pNext;while(p!=NULL){if(p->s_work.arrive_times_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_times_work.work_time)q=p;p=p->pNext; }elsep=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 ",q->s_work.work_time);printf("完成时间是：%d",w_finish_time[0]);printf("周转时间是：%d ",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个作业！ ",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 ",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个作业在当前作业完成时已经到达！ ",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;//此时p指向第一个节点，q指向第二个节点，还是找最先到达的while(p!=NULL){if(p->s_work.arrive_times_work.arrive_time)q=p;p=p->pNext;}w_finish_time[i+1]=q->s_work.arrive_time+q->s_work.work_time;return; }}w_finish_time[i+1]=w_finish_time[i]+q->s_work.work_time;}PNODEpriorit(PNODEpHead){PNODEp=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;} elsep=p->pNext;}p=pHead->pNext;PNODEq;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;}elsep=p->pNext;}printf("该进程优先级最高，为：%f ",q->s_work.priority);returnq;}实验结果：系统自动为每个算法模拟分配五个作业，同时随机生成作业的编号，作业的到达时间，作业估计运行的时间。1.先来先服务算法 该算法严格按照各作业到达时间来为其分配进程和资源，实验的结果见截图，最后算出该算法五个作业的平均周转时间。2.短作业优先短作业优先算法考虑的比较多，系统先找出最先到达的作业，若有多个相同时间到达的作业，则按照其运行时间长短先为时间短的服务。 3.高响应比优先算法 代码中主要运用PNODEpriorit(PNODEpHead)函数计算作业的优先权。四.实验小结通过的代码的实现，对三种作业调度算法有了更深的理解。短作业优先算法要考虑的是后备队列