linux内核调度器CFS

Question

linux内核的CFS调度器如何在sched_latency_ns时间内调度所有进程。 是遍历红黑树还是每次进程切换后重新平衡。

Answer 1

从维基百科文章开始...

与旧版 Linux 2.6 内核中使用的 O(1) 调度程序相比，CFS 调度程序实现不基于运行队列。相反，红黑树实现了未来任务执行的“时间线”。此外，调度程序使用纳秒粒度计算，即分配单个进程的 CPU 份额的原子单位（从而使之前的时间片概念变得多余）。例如，这种精确的知识还意味着不需要特定的启发式方法来确定流程的交互性。[2]

Answer 2

这里详细描述CFS以及片段源代码。

Answer 3

CFS 从 rbtree 中选取最左边的节点，复杂度为 O(1)，因为它被缓存了。然后CFS给它分时。 如果任务完成，那么 CFS 就完成它。 如果尚未完成，但时间份额已用完。现在它再次插入到 rbtree，并在需要时重新平衡。