《作业调度算法(先来先服务算法,短作业算法).pdf》由会员分享，可在线阅读，更多相关《作业调度算法(先来先服务算法,短作业算法).pdf（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、操作系统实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037 一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。二、实验原理 1.先来先服务（FCFS）调度算法 FCFS 是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建
2、进程。然后把它放入就绪队列。2.短作业优先算法 SJF 算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF 算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待
3、期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为：优先权=（等待时间+要求服务时间）/要求服务时间 三、实验内容 源程序：#include#include#include struct work int id;int arrive_time;int work_time;int wait;float priority;typedef struct sjf_work struct work s_work;/数据域 struct sjf_work*pNext;/指针域 NODE,*PNODE;void FCFS();void SJF();void showmenu
4、();bool Is_empty(PNODE pHead);int cnt_work(PNODE pHead);PNODE do_work(PNODE pHead,int*w_finish_time,int i);void show(int*w_finish_time,int i,PNODE q,int*w_rel_time);void HRRN();PNODE priorit(PNODE pHead);void do_work_1(PNODE pHead,int*w_finish_time,int i);int main()int choice;/设置选择数 showmenu();/显示菜单
5、 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(感谢您使用本系统，再见！);r
6、eturn 0;void FCFS()int j,k;int w_rel_time5;int w_finish_time5;float rel_time=0;struct work temp;int i;struct work w5;srand(time(0);for(i=0;i5;i+)wi.id=rand()%10;wi.arrive_time=rand()%10;wi.work_time=rand()%10+1;for(j=0;j5;j+)printf(第%d 个作业的编号是：%dt,j+1,wj.id);printf(第%d 个作业到达时间：%dt,j+1,wj.arrive_time
7、);printf(第%d 个作业服务时间：%dt,j+1,wj.work_time);printf(n);for(j=1;j5;j+)for(k=0;k 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;j5;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_fini
8、sh_timej+wj+1.work_time;for(j=0;j5;j+)w_rel_timej=w_finish_timej-wj.arrive_time;for(j=0;j5;j+)rel_time+=w_rel_timej;for(j=0;jpNext=NULL;/定义该链表有头结点，且第一个节点初始化为空 for(i=0;is_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
9、;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
10、 s_work.arrive_time)q=p;p=p-pNext;PNODE r=pHead-pNext;/r 也指向第一个节点 int cnt=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
11、 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
12、 ,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;ipNext!=q)p=p-pNext;p-pNext=q-pNext;free(q);q=NULL;for(j=0;jpNext;int len=0;while(p!=NULL)len+;p=p-pNext;if(len=0)return true;/当没有作业时，返回为真 else return fal
13、se;int cnt_work(PNODE pHead)/计算当前还剩多少作业 PNODE p;p=pHead-pNext;int len=0;while(p!=NULL)len+;p=p-pNext;return len;PNODE do_work(PNODE pHead,int*w_finish_time,int i)PNODE p,q;int cnt=0;/计数器清 0，计算当前作业完成时，系统中有多少个作业已经到达 p=pHead-pNext;q=p;while(p!=NULL)if(p-s_work.arrive_time pNext;else p=p-pNext;/q 指向当前到达
14、时间小于刚刚完成的作业，但不一定是服务时间最短的(如果有的话)printf(系统中有%d 个作业在当前作业完成时已经到达！n,cnt);p=pHead-pNext;while(p!=NULL)if(cnt1)/执行此次判断后，q 现在指向所有条件都满足的作业（如果有的话）if(p-s_work.arrive_time s_work.work_time s_work.work_time)q=p;p=p-pNext;else p=p-pNext;else p=p-pNext;else /当前作业完成时，没有作业到达的情况 p=p-pNext;/用 q 来接收最先到达的，用 p 来遍历 while(
15、p!=NULL)if(p-s_work.arrive_times_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,int i,PNODE q,int*w_rel_time)w_finish_timei+1=w_finish_timei+q-s_work.work_time;w_rel_timei
16、+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);void showmenu()printf(*n);printf(请选择你要执行的命令:n);printf(1：先来先服务算法n);printf
17、(2：短作业优先算法n);printf(3:高响应比优先算法n);printf(0:退出菜单n);printf(*n);void HRRN()int w_rel_time10;int w_finish_time10;float rel_time=0;float priority;/计算优先权 srand(time(0);int i;int j=0;PNODE pHead=(PNODE)malloc(sizeof(NODE);if(NULL=pHead)printf(分配失败,程序终止!n);exit(-1);PNODE pTail=pHead;pTail-pNext=NULL;/定义该链表有头
18、结点，且第一个节点初始化为空 for(i=0;is_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(第%
19、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 s_work.arrive_time)q=p;p=p-pNext;PNODE r=pHead-pNext;/r 也指向第一个节点 int cnt=0;/记录所有节点数据域中到达时间最短且相等的个数 while(r!=NULL)if(r-s_work.arrive_time=q-s_wo
20、rk.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 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_ti
21、me0-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;/已经找到并
22、执行第一个进程，执行完之后又将其删除了 for(i=0;ipNext!=q)p=p-pNext;p-pNext=q-pNext;free(q);q=NULL;for(j=0;jpNext;q=p;while(p!=NULL)if(p-s_work.arrive_time pNext;else p=p-pNext;/q 指向当前到达时间小于刚刚完成的作业，但有可能有另外几个进程也已经到达了，所以要进行下面的判断 printf(系统中有%d 个作业在当前作业完成时已经到达！n,cnt);p=pHead-pNext;while(p!=NULL)if(cnt1)/说明此时有好几个都已经到达了 if(p
23、-s_work.arrive_time 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 s_work.arrive_time)q=p;p=p-pNext;w_finish_timei+1=q-s_work.arrive_time+q-s_work.work_t
24、ime;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 已经指向
25、第二个节点 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)函数计算作业的优先权。四.实验小结 通过的代码的实现，对三种作业调度算法有了更深的理解。短作业优先算法要考虑的是后备队列