( Round - Robin , RR )
算法思想:
公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应 ;
算法规则:
按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片( 时间片长度由自己定义 )若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队;
用于作业 / 进程调度:
用于进程调度( 只有作业放入内存建立了相应的进程后,才能被分配处理机时间片 )
是否可抢占:
若进程没有在时间片内运行完,将被强制剥夺处理机使用权,所以时间片轮转是抢占式的算法;
优缺点:
优点:
公平、响应快,适用于分时操作系统;
缺点:
- 由于高频率的进程切换,因此有一定开销;
- 不会区分任务的紧急程度;
是否会导致饥饿:(某进程 / 作业长期得不到服务)
不会
补充:
- 如果时间片太大,每个进程都可以在一个时间片内完成,会导致徒增响应时间,那么适合退化为先来先服务的调度算法;
- 如果时间片太小,那么会导致进程切换过于频繁,系统花费大量的时间进行处理进程的切换,从而导致实际用于执行的时间在总时间的比例降低;
- 也就是说时间片轮转算法的时间片取值不适合时间片过大和过小;
算法思想:
根据就绪队列中任务的紧急程度进行排列处理顺序;
算法规则:
调度时选择优先级最高的作业 / 进程;
用于作业 / 进程调度:
即可用于作业调度,也可用于进程调度;
是否可抢占:
抢占和非抢占都有,区别在于抢占式会中断正在运行的进程优先运行高优先级的进程,而非抢占式的只会在当前进程结束后再进行判断进入进程的优先级;
优缺点:
优点:
用优先级区分紧急程度、重要程度,适用于实时操作系统,可以调整对于作业 / 进程的优先程度;
缺点:
如果一直有高优先的进程到来会导致饥饿;
是否会导致饥饿:(某进程 / 作业长期得不到服务)
会;
补充:
优先级分为两种:
**静态优先级:**创建进程时确定,之后一直不变;
**动态优先级:**创建进程时有一个初始值,之后会根据情况动态地调整优先级;
算法思想:
对其他调度算法的折中权衡;
算法规则:
- 设置多级就绪队列,各级队列优先级由高至低,时间片从小到大;
- 新进程到达时先进入第 1 级队列排队等待被分配时间片,如果时间片用完进程还未结束则进程进入下一级队列队尾,若处于最下级的队列则放入队尾;
- 只有第 k 级队列为空时,才会为 k + 1 级队列发进程分配时间片;
用于作业 / 进程调度:
用于进程调度;
是否可抢占:
抢占式的算法,在第 k 级进程运行时,如果 k 级前进入了一个新进程,则优先处理新进程,被抢占的进程放入当前队列的队尾;
优缺点:
优点:
- 对各类型进程相对公平;
- 每个新到达的进程都可以很快就得到响应;
- 短进程只用较少的时间就可完成
- 不必实现估计进程的运行时间;
- 可灵活的调整对各类进程的偏好程度;
是否会导致饥饿:(某进程 / 作业长期得不到服务)
会;