Linux 2.6 Completely Fair Scheduler 内幕(2)

CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡(公平性)。这意味着应给进程分配相当数量的处理器。分给某个任务的时间失去平衡时(意味着一个或多个任务相对于其他任务而言未被给予相当数量的时间),应给失去平衡的任务分配时间,让其执行。

要实现平衡,CFS 在叫做虚拟运行时 的地方维持提供给某个任务的时间量。任务的虚拟运行时越小, 意味着任务被允许访问服务器的时间越短 — 其对处理器的需求越高。CFS 还包含睡眠公平概念以便确保那些目前没有运行的 任务(例如,等待 I/O)在其最终需要时获得相当份额的处理器。

但是与之前的 Linux 调度器不同,它没有将任务维护在运行队列中,CFS 维护了一个以时间为顺序的红黑树(参见图 1)。 红黑树 是一个树,具有很多有趣、有用的属性。首先,它是自平衡的,这意味着树上没有路径比任何其他路径长两倍以上。 第二,树上的运行按 O(log n) 时间发生(其中 n 是树中节点的数量)。这意味着您可以快速高效地插入或删除任务。


图 1. 红黑树示例

红黑树示例


任务存储在以时间为顺序的红黑树中(由 sched_entity 对象表示),对处理器需求最多的任务 (最低虚拟运行时)存储在树的左侧,处理器需求最少的任务(最高虚拟运行时)存储在树的右侧。 为了公平,调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。任务通过将其运行时间添加到虚拟运行时, 说明其占用 CPU 的时间,然后如果可运行,再插回到树中。这样,树左侧的任务就被给予时间运行了,树的内容从右侧迁移到左侧以保持公平。 因此,每个可运行的任务都会追赶其他任务以维持整个可运行任务集合的执行平衡。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/27560.html