哈工大李治军老师操作系统笔记【12】：CPU调度策略（Learning OS Concepts By Coding Them !）

0 引言

• 只讲最基本的CPU调度算法
• CPU调度就是多进程情况下自然引发的
• 调度和前面讲的切换连在一起，调度就是要获得下一个，也就是next
• 获得完next就要切换到next，进行switch_to_next，所以和那个部分结合在一起就可以使用了

0.1 一个调度例子

• 如下图，PID:1的进程阻塞了，接下来要从PD:2和PD:3的进程中挑一个，挑哪个？
• PID:2的进程是刚列read调用的，PID:3的进程时刚风列时间片用完了的，挑哪个比较好？后面回答这个问题

---

---

1 直观想法

• FIFO？优先级？实际情况比较复杂多变

---

---

• 不同场景下调度算法的目标
• 总原则：系统专注于任务执行，又能合理调配任务
• 系统内耗指的是调度与切换的时间消耗，内耗时间应该小，吞吐量应该大一点，这样系统的调度就可以
• 度量最关键的一个标准，希望时间最短，所以最核心就是时间，尽快结束任务，响应时间是从操作发生到响应的时间

---

---

1.1 折中和综合

---

---

• 前台任务更关注响应时间，后台任务更关注周转时间

• 响应时间的示意图，两个箭头之间就是响应时间，要想响应时间小，也就是前台任务，就需要切换次数多，因为切换次数一多，这个间隔的响应时间就很小

• 但是切换次数一多，系统内耗就要更大了

• 内耗大了，吞吐量就变小了

• 响应时间小，后台任务的周转时间就要受到影响，所以这是一种相互有影响的矛盾，所以需要进行折中综合考虑

---

---

• 不同场景下的矛盾与折中
• 折中和综合让操作系统变得复杂，但有效的系统又要求尽量简单……所以调度算法的具体实现可能会非常的精妙
• IO-bound和CPU-bound应该哪个优先？IO-bound，因为IO-bound只需要很短的CPU时间就进入IO阻塞了，就会释放CPU占用
• IO约束型CPU的优先级更高一点，因为如果是IO约束型高的话，CPU就会优先执行，稍微执行一段，IO就启动了，然后紧接着切出去执行，现在IO和CPU就并行起来了，而如果CPU约束，就是CPU一直运行很长时间，不停，所以IO约束型任务优先级更高
• 另一个角度，前台任务很可能是IO-bound的，需要较小的响应时间，从这个角度来说，IO-bound优先级高一点也是合理的

---

---

2 各种CPU调度算法

2.1 First Come First Served (FCFS)

• 谁先来了就先服务谁
• 也就是先来先服务算法

---

---

• 问：为什么周转时间这样算？
• 因为你后面的进程排着队等着，等待时间得算进去
• 如果把短作业提前，短作业提前结束，那么周转时间就会减小
• 所以引入：SJF：短作业优先，可以缩短周转时间

2.2 SJF（短作业优先）

---

---

• 将短作业往前提
• 那么，能不能将作业时间长短顺序从短往前排呢？
• 简单证明，这种方法导致周转时间是最小的
• 你看，假设调度顺序是$p_1{p}_2{p}_3...p_n$这样的顺序，那么包含$p_1$的有$n$项，包含$p_2$的有$n-1$项，以此类推，包含$p_n$的有$1$项，因为$p_1$乘的是$n$，系数最大，所以$p_1$越小，将来所求的数就越小
• 在计算最终的周转时间时，排在前面的任务被计算了多次，影响较大

---

---

• 所以短作业应该放在前面
• 而先来先服务保证了公平
• 所以将这两个算法进行柔和折中

2.3 时间片轮转调度

---

---

• 时间片轮转调度，主要考虑响应时间

• 这个时间片应该做的越小越好

---

---

• 同时系统中也得规定$n$的个数不能太大
• 所以一个操作系统当中，进程的个数一定是有限制的

2.4 响应时间和周转时间同时存在

• 一个调度算法没办法让多种类型的任务都满意
• 直观想法：不同类型的任务放在不同的队列中；例如分为前台任务队列和后台任务队列，前台RR（时间片轮转），后台SJF，这是典型的综合思想，只有前台任务没有时才调度后台任务

---

---

• 采用优先级调度
• 问题：前台任务优先级高，后台任务优先级低
• 前台优先级绝对高，这样会造成什么事？
• 如下，6年没有执行那个进程，好孤单的进程

---

---

• 所以说单纯的死板的固定的执行优先级调度的话，就会造成饥饿，因为一个系统中前台任务不断的出现，总是ppt，word，那么后台任务一点也别想执行，很不合适，产生饥饿
• 所以应该动态调整任务的优先级，例如后台任务的优先级动态升高
• 但是后台任务很可能是CPU-Bound的任务，所以后台任务也得有时间片，那么就一直短作业优先，一直执行直到作业完事儿就行
• 那后台一旦执行了，前台的响应时间又没法看了？这里就产生矛盾了

梳理：如果单纯的死板的固定的执行优先级调度的话，后台得不到CPU资源，会产生饥饿，周转时间（后台任务）得不到保证；如果动态优先级，优先级不断变化的话，后台任务就会上来，后台任务的优先级就会提高，而后台任务往往是CPU很长的任务，比如GCC编译很大的文件，你编译文件的时候会导致很长时间不释放CPU，那么响应时间（前台任务）又没办法保证

• 但是这样又违背了后台任务采用SF降低周转时间的初衷
• 总结：以轮转调度为核心，在此基础上增加优先级调度(SJF也是一种以时间为优先级的调度、前台任务优先级高于后台任务)

3 总结

---

---

• 怎么知道一个任务是前台任务还是后台任务
• 一个任务并不总是前台的，也并不总是后台的，GCC作为一个典型的后台应用，同样会有少量的前台操作
• SJF中，如何判断作业的长短
• 等等，还有很多折中综合的问题