《作业调度算法(先来先服务算法短作业算法)》由会员分享,可在线阅读,更多相关《作业调度算法(先来先服务算法短作业算法)(45页珍藏版)》请在金锄头文库上搜索。
1、操作系统实验报告题目:作业调度算法班级:网络工程姓名:朱锦涛学号: E31314037一、实验目的用代码实现页面调度算法,即先来先服务( FCFS调度算法、 短作业优先算法、高响应比优先调度算法。 通过代码的具体实现,加深对算法的核心的理解。二、实验原理1 .先来先服务(FCFS调度算法FCFSM最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,系统将按照作业到达的先后次序来进行调度,或者说它是优先考虑在系统中等待时间最长的作业,而不管该作业所需执行的时间的长短,从后备作业队列中选择几个最先进入该队列的作业,将它们调入内存,为它们分配资源和创建进程。然后把
2、它放入就绪队列。2 . 短作业优先算法SJF 算法是以作业的长短来计算优先级,作业越短,其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时,它将从外存的作业后备队列中选择若干个估计运行时间最短的作业,优先将它们调入内存。3、高响应比优先调度算法高响应比优先调度算法则是既考虑了作业的等待时间,又考虑了作业的运行时间的算法,因此既照顾了短作业,又不致使长作业等待的时间过长,从而改善了处理机调度的性能。如果我们引入一个动态优先级,即优先级是可以改变的令它随等待的时间的延长而增加,这将使长作业的优先级在等待期间不断地增加
3、,等到足够的时间后,必然有机会获得处理机。该优先级的变化规律可以描述为:优先权 = (等待时间 + 要求服务时间) / 要求服务时间三、实验内容源程序:#include#include#includestruct worki nt id;i nt arrive_time;i nt work_time;i nt wait;f loat priority;typedef struct sjf_workstruct work s_work; / 数据域struct sjf_work * pNext; /指针域NODE,*PNODE;void FCFS();void SJF();void showme
4、nu();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(
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)
6、;printf( 感谢您使用本系统,再见! );r eturn 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;i5;i+)wi.id = rand()%10;wi.arrive_time = rand()%10;wi.work_time = rand()%10+1;f or(j=0;j5;j+)printf(第dj作业的编号是:%dt,j+1,wj.id);pr
7、intf(第个作业到达时%dt,j+1,wj.arrive_time);printf(第个作业服务时%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
8、+1.work_time;elsew_finish_timej+1 = w_finish_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; / 定义该链表有头结点,且第一个节点初始化为空f or(i=0;is_work.id = rand()%100;pNew-s_work.arrive_time = rand()%10;pNew-s_work.work_ti
9、me = 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(第个作业到达时间:%dt,j+1,p-s_work.arrive_time);printf(第个作业服务时间:%dt,j+1,p-s_work.work_time);printf(n);p = p-pNext;printf(n);j+;只供学习与交流p = pHead-pN
10、ext;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 也指向第一个节点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 !=
11、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;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(服务时间是:%dn,q-s_work.work_time);printf(完成时间是:%d,w_finish_time0);printf(周转时间是:%dn,w_rel_time0);p = pHead; / 寻找 q 的前一个节点,方便删掉q 节点while( p-pNext != q )p = p-pNext;p-pNext = q-pNext;f ree(q);只供学习与交流q = NULL;f o