50-CPU调度

单处理器调度

处理器调度类型

长程调度

决定哪个程序可以进入系统中处理，因此控制了系统的并发度。一旦进入，作业或程序就成为进程，并添加到供短程调度程序使用的队列中，等待调度。

中程调度

与系统交换功能有关，参看 20、40 两章。

换入取决于管理系统并发度的需求，换出考虑进程的存储需求。

短程调度

短程调度程序（dispatcher），执行最为频繁，精确地决定下一次执行哪个进程。

导致当前进程阻塞或抢占当前运行进程的事件发生时，如时钟中断、IO 中断、Syscall、信号等，短程调度程序启动。

调度算法

短程调度规则

1. 以用户为本，注重绩效
   1. 周转时间 这是一个进程从提交到完成的时间间隔。包括实际执行时间和等待资源（包括处理器）的时间。这是批处理作业的适当衡量标准。
   2. 响应时间 对于交互式进程，这是从提交请求到开始收到响应的时间。通常情况下，进程可以在继续处理请求的同时开始向用户提供一些输出。因此，从用户的角度来看，这是一个比周转时间更好的衡量标准。调度规则应努力实现较低的响应时间，并使获得可接受响应时间的交互式用户数量最大化。
   3. 最后期限 当可以指定流程完成的最后期限时，调度纪律应将其他目标置于最大限度地提高最后期限满足率的目标之下。
2. 以用户为导向，其他
   1. 可预测性 无论系统负载如何，给定任务都应在大致相同的时间内以大致相同的成本运行。响应时间或周转时间的巨大差异会分散用户的注意力。它可能预示着系统工作量的大幅波动，或需要对系统进行调整以消除不稳定性。
3. 面向系统，与性能有关
   1. 吞吐量 调度策略应尽量增加单位时间内完成的进程数量。这是对正在执行的工作数量的衡量。这显然取决于进程的平均长度，但也受调度策略的影响，后者可能会影响利用率。
   2. 处理器利用率 这是处理器忙碌时间的百分比。对于昂贵的共享系统来说，这是一个重要的标准。在单用户系统和其他一些系统（如实时系统）中，这一标准不如其他一些标准重要。
4. 面向系统、其他
   1. 公平性 在没有用户指导或其他系统提供指导的情况下，进程应受到同等对待，任何进程都不应处于饥饿状态。
   2. 执行优先级 当进程被指定优先级时，调度策略应有利于优先级较高的进程。
   3. 平衡资源 调度策略应使系统资源保持繁忙。应优先考虑那些未充分利用紧张资源的进程。这一标准还涉及中期和长期调度。

优先级的使用

优先级相关的调度有可能会有饥饿现象，解决办法是动态调整优先级。

调度策略

评价参数与决策模式

参数：

• $w$：目前为止在系统中停留时间；
• $e$：目前为止执行时间；
• $s$：进程需要的总服务时间。

决策模式：

1. 非抢占：只要开始执行，就不会被其他进程打断，只能自己申请资源或服务而主动放弃；
2. 抢占：正在运行的进程被 OS 中断，转换为就绪态，在新进程到达、中断发生后将阻塞态进程置为就绪态、周期性时间中断时需要抢占决策； 抢占虽然有较大开销，但避免了进程长期占用 CPU 的情形，有效提高系统响应率。

实例运行：

• 周转时间（turnaround time）= 驻留时间 $T_r$ = 等待时间+服务时间
• ==归一化周转时间 = 周转时间/服务时间==，
  • 表示进程的相对延迟情况，
  • 比值越大，服务级别越低；比值最低为 1.0，表示服务级别最高，一创建就调度
  • 通常进程执行时间越长，可容忍的延迟时间越长。

First Come, First Serve

特点：

• 更适用于长进程。短进程紧跟在长进程之后，会使归一化周转时间很不协调。
• 更适用于 CPU 密集型进程，而不是 IO 密集型。例如，
  • 若 CPU 密集型进程在运行，则所有 IO 密集型进程等待，而 IO 队列中的阻塞态进程在等待中可能恢复就绪，但此时不仅无法获得 CPU，IO 设备也变为空闲；
  • 若 IO 密集型进程运行，快速完成处理后， CPU 后等待 IO 返回，此时 CPU 空闲；
  • 因此综合来看，CPU 和 IO 设备的利用率都不高。

