【5 操作系统调度】

---

1. 调度机制

1.1 长期、中期、短期调度

进程调度机制负责进程在这些状态间的转换。进程调度根据职责的不同，具体分为长期、中期、短期调度。

• 长期调度的触发间隔较长，它粗粒度地决定是否应该将一个新的进程纳人调度管理，负责增加系统中可被调度的进程的数量。
• 中期调度的触发相对频繁，它辅助换页机制，负责限制系统中可被调度的进程的数量。
• 短期调度的触发最为频繁，它负责细粒度地调度进程的执行，做出相应的调度决策。

2. 单核调度策略

2.1 经典调度

• 先到先得(FIFO / FCFS)：
  选取运行队列中的第一个任务，将其移出运行队列并执行;当一个任务执行完后，它会被再次放入运行队列的队尾。
  • 缺点：
    1. 在长短任务混合的场景下对短任务不友好。
• 最短任务优先(SJF)：
  调度时会选择运行时间最短的任务执行。
  • 缺点：
    1. 必须预知任务的运行时间。
    2. 其表现严重依赖于任务到达时间点
• 最短完成时间任务优先(STCF)：
  • 缺点：
    1. 长任务饥饿。
    2. 需要预知任务的运行时间。

非抢占式调度：调度器必须等一个任务执行完或者主动退出执行才能升始下—个调度。
抢占式调度：任务到达系统时会进行调度，有可能会中断当前正在执行的任务，转而执行其他任务。

• 时间片轮转(RR)：
  需要为任务设置时间片，限定任务每次执行的时间。当前任务执行完时间片后，就切换到运行队列中的下一个任务。
  • 缺点
    1. 在任务运行时间相似的场景下平均周转时间高。

响应时间：指的是从用户发起请求到任务响应用户所需的时间。
时间片：每个请求一次可以占用多长时间的资源。

2.2 优先级调度

优先级：会根据重要程度给每个请求分配优先级，优先级高的请求可以优先使用资源。

• 多级队列(MLQ)：
  • 每个任务会被分配预先设置好的优先级，每个优先级对应一个队列，任务会被存储在对应的优先级队列中。如果优先级不同的任务同时处于预备状态，那么调度器应该倾向于调度优先级较高的任务，因此一个任务必须等到所有优先级比它高的任务调度完才可以被调度。处于相同优先级队列的任务。它们内部的调度方式没有统一标准，可以针对性地为不同队列采用不同调度策略，例如FCPS策略或RR策略。
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-w69jd02I-1661672910708)(https：//img-blog.csdnimg.cn/6375960d780b4c1cb786b051f79a5fbd.png)]
  • 缺点：

    1. 低优先级任务饥饿 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CYLJOcEC-1661672910709)(https：//img-blog.csdnimg.cn/2fe2d6fca3bf48be968a6d1e42e39286.png)]

    2. 优先级反转：

优先级反转：
 假设现在有3个任务A、B、C，它们的优先级为A＞B＞C。任务C在运行时持有一把锁，然后它被高优先级的任务A抢占了(任务C的锁没有被释放)。此时任务A恰巧也想申请任务C持有的锁，但是申请失败，因此进人阻塞状态等待任务C放锁。此时，任务B、C都处于可以运行的状态，由于任务B的优先级高于C，因此B优先运行。综合观察该情况，就会发现任务B好像优先级高于任务A，先于任务A执行。这一问题称为优先级反转。
优先级继承：
 任务A通过将自己的优先级转移给占有锁的任务C，让任务C优先执行并放锁。之后，任务A可在任务C放锁后以抢占的方式立即执行，从而避免了优先级反转的问题。

• 多级反馈队列(MLFQ)：
  • 短任务拥有更高的优先级
  • 低优先级的任务采用更长的时间片
  • 定时地将所有任务的优先级提升至最高

2.3 公平共享调度

这类调度器会量化任务对系统资源的占有比例，从而实现对资源的公平调度。我们将以份额(share)来量化每个任务对CPU时间的使用。

• 彩票调度
• 步幅调度

2.4 实时调度

根据任务超过截至时间所造成的后果来分类：

• 硬实时任务：
  该类任务必须在截止时间前完成，否则系统无法承担任务处理超过截止时间的后果。
• 软实时任务：
  该类任务可以偶尔超过截止时间完成，其结果是可接受的。

根据被触发的时间来分类：

• 周期任务：
  指到达系统时间遵循一定周期的任务。
• 偶发任务：
  指不会周期性地到达系统的任务，且还要满足连续两个相同偶发任务到达系统的时间间隔有最小值，即系统不会在同—时刻处理两个相同的偶发任务。
• 非周期任务：
  指到达系统时间随机的任务。

实时操作系统的特点是确定性，即实时任务的完成时间应该是有明确上界的。
实时调度策略：

• 速度单调(RM)：
  该调度策略需要预知任务的周期T，并且根据周期静态地为每个任务分配一个优先级，任务的周期越短，意味着其截止时间要求越迫切，则其优先级越高。RM策略还支持抢占调度，高优先级的任务可以抢占低优先级的任务执行。
• 最早截至时间优先(EDF)：
  任务的截止时间越近则优先级越高。

3. 多核调度策略

3.1 负载分担

 多核共享—个全局运行队列。当一个CPU核心需要调度任务时，根据给定的调度策略，决定全局运行队列中下一个由它执行的任务。给定的调度策略可以是单核调度中的任一策略。

3.2 协同调度

 尽可能让一组任务并行执行，避免调度器同时调度有依赖关系的两组任务，同时避免关联任务(倾向于同时执行的—系列任务，比如需要相互通信的任务)执行效率降低的问题。

• 群组调度：
  将关联任务设置为一组(gang)，并以组为单位调度任务在多个CPU核心上执行，使它们的开始时间和结束时间接近相同。

3.3 两级调度

 全局调度器会使得任务在不同CPU核心上切换执行，造成切换开销。为了减少开销，每个任务应尽可能只在一个CPU核心上进行调度。因此，新的调度策略改为每个CPU核心都引人一个本地调度器，并用它管理对应核心上执行的任务。这种调度策略使用全局调度器和本地调度器，构成了层级化结构，—般称之为两级调度(two level scheduling)。

3.4 负载追踪与负载均衡

 通过追踪每个CPU核心当前的负载情况，将处于高负载的CPU核心管理的任务迁移到低负载的CPU核心上，尽可能地保证每个核心的负载大致相同。

• 调度实体粒度负载追踪
• 负载均衡