AI 摘要：Linux 如何调度进程？大学老师不讲的，看完动画秒懂！

摘要

视频通过动画演示了 Linux 系统中进程调度的基本原理和优化过程。从最初的简单交替执行，到引入时间片、优先级、多队列和虚拟运行时间等概念，逐步展示了调度算法的复杂化和优化。最终介绍了 Linux 中的 O (1) 调度算法和 CFS 完全公平调度算法的雏形。

亮点

🔄 交替执行：最初只有两个程序时，通过交替执行来实现简单的调度。
⏱️ 时间片：引入时间片概念，每个进程执行一小段时间后切换，提高响应速度。
📊 优先级：随着进程增多，引入优先级概念，高优先级进程优先执行。
📈 多队列：按优先级拆分队列，提高调度效率，避免低优先级进程被饿死。
🕒 虚拟运行时间：通过虚拟运行时间来公平调度，消除权重带来的时间分配不均问题。

#Linux调度 #进程管理 #调度算法

思考

Linux 中的 O (1) 调度算法和 CFS 完全公平调度算法的主要区别是什么？
如何通过虚拟运行时间来实现进程调度的公平性？
在多队列调度中，如何处理高优先级进程长时间占用 CPU 的问题？

视频章节总结

00:00 - ⏰进程调度

最初，程序通过主动调用 API 函数交出 CPU 实现交替执行。但程序可能不合作，导致死循环或长时间占用 CPU。因此，引入时钟中断机制，在中断处理程序中实现抢占式调度，每个进程执行一个时间片（例如 100 毫秒）。随着进程增多，使用就绪队列管理进程。进一步优化，将阻塞的进程（等待锁、IO 或 sleep）移入等待队列，避免 CPU 空转，提高效率。

2:09 - 🤔进程过多导致系统卡顿

系统最初进程少时运行流畅，但进程增多到数百个，每个进程执行时间即使缩短到 10 毫秒，上下文切换总时间仍然过长导致系统卡顿。继续缩短进程执行时间又会增加上下文切换开销，得不偿失。

2:47 - ⏳双队列进程调度

为解决进程调度问题，系统最初采用单队列按优先级（1-40）调度，但效率低。后改进为 40 个优先级队列，用位图标记队列状态，提高查找效率。然而，高优先级进程可能导致低优先级进程“饿死”。最终方案采用两个队列（active 和 expi），高优先级进程执行后移入 expi 队列，待 active 队列所有进程执行完毕后，交换两个队列指针，保证所有优先级进程都能得到执行机会，每个进程的时间片仍为 100 毫秒。

5:33 - 优先级调度改进

为解决高优先级进程 CPU 时间过短的问题，系统采用基于优先级的动态时间片分配算法：优先级 20 的进程时间片为 100 毫秒，每升降一级时间片增减 5 毫秒。但此算法存在缺陷：优先级差距对 CPU 占比影响不均匀，例如优先级相差 1，占比差距可能从 2.5%到一倍不等。因此，需要采用相对时间片而非绝对时间片来改进算法。

7:01 - ⏳权重优先调度

该调度算法以 100 毫秒为周期，根据进程优先级（权重）分配时间片。高优先级进程获得更多时间，但设置最小运行时间避免过度切换。为解决高优先级进程可能未用完时间片的问题，算法考虑优先执行运行时间最短的进程。最后，通过引入虚拟运行时间，补偿因权重差异造成的时间分配不均，确保所有进程在理想情况下获得公平的运行时间。

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

该段落描述了一种进程调度算法的雏形，其核心思想是根据进程的虚拟时间排序，选择虚拟时间最短的进程执行。为了高效管理进程，作者探讨了使用二叉搜索树和红黑树，最终选择红黑树来维护进程，并缓存最左节点（虚拟时间最短的进程）以提高调度效率。这与 Linux 的 O (1) 调度算法和 CFS 算法类似，但进行了简化。