Round Robin

基于时钟的抢占策略。

周期性地产生时钟中断，出现中断时当前进程放置到就绪队列，然后基于 FCFS 策略选择下一个就绪作业。

时间片划分建议略大于一次典型交互时间。当时间片比时间最长的进程还要长时，就退化成 FCFS。

适用于分时系统或事务处理系统。另外对于 IO 密集型进程性能不好，使用 IO 设备效率低，响应时间变化大。因为 CPU 密集型进程不公平地使用了大部分处理器时间，而 IO 密集进程短时间占用 CPU 后又被 IO 申请阻塞，多余的时间都供给 CPU 密集进程占用。

Virtual Round Robin

优化了 RR 策略中对 IO 密集和 CPU 密集进程的不公平性。

1. 新进程经 FCFS 调度进入就绪队列；
2. 进程用完时间片会返回就绪队列；
3. 因 IO 阻塞则会加入 IO 队列，解除阻塞后移至辅助队列，辅助队列的优先级高于就绪队列；

调度辅助队列中的进程时，该进程的运行时间不会长于基本时间-上次运行的时间。

Shortest Process Next

解决 FCFS 不利于短作业的策略，非抢占，下次调度预计处理时间最短的进程。

• 响应时间显著改善，但响应时间的波动加剧，长进程尤其如此，可预测性不高。
• 困难之处在于，难以准确估计进程需要的处理时间：可行办法是收集频繁运行的进程，计算统计值 $S_{n+1}=\frac{1}{n}{\Sigma }_{i=1}^n{T}_i$ ，T 指处理器执行时间，S 指预测值。
• 风险在于，只要一直提供更短的进程，长进程就会饥饿，并且由于缺少抢占机制，在处理长进程时对分时系统的响应性能不好。

Shortest Remaining Time

SPN 添加抢占策略的优化版，总是选择预期剩余时间最短的进程。只要进程就绪，并且剩余时间更短，调度就可以抢占当前运行的进程。

• 不像 FCFS 偏向于长进程，不像 RR 产生额外中断，降低了部分开销；
• 但是必须记录过去服务的时间，此处增加了开销；
• 总体分析：周转时间的性能强于 SPN，但同样可能饥饿。

Highest Response Ratio Next

$$响应比=\frac{等待时间+服务时间}{服务时间}=\frac{w+s}{s}=R$$

• R 最小值为 1.0，即进程刚被创建就立即被调度。
• 兼顾长进程和短进程，短进程优先级天然较高，且长进程会因为等待时间增加而提高响应比，也可以被调度。因此没有饥饿现象。
• 类似与 SPN、SRT，HRRN 也需要预估服务时间

Feedback

无法获取进程运行时间信息时，SPN、SRT、HRRN 都无法使用，则必须结合已知信息——已获得的服务时间——进行调度，为了使短进程保持优先，应当惩罚运行时间较长的作业。

具体方法：基于抢占原则并使用动态优先级机制：

1. 进程首次进入会放置于 RQ 0；
2. 首次被抢占并返回就绪态时，放入 RQ 1，之后每次被抢占都下调一个队列；
3. 新的进程和短进程的动态优先级，都会优于老的、长的进程。
4. 除优先级最低队列，都使用 FCFS 策略，最低优先级队列中进程不会再降低，但会持续返回该队列，因此用 RR 策略。

• 缺点：长进程可能被一直频繁进入的短进程打断，从而饥饿。
• 解决办法：给不同队列以不同的执行时间，一般 RQi 中的进程给予 $q=2^i$ 的时间单位，虽然仍可能饥饿；还可以限定在低优先级队列中等待一定时间后就上调优先级。

Fair Share Scheduler

