第九章

第九章单处理器调度

了解

调度的评价准则

面向用户

响应时间：从任务提交到开始有响应输出的时间，一般的当处理器开始处理任务时即开始有输出。

周转时间：从任务提交到任务完成的时间。

最后期限：当可以指定最后期限时，操作系统降低其它目标，是满足最后期限的作业数目的百分比达到最高。

可预测性：无论系统当前负载情况是繁重还是空闲，一个给定工作完成的总时间和总代价应该是相等的。

面向系统

吞吐量：单位时间内完成的进程数。

处理器利用率：处理器处于忙状态的时间百分比。对于昂贵的共享系统来说这是一个重要的准则，对于个人系统则显得不那么重要。

公平性：没有来自用户或其它系统的指导时操作系统应该公平的对待所有进程，没有一个进程会处于饥饿状态。

强制优先级：当指定了优先级后调度策略应优先响应高优先级的进程。

平衡资源：调度策略应是系统的所有资源保持忙碌的状态，较少使用紧缺系统资源的进程应该得到照顾。

理解

调度类型

短程调度

决定哪一个就绪的进程将被执行，比如：从就绪队列中选取进程执行

中程调度

决定进程的部分或全部加入到内存中，比如：阻塞态到阻塞/挂起态的转换，就绪态到就绪/挂起态的转换

长程调度

决定是否将新建进程加入到待执行的进程池中，比如：新建态到就绪态

决策模式（decision mode）

非抢占式，一旦进程处于运行态，它就不断地执行直到终止，不能被操作系统中断，直至该进程完成或发生某种事件（如I/O请求），才主动放弃。

抢占式，当前正在运行的进程可以被系统中断，转移到就绪态。

进程调度算法

先来先服务（FCFS）

没有优先级和抢占，所有进程按照加入的顺序执行。这样的调度偏向于执行时间长的进程。FCFS策略本身对操作系统不是很有吸引力，但是它经常和优先级系统配合使用产生有价值的调度策略。

轮转（RP）

对处理器资源进行时间分片，依次分配相同的时间资源给每个就绪的进程。轮转的时间片最好略大于一次典型交互的时间，当时间片足够大时退化为FCFS策略。

最短进程优先（SPN）

具有最短执行时间的进程有更高的优先级，它依赖于系统估计进程的执行时间，在批处理系统中任务加入时程序员给出任务的估计时间，如果任务执行时间远远超过给出的估计时间它将被废弃。在生产环境中有大量的重复任务，系统将监控每次任务执行的时间以估计执行时间，最简单的公式是s=(各次时间和)/n，一个避免每次求和的优化是s=S(n-1) + Tn/n，上述公式每次执行的权值是相同的，典型情况下我们希望最近的执行情况有更大的权值Sn+1 = aTn + (1-a)Sn。

最短剩余时间（SRT）

是SPN的改进版本增加了抢占机制，在不断有短进程加入的情况下长进程可能处于饥饿状态。

最高响应比优先（HRRN）

使用公式(w+s)/s，其中w是等待时间，s是服务时间。操作系统始终选择具有最高相应比的进程，同样需要估计和记录进程的服务时间。该策略非常具有吸引力，当偏向短进程时，长进程由于得不到处理响应比不断增加。

反馈（FB）

不想SPN、STR、HRRN策略那样需要估计时间，反馈策略倾向于短进程，它具备多个队列Q1~Qn，当进程加入时处于Q1队列中，采用FCFS的顺序服务队列中的每个进程，当进程允许超过时间阈值时中断并加入到下一级队列中Q2，依次类推。Q1具有最高的优先级，只有Q1中不存在进程是才执行下一级的队列。这样可能导致的问题是过长的队列可能加入到Qn队列后处于饥饿状态，因此要见识进程的等待时间，如果超过一定长度则重新调入到Q1中。