进程调度¶
基础概念¶
- 周转时间(Turnaround Time) 从提交作业到作业完成所经过的时间。
- 响应时间(Response Time) 从提交作业到作业开始执行所经过的时间。
- 抢占式调度(Preemptive Scheduling) 允许操作系统进行上下文切换，临时暂停一个正在运行的进程，并恢复（或启动）另一个进程。
几种调度算法¶
FIFO (First In First Out)¶
最简单的我们能想到先进先出调度
原理¶
FIFO 很简单，就是先来的先处理，处理完一个再处理下一个
优点¶
简单 没了，这么简单的东西你还指望什么
缺点¶
- 护航效应（convoy effect） 当一个短作业等待一个长作业完成时，短作业会被长期等待，导致效率低下。
SJF (Shortest Job First)¶
很自然的，我们会想到先处理短作业，这就是最短作业优先 SJF
原理¶
选择下一个要运行的作业时，选择剩余运行时间最短的作业。
优点¶
- 最小化平均周转时间
缺点¶
- 仍然存在护航效应 由于是非抢占式调度，长作业仍然会阻塞短作业。
STCF (Shortest Time-to-Completion First)¶
我们很容易就想到加入抢占式调度，那么这就是最短完成时间优先 STCF
原理¶
每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。
优点¶
- 最小化平均周转时间
缺点¶
- 响应时间长 由于频繁的抢占，可能导致某些作业长时间得不到执行。
RR (Round-Robin)¶
当我们希望响应时间短时（例如交互式作业），我们可以使用轮转调度 RR
原理¶
RR在一个时间片（time slice）内运行一个工作，然后切换到运行队列中的下一个任务，反复执行，直到所有任务完成。
优点¶
- 响应时间短
缺点¶
- 上下文切换开销 频繁的上下文切换会带来额外的开销，影响系统性能。
- 周转时间长 由于每个作业只能在其时间片内运行，可能导致总的周转时间大幅增加。
MLFQ (Multi-Level Feedback Queue)¶
这里我们要开始考虑一个严重的问题，大部分时候我们并不知道一个程序的运行时间 同时我们还希望兼顾响应时间和周转时间，那么我们可以使用多级反馈队列 MLFQ
原理¶
- 如果A的优先级 > B的优先级，运行A（不运行B）。
- 如果A的优先级 = B的优先级，轮转运行A和B。
- 工作进入系统时，放在最高优先级（最上层队列）。
- 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
- 经过一段时间S，就将系统中所有工作重新加入最高优先级队列。
优点¶
- 兼顾响应时间和周转时间