操作系统响应比高者优先调度算法的思想?
最高响应比优先法(HRN,Highest Response_ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短,而SJF方式只考虑执行时间而未考虑等待时间的长短。因此,这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短,从中选出响应比最高的作业投入执行。 响应比R定义如下: R =(W+T)/T = 1+W/T
其中T为该作业估计需要的执行时间,W为作业在后备状态队列中的等待时间。每当要进行作业调度时,系统计算每个作业的响应比,选择其中R最大者投入执行。这样,即使是长作业,随着它等待时间的增加,W / T也就随着增加,也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行,在同一时间内处理的作业数显然要少于SJF法,从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外,由于每次调度前要计算响应比,系统开销也要相应增加
(1)等待时间相等时。则服务时间越短,优先级越高,符合SJF思想。
(2)服务时间相等时,则等待时间越长,优先级越高,符合FCFS思想。
(3)对于长作业,只要其等待时间足够长,也能获得处理机。
怎样实现短作业优先和高响应比优先算法
1.先来先服务调度算法(FCFS):就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单,公平。其缺点是没有考虑到系统中各种资源的综合使用情况,往往使短作业的用户不满意,因为短作业等待处理的时间可能比实际运行时间长得多。
2.短作业优先调度算法(SPF): 就是优先调度并处理短作业,所谓短是指作业的运行时间短。而在作业未投入运行时,并不能知道它实际的运行时间的长短,因此需要用户在提交作业时同时提交作业运行时间的估计值。
3.最高响应比优先算法(HRN):FCFS可能造成短作业用户不满,SPF可能使得长作业用户不满,于是提出HRN,选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。
4. 基于优先数调度算法(HPF):每一个作业规定一个表示该作业优先级别的整数,当需要将新的作业由输入井调入内存处理时,优先选择优先数最高的作业。
5.均衡调度算法,即多级队列调度算法
基本概念:
作业周转时间(Ti)=完成时间(Tei)-提交时间(Tsi)
作业平均周转时间(T)=周转时间/作业个数
作业带权周转时间(Wi)=周转时间/运行时间
响应比=(等待时间+运行时间)/运行时间
什么是高响应比优先调度算法,它采用何种调度方式
高响应比优先调度算法就是把CPU分配给就绪队列中响应比最高的进程。响应比=等待时间/要求服务时间+1。采用非抢占式调度方式。030
高响应比优先调度算法
该算法实际上是一种动态优先调度算法,它以相应比作为作业或进程的动态优先权,其目的是既照顾短作业,又考虑到作业的等待时间,使长作业不会长期等待;但每次调度前,都要进行响应比计算,会增加系统开销。
求一份儿C语言优先级调度算法要求如下
#include “string.h”
#define n 10/*假定系统中可容纳的作业数量为n*/
typedef struct jcb
{char name[4];/*作业名*/
int length;/*作业长度,所需主存大小*/
int printer;/*作业执行所需打印机的数量*/
int tape;/*作业执行所需磁带机的数量*/
int runtime;/*作业估计执行时间*/
int waittime;/*作业在系统中的等待时间*/
int next;/*指向下一个作业控制块的指针*/
}JCB;/*作业控制块类型定义*/
int head; /*作业队列头指针定义*/
int tape,printer;
long memory;
JCB jobtable[n];/*作业表*/
int jobcount=0;/*系统内现有作业数量*/
shedule( )
/*作业调度函数*/
{float xk,k;
int p,q,s,t;
do
{p=head;
q=s=-1;
k=0;
while(p!=-1)
{ if(jobtable[p].length=memoryjobtable[p].tape=tapejobtable[p].printer=printer)
{ /*系统可用资源是否满足作业需求*/
xk=(float)(jobtable[p].waittime)/jobtable[p].runtime;
if(q==0||xkk)/*满足条件的第一个作业或者作业q的响应比小于作业p的响应比*/
{k=xk;/*记录响应比*/
q=p;
t=s;
}/*if*/
}/*if*/
s=p;
p=jobtable[p].next;/*指针p后移*/
}/*while*/
if(q!=-1)
{ if(t==-1)/*是作业队列的第一个*/
head=jobtable[head].next;
else
jobtable[t].next=jobtable[q].next;
/*为作业q分配资源:分配主存空间;分配磁带机;分配打印机*/
memory=memory-jobtable[q].length;
tape=tape-jobtable[q].tape;
printer=printer-jobtable[q].printer;
printf(“选中作业的作业名:%s\n”,jobtable[q].name);
}
}while(q!=-1);
}/*作业调度函数结束*/
main( )
{char name[4];
int size,tcount,pcount,wtime,rtime;
int p;
/*系统数据初始化*/
memory=65536;
tape=4;
printer=2;
head=-1;
printf(“输入作业相关数据(以作业大小为负数停止输入):\n”);
/*输入数据,建立作业队列*/
printf(“输入作业名、作业大小、磁带机数、打印机数、等待时间、估计执行时间\n”);
scanf(“%s%d%d %d %d %d”,name,size,tcount,pcount,wtime,rtime);
while(size!=-1)
{/*创建JCB*/
if(jobcountn)p=jobcount;
else { printf(“无法再创建作业\n”);
break;
}
jobcount++;
/*填写该作业相关内容*/
strcpy(jobtable[p].name,name);
jobtable[p].length=size;
jobtable[p].printer=pcount;
jobtable[p].tape=tcount;
jobtable[p].runtime=rtime;
jobtable[p].waittime=wtime;
/*挂入作业队列队首*/
jobtable[p].next=head;
head=p;
/* 输入一个作业数据*/
printf(“输入作业名、作业大小、磁带机数、打印机数、等待时间、估计执行时间\n”);
scanf(“%s%d%d%d%d%d”,name,size,tcount,pcount,wtime,rtime);
}/*while*/
shedule( );/*进行作业调度*/
}/*main( )函数结束*/