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 - ⏳ 双队列进程调度
总结：
- 为了解决高进程数量带来的效率问题，系统采用了双队列调度：
- active 队列：用于存放正在运行的进程。
- expi 队列：用于存放高优先级的进程，暂时不执行。
- 这种方法的关键是避免高优先级进程长期占用 CPU 资源，导致低优先级进程“饿死”。在某一轮调度后，系统将高优先级进程移到 expi 队列，然后继续执行 active 队列中的进程，直到所有进程都执行完后，交换两个队列指针，确保所有优先级的进程都有机会执行。
示例：
假设有两个队列：
- active 队列：[进程 A, 进程 B, 进程 C]
- 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 会被选中执行。