Linux调度算法相关2

发表于 更新于

实时进程调度概述

标准调度与实时调度的差异

标准内核调度算法通常可以为交互式和后台进程的混合提供足够的性能和响应能力。然而，实时应用程序对调度器的需求更加严格

1. 提供外部输入的最大响应时间保证

  • 实时应用程序必须保证对外部输入的最大响应时间。在许多情况下，这些最大响应时间需要非常短，例如在毫秒或几分之一秒的级别。

附加措施

  • 一些时间关键型的应用可能需要采取其他措施来避免不可接受的延迟。例如：
    • 使用 mlock() 或 mlockall() 将应用程序的所有虚拟内存锁定到 RAM 中，避免页面错误造成的延迟。

2. 保持对 CPU 的独占访问权

  • 高优先级进程在完成任务或自愿放弃 CPU 之前，应该能够独占地使用 CPU，确保任务的顺利执行。

    3. 进程顺序控制

  • 实时应用程序需要对其成员进程精确顺序的调度权。

实时调度的 POSIX API

SUSv3 的实时调度 API

SUSv3 定义了一个实时进程调度 API，部分满足了实时应用的严格需求：

  • 提供两种实时调度策略：
    • SCHED_FIFO（先进先出）
    • SCHED_RR（轮转）
  • 使用这些策略的进程优先级总是高于采用 SCHED_OTHER（普通时间共享）的进程。

实时优先级范围

  • 每种实时调度策略至少需要支持 32 个离散优先级。
  • 高优先级的进程总是优先于低优先级的进程。

多处理器系统中的调度行为

在多处理器系统（包括超线程系统）中，调度行为有一些特殊性：

  1. 每个 CPU 维护一个独立的运行队列。这种设计优于单一的系统级运行队列，可以提高性能。
  2. 进程只能在其所属 CPU 的运行队列中被调度。
  3. 举例：
    • 在一个双处理器系统中，如果有三个进程：
      • 进程 A：实时优先级为 20；
      • 进程 B：实时优先级为 30；
      • 进程 C：实时优先级为 10；
    • 如果当前 CPU0 正在运行 B，A 只能等待 CPU0 空闲，即使 A 的优先级高于 CPU1 上正在运行的 C。

Linux 提供了 99 个实时优先级，从 1（最低）到 99（最高）。这一区间适用于两种实时调度策略（SCHED_RR 和 SCHED_FIFO）。两种策略中的优先级是等效的。

这意味着：

  • 如果两个进程具有相同的优先级，一个使用 SCHED_RR 策略，另一个使用 SCHED_FIFO 策略，那么哪个进程会被调度取决于它们被放入队列的顺序。

实际上，每个优先级都维护着一个可运行进程的队列。

  • 调度时，系统会从最高优先级的非空队列中选择队列头部的进程来运行。

POSIX 实时 vs 硬实时

POSIX 实时（软实时）

POSIX 提供的是软实时调度功能，具体表现为：

  • 可以控制进程何时被调度。
  • 不能完全保证处理输入时的响应时间。
  • 适用于绝大多数实时场景，但无法满足某些严格的硬实时需求。

硬实时

  • 硬实时系统保证所有任务在规定的时限内完成。
  • 实现硬实时通常需要操作系统支持额外的功能，而 Linux 默认不支持。
  • Linux 内核自 2.6.18 版本以来添加了一些功能，目标是原生支持硬实时应用，但仍需配置和优化。

SCHED_RR 策略详解

基本规则

在 SCHED_RR 策略下：

  • 同一优先级的任务按照轮转方式共享 CPU，每个任务在每次使用 CPU 时获得一个固定长度的时间片。

执行控制

任务保持对 CPU 的控制直到以下任一情况发生：

  1. 时间片耗尽：
    • 任务被移至同一优先级队列的末尾，其他同优先级任务可以被调度。
  2. 自愿放弃 CPU：
    • 例如，调用了 sched_yield() 或执行了阻塞操作。
  3. 任务终止。
  4. 被更高优先级的任务抢占。

对于前两个事件（时间片耗尽或主动放弃 CPU）中的情况，当运行在 SCHED_RR 策略下的进程失去对 CPU 的访问权限时，它会被移至其优先级队列的末尾。
在最后一种情况中（被更高优先级的进程抢占），当高优先级进程结束执行后，被抢占的进程会继续运行，使用其剩余的时间片（即被抢占的进程会回到其优先级队列的头部）。

SCHED_RR 和 SCHED_FIFO

在 SCHED_RR 和 SCHED_FIFO 策略中，当前运行中的进程可能因以下原因之一被抢占：

  1. 一个更高优先级的进程从阻塞状态变为非阻塞状态（例如，I/O 操作完成）。
  2. 另一个进程的优先级被提升到高于当前运行进程的优先级。
  3. 当前运行进程的优先级被降低到低于某些其他可运行进程的优先级。

SCHED_RR 策略类似于标准的轮转时间共享调度算法（SCHED_OTHER），它允许一组相同优先级的进程共享 CPU。

两者的主要区别：

  1. 优先级规则：

    • SCHED_RR 策略严格区分优先级，高优先级的进程总是优先于低优先级的进程。
    • 而 SCHED_OTHER 策略中，较低的 nice 值（即较高的优先级）虽然增加了调度权重，但不能保证独占 CPU。

  2. 时间片保障：

    • 在 SCHED_OTHER 策略中，任何具有低优先级（高 nice 值）的进程始终可以获得一定的 CPU 时间。
    • SCHED_RR 策略允许我们更精确地控制进程的调度顺序和执行时间。

SCHED_FIFO 策略详解

基本规则

SCHED_FIFO（先进先出）策略与 SCHED_RR 类似，但没有时间片限制。

  • 任务可以一直运行，直到以下任一情况发生：
    1. 主动放弃 CPU（例如阻塞操作）。
    2. 任务终止。
    3. 被更高优先级任务抢占。

在第一种情况下，进程会被放置到其优先级队列的末尾。
在最后一种情况下，当高优先级的进程停止执行（例如由于阻塞或终止）时，被抢占的进程会继续执行（即，被抢占的进程会保持在其优先级队列的队首）。

SCHED_BATCH 和 SCHED_IDLE 策略

SCHED_BATCH 策略

  • 功能：用于批处理型任务。
  • 特点：
    • 适用于 CPU 密集型任务。
    • 对调度延迟不敏感。
    • 调度器会根据任务的 nice 值决定优先级。
  • 引入版本：Linux 2.6.16。

SCHED_IDLE 策略

  • 功能：用于低优先级任务，仅在系统完全空闲时执行。
  • 特点：
    • 优先级比所有其他任务都低（甚至低于 nice +19）。
    • nice 值对该策略没有影响。
  • 引入版本：Linux 2.6.23。