【操作系统】进程是如何调度的？

调度

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

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

调度时机

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

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

调度原则

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

调度算法

调度算法分为两类：

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

先来先服务调度算法

先来先服务（FCFS）算法是非抢占式的调度算法。

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

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

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

最短作业优先调度算法

最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

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

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

时间片轮转调度算法

最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法。

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

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

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

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

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

最高优先级调度算法

前面的「时间片轮转算法」做了个假设，即让所有的进程同等重要，也不偏袒谁，大家的运行时间都一样。

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

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

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

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

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

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

多级反馈队列调度算法

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

顾名思义：

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

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

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

参考链接：小林coding