从Linux 2.6.23开始
康·科利瓦斯(Con Kolivas)的工作,最重要的是他实施了“公平调度”(称为“旋转楼梯截止期限”),鼓舞了英戈·莫尔纳尔(IngoMolnár)开发完全公平调度器,以替代早期的
O(1)
调度器,在此基础上对科利瓦斯表示赞赏。在完全公平调度器(CFS)使用一种称为公平排队最初发明的分组网络精心研究,经典的调度算法。公平排队以前曾以步幅调度的名义应用于CPU调度。
公平队列CFS调度程序的调度复杂度为
O(log N)
,其中N是运行队列中的任务数。选择任务可以在固定时间内完成,但是在任务运行后重新插入任务需要进行O(log N)
操作,因为运行队列是由红黑树实现的。CFS是在通用操作系统中广泛使用的公平排队过程调度程序的第一个实现。
如果您愿意查看源代码,sched/fair.c
实现CFS并sched/rt.c
实现POSIX所需的FIFO(或您称为FCFS)和实时处理的循环算法(RR)。
进一步阅读:
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句