单处理器调度

一、调度类型

​ 长程调度：决定是否把进程加入当前活跃的进程集中。创建进程时发生。

​ 中程调度：它是交换过程的一部分，它决定是否把进程添加到就绪队列或阻塞、挂起队列中

​ 短程调度：决定处理器执行哪个可运行的进程

​ IO调度：决定可用IO设备处理哪个进程的IO请求

二、短程调度

1.调度规则

​ 面向用户：与单个用户或进程感知到的系统行为有关。如交互式程序的响应时间，这是用户可以感受到的，面向用户调度力求降低响应时间。

​ 面向系统：重点是提高处理器的使用效果和效率

一些名词

​ 周转时间：一个进程从提交到完成的时间。包括实际执行时间和等待资源（处理器资源、IO资源等）时间

​ 归一化周转时间：周转时间与实际执行时间的比值

​ 响应时间：交互式进程从提交请求到得到相应所经过的时间

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

​ 处理器利用率：处理器处于忙状态的百分比

2.优先级

​ 许多系统中，每个进程被指定一个优先级，调度程序优先选择优先级高的进程调度。系统通常维护一组优先级队列，一个优先级维护一个队列。纯优先级调度会出现优先级低的进程饥饿的问题、

3.决策模式

​ 抢占：当前中运行的进程可能被操作系统中断，并转为就绪态。如出现时间中断时，需要进行抢占决策

​ 非抢占：一旦进程处于运行态，它会一直执行到终止。除非出现等待IO或系统调用而阻塞。

三、调度算法

1.先来先服务（FCFS）

​ 这种方法十分简单，每个进程就绪后加入就绪队列，系统从队列中依次取出进程执行。FCFS更适用于长进程。

​ FCFS更有利于处理器密集型进程。若一个IO密集进程因等待IO被阻塞，调度算法选择了一个处理器密集型进程来执行。在执行过程中，可能IO完成了，但IO密集进程只能等待。导致大多IO设备空闲。

2.轮转

​ 轮转算法是基于时钟的抢占策略。系统给每个进程分配一个时间片，时间片结束，进执行中的进程被抢占，按FCFS在就绪队列中选择一个进程来执行。

​ 时间片长度最好略大于一个经典交互的时间，但不能过大。

​ 这种方式在分时系统或事务处理系统中很有效。但由于IO密集型进程短时间使用处理器后便会阻塞，而处理器密集型进程可以用完整个时间片。所以这种算法对IO密集进程不公平，使得进程性能 降低。

虚拟轮转法

​ 为了优化上述问题，虚拟轮转法加入了一个辅助队列。由于等待IO而阻塞的进程阻塞结束后会加入辅助队列，进行调度时，辅助队列中的进程优先于就绪队列

3.最短进程优先（SPN）

​ 这是一个非抢占策略，它的原则是下次选择预计处理时间最短的进程。

​ 对短作业有利，对长作业不利。可能产生饥饿现象。另外，进程/作业的运行时间都是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。

4.最短剩余时间（SRT）

​ 在SPN算法中增加了抢占机制。调度程序总是选择预期剩余时间最短的进程。

​ 每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理器，当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度。

​ 同样有长进程饥饿风险

5.最高响应比优先（HRRN）

​ 响应比即归一化周转时间

​ 响应比R = (w+s）/ s

​ w:等待处理器的时间 s：预计服务时间

​ 当前进程完成或阻塞时，选择响应比最大的进程。它相对于前两种算法，比较公平。因为它反映了进程的年龄。偏向短进程时，长进程由于得不到服务，等待时间一直增加，R变大，最终赢过短进程。

6.反馈法

​ 反馈法触发运行时间较长的进程。调度基于抢占原则并使用动态优先级机制。一个进程刚进入系统时，优先级最高，之后每被抢占一次，优先级下降一级。短进程会很快执行完毕，长进程会 多次降级。因此新进程和短进程会优于老进程和长进程。

优先级降到最低后不会再降，会重复返回到最低优先级队列。

​ 为了避免老进程和长进程饥饿，当一个进程在当前队列中等待服务的时间超过一定时间后，就把它的优先级提高一级

7.总结


​