之前算法都是单一进程池，若进程池有多个且也有优先级，构成进程集合结构，这在多用户系统很常见。用户不关心特定进程的执行，而是构成应用的进程组如何执行。基于进程组的调度策略称为公平共享调度 (fair-share scheduling)。

• 基本原则：每个用户被指定了某种类型的权值，该权值定义了用户对系统资源的共享程度，而且作为在所有使用资源中所占的比例。
• 实现方案之一就是 FSS，在进行调度决策时，考虑相关进程组的执行历史，以及每个进程的执行历史。

调度是根据优先级进行的，综合考虑了进程的基本优先级、近期使用 CPU 的情况、进程组近期使用 CPU 的情况。适用于组 k 中进程 j 的公式：

$$\begin{array}{rl}CP{U}_j(i)& =\frac{CP{U}_j(i-1)}{2}\\ GCP{U}_k(i)& =\frac{GCP{U}_k(i-1)}{2}\\ P_j(i)& =Bas{e}_j+\frac{CP{U}_j(i)}{2}+\frac{GCP{U}_k(i)}{4W_k}\end{array}$$

$CP{U}_j(i)=$ 进程 j 在时间区间 i 中时使用处理器情况的测度, $GCP{U}_j(i)=$ 进程组 k 在时间区间 i 中时使用处理器情况的测度, $P_j(i)=$ 进程 j 在时间区间 i 开始处的优先级, 数值越小优先级越高 $Bas{e}_i=$ 进程 j 的基本优先级， $W_k=$ 分配给进程组 k 的权重，满足条件： $0<W_k\le 1$ and $\sum _k{W}_k=1$.

• 每个进程分配一个基本优先级，进程的优先级会随进程使用处理器及进程所在组使用处理器而降低（数值上提高）。
• 对于进程组使用 CPU 的情况，用平均值除以该组的权值归一化平均值。
• 分配给某个组的权值越大，则使用处理器对权值的影响越小。

多处理器调度

多处理器系统分类

1. 松耦合、分布式多处理器、集群；
2. 专用处理器：IO
3. 紧耦合多处理器：⭐

粒度

无约束并行性

进程间独立进行，每个进程都好像独占整个系统。

粗粒度、极粗粒度并行性

可以简单地处理为一组运行在多道程序单处理器上的并发进程。

使用多处理器结构，对所有需要通信或同步的并发进程集都有好处。进程间交互不频繁时，分布式系统可以提供较好的支持；但交互频繁时，分布式系统中的网络通信开销会抵消潜在的加速比，此时多处理器组织结构能提供最有效的支持。

中粒度并行性

处理线程调度时，系统对频繁交互的线程的调度决策可能会影响整个应用的性能。

细粒度并行性

设计问题

进程分配到处理器

若多处理器结构统一、均匀，最简单的调度方法是将处理器视为资源池，并按照需求将进程分配到相应的处理器。

分配应该是静态的还是动态的？

1. 静态分配：进程从激活到完成，都分配给同一处理器
   • 实现：需要为每个处理器维护专门的短程队列
   • 优点：开销小，任何进程都只需分配一次，专用处理器还允许组调度策略；
   • 缺点：处理器利用不均匀。
2. 动态分配: 进程能在不同处理器间转移
   • 实现：一是构造全局公共队列，所有进程都基于此进行调度，这样在进程不同生命周期可以处于不同的处理器上；二是使用动态负载平衡策略，线程能在不同处理器对应的队列之间转移；
   • 底层原理支持：紧密耦合的共享存储器结构中，所有处理器都能得到所有进程的上下文信息（通过PCB），因此调度进程的开销与调度到哪个处理器无关。

分配进程到处理器的方法

1. 主从式：OS 核心功能在特定处理器上执行，其他处理器仅用于用户程序，主处理器负责调度作业；
   • 优点：实现简单，且主处理器拥有对所有存储器和 IO 资源的控制，因此冲突解决方案也比较简单；
   • 缺点：主处理器的失败会造成整个系统失败；主处理器的性能成为系统瓶颈；
2. 对等式：OS 能在任一处理器上执行，每个处理器从可用进程池中调度
   • OS 必须确保两个处理器不会运行同一进程，进程也不能在队列中丢失，
   • 还需要对资源竞争和同步的特殊处理；
