主页 / ubuntu / 问题 / 512975
Accepted
Mohammad Reza Rezwani
Asked: 2014-08-19 07:45:36 +0800 CST

内核使用哪种调度算法？

  • 772

我知道处理器有很多调度算法。比如FCFS（先到先得）或者SJF（short job first）等等。如何知道内核使用哪种算法？

process

1 个回答

  1. Best Answer

    两者都不：

    从 Linux 2.6.23 开始

    Con Kolivas 的工作，最重要的是他实现了名为“旋转楼梯截止日期”的“公平调度”，启发了 Ingo Molnár 开发完全公平调度程序作为早期O(1)调度程序的替代品，Kolivas 在他的声明中称赞了这一点。

    完全公平调度程序 (CFS)使用一种经过充分研究的经典调度算法，称为公平队列，最初是为分组网络发明的。公平排队以前曾以 stride scheduling 的名义应用于 CPU 调度。

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

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

    如果您愿意查看源代码，sched/fair.c实施 CFS，并sched/rt.c实施POSIX 要求的FIFO（或您所说的 FCFS）和实时进程的循环 (RR) 算法。

    延伸阅读：

    1. 内核文档
    2. IBM developerWorks 关于 CFS 的文章
    3. 关于 CFS 的 Linux 期刊文章
    • 1

相关问题