操作系统之进程与线程4——进程调度
一、进程调度策略
进程调度策略依照不同的应用也有不同的策略，比如卫星导航系统需要实时性强、嵌入式系统需要省电等调度策略具体实现。而且面对不同的情况，有无穷尽的调度策略，因此本文只讨论一般普通PC机的几种一般调度策略。
由前边进程、线程切换的知识可知，进程调度策略即是：如何从进程就绪队列中选取下一个即将运行的进程（即作为p_NEXT，进行进程切换），从而实现多进程的并发执行。
进程调度（又称 低级调度）是操作系统的最基本的一种调度，在一般操作系统中都必须配置进程调度（不可或缺）。进程调度的频率很高，一般几十毫秒一次。
进程调度策略满意度判断？
CPU调度策略的目标应该是：进程满意—— 时间问题：- 周转时间短（任务进入到任务结束）：尽快结束任务；—— 多为后台计算任务，编译等
- 响应时间短（从操作到得到响应）：用户的操作尽快得到响应；—— 多为前台实时响应操作
- 内耗时间少：吞吐量大（完成任务量多）；—— 注：进程、线程切换时间等都是内耗
如何做到合理调度？
—— 需要折中、综合 ...
- 响应时间可以通过时间片的方式处理，但时间片越短，即切换越频繁，系统内耗增加，系统吞吐量减少。
- 一个操作系统需要处理好多种任务，既有Word、PPT等，又有编译、计算等各种任务，同时类似Word也不仅有前台操作，也有好多后台计算操作。
- 前台任务更需要响应时间短；后台任务更需要周转时间短；
- 类似read()、Word输入输出等任务，CPU操作时间很短即转入IO操作；而类似GCC等任务大多时间都需要CPU计算。——因此IO约束型任务优先级更高一些，执行很短时间该任务即可切换至其他任务，可以实现多任务并发执行；若CPU约束型任务优先级高，即先执行此任务时间太长，则可能对其他任务产生饥饿。
- IO约束型任务更类似于前台任务，需要不断地完成交互，因此响应时间要求短，可以设置优先级高一些。
各种CPU基本调度算法
第一种：FCFS + 短作业优先（SJF）
先来先服务——> 短作业优先提高 短作业的周转时间，提高短作业的满意度，从而提高总体满意度。
优缺点：
此种方法平均周转时间最短（可证明），但对进程调度的响应时间没有考虑。——> 采用时间片轮转调度（RR：Round Robin）
分成小时间片，轮转调度各个任务，在时间片内完成任务则切换下一个任务。
优缺点：
时间片小：保证响应时间短，但频繁切换任务导致吞吐量小；
时间片大：难以保证响应时间；
——> 因同时必须限制进程的个数，减小响应时间最大值。
同时有后台任务和前台任务存在时，Word更关心响应时间，GCC更关心周转时间如何做到让两个任务都满意？
——> 直观想法：采用两个任务队列，队列中采用不同的调度策略，队列间采用优先级调度（前台任务优先级高）——> 产生问题：若采用绝对优先调度，如果一直有前台操作时，可能有后台任务产生“饥饿”——> 因此，优先级应该采用动态优先级，若后台任务长时间得不到运行，需要动态调整其优先执行——>但此时前台任务的响应时间又得不到满足.......产生矛盾。
仍然存在的问题？
- 如何区分前台任务，后台任务？——> 算法应该有一定的学习机制，可以动态识别；
- 前台任务含有大量计算操作时，后台任务含有交互操作时？
- 如何判断作业的长度进行SJF调度？
多级反馈队列调度算法
——集合了前几种算法的优点
多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合和发展，如图2-5 所示。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；同时，也不必事先估计进程的执行时间。
- 应设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低。
- 赋予各个队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的运行时间片就越小。例如，第2级队列的时间片要比第1级队列的时间片长一倍， ……第i+1级队列的时间片要比第i级队列的时间片长一倍。
- 当一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样地按FCFS 原则等待调度执行；如果它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列……如此下去，当一个长进程从第1级队列依次降到第 n 级队列后，在第 n 级队列中便釆用时间片轮转的方式运行。
- 仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行；仅当第1 ~ (i-1)级队列均为空时，才会调度第i级队列中的进程运行。如果处理机正在执行第i级队列中的某进程时，又有新进程进入优先级较高的队列（第 1 ~ (i-1)中的任何一个队列），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i级队列的末尾，把处理机分配给新到的更高优先级的进程。