一.先来先服务调度算法FCFS
最简单的调度算法。按照先后顺序选择作业队列中的作业进行调度。
有利于长作业(进程),不利于短作业(进程)。长作业一旦开始就要执行完成。相对来说短作业需要等待更长的时间。
二.短作业优先SJF
从后备队列中选择估计运行时间最短的作业。
短进程优先SPF
短作业或短进程优先调度算法,有利于短作业的执行,不利于长作业的执行。长作业有可能一直等到短作业的执行,而得不到执行机会。
缺点:
- 不利于长作业
- 未考虑作业的紧迫程度
- 预估执行时间和实际的执行时间可能有出入
三.高优先权优先调度算法
每个作业有一个优先权级别,每次调度时选择优先权最高的来执行。
分为非抢占式优先权算法和抢占式优先权算法
优先权分为静态优先权(保持不变)和动态优先权(例如可以随等待时间的增长而提高优先权、采用抢占式优先权算法当前进程的优先权随执行时间而下降,从而避免一个长作业长时间占用处理器)
四.基于时间片的轮转调度算法
用于分时系统。
4.1时间片轮转法
将所有就绪进程按FCFS原则排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片。当执行完后,将该进程放入就绪队列的队尾;然后再处理队列中新的队首进程。
需要选择一个合适的时间片大小。太小会导致进程切换频繁而增大切换的开销。太大会降低实时性。
4.2多级反馈队列调度算法
不必事先知道进程的执行时间。满足各种类型进程的需要。是公认的较好的一种进程调度算法。
算法描述:
1.设置多个优先级依次递减、时间片依次递增的的就绪队列。时间片每一级增长一倍。
2.当一个新进程进入内存后,先将其放入第一个优先级队列的末尾,按FCFS原则排队等待调度。如果在第一次调度后没有执行完成,则将其放入第二个队列的末尾……依次往下,直到将其放入最后一个队列,此时则继续按时间片轮转等待调度但不再切换所在队列
3.仅当第一队列空闲时,调度程序才调度第二队列中的进程;仅当1-(i-1)队列均空时,才会调度第i队列中的进程运行。如果正在执行第i队列,此时1-(i-1)队列中有新进入的进程,则抢占式进行。
优点:满足了各类用户的需要。
- 终端型作业用户,大多是交互式作业,执行时间较短,一般在第一个队列就能执行完
- 短作业,很快执行完
- 长作业,最多到最后一个队列等待轮转,不能长时间得不到指行