作业调度算法先来先服务算法短作业算法.docx

?操作系统?实验报告题目：作业调度算法班级：网络工程姓名：朱锦涛心口 子»:一、实验目的用代码实现页面调度算法,即先来先效劳 FCFS调度算法、短作业优先算法、高响应比优先调度算法.通过代码的具体实现,加深对算法的核心的理解.二、实验原理1.先来先效劳FCFS调度算法FCF麋最简单的调度算法,该算法既可用于作业调度,也可用于进程调 度.当在作业调度中采用该算法时,系统将根据作业到达的先后次序来进行 调度,或者说它是优先考虑在系统中等待时间最长的作业,而不管该作业所 需执行的时间的长短,从后备作业队列中选择几个最先进入该队列的作业, 将它们调入内存,为它们分配资源和创立进程.然后把它放入就绪队列.2,短作业优先算法SJF算法是以作业的长短来计算优先级,作业越短,具优先级越高.作业的长短是以作业所要求的运行时间来衡量的. SJF算法可以分别用于作业和 进程调度.在把短作业优先调度算法用于作业调度时, 它将从外存的作业后 备队列中选择假设干个估计运行时间最短的作业,优先将它们调入内存.3、高响应比优先调度算法高响应比优先调度算法那么是既考虑了作业的等待时间,又考虑了作业的运行时间的算法,因此既照顾了短作业,又不致使长作业等待的时间过长,从 而改善了处理机调度的性能.如果我们引入一个动态优先级,即优先级是可以改变的令它随等待的时间的延长而增加,这将使长作业的优先级在等待期间不断地增加,等到足够的时间后,必然有时机获得处理机.该优先级的变化规律可以描述为：优先权=等待时间+要求效劳时间/要求效劳时间三、实验内容源程序：#include<stdio.h>#include<stdlib.h>#include<time.h> struct worki nt id;i nt arrive_time;i nt work_time;i nt wait;f loat 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()i nt 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()(i nt j,k;i nt w_rel_time5;i nt w_finish_time5;f loat rel_time = 0;struct work temp;i nt i;struct work w5;srand(time(0);f or(i=0;i<5;i+)wi.id = rand()%10;wi.arrive_time = rand()%10;wi.work_time = rand()%10+1;)f or(j=0;j<5;j+)printf(" 第 dj作业的编号是：%dt",j+1,wj.id);printf(" 第 个作业到达时间：%dt",j+1,wj.arrive_time);printf(" 第 个作业效劳时间：%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;)elsew_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("第dj系统执行的作业到达时间：%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() i nt w_rel_time10;i nt w_finish_time10;f loat rel_time = 0;srand(time(0);i nt i;i nt j = 0;PNODE pHead = (PNODE)malloc(sizeof(NODE);i f (NULL = pHead)(printf(" 分配失败,程序终止！n");exit(-1);PNODE pTail = pHead;pTail->pNext = NULL; 定义该链表有头结点,且第一个节点初始化为空f or(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("第 1个作业的编号是：%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也指向第一个节点i nt 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;elsep =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;f ree(q);q = NULL;f or(i=0;i<9&&!Is_empty(pHead);i+)(printf("现在系统还剩 个作业！ 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;)f or(j=0;j<10;j+)(rel_time += w_rel_timej;)printf("平均周转时间：fn",rel_time/10);)bool Is_empty(PNODE pHead) /判断作业是否做完(PNODE p;p = pHead->pNext;i nt len = 0;while(p != NULL)(len+;p = p->pNext;i f(len = 0)return true; /当没有作业时,返回为真elsereturn false;)int cnt_work(PNODE pHead) /计算当前还剩多少作业(PNODE p;p = pHead->pNext;i nt len = 0;while(p != NULL)(len+;p = p->pNext;)r eturn len;PNODE do_work(PNODE pHead,int *w_finish_time,int i)(PNODE p,q;i nt cnt = 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;)elsep = 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;elsep = p->pNext;)elsep = 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;r eturn q;void showint *w_finish_time,int i,PNODE q,int *w_rel_timew_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,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("2:短作业优先算法n");printf("3:高响应比优先算法n");printf("0:退出菜单 n");printf(*n");void HRRN()(i nt w_rel_time10;i nt w_finish_time10;f loat rel_time = 0;f loat priority; /计算优先权srand(time(0);i nt i;i nt j = 0;PNODE pHead = (PNODE)malloc(sizeof(NODE);i f (NULL = pHead)printf(" 分配失败,程序终止！n");exit(-1);PNODE pTail = pHead;pTail->pNext = NULL; /定义该链表有头结点,且第一个节点初始化为空f or(i=0;i<10;i+) /定义了十个进程PNODE pNew = (PNODE)malloc(sizeof(NODE);if (NULL = pNew)printf"分配失败,程序终止!n")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("第 个作业的编号是：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 也指向第一个节点i nt 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;)elsep =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;f reeq;q = NULL; /已经找到并执行第一个进程,执行完之后又将其删除了f or(i=0;i<9&&!Is_empty(pHead);i+)(printf("现在系统还剩 个作业！ 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;f or(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,int i)(PNODE p,q;i nt cnt = 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 )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;)elsep = 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)p = p->pNext;)elsep = p->pNext;)elsep = p->pNext;)printf("该进程优先级最高,为： %fn",q->s_work.priority);return q;)实验结果：系统自动为每个算法模拟分配五个作业,同时随机生成作业的编号, 作业的到达时间,作业估计运行的时间.1.先来先效劳算法该算法严格根据各作业到达时间来为其分配进程和资源,实验的结 果见截图,最后算出该算法五个作业的平均周转时间.2,短作业优先短作业优先算法考虑的比拟多,系统先找出最先到达的作业,假设有 多个相同时间到达的作业,那么根据其运行时间长短先为时间短的效劳.3.高响应比优先算法代码中主要运用 PNODE priorit(PNODE pHead)函数计算作业的优先 权.四,实验小结通过的代码的实现,对三种作业调度算法有了更深的理解.短作业优先算法要考虑的是后备队列