进程调度的原理
需要**进程调度（Process Scheduling）**的理由很简单，即充分利用计算机系统中的CPU资源，让计算机系统能够多快好省地完成我们让它做的各种任务。
具体来说，当只有一个单核的CPU时，若同时有多个进程处于就绪状态，操作系统必须决定哪一个进程占用CPU，而进程调度器（Process Scheduler）正是负责这一工作，对应采用的调度方法就称为调度算法（scheduling algorithm）。
进程调度器希望进程们能够高效（高的吞吐量–throughput）、及时（低延迟–latency）、公平（fairness）地使用CPU。
而调度器需要设计不同的调度算法（Scheduling algorithm）来选择进程，这体现了进程调度的策略，同时还需进一步通过进程的上下文切换（context switch）来真正完成进程切换，这体现了进程调度的机制。
总体上说，我们需要在何时进行调度（调度的时机）、是否在内核执行的任意位置进行调度（调度的方式）、如何选择“合适”的进程执行调度（调度策略/调度算法）、如何完成进程切换（上下文切换）、如何评价选择的合理性（进程调度的指标）。了解上述细节，也就可以说是了解了进程调度。
当引入了线程的概念后，真正占用CPU执行的最小单元就变成了线程（而进程是资源调度的最小单元）。因此，线程与进程的调度机制是类似的，只是实现线程调度机制的实体，变成了线程调度器（thread scheduler）。
进程调度的时机
进程调度发生的时机（也称为调度点）与进程的状态变化有直接的关系。回顾进程状态变化图，我们可以看到进程调度的时机直接与进程在运行态<–>退出态/就绪态/阻塞态的转变时机相关。简而言之，引起进程调度的时机可归结为以下几类：
- 正在执行的进程执行完毕（Terminated），需要选择新的就绪进程执行。
- 正在执行的进程调用相关阻塞式系统调用（包括与I/O操作，同步互斥操作等相关的系统调用）导致需等待某事件发生或资源可用，从而切换为阻塞态（Blocked）。
- 正在执行的进程主动调用放弃CPU的系统调用，从而进入就绪态（Ready），并被放到就绪队列中。
- 等待事件发生或资源可用的进程进入就绪队列，对应从阻塞态回到就绪态，并可参与到调度中。
- 正在执行（Running）的进程的时间片已经用完，切换为就绪态（Ready），且被重新放到就绪队列中。
- 在执行完系统调用后准备返回用户进程前的时刻，可调度选择一新用户进程执行。
- 就绪队列中某进程的优先级高于当前执行进程的优先级，从而也将引发进程调度。
进程调度的方式
通常，存在两种进程调度方式：
- 非抢占式调度算法（nonpreemptive scheduling algorithm）
- 可抢占式调度算法（preemptive scheduling algorithm）
非抢占式调度算法（nonpreemptive scheduling algorithm）
非抢占式调度算法（nonpreemptive scheduling algorithm）会选择一个进程进行运行，直到该进程运行结束或进入阻塞状态。
可抢占式调度算法（preemptive scheduling algorithm）
可抢占式调度算法（preemptive scheduling algorithm）通常基于某个指标，比如**截止时间（deadline）、运行时间（burst time）或进程执行优先级（priority）**等，我们通常笼统地称其为优先级。
根据抢占的时机，又细分为：
- 基于时钟中断的抢占式优先权调度算法
- 立即抢占的优先权调度算法
基于时钟中断的抢占式优先权调度算法
当新进程到达后，如果该进程的优先级别高于当前正在执行的进程的优先级，新进程并不立即抢占当前进程的CPU，而是等到时钟中断到来时，调度程序才剥夺当前进程的执行，并将CPU分配给新到的高优先权的进程。
立即抢占的优先权调度算法
在这种调度策略中，要求操作系统具有快速响应外部时间中断的能力。
一旦出现外部中断，且新进程的优先级高于当前正在运行的进程，只要当前进程未处于临界区，便立即剥夺当前进程的执行，并把CPU分配给请求中断的紧迫任务。
在分时系统（time-sharing system）中，通常存在CPU时间片的概念。
因此，当优先级较高的进程在用完其CPU时间片后，仍然需要将时间片让给优先级较低的进程。这意味着，即使采取抢占式地进程调度方式，优先级较低的进程仍有被执行的可能（而不是直到优先级较高的进程在完成执行完成后，才将CPU时间片让给优先级较低的进程）。
进程调度的指标（metrics）
不同的进程调度算法具有不同的特征，为此需要建立衡量一个算法的基本指标。一般而言，衡量和比较各种进程调度算法性能的主要因素如下所示：
- CPU利用率（CPU utilization）：CPU是计算机系统中的稀缺资源，所以应在有具体任务的情况下尽可能使CPU保持忙，从而使得CPU资源利用率最高。
- 吞吐量（throughput）：CPU运行时的工作量大小是以每单位时间所完成的进程数目来描述的，即称为吞吐量。
- 周转时间（turnaround time）：指从进程被创建到进程被完成所经过的时间，这期间包括了由于各种因素导致的等待时间，具体包括因等待I/O操作完成而发生的进程阻塞，处于就绪态并在就绪队列中排队，在处理机上运行所花时间。
- 等待时间（waiting time）：即进程在就绪队列中等待所花的时间总和（进程从进入就绪队列至获得CPU）。因此衡量一个调度算法的简单方法就是统计进程在就绪队列上的等待时间。
- 响应时间（response time）：指从发出一个命令到得到结果所经过的时间。在交互式桌面计算机系统中，用户希望响应时间越快越好，但这常常要以牺牲吞吐量为代价。
这些指标其实是相互有冲突的，响应时间短也就意味着在相关事件产生后，操作系统需要迅速进行进程切换，让对应的进程尽快响应产生的事件，从而导致进程调度与切换的开销增大，这会降低系统的吞吐量。
调度器的类型
长期调度器（Long-term scheduling）
进程调度算法（algorithm）
进程调度算法的分类（Categories of Scheduling Algorithms）
显然，在不同的场景中，需要的调度算法是不同的。这些场景可以被分类为：
- 批处理（batch）系统
- 交互型（interactive）系统
- 实时（real-time）系统
批处理（batch）系统
批处理（batch）系统仍然被广泛地运用于工资结算、库存、银行利息计算等等周期性任务（periodic tasks）中。
由于不需要快速地响应用户的请求，非抢占式的调度算法或包含长执行周期的抢占式调度算法通常在批处理系统中被使用。由于尽可能地减少了进程切换，因而获得较高的执行效率（CPU利用率）。
交互型（interactive）系统
在包含用户交互（user interaction）的系统中，抢占式的调度算法通常被使用，这样做可以防止一个进程长时间占用CPU，从而交互可以获得很快的响应。
实时（real time）系统
在包含实时处理（real time）的系统中，抢占式的调度算法有时不会被需要，因为进程们不会长时间地占用CPU。
在实时系统中，任务通常会有执行截止时间（deadline），即任务必须在某一个时间节点前完成，否则就没有执行的意义了。举个例子，一台计算机控制一个设备（device）并使其以一定的周期定时产生监测数据，如果没有及时地采集这个监测数据，则意味着数据的丢失。因此，在新的数据产生之前（对应的截止时间），及时地采集监测数据非常重要。
批处理系统（batch systems）中的调度算法
先来先服务调度算法（FCFS: first-come, first-served）
先来先服务调度算法（FCFS: first-come, first-served）是一种最简单的非抢占式调度算法。
它基于队列的特性，早就绪的进程排在就绪队列（ready queue）的前面，迟就绪的进程排在就绪队列的后面。
先来先服务调度算法总是把当前处于就绪队列之首的那个进程优先切换为运行状态。也就是说，它只考虑进程进入就绪队列的先后，而不考虑它占用CPU的时间长短及其他因素。
换言之，先进入就绪队列的进程，先分配CPU。一旦一个进程占有了CPU，它就一直运行下去（甚至运行一天），直到该进程结束（terminated）或者被阻塞时（因为等待某事件发生而不能继续运行），才释放CPU并进行上下文切换（context switch）。当一个被阻塞的进程变为就绪状态后，它会被放入就绪队列的末端，等待被执行。
讨论
由于长任务可以长期占有CPU，因此CPU的利用率可以很高，然而，吞吐量可能会很低，而且周期时间、等待时间和响应时间可能也会很长。
先来先服务调度算法最大的缺点就是它不适合处理I/O密集型（I/O-bound）的任务。因为当一个进程因为执行I/O操作而被阻塞后，当I/O操作完成时，这个进程会被放到就绪队列的末端。只有当它前面的进程都被执行完成后，它才能被执行。因此，进程的等待时间会相对较长。而且，当这个进程的I/O操作很频繁时，进程的等待时间就会成倍数形式增加。
总结来收缩，该调度算法适用于包含大量CPU密集型（CPU-bound）的作业的场景，而不适用于包含大量I/O密集型（I/O-bound）的作业的场景。因此，由于在非科学计算使用的现代操作系统中，往往包含频繁的I/O操作，因此先来先服务调度算法并不非常适用。
- 优点：有利于长作业以及CPU密集型的作业
- 缺点：不利于短作业以及I/O密集型的作业
最短作业优先调度算法（Shortest job first）
**最短作业优先调度算法（Shortest job first）**是另一个非抢占式（nonpreemptive）调度算法。
在最短作业优先调度算法中，我们假定进程的运行时间（run time）是已知的。而事实上，一个任务的运行时间也是很容易预测的。比如，在保险公司每天后台的批处理服务中，每个索赔任务（claim）的处理时间是几乎一致的，因此根据需要处理的数量可以计算出运行时间。
我们来看一个例子，当前有4个任务 A、B、C和D，它们的运行时间（run time）分别为8、4、4和4分钟。
若以默认的顺序运行（如上图中 a 所示），则A、B、C和D任务的周转时间（turnaround time）分别为8分钟、12分钟、16分钟和20分钟，其中平均周转时间为14分钟。
若采用最短作业优先调度算法（如上图中 b 所示），则周转时间分别为4、8、12和20分钟，其中平均周转时间为11分钟。
显然，最短作业优先调度算法更优。
说明
值得一提的是，只有当所有任务的到来时间（arrival time）都相同时，最短作业优先调度算法才是最优解。
最短执行剩余时间优先调度算法（Shortest remaining time next）
最短执行剩余时间优先调度算法（Shortest remaining time next）可以看做是最短作业优先调度算法（Shortest job first）的抢占式版本。
在最短执行剩余时间优先调度算法中，当一个新任务到来时，调度器会将这个新任务执行所需要的执行时间和当前正在执行的任务所需要的剩余执行时间进行比较，如果前者小于后者，则发生抢占，即当前正在执行的任务被挂起（susspended），而新任务开始执行。
与最短作业优先调度算法类似，最短执行剩余时间优先调度算法也需要提前知道运行时间（run time）。
交互系统（interactive systems）中的调度算法
在早期操作系统的调度方式大多数是非抢占式的，这是由于早期的应用一般是科学计算或事务处理，不太把人机交互的响应时间指标放在首要位置。
在这种情况下，正在运行的进程可一直占用CPU直到进程阻塞或终止，这种方式对应的调度算法实现简单。
随着计算机的应用领域进一步扩展，计算机更多地用在了多媒体等人机交互应用上。
为此，采用可抢占式（preemptive）的调度方式可在一个进程终止或阻塞之前就剥夺其执行权，并把CPU尽快分配给另外的“更重要”进程，使得就绪队列中的进程有机会响应它们用户的I/O事件，最终获得较短的整体响应时间。
时间片轮转调度算法 (Round-robin scheduling)
时间片轮转调度算法 (Round-robin scheduling) 是最古老、简单、公平也最为被广泛使用的调度算法。
在时间片轮转调度算法中，系统将所有就绪进程按FIFO规则排队（称为就绪队列），按一定的时间间隔（time interval）把CPU分配给队列中的进程。这样，就绪队列中所有进程均可获得一个CPU时间片而运行。
时间片轮转调度算法是抢占式的。当一个进程执行到CPU时间片末端而仍没有执行完成时，它会被放到就绪就绪队列的末端，并且接着执行下一个进程。在下图的例子中，进程B就执行到CPU时间片末端但仍没有执行完成，因此被放到就绪就绪队列的末端；并且，F进程会被开始执行
说明
一个潜在的问题是如何设置时间片轮转调度算法的CPU时间片长度。
由于进行进程上下文切换（context switch）需要一定的时间，这其中包括保存、加载寄存器（register）和内存映射（memory maps）等等。
若设置较短的CPU时间片长度，会导致频繁的进程上下文切换，因而降低CPU的效率；而设置较长的CPU时间片长度，会对短交互式的请求提供较慢的响应。
在实践中，20到50毫秒通常是一个合理的取值。
基于优先级调度算法 （Priority Scheduling）
时间片轮转调度算法假定所有进程都是完全同等重要的。而事实上，不同进程应该有优先级。比如，一个处于后台运行的邮件发送进程相较于一个实时显示视频的进程，应该被设置更低的优先级。
采取基于优先级调度算法要考虑进程饿死（starving）的问题，因为高优先级的进程总是会被优先调度，具有低优先级的进程可能永远都不会被内核调度执行。
为了防止高优先级的进程无限地运行，调度器可以在每隔一定的时钟周期（clock tick）降低正在运行的进程的优先级。当这个进程的优先级低于第二高优先级的进程时，上下文切换发生。或者，可以设置一个最大CPU时间片值，当一个进程的这个最大CPU时间片被用尽时，就轮到了优先级次之的进程运行。
作为一个改进方案，结合时间片轮转调度算法，我们可以根据进程的优先级（priority）进行分组（同优先级的进程归为一组），每一组按照时间片轮转调度算法进行执行。当高优先级的进程队列为空时，次级优先级的进程队列才开始被执行。
这样做的一个不足在于，当高优先级的进程队列一直不为空时，下层的优先级的进程就一直没有机会被执行。
多级队列调度算法（Multilevel queue scheduling）
为了解决”因设置较短的CPU时间片长度，会导致频繁的进程上下文切换，因而降低CPU的效率；而设置较长的CPU时间片长度，会对短交互式的请求提供较慢的响应“的问题，
在多级队列调度算法，位于最高级进程队列的进程被分配一个CPU时间片，位于次最高级进程队列的进程被分配两个CPU时间片，而位于再次级进程队列的进程被分配四个CPU时间片。
当一个进程用完其CPU时间片而未执行完成时，将它放到下一级进程队列中。
比如，一个进程需要100个CPU时间片才能完成。最初，它使用了1个CPU时间片（此时位于最高级的进程队列），之后这个被移到次一级的进程队列，并且发生上下文切换，以让其他进程进行执行。当再次执行到这个进程时，它被提供2个CPU时间片，完成执行后又被移到再次一级的进程队列。在后续的执行中，这个进程会分别获得4、8、16、32、64个CPU时间片。在最后一次执行时，这个进程实际上只会占用37个CPU时间片（而不需要所有的被需要的64个），就完成了。
在上面这个过程中，总共发生了7次上下文切换（包括第一次运行实的加载），而如果采用朴素的时间片轮转调度算法，则需要进行100次上下文切换。
Shortest Process Next
Guaranteed Scheduling
Lottery Scheduling
Fair-Share Scheduling
实时系统（real-time systems）中的调度算法
在典型的实时系统（real-time systems）中，一个或多个外部物理设备产生刺激，计算机必须在指定的时间内完成对其的响应。
比如，CD机读取CD盘片上的位信息并发送给计算机，计算机必须在一定的时间内读取这个信息并转换为音乐进行播放。如果这个转换时间太长，这个音乐的播放就会是听起来变调的。
实时系统通常又被分别硬实时（hard real-time）或者软实时（soft real-time）：
- 硬实时意味着包含绝对的截止时间（deadline），错过这个截止时间会导致严重的错误；
- 软实时意味着偶然错过截止时间虽然是不被期望的，但是仍然可以被忍受。
进程切换（Process Switch）
为了控制进程的执行，内核必须提供挂起（suspend）一个正在运行的进程并且恢复一个之前被挂起的进程的能力，这个过程也称为进程切换（Process Switch）。
在这个过程中，虽然每一个进程拥有独立的内存地址空间（address space），所有的进程不得不共享CPU的寄存器（registers）。因此，在恢复一个进程的执行时，内核必须将所有被这个进程用到的寄存器都恢复成这进程之前被挂起前的状态，这个过程称为硬件上下文（hardware context）。
硬件上下文是进程上下文（Process context）的子集。在Linux中，一部分硬件上下文被存储在进程描述符（process descriptor）中，而另一部分被保存在内核态栈中（Kernel Mode stack）。
从一个进程的运行转到另一个进程上运行，这个过程中经过下面这些变化：
- 保存当前进程状态至一个进程控制块（PCB, process control blocks），包括程序计数器（program counter）和其他被操作系统用于当前进程以保存数据的寄存器（registers），程序计数器也是一种寄存器。
- 把进程的PCB移入相应的队列，如就绪队列、阻塞队列中。
- 选择另一个进程执行，获取其PCB并恢复到内存和CPU缓存中。
- 执行该新进程。
线程调度（Thread scheduling）
Reference
- 《Modern Operating System 4th》
- 《UnderStanding The Linux Kernel 3rd Edition》
- 【原理】进程调度算法 - https://blog.csdn.net/m0_37925202/article/details/79471445
- 进程调度的算法及思想 - https://www.jianshu.com/p/f7a1caa481ed
- Wikipedia Scheduling (computing) - https://en.wikipedia.org/wiki/Scheduling_(computing)