Linux内核的CFS调度器是如何在sched_latency_ns时间内调度所有进程的，是遍历红黑树还是在每次进程切换后重新平衡。
vawmfj5a1#
从Wikipedia文章开始...与以前在旧的Linux 2.6内核中使用的O（1）调度器相比，CFS调度器的实现不是基于运行队列。相反，红黑树实现了未来任务执行的“时间轴”。此外，调度器使用纳秒粒度会计，分配给单个进程的CPU份额的原子单位这种精确的知识也意味着不需要特定的逻辑来确定进程的交互性。[2]
ebdffaop2#
here详细介绍了CFS，并提供了源代码片段。
66bbxpm53#
CFS以O（1）的复杂度从rbtree中选择最左边的节点，因为它是缓存的。然后CFS给它时间共享。如果任务完成了，那么CFS只是完成它。如果它还没有完成，但是时间共享用完了，或者它自愿停止（等待IO阅读、写、网络数据包.）。它现在再次插入到rbtree中，复杂度为O（logN），如果需要，还可以重新平衡。
3条答案
按热度按时间vawmfj5a1#
从Wikipedia文章开始...
与以前在旧的Linux 2.6内核中使用的O（1）调度器相比，CFS调度器的实现不是基于运行队列。相反，红黑树实现了未来任务执行的“时间轴”。此外，调度器使用纳秒粒度会计，分配给单个进程的CPU份额的原子单位这种精确的知识也意味着不需要特定的逻辑来确定进程的交互性。[2]
ebdffaop2#
here详细介绍了CFS，并提供了源代码片段。
66bbxpm53#
CFS以O（1）的复杂度从rbtree中选择最左边的节点，因为它是缓存的。然后CFS给它时间共享。
如果任务完成了，那么CFS只是完成它。
如果它还没有完成，但是时间共享用完了，或者它自愿停止（等待IO阅读、写、网络数据包.）。它现在再次插入到rbtree中，复杂度为O（logN），如果需要，还可以重新平衡。