3. 专为内核处理提供一个处理器子集，而非只用一个处理器；
4. 基于优先级和执行历史，简单地管理内核进程和其他进程之间的需求差异；

多处理器系统追求的目标

多处理器系统中，

• 单个处理器上是否严格使用多道程序设计以提高利用率已不再重要，
• 更加关心如何为应用提供最好的平均性能。

多线程程序性能可能很差，除非所有线程都协调运行。

进程的实际分派

相对于单处理器系统上必要的 FCFS、RR、HRRN 等调度策略，

• 多处理器系统不必如此复杂的进程调度策略，FCFS 已经足够有效，但线程并非如此。

进程调度

$C_s=\frac{{\sigma }_s}{T_s}$ ，表示服务时间的变化程度，$T_s$ 一定时，$C_s$ 越大，代表进程服务时间的差异越大。

• 将多处理器系统视为多服务器排队结构，使用多个基于优先级的队列，送入相同的处理器池中。
• 上图说明，双处理器显著降低了 RR、SRT 相对于 FCFS 的吞吐量优势，因此对进程而言调度策略不重要，FCFS 足够简单、有效。

线程调度

多处理器系统中，线程可开发应用程序中真正的并行性，对于线程间需要交互的应用程序（中粒度并行性），线程管理和调度对性能的影响十分显著。

4 种方案：

负载分配 load sharing

进程不分配到特定处理器，系统维护一个就绪线程的全局队列，每个处理器只要空闲就从队列中选择一个线程。

优点

1. 负载均匀地分配给各个处理器，只要有工作，处理器就不会空闲
2. 不需要集中调度程序，空闲处理器直接调用线程调度例程，以获得下一个线程；
3. 可以使用多种策略组织全局队列，如 FCFS、基于优先级等；

三种负载分配方案

1. FCFS：相对于其它两种策略，在多作业情形更有优势。
2. 最少线程优先（最小作业量优先）：共享就绪队列以基于优先级的策略组织，一个作业包含的未调度线程数量最少时，得以指定最高优先级；
3. 可抢占的最少线程优先；

缺点

1. 中心队列占据了必须互斥访问的存储器区域。对于大量处理器的系统，这将成为性能瓶颈；
2. 被抢占的线程不一定在同一处理器上恢复运行。这不利于处理器缓存的效率，不能很好地利用局部性原理；
3. 所有线程都放在一个公共线程池，若属于同一进程的多个线程需要协同工作，进程的切换、执行严重影响性能，强行分裂了线程间的关联。

改善

为每个处理器维护一个本地运行队列和一个共享全局运行队列

• 处理器的本地运行队列供临时绑定在某个特定处理器上的进程使用；
• 处理器首先检查本地运行队列，使绑定的线程绝对优先于未绑定线程；
• 应用例子是，
  • 1️⃣用一个或多个处理器专门运行 OS 的进程，
  • 2️⃣特定应用程序的线程分布在许多处理器上，通过适当软件可以实现为组调度；

组调度 gang scheduling

• 一组相关的线程基于一对一的原则，同时调度到一组处理器上运行。
• 对于中粒度到细粒度的并行应用程序，组调度非常必要，因为这种应用程序的一部分准备运行，另一部分还未运行时，性能会严重下降。
• 组调度显著提高程序性能的方式——使进程切换开销最小：线程天然有切换开销小的优点；合作线程同时调度，避免了同步时的不必要等待，节省了资源分配的时间；

对处理器分配的要求

1. 均匀分配时间的效率很低，尤其在多个进程的线程数严重不匹配时，大量的空闲气泡🫧浪费了处理器资源；
2. 应该根据线程数加权调度：

专用处理器调度 dedicated processor assignment

• 将线程指定到处理器，每个程序在执行过程中，都分配给一组处理器，处理器的数量与程序中线程数量相等，程序终止时返回处理器到总处理器池，以便分配给下一个程序。

支持策略的考量

看起来效率不高，因为总有阻塞的进程空占处理器，但也可以解释：

