进程调度算法

一.先来先服务调度算法FCFS

最简单的调度算法。按照先后顺序选择作业队列中的作业进行调度。

有利于长作业（进程），不利于短作业（进程）。长作业一旦开始就要执行完成。相对来说短作业需要等待更长的时间。

二.短作业优先SJF

从后备队列中选择估计运行时间最短的作业。

短进程优先SPF

短作业或短进程优先调度算法，有利于短作业的执行，不利于长作业的执行。长作业有可能一直等到短作业的执行，而得不到执行机会。

缺点：

• 不利于长作业
• 未考虑作业的紧迫程度
• 预估执行时间和实际的执行时间可能有出入

三.高优先权优先调度算法

每个作业有一个优先权级别，每次调度时选择优先权最高的来执行。

分为非抢占式优先权算法和抢占式优先权算法

优先权分为静态优先权（保持不变）和动态优先权（例如可以随等待时间的增长而提高优先权、采用抢占式优先权算法当前进程的优先权随执行时间而下降，从而避免一个长作业长时间占用处理器）

四.基于时间片的轮转调度算法

用于分时系统。

4.1时间片轮转法

将所有就绪进程按FCFS原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行完后，将该进程放入就绪队列的队尾；然后再处理队列中新的队首进程。

需要选择一个合适的时间片大小。太小会导致进程切换频繁而增大切换的开销。太大会降低实时性。

4.2多级反馈队列调度算法

不必事先知道进程的执行时间。满足各种类型进程的需要。是公认的较好的一种进程调度算法。

算法描述：
1.设置多个优先级依次递减、时间片依次递增的的就绪队列。时间片每一级增长一倍。
2.当一个新进程进入内存后，先将其放入第一个优先级队列的末尾，按FCFS原则排队等待调度。如果在第一次调度后没有执行完成，则将其放入第二个队列的末尾……依次往下，直到将其放入最后一个队列，此时则继续按时间片轮转等待调度但不再切换所在队列
3.仅当第一队列空闲时，调度程序才调度第二队列中的进程；仅当1-(i-1)队列均空时，才会调度第i队列中的进程运行。如果正在执行第i队列，此时1-（i-1）队列中有新进入的进程，则抢占式进行。

优点：满足了各类用户的需要。

• 终端型作业用户，大多是交互式作业，执行时间较短，一般在第一个队列就能执行完
• 短作业，很快执行完
• 长作业，最多到最后一个队列等待轮转，不能长时间得不到指行

---