☰

内核使用哪种调度算法？

tag-icon • tag-icon process schedule
内核使用哪种调度算法？

我知道有很多处理器调度算法。比如先期先得（先到先得）或顺风车（先简短地做作业）等等。如何知道内核使用了哪种算法？

答案1

两者都不：

自 Linux 2.6.23 起

鉴于 Kolivas 的工作，其中最重要的是他实现的名为“旋转阶梯截止时间”的“公平调度”，这启发了 Ingo Molnár 开发完全公平调度程序来替代早期的O(1)调度程序，并在他的声明中对 Kolivas 表示感谢。

这完全公平调度程序（CFS）使用一种经过充分研究的经典调度算法，称为公平排队，最初是为分组网络发明的。公平排队之前曾以步幅调度的名称应用于 CPU 调度。

公平排队 CFS 调度程序的调度复杂度为O(log N)，其中 N 是运行队列中的任务数。选择一个任务可以在常数时间内完成，但在任务运行后重新插入需要O(log N)操作，因为运行队列是以红黑树的形式实现的。

CFS 是第一个在通用操作系统中广泛使用的公平排队进程调度程序的实现。

如果你愿意看看源代码，sched/fair.c实施 CFS，并且sched/rt.c实现POSIX 要求用于实时进程的FIFO（或称为FCFS）和Round-Robin（RR）算法。

进一步阅读：

  1. 内核文档
  2. IBM developerWorks 关于 CFS 的文章
  3. Linux Journal 有关 CFS 的文章

答案2

默认内核调度程序（CFS 或 EEVDF）和https://www.phoronix.com/news/Rust-Linux-Scheduler-Experiment

相关内容