1. 高度并行的多处理器系统中，少量处理器空闲的代价并不高，处理器利用率不是衡量有效性关键因素；
2. 在程序的生命周期中，避免进程切换能够确保程序尽快完成。

应用加速比与线程数量关系

• 随着每个应用程序的线程数量增加，两种运算的加速比先增后减。
• 主要原因是线程数量过多时，处理抢占和调度的开销过大，降低了资源的使用效率。
• 比较有效的策略是限制活跃线程的数量，使其不超过系统中处理器的数量。

处理器分配问题

多处理器系统中的处理器分配问题，类似于单处理器中的存储器分配问题，即某一给定时刻给一个程序分配多少个处理器，类似于给定时刻给进程分配多少页框。 因此，提出

• 活动工作集——为了保证应用程序以可以接受的速度继续执行，在处理器上必须同时调度的最少数量的活动线程。
• 调度活动工作集中所有元素失败时，可能导致 处理器抖动 ，尤其发生于调度需要服务的线程进而导致那些服务将被用到的线程取消调度；
• 处理器碎片 指当一些处理器剩余而其他处理器已被分配，剩余处理器无论从数量上还是从适合程度上，都难以支持正在等待的应用程序的需要。

动态调度 dynamic scheduling

• 执行期间，进程中线程的数量可以改变。通常由 OS 和应用程序共同进行调度决策，
  • OS 负责把处理器分配给作业，每个作业通过把它的一部分可运行任务映射到线程，使用当前划分给它的处理器执行这些任务；
  • 运行哪个子集、进程被抢占时哪个线程被挂起的决策由应用程序解决。

处理器分配策略

动态调度局限于处理器分配，而处理器分配策略是：

1. 对于作业请求一个或多个处理器（或作业第一次到达，或请求发生变化）：
   • 若有空闲处理器，则满足其请求；
   • 若作业新到达，则从当前已分配了多个处理器的作业中分出一个处理器给新作业；
   • 若该请求的任何分配都无法满足，则保持未完成状态，直到处理器可用或作业取消请求；
2. 释放若干处理器时：
   • 为这些处理器扫描未得到满足的请求队列，
   • 给表中每个当前还没有处理器的作业分配一个处理器，
   • 然后再次扫描这个表，按 FCFS 原则分配剩余处理器。

优点：性能优于组调度和专用处理器分配

多核线程调度

• 多处理器的策略并不适合于多核系统。
• 随着芯片上内核数量增加，最小化访问片外存储器比最大化处理器利用率更优先。
• 最小化访问片外存储器的主流方法仍然是利用 cache ——局部性原理：

内核并非共享全部缓存时，调度期间线程分配给内核的方式对性能有明显影响。

• 最好的分配：若两个线程需要共享内存资源，则应将它们分配给相邻的内核以提高性能，若不共享内存资源，则分配到不相邻的资源使得负载均衡；
• 实际上缓存共享需要考虑合作资源共享和资源抢占：合作资源共享使多个线程可以访问相同的资源区域，线程在相邻内核竞争缓存内存地址；

实时调度

• 实时计算：系统的正确性不仅取决于计算的逻辑结果，而且取决于产生结果的时间；

实时任务：对于试图控制外部世界发生的事件、或对这些事件做出反应，需要在最后期限前实现响应，有一定紧急度要求：

• 硬实时任务：必须满足最后期限的任务，否则会给系统带来致命错误；
• 软实时任务：对于最后期限，是尽可能满足，但并不强制，即使超过了最后期限，调度与完成这个任务仍有意义；

实时任务的周期性：

• 非周期任务：有一个必须开始或结束的最后期限，或有一个关于开始时间和结束时间的约束条件；
• 周期任务：每个周期 T 完成一次的约束条件；

实时 OS 需求

五个需求：

可确定性 deterministic

指能按照固定的、预先确定的时间或时间间隔执行操作。

graph LR

A[实时系统可确定性满足请求的能力]
B[响应中断的速度]
C[要求时间内处理请求的能力]

A-->|determined by| B
A-->|determined by| C 

