类型课后复习调度算法(先来先服务算法短课后复习算法).doc

收藏

编号:2627437    类型:共享资源    大小:313.66KB    格式:DOC    上传时间:2020-04-25
  
10
金币
分享到微信 分享到微博 分享到QQ空间
关 键 词:
课后 复习 温习 调度 算法 先来先 服务
资源描述:
^` 《操作系统》实验报告 题目:作业调度算法 班级:网络工程 姓名:朱锦涛 学号:E31314037 一、实验目的 用代码实现页面调度算法,即先来先服务(FCFS)调度算法 、短作业优先算法、高响应比优先调度算法。通过代码的具体实现,加深对算法的核心的理解。 二、实验原理 1.先来先服务(FCFS)调度算法 FCFS是最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,系统将按照作业到达的先后次序来进行调度,或者说它是优先考虑在系统中等待时间最长的作业,而不管该作业所需执行的时间的长短,从后备作业队列中选择几个最先进入该队列的作业,将它们调入内存,为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级,作业越短,其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时,它将从外存的作业后备队列中选择若干个估计运行时间最短的作业,优先将它们调入内存。 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(); 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(); //显示菜单 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() { int j,k; int w_rel_time[5]; int w_finish_time[5]; float rel_time = 0; struct work temp; int i; struct work w[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); } void SJF() { int w_rel_time[10]; int w_finish_time[10]; float rel_time = 0; 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; //定义该链表有头结点,且第一个节点初始化为空 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个作业的编号是:%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; 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也指向第一个节点 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 < 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); } bool Is_empty(PNODE pHead) //判断作业是否做完 { PNODE p; p = pHead->pNext; int len = 0; while(p != NULL) { len++; p = p->pNext; } if(len == 0) return true; //当没有作业时,返回为真 else return false; } 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 <= 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; return q; } void show(int *w_finish_time,int i,PNODE q,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]); } void showmenu() { printf("**********************************\n"); printf("请选择你要执行的命令~: \n"); printf("1:先来先服务算法\n"); printf("2:短作业优先算法\n"); printf("3: 高响应比优先算法\n"); printf("0: 退出菜单\n"); printf("**********************************\n"); } void HRRN() { int w_rel_time[10]; int w_finish_time[10]; 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; //定义该链表有头结点,且第一个节点初始化为空 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个作业的编号是:%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; 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也指向第一个节点 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 < 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); } void do_work_1(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 <= 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; //此时p指向第一个节点,q指向第二个节点,还是找最先到达的 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; return; } } w_finish_time[i+1] = w_finish_time[i] + 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("该进程优先级最高,为:%f\n",q->s_work.priority); return q; } 实验结果: 系统自动为每个算法模拟分配五个作业,同时随机生成作业的编号,作业的到达时间,作业估计运行的时间。 1.先来先服务算法 该算法严格按照各作业到达时间来为其分配进程和资源,实验的结果见截图,最后算出该算法五个作业的平均周转时间。 2.短作业优先 短作业优先算法考虑的比较多,系统先找出最先到达的作业,若有多个相同时间到达的作业,则按照其运行时间长短先为时间短的服务。 3.高响应比优先算法 代码中主要运用PNODE priorit(PNODE pHead)函数计算作业的优先权。 四.实验小结 通过的代码的实现,对三种作业调度算法有了更深的理解。短作业优先算法要考虑的是后备队列
展开阅读全文
提示  得力文库 - 分享文档赚钱的网站所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:课后复习调度算法(先来先服务算法短课后复习算法).doc
链接地址:https://www.deliwenku.com/p-2627437.html
关于得利文库 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知得利文库网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号-8 |  经营许可证:黑B2-20190332号 |   黑公网安备:91230400333293403D

© 2020-2023 www.deliwenku.com 得利文库. All Rights Reserved 黑龙江转换宝科技有限公司 

黑龙江省互联网违法和不良信息举报
举报电话:0468-3380021 邮箱:hgswwxb@163.com  

收起
展开