2.4 进程调度算法

2.4.5 高响应比优先

　　先来先服务算法与最短作业优先算法都是比较片面的调度算法。先来先服务算法只考虑作业的等候时间而忽视了作业的计算时间，而最短作业优先算法恰好与之相反，它只考虑用户估计的作业计算时间而忽视了作业的等待时间。响应比最高者优先算法（Highest Response Ratio First）是介乎这两种算法之间的一种折中的策略，既考虑作业等待时间，又考虑作业的运行时间，这样既照顾了短作业又不使长作业的等待时间过长，改进了调度性能。缺点是每次计算各道作业的响应比会有一定的时间开销，需要估计期待的服务时间，性能要比SJF 略差。
　　在批处理系统中，短作业优先算法是一种比较好的算法，但不足之处是长作业的运行得不到保证。如果能为每个作业引入前面所述的动态优先级，并使作业的优先级随着等待时间的增加而以一定速率提高，则长作业在等待一定的时间后，必然有机会分配到处理机，该优先级的变化规律可描述为：

优先级 = (等待时间+要求服务时间)/要求服务时间

　　由于等待时间与服务时间之和，就是系统对该作业的相应时间，故该优先级又相当于响应比Rp。因此，又可表示为：

Rp = (等待时间+要求服务时间)/要求服务时间 = 响应时间/要求服务时间

　　例如，若有表2-3所示四个作业先后到达系统进入调度：

　　假设系统中没有其他作业，现对它们实施SJF 调度算法，这时的作业调度顺序为作业1、3、4、2，平均作业周转时间T=(20+25+35+50)/4=32.5。平均带权作业周转时间W=(20/20+25/5+35/10+50/15)/4=3.2。
　　如果对它们施行FCFS 调度算法，这时的作业调度顺序为作业1、2、3、4，平均作业周转时间T=(20+35+40+50)/4=36.25。平均带权作业周转时间W=(20/20+35/15+40/5+50/10)/4=4.1。
　　如果对这个作业流执行HRRF 调度算法：
　　开始时只有作业1，作业1 被选中，执行时间20；
　　作业1 执行完毕后，响应比依次为1+15/15、1+10/5、1+5/10，作业3 被选中，执行时间5；
　　作业3 执行完毕后，响应比依次为1+20/15、1+10/10，作业2 被选中，执行时间15；
　　作业2 执行完毕后，作业4 被选中，执行时间10。
　　平均作业周转时间T=(20+25+40+50)/4=33.75。
　　平均带权作业周转时间W=(20/20+25/5+40/15+50/10)/4=3.4。
　　由此可见HRRF的性能界于SJF和FCFS之间。