• 度量：高优先级设备中断发生、至系统获知中断之间的延迟。

可响应性 responsiveness

• 度量：系统在知道中断发生后、为中断提供服务的时间。

主要包括：

1. 最初处理中断并开始执行中断服务例程 ISR 所需的时间总量。（ISR 进程切换的开销）
2. 执行 ISR 所需的时间总量。（与硬件平台相关）
3. 中断嵌套的影响。

$$响应时间=可确定性+可响应性$$

用户控制 user control

• 允许用户细粒度地控制任务优先级。

用户的控制权限

1. 硬实时和软实时；
2. 每类中的相对优先级；
3. 使用页面调度还是进程交换；
4. 哪个进程常驻内存
5. 使用何种磁盘扫描算法
6. 不同优先级进程各有什么权限

可靠性 reliability

要求严格，必须可靠

故障弱化操作 fail-soft operation

• 指系统在发生故障时，尽可能多地保存性能和数据，
• 并尝试改正问题或最小化其影响，使系统能够继续运行。
• 一个重要特征是稳定性 stability：指当实时系统不能满足所有任务的最后期限时，即使总是不能满足一些不太重要任务的最后期限，也应优先满足最重要的、优先级最高的任务的最后期限。

实时 OS 功能

1. 使用更严格的使用优先级，以抢占式调度来满足实时性要求；
2. 中断延迟（设备从运行到中断的时间）有界且较短；
3. 更精确、更可预测的时序特征。

RTOS 的目标

• RTOS 的核心是短程任务调度程序，
• 公平性、最小平均响应时间、利用率都不重要，
• 所有硬实时任务在最后期限内完成或开始，尽可能多的软实时任务能够在最后期限内完成或开始才重要。

常规调度方法分析

调度时间过长；

非抢占式执行，延迟不可控；

时间中断点作为抢占点，进行抢占判断，对于大部分实时应用已经足够；

除非系统处于临界区中，否则系统立即响应中断。

实时调度

考察实时调度算法的方面

1. 系统是否执行可调度性分析；
2. 执行可调度性分析是动态还是静态的；
3. 分析结果自身是否根据在运行时分派的任务产生一个调度或计划；

静态表调度法

• static table-driven scheduling：执行关于可行调度的静态分析，分析结果是一个调度，确定在运行时任务何时需要开始执行。

特点

1. 适用于周期性任务。分析的输入为周期性的到达时间、执行时间、周期性的结束 deadline 和每个任务的相对优先级；
2. 可预测的方法，但不够灵活，任何任务要求的变化都要重做调度；

应用算法举例

• 最早 deadline 优先
• 周期性 deadline 技术

静态优先级抢占调度法

• static priority-driven preemptive scheduling：执行一个静态分析，但未指定调度，而是通过给任务指定优先级，使得可以使用传统的基于优先级的抢占式调度程序。
• 抢占机制与优先级相关，优先级的分配与每个任务的时间约束相关。
• 算法举例：速率单调算法——根据周期的长度来给任务指定静态优先级；

基于动态规划的调度法

• dynamic planning-based scheduling：在运行时动态地确定可行性，到达的任务仅能在满足其他时间约束时，才可被接受并执行。可行性分析的结果是一个调度或规划，可用于确定何时分派这个任务。
• 在一个任务已到达但未执行时，试图创建一个包含前面被调度任务和新到达任务的调度，若新到达的任务能够满足它的最后期限、且之前被调度的任务不会错过最后期限，则修改这个调度以适应新任务。

动态尽力调度法

• dynamic best effort scheduling：不执行可行性分析，系统总是试图满足所有的 deadline，并终止任何已经开始运行但错过最后期限的进程。
• 一个任务到达时，系统根据任务的特性给它指定一个优先级，并使用时限调度 deadline scheduling，如最早 ddl 调度。
• 适用于非周期性任务，这类任务不能用静态调度分析。
• 缺点：这类调度直到到达 deadline 或完成之前，都不知道是否满足时间约束。
• 优点：易于实现

限期调度(deadline scheduling)

