2.5 操作系统进程调度

一、进程调度算法

先来先服务——短作业优先——最短剩余时间优先——优先级调度——时间片轮转——多级反馈队列调度（每个队列的时间片长度不一样）

二、进程调度器

确保CPU时间片能在各个进程间合理分配，最大化系统资源利用率，同时考虑进程的响应时间。一个进程只属于一个调度器。

调度器是 CPU 中央处理器的管理员，主要负责做两件事情：

一、选择某些就绪进程执行。

二、是打断某些执行的进程让它们变为就绪状态。

调度器分配CPU时间的基本依据：进程的优先级。

上下文切换（context switch ）：负责存储和切换被切换掉之前的CPU 状态。

三、调度策略

#define SCHED_NORMAL        0
#define SCHED_FIFO        1
#define SCHED_RR        2
#define SCHED_BATCH        3
#define SCHED_IDLE        5
#define SCHED_DEADLINE        6

CHED_NORMAL：定义了普通进程调度策略，即非实时调度策略。在Linux内核中，使用完全公平调度器来实现，它旨在为所有进程提供公平的CPU时间分配，依据进程的nice值（优先级）和虚拟运行时间来平衡各进程的执行机会。

SCHED_FIFO：代表先进先出（First In, First Out）的实时调度策略。在该策略下，实时进程按到达就绪队列的顺序执行，具有该调度策略的进程一旦获得CPU就不会被更低优先级的进程抢占，除非自身主动释放CPU，或者有更高优先级的SCHED_FIFO或SCHED_RR实时进程变得可运行。

SCHED_RR：轮转（Round Robin）实时调度策略，类似于SCHED_FIFO，但是实时进程在一个时间片（quantum）结束之后会被放置到同优先级实时进程队列的末尾，等待再次轮到自己执行，这样保证同一优先级的实时进程可以轮流获得执行机会。

SCHED_BATCH：批处理调度策略，适用于CPU密集型且对响应时间要求不高的批处理作业。使用此策略的进程会尽量减少上下文切换，从而提高CPU缓存的局部性并减少开销，有利于提高整体系统吞吐量。 SCHED_IDLE：空闲调度策略，应用于低优先级后台任务。这类任务只有在系统完全空闲时才会得到执行，不会影响其他任何进程的调度。

SCHED_DEADLINE：截止期限（Deadline）调度策略，专为那些有严格截止时间约束的进程设计。此类进程需要在预设的截止时间内完成计算任务，调度器会确保进程在规定时间内获得足够的CPU资源来满足其执行需求。

四、任务优先级

task_struct结构体中采用三个成员表示进程的优先级： prio 和 normal_prio 表示动态优先级，static_prio 表示进程的静态优先级。权重越大的进程获得的虚拟运行时间越小，那么它将被调度器所调度的机会就越大。

内核将任务优先级划分，实时进程的优先级范围是0 到 MAX_RT_PRIO-1 （即 99 ），而普通进程的静态优先级范围是从 MAX_RT_PRIO 到 MAX_PRIO-1 （即 100到139）。数字越小优先级越高。

DL：0； RT：1-99；CFS：100-139（nice：-20-19）

五、CFS

CFS 给 cfs_rq (cfs的run queue) 中的每一个进程都设置一个虚拟时钟 virtual runtime(vruntime)。如果一个进程得以执行，随着执行时间的不断增长，vruntime 也将不断增大，没有得到执行的进程 vruntime 将保持不变。根据这种“不公平时间”也就是就绪队列中进程的等待时间分配CPU资源。

（1）CFS主要引入了下面几个特性：

虚拟运行时间（vruntime）：CFS摒弃了传统固定时间片的轮转调度方式，转而使用虚拟运行时间来衡量进程的执行时间。每个进程在运行时，其虚拟运行时间会逐渐增加，未运行的进程则保持不变。调度器会比较所有进程的虚拟运行时间来决定下一个应该运行的进程，确保所有进程在虚拟运行时间上的相对差距反映其应该得到的CPU时间比例。

权重计算：CFS根据进程的nice值（优先级）来调整其权重。nice值范围通常是从-20（最高优先级）到19（最低优先级，默认值为0）。nice值越高，进程的权重越小，意味着它在同等时间内获得的CPU份额越少，反之亦然。

红黑树排序：CFS使用红黑树来组织就绪队列，进程节点按照其虚拟运行时间排序。每次调度时，会选择vruntime最小的进程执行，这样可以保证所有进程在长时间运行后达到近似的执行时间比例。

动态优先级调整（vruntime）： 随着进程的执行，CFS会动态调整进程的优先级，确保即使在短时间段内也能表现得相对公平。当一个进程使用完其相对应的CPU时间后，其虚拟运行时间将会增加，从而降低其在红黑树中的优先级。

其他特性：CFS支持多核环境下的负载均衡，即在不同CPU间迁移进程以达到总体负载的均衡分布。此外，CFS设计时考虑了系统性能和电源管理，确保在兼顾公平性的同时，还能在适当时候将CPU资源交给idle进程，进而触发节能措施。

（2）CFS 如何实现完全公平

真实运行时间（Real Runtime）： 真实运行时间是指进程在物理CPU上实际消耗的时间，即从进程开始执行到目前为止，所经历的 wall clock 时间。这个时间包括进程在用户空间执行的时间（即进程执行指令的时间）以及在内核空间执行系统调用和服务的时间。真实运行时间是由系统时钟精确测量的，反映了进程实际占用CPU资源的情况。

虚拟运行时间（Virtual Runtime, vruntime）： 虚拟运行时间在CFS调度器中是决定进程调度顺序的关键因素。它并不是指进程实际占用CPU的时间，而是经过权重调整后用来衡量进程“应当”消耗的CPU时间。CFS调度器根据每个进程的nice值、进程优先级和其他相关因素计算得出每个进程的虚拟运行时间，并用它来决定下一个将被执行的进程。在CFS调度器的红黑树结构中，虚拟运行时间最短的进程将被优先调度。内核可以确保在长时间段内，所有进程都能得到与其优先级和系统负载相对应的CPU时间分配，从而实现“完全公平”的调度效果。

（3）虚拟运行时间和真实时间的计算

六、实时调度器类

SCHED_FIFO（先进先出实时调度策略）： 使用SCHED_FIFO策略的实时进程一旦获得CPU执行权，就会一直运行下去，直到该进程自愿放弃CPU（如调用了阻塞系统调用或显式释放CPU），或者有更高优先级的实时进程变得可运行。实时进程按照优先级排队，优先级高的进程始终排在优先级低的进程之前。

SCHED_RR（轮转实时调度策略）： 类似于SCHED_FIFO，但每个SCHED_RR实时进程在执行完一个时间片（quantum）后，即使没有完成任务，也会被迫让出CPU给同一优先级的其他SCHED_RR进程。这样一来，同一优先级的实时进程能够实现时间片轮转，确保在紧迫性相同的情况下公平分配CPU时间。