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

1、操作系统实验报告题目：作业调度算法班级：网络工程姓名：朱锦涛学号：E一、实验目的用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。二、实验原理1.先来先服务（FCFS）调度算法FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。2.短

2、作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。3、高响应比优先调度算法高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有

3、机会获得处理机。该优先级的变化规律可以描述为：优先权 = （等待时间+ 要求服务时间）/要求服务时间三、实验内容源程序：#include#include#includestruct workint id;intarrive_time;intwork_time;int wait;float priority;typedefstructsjf_workstruct work s_work; /数据域structsjf_work * pNext; /指针域NODE,*PNODE;void FCFS();void SJF();voidshowmenu();boolIs_empty(PNODE pHea

4、d);intcnt_work(PNODE pHead);PNODE do_work(PNODE pHead,int *w_finish_time,inti);void show(int *w_finish_time,inti,PNODEq,int *w_rel_time);void HRRN();PNODE priorit(PNODE pHead);void do_work_1(PNODE pHead,int *w_finish_time,inti);int main()int choice; /设置选择数showmenu(); /显示菜单scanf(%d,&choice);while(cho

5、ice != 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()intj

6、,k;intw_rel_time5;intw_finish_time5;floatrel_time = 0;struct work temp;inti;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);printf(第%d个作业服务时间：%d

7、t,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;elsew_finish_timej+1 = w_finish_timej

8、+ 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

9、;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(第%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 != NUL

10、L)if(p-s_work.arrive_times_work.arrive_time) q = p;p = p-pNext;PNODE r = 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

11、 = q-s_work.arrive_time )if( p-s_work.work_times_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

12、);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; for(i=0;ipNext != q )p = p-pNext; p-pNext = q-pNext;free(q);q = NULL; for(j=0;jpNext;intlen = 0;w

13、hile(p != NULL)len+;p = p-pNext;if(len = 0)return true; /当没有作业时，返回为真elsereturn false;intcnt_work(PNODE pHead) /计算当前还剩多少作业PNODE p;p = pHead-pNext;intlen = 0;while(p != NULL)len+;p = p-pNext;returnlen;PNODE do_work(PNODE pHead,int *w_finish_time,inti)PNODE p,q;intcnt = 0; /计数器清0，计算当前作业完成时，系统中有多少个作业已经到

14、达 p = pHead-pNext;q = p;while(p != NULL) if( p-s_work.arrive_timepNext;elsep = p-pNext; /q指向当前到达时间小于刚刚完成的作业，但不一定是服务时间最短的(如果有的话)printf(系统中有%d个作业在当前作业完成时已经到达！n,cnt);p = pHead-pNext;while(p != NULL)if(cnt1) /执行此次判断后，q现在指向所有条件都满足的作业（如果有的话）if( p-s_work.arrive_times_work.work_times_work.work_time )q = p;p

15、 = 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_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

16、q;void show(int *w_finish_time,inti,PNODEq,int *w_rel_time)w_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个系统执行的作业到达时间：%d ,i+2,q-s_work.arrive_time);printf(编号是：%d ,q-s_work.id);printf(服务时间是：%dn,q-s_work.work_time);printf(完成时间是

17、：%d ,w_finish_timei+1);printf(周转时间是：%d n,w_rel_timei+1);voidshowmenu()printf(*n);printf(请选择你要执行的命令: n);printf(1：先来先服务算法n);printf(2：短作业优先算法n);printf(3: 高响应比优先算法n);printf(0: 退出菜单n);printf(*n);void HRRN()intw_rel_time10;intw_finish_time10;floatrel_time = 0;float priority; /计算优先权srand(time(0);inti;int j

18、 = 0;PNODE pHead = (PNODE)malloc(sizeof(NODE);if (NULL = pHead)printf(分配失败, 程序终止!n);exit(-1);PNODE pTail = pHead;pTail-pNext = 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;pTai

19、l = 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(第%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(

20、p-s_work.arrive_times_work.arrive_time) q = p;p = p-pNext;PNODE r = 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-

21、s_work.arrive_time )if( p-s_work.work_times_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);pri

22、ntf(服务时间是：%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; /已经找到并执行第一个进程，执行完之后又将其删除了for(i=0;ipNext != q )p = p-pNext; p-pNext = q-pNext;free(q);q = NULL; for(j=0

23、;jpNext;q = p;while(p != NULL) if( p-s_work.arrive_timepNext;elsep = p-pNext; /q指向当前到达时间小于刚刚完成的作业，但有可能有另外几个进程也已经到达了，所以要进行下面的判断printf(系统中有%d个作业在当前作业完成时已经到达！n,cnt);p = pHead-pNext;while(p != NULL)if(cnt1) /说明此时有好几个都已经到达了if(p-s_work.arrive_times_work.wait = w_finish_timei - p-s_work.arrive_time;p = p-p

24、Next;elsep-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_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;w