实时应用程序通常并不关心纯粹的速度，而关注在最有价值的时间完成（或启动）任务，既不能太早也不能太晚。尽管存在动态资源需求和冲突、处理超载以及硬件或软件故障。因此，优先级只是一种粗略的工具，并不能满足在最有价值的时间完成（或启动）任务的要求。

需要关注的任务的额外信息

• 就绪时间：任务开始准备执行的时间。
  • 对周期性任务这是事先预知的时间序列，
  • 对非周期任务除非任务明确表示，否则 OS 仅知道什么时候任务真正就绪。
• 启动 deadline；
• 完成 deadline：（二者取一）
• 处理时间：从执行到完成任务
• 资源需求；
• 优先级：度量任务的相对重要性。
• 子任务结构：一个任务可以分解为必须执行的子任务和可选执行的子任务，只有必须执行的子任务拥有硬 deadline。

实时调度功能可分为两个维度——下次调度哪个任务、允许哪种类型抢占。

最早 deadline 优先策略

最早最后期限优先 (earliest deadline first)：

• 对给定抢占策略，无论是启动 deadline 还是完成 deadline，这种策略都可以使超过ddl的任务数最少。
• 对于启动 deadline 已经确定的任务，可以使用非抢占策略，在任务完成必须执行的部分或关键部分后，阻塞自身以允许其它实时启动 deadline 的程序或要求满足；
• 对于完成 deadline 的系统，最适合使用抢占策略。

应用 1: 完成 deadline 的周期性实时任务

（计算机每隔 10ms 进行一次调度决策）

最后一行表明，通过在每个可抢占点上优先调度与最后期限最临近的进程，可以满足系统的所有要求。由于任务是周期性和可预测的，因此可以使用静态表调度法。

应用 2: 启动 deadline 的非周期实时任务

解读：

1. 永远调度具有最早 deadline 的任务，并让直一致运行到完成。但是 B 虽然请求，但未获得服务，这表明在处理非周期任务时非常危险；
2. 若事先知道启动 deadline，则使用 自愿空闲时间的最早deadline策略 ：总是调度最后期限最早的合格任务，并让该任务运行直到完成。

速率单调调度

速率单调调度 (rate monotonic scheduling)：

• 解决周期性多任务调度冲突。
• RMS 基于任务的周期指定优先级，周期越短优先级越高。

判断 RMS 是否有效

• 任务周期 T：任务的一个实例到达至下一个实例到达的时间间隔
• 任务速率 C：周期的倒数，单位 Hz
• 执行时间：执行时间不大于周期 $C\le T$；
• 处理器利用率 U：$U=\frac{C}{T}$

• 衡量周期调度算法的有效性——是否能够满足所有硬 deadline：

$$\frac{C_1}{T_1}+\frac{C_2}{T_2}+\cdots +\frac{C_n}{T_n}\le 1$$

上式是理想状态，对于不同的周期调度算法，任务数量具有不同的界限。对于 RMS，则变为：

$$\frac{C_1}{T_1}+\frac{C_2}{T_2}+\cdots +\frac{C_n}{T_n}\le n(2^{\frac{1}{n}}-1)$$

考虑极限，$n\to \infty$ 时，上式上界为 $\ln 2\approx 0.693$ 。

则返回思考之前失败的三个进程：

$$U_1+U_2+U_3=\frac{1}{4}+\frac{2}{5}+\frac{2}{7}=\frac{131}{140}\approx 0.936>0.779$$

因此 RMS 调度一定无法实现三者不冲突。

RMS 的优势

RMS 广泛应用与工业应用，其优势有：

1. 实践中性能差别很小，公式中对上界的估计非常保守，实际任务不会非常多，利用率通常高于 0.9；
2. 硬实时任务的 RMS 调度中空闲时间，可以给软实时任务使用；
3. RMS 易于保障稳定性。当系统由于过载或瞬时错误而无法满足所有截止时间要求时，需要保证基本任务的截止时间，前提是这部分任务是可调度的。
   • 在静态优先级分配方法中，只需确保基本任务具有相对较高的优先级。
   • 在 RMS 中，这可以通过将基本任务结构化为短周期或修改 RMS 优先级来实现。或通过修改 RMS 优先级来实现。基本任务。在最早 deadline 调度中，周期性任务的优先级会从一个周期变为另一个周期。周期任务的优先级会在周期变化时随之改变。这样就更难确保重要任务在截止日期前完成。其最后期限。

