（学习笔记-进程管理）进程调度

进程都希望自己能够占用CPU进行工作，那么这涉及到前面说过的进程上下文切换。

一旦操作系统把进程切换到运行状态，也就意味着该进程占用着CPU在执行，但是操作系统把进程切换到其他状态的时候，就不能在CPU中执行了，于是操作系统会选择下一个要运行的进程。

选择一个进程运行这一功能是在操作系统中完成的，通常称为调度程序（scheduler）。

---

调度时机

在进程的生命周期中，当进程从一个运行状态到另一个状态变化的时候，其实就会触发一次调度。

比如：

• 从就绪态 -> 运行态：当进程被创建的时候，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行
• 从运行态 -> 阻塞态：当进程发生I/O事件而阻塞时，操作系统必须选择另外一个进程运行
• 从运行态 ->结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行

因为，这些状态变化的时候，操作系统是需要考虑是否要让新的进程给CPU运行，或者是否让当前进程从CPU上退出来而换到另一个进程运行。

另外如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断，把调度算法分为两类：

• 非抢占式调度算法挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另一个进程，也就是说不会管时钟中断这个事情
• 抢占式调度算法挑选一个进程，然后让该进程只允许某段时间，如果在该时间段结束时，该进程仍然在运行，则会将其挂起，接着调度程序从就绪队列中挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把CPU控制返回给调度程序进行调度，也就是时间片机制

---

调度原则

原则一：如果运行的程序发生了I/O事件的请求，那么CPU使用率肯定很低，因为此时进程在阻塞等待硬盘的数据返回。这样的过程势必会造成CPU突然的空闲。所以，为了提高CPU利用率，在这种发送I/O事件致使CPU空闲的情况下，调度程序需要从就绪队列中选择一个进程来运行。

原则二：有的程序执行某个任务花费的时间会比较长，如果这个程序一直占用着CPU，会造成系统吞吐量（CPU单位时间内完成的进程数量）的降低。所以，要提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量。

原则三：从进程开始到结束的过程中，实际上是包含两个时间，分别是进程运行时间和进程等待时间，这两个时间总和就称为周转时间。进程的周转时间越小越好，如果进程的等待时间很长而运行的时间很短，那周转时间就很长，这不是我们所希望的，调度程序应该避免这种情况发生。

原则四：处于就绪队列的进程，也不能等太久，当然希望这个等待的时间越短越好，这样可以使得进程更快的在CPU中执行。所以，就绪队列中进程的等待时间也是调度程序所需要考虑的原则。

原则五：对于鼠标、键盘这种交互式比较强的应用，我们当然希望它的响应时间越快越好，否则就会影响用户体验。所以，对于交互式比较强的应用，响应时间也是调度程序需要考虑的原则。

 针对上面的五种调度原则，总结成如下：

• CPU利用率：调度程序应确保CPU是始终匆忙的状态，这可以提高CPU的利用率
• 系统吞吐量：吞吐量表示的是单位时间内CPU完成进程的数量，长时间的进程会占用较长的CPU资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量
• 周转时间：周转时间是进程运行 + 阻塞时间 + 等待时间的总和，一个进程的周转时间越小越好
• 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待时间越长，用户越不满意
• 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

---

调度算法

不同的调度算法适用的场景也是不同的。

单核CPU系统中常见的调度算法：
 

先来先服务调度算法

最简单的一个调度算法，就是非抢占式的先来先服务算法（FCFS）：

 每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

这似乎很合理，但是当一个作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。

FCFS对长作业有利，适用于CPU繁忙型作业的系统，而不适用于I/O繁忙型作业的系统。

最短作业优先调度算法

最短作业优先（SJF）调度算法，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

 这显然对长作业不利，很容易造成一种极端现象。

比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断地往后推，周转时间边长，致使长作业长期不会被运行。

高响应比优先调度算法

前面的 [先来先服务调度算法] 和 [最短作业优先调度算法] 都没有很好的权衡短作业和长作业。

那么，高响应比优先（HRRN）调度算法主要是权衡了短作业和长作业。

每次进行进程调度时，先计算 [响应比优先级] ，然后把 [响应比优先级]最高的进程投入运行， [响应比优先级]的计算公式：

从上面的公式可以发现：

•  如果两个进程的 [等待时间] 相同， [要求的服务时间] 越短，[响应比] 就越高，这样短作业的进程容易被选中运行
• 如果两个进程 [要求的服务时间] 相同时， [等待时间] 越长，[响应比] 就越高，这就兼顾到了长作业的进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会；

但是进程要求的服务时间是不可知的，所以高响应比优先调度算法是理想型的调度算法，现实中是实现不了的。

时间片轮转调度算法

最古老，最简单，最公平且最广泛的算法就是时间片轮转（RR）调度算法。

 每一个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行。

• 如果时间片用完，进程还在运行，那么将会把此进程从CPU释放出来，并把CPU分配给另外一个进程
• 如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换

另外，时间片的长度就是一个很关键的点：

• 如果时间片设的太短会导致过多的进程上下文切换，降低了CPU效率
• 如果设的太长了又可能引起对短作业进程的响应时间变长

一般来说，时间片设为 20ms~50ms 通常是一个比较合理的折中值

最高优先级调度算法

前面的 [时间片轮转算法] 做了个假设，即让所有的进程同等重要，大家的运行时间都是一样。

但是，对于用户计算机系统，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（HPF）算法。

进程的优先级可以分为，静态优先级和动态优先级：

• 静态优先级：创建进程的时候，就已经确定了，然后整个运行时间优先级都不会变化
• 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级

该算法也有两种处理优先级的方法，非抢占式和抢占式：

• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

多级反馈队列调度算法

多级反馈队列（MFQ）调度算法是 [时间片轮转算法] 和 [最高优先级算法] 的综合和发展。

•  [多级] 表示有多个队列，每个队列的优先级从高到低，同时优先级越高时间片越短
•  [反馈] 表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列

 工作方式：

• 设置多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短
• 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成
• 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行。

可以发现，对于短作业可能可以在第一级队列很快被处理完成。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待时间变长了，但是运行时间也变长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。