Linux プロセススケジューリング

00:00 - ⏰ プロセス调度

#

まとめ：

#

• プロセス调度的目的是在多个程序或プロセス之间合理分配 CPU 时间。最初，程序通过主动调用 API 函数交出 CPU，但有时プロセス不合作，比如陷入死循环或长时间占用 CPU，导致其他プロセス无法执行。

• 为了避免这些問題，システム引入了时钟中断机制，在每个时钟周期结束时，强制切换プロセス，这つまり抢占式调度的基础。每个プロセス被分配一个固定的时间片（比如 100 毫秒），时间片用完时，调度器会选择其他プロセス执行。

• 随着プロセス数量增加，システム通过就绪队列管理プロセス（即正在等待 CPU 执行的プロセス）。此外，将阻塞的プロセス（如等待 I/O 或锁的プロセス）移到等待队列，避免 CPU 空转。

例：

#

假设你有 5 个プロセス在実行，每个プロセス执行 100ms，调度器每 100ms 中断一次。もしプロセス A 被选中実行，但它一直在等待 I/O，システム就会把它移入等待队列，调度下一个プロセス。这样，CPU 就不会空闲，而是去执行其他プロセス。

2:09 - 🤔 プロセス过多导致システム卡顿

#

まとめ：

#

• 初始时システムプロセス较少，実行流畅，但随着プロセス增多（达到数百个），即使每个プロセス的执行时间很短（たとえば 10 毫秒），每个プロセス上下文切换的开销依然很大。

• 上下文切换包括保存和加载プロセス的状态，这些操作有较高的开销。もし进一步缩短每个プロセス的执行时间，虽然每个プロセス的 CPU 时间减少了，但上下文切换的开销却增加了，反而导致システム卡顿。

例：

#

假设有 1000 个プロセス，每个プロセス分配 10ms 执行时间。理论上每个プロセス执行 10ms 后进行一次上下文切换，但上下文切换本身必要时间（假设每次切换花费 1ms），もしシステム做过多上下文切换，反而会导致效率低下，システム变得卡顿。

2:47 - ⏳ 双队列プロセス调度

#

まとめ：

#

• 为了解決高プロセス数量带来的效率問題，システム采用了双队列调度：
  1. active 队列：用于存放正在実行的プロセス。
  2. expi 队列：用于存放高优先级的プロセス，暂时不执行。
• 这种方法的关键是避免高优先级プロセス长期占用 CPU 资源，导致低优先级プロセス**“饿死”。在某一轮调度后，システム将高优先级プロセス移到 expi 队列**，その後继续执行 active 队列中的プロセス，直到所有プロセス都执行完后，交换两个队列指针，确保所有优先级的プロセス都有机会执行。

例：

#

假设有两个队列：

1. active 队列：[プロセス A, プロセス B, プロセス C]
2. expi 队列：[プロセス D, プロセス E]

调度时，高优先级プロセス（D, E）会被暂时放入 expi 队列，只有 active 队列中的プロセス（A, B, C）能被调度。待 active 队列中的プロセス执行完后，交换队列指针，使得 expi 队列中的プロセス得以执行。

5:33 - 优先级调度改进

#

まとめ：

#

• 为了解決优先级调度中出现的問題，采用了动态时间片分配アルゴリズム。该アルゴリズム根据プロセス的优先级来分配时间片：优先级较高的プロセス拥有较短的时间片，优先级较低的プロセス则拥有较长的时间片。

• 举例来说，优先级为 20 的プロセス的时间片是 100 毫秒，每升高或降低一级，时间片增加或减少 5 毫秒。然而，存在缺陷：もし两个プロセス优先级相差 1，CPU 占用的差距可能非常大，有时能达到几倍的差异。

例：

#

假设有两个プロセス，プロセス A 和プロセス B，优先级分别为 20 和 19：

• プロセス A 时间片是 100ms，プロセス B 时间片是 105ms。理论上，プロセス B 会占用更多的 CPU 时间，但もしシステム频繁切换プロセス，B 却可能なぜなら时间片过长而阻塞过久，A 反而会更频繁地被调度，影响公平性。

7:01 - ⏳ 权重优先调度

#

まとめ：

#

• 权重优先调度アルゴリズム基于プロセス优先级的权重来分配 CPU 时间。每个プロセス的时间片根据其权重进行调整，权重越大的プロセス获得更多的 CPU 时间。

• たとえば，プロセス A 权重为 1，プロセス B 权重为 2，プロセス A 每次获得 100 毫秒的时间片，而プロセス B 则获得 200 毫秒的时间片。为了避免过度切换，アルゴリズム还设置了最小时间片。

• もしプロセス的时间片没有完全用完，调度器会考虑优先执行那些実行时间最短的プロセス。通过引入虚拟実行时间，アルゴリズム能够补偿权重差异所导致的时间片分配不均，确保システム公平。

例：

#

• 假设プロセス A 的权重是 1，プロセス B 的权重是 2。假如它们的时间片分别为 100ms 和 200ms。
• もしプロセス A 没有完全用完 100ms，它会较快地再次获得 CPU，プロセス B 则较慢。为了补偿プロセス B なぜなら权重较大而执行时间过长，调度器会让プロセス A 在某些时刻得到更多的 CPU 时间。

9:02 - ⏱️ 虚拟时间调度

#

まとめ：

#

• 这种调度アルゴリズム的核心思想是通过プロセス的虚拟时间来决定其执行顺序。虚拟时间是指プロセス已消耗的“公平时间”，プロセス的虚拟时间越短，它会越早被选中执行。

• 为了高效管理这些プロセス，システム使用红黑树来维护プロセス。通过缓存最左节点（虚拟时间最短的プロセス），调度器能够快速找到下一个应该执行的プロセス。

• 这种方式与 Linux 的 O(1) 调度アルゴリズム和 CFS 调度アルゴリズム类似，但做了一些简化，仍然能保证高效且公平的调度。

例：

#

• 假设有 3 个プロセス A、B 和 C，它们的虚拟时间分别为 5ms、10ms 和 15ms。调度器会根据虚拟时间来选择最短的プロセス（A）执行。
• 红黑树用于快速查找最短虚拟时间的プロセス，プロセス A 会被选中执行。