优先级反转

• 任何基于优先级的可抢占调度方案都会出现的现象。
• 当低优先级任务占据了共享资源，而高优先级任务抢占后却被迫等待低优先级任务释放共享资源。

无界限优先级反转 (unbounded priority inversion)：优先级反转的持续时间不仅取决于处理共享资源的时间，还取决于其它不相关任务的不可预测行为。以探路者优先级反转为例，优先级递减的三个任务为： $T_3$：周期性检查太空船和软件状况； $T_2$：处理图片数据 $T_1$：随机检测设备的状态

造成优先级反转的几个条件

1. 固定的优先级；
2. 可抢占的调度策略；
3. 至少三个优先级不同的任务，且最低和最高优先级任务共享资源

解决办法

优先级继承

• 思路：优先级较低的任务继承任何与其共享同一资源的较高优先级任务的优先级。
• 操作：当高优先级任务在共享资源上阻塞时，立即更改优先级使得低优先级任务开始执行，当资源被低优先级任务释放时，高优先级任务的优先级改变结束。

优先级置顶

• 思路：优先级与每个资源相关联，资源的优先级被设定为比使用该资源的最高优先级的任务的优先级高一级，调度程序动态地将这个优先级分配给任何访问该资源的任务，一旦使用完资源，就返回到以前的值。

Linux 调度

实时调度

负责 linux 调度的三个类是：

• SCHED_FIFO：先进先出实时线程；
• SCHED_RR
• SCHED_NORMAL：其它非实时线程，仅当无实时类线程运行时，才可以运行该非实时类线程。

每个类使用多个优先级，实时类的优先级高于非实时类。默认实时类优先级范围为 099，非实时类为 100139。数字越小优先级越高。

SCHED_FIFO

运行规则：

1. 系统不会中断正在执行的 FIFO 线程，除非出现以下情况：
   • 另一个优先级更高的 FIFO 线程准备就绪。
   • 执行中的 FIFO 线程被阻塞，如等待 I/O 等事件。
   • 执行中的 FIFO 线程在调用 sched_yield 原语后主动放弃了处理器。
2. 当正在执行的 FIFO 线程被中断时，它会被放入与其优先级相关联的队列中。
3. 当 FIFO 线程就绪时，如果该线程的优先级高于当前执行的线程，那么当前执行的线程将被抢占，执行优先级最高的就绪 FIFO 线程。如果有多个线程具有最高优先级，则选择等待时间最长的线程。

SCHED_RR

类似于 SCHED_FIFO，只是每个线程都有一个与之关联的时间片，一个 SCHED_RR 线程在时间片内执行结束后，将被挂起，由调度程序选择一个具有相同或更高优先级的实时线程。

非实时调度

O (1) 调度

• 不论系统的负载或处理器的数量如何变化，选择合适的任务并执行的时刻都是恒定的。

代码量大，实现复杂。

CFS 调度

completely fair scheduler:

• 在真实硬件上建模一个理想的多任务 CPU，能够为所有任务提供公平的 CPU 访问。
• CFS 为每个任务维护一个虚拟运行时间——指被当前可运行进程数量归一化的已运行时间。虚拟运行时间越短（即任务被允许访问处理器的时间越短，代表对处理器的需求越强。）
• 引入睡眠公平，用于保证当前不可运行的任务能够在它们最终需要处理器时获得一个公平的比例。

CFS 调度器

• 实现在 fair_sched_class 调度类中，基于红黑树实现：
• 最左边节点表示对 CPU 需求最高，因此首先被选用；
• 运行部分后再插回红黑树，自平衡找到应当存放的位置；
• 红黑树插入操作时，最左边节点总是缓存在 sched_entity 中供快速查找。