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

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

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

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_workstruct work s_work; / 数据域struct sjf_work *

4、 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_

5、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");H

6、RRN();break;default:printf(" 请重新选择！");break;printf("n");printf(" 下面是菜单，请继续，或者按0退出");showmenu();文案大全实用标准文档scanf("%d",&choice);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 wor

7、k 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);p

8、rintf("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

9、+ 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（"

10、服务时间是：%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 pHea

11、d = (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 = r

12、and()%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("第个作业到达时间：%dt",j+1,p->s_work.a

13、rrive_time);printf("第个作业服务时间：%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

14、 = 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_tim

15、e )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

16、）;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 = N

17、ULL;f or(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;f or(j=0;j<10;j+

18、)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->p

19、Next;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

20、= p->pNext;/q 指向当前到达时间小于刚刚完成的作业，但不一定是服务时间最短的( 如果有的话)printf("系统中有dj作业在当前作业完成时已经到达！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 =

21、 p->pNext;elsep = p->pNext;elsep = p->pNext;else / 当前作业完成时，没有作业到达的情况p 来遍历p = p->pNext; / 用 q 来接收最先到达的，用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

22、_timei+1 = w_finish_timei + q->s_work.work_time;r eturn 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+1 = w_finish_timei+1 - q->s_work.arrive_time;printf（"第d个系统执行的作业到达时间：d",i+2,q->s_work.arrive_t

23、ime）;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"）;

24、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)实用标准文档

25、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 =

26、 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("第个作业到达时间：%dt",j+1,p->s_work.arrive_time);printf("第个作业服务时间：%dt&q

27、uot;,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

28、 = 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.w

29、ork_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_

30、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 or(i=

31、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;f or(j=0;j<

32、;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->pNe

33、xt;elsep = p->pNext;文案大全实用标准文档/q 指向当前到达时间小于刚刚完成的作业，但有可能有另外几个进程也已经到达了，所以要进行下面的判断printf(" 系统中有dj作业在当前作业完成时已经到达！ 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.arriv

34、e_time;p = p->pNext;elsep->s_work.wait = 0;p = p->pNext;else / 当前作业完成时，没有作业到达的情况q 指向第二p = p->pNext; / 此时 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.wo

35、rk_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-&

36、gt;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)q = p;p = p->pNext; elsep = p->pNext;elsep = p->pNext;printf（" 该进程优先级最高，为： %fn",q-&

37、gt;s_work.priority）;return q;实验结果：系统自动为每个算法模拟分配五个作业，同时随机生成作业的编号，作业的到达时间，作业估计运行的时间。1 . 先来先服务算法文案大全实用标准文档JpIM0 1 2 1 3 K « : X nn日_lB -B -B -UJWJ2r>w_Ex月_八个12 3n司.司印 1J!二 " nr m ftt rr nr JM达B达Myl£一-一It / Jr J? r Jr 12 3 4 3 力 r 八日 rgT?ffT7ffr =ww要算算 有 2 5 8 3 1 r*f Bc 缪¥胥嘉一公 hx

38、l til tl Fgll-?三 |-?rL8? *3 1-聿 4yrj.rf 问向勺-Z?skkkkktj、- I -3、- 一 口七 LLk l_lk 厂4- nnnH 12 3 4b Hl周转时 周转时 周转时周转 周转完成时间是；S 完成时间是：1B 完成时间是：工口完期悯是；23完成时间是：33度务时间是;9 服务时间是：之 朦务时间3 JB翁时间是:1B 服务时间是:10编号是: 编号是； 编号是: 编号是: 编号是:和个系统执行的作业到达时间; 同鼻®盍 系统执行的作业¥1达时胤 耨媒统执行的归峥I达时间: 间是：方净统执行的作业到达时间: 时间悬ifi5传统执行的作i国达时间:r面最奉单，请蛛 或者按5魏建盛令土,:TC林计服书昌4霜先器0：EW 老言 g'DebugMOPljese'文案大全该算法严格按照各作业到达时间来为其分配进程和资源，实验的结果见截图，最后算出该算法五个作业的平均周转时间。2 .短作业优先短作业优先算法考虑的比较多，系统先找出最先到达的作业，若有多个相同时间到达的作业， 则按照其运行时间长短先为时间短的服务。讦作I既算浮第作E到让时间:第z个作业到达队间,第rM乍业服务时间:第。个作业赧曷时间.1918第34、作业到达时间: 第4个作业到达时间; 第B个作业到达时间: 第心个作业到达时间: