我正在互联网上的某个地方读书，但我不记得...... Linux调度程序试图锻炼“活动”队列和进程几乎在O（1）中运行 .
我的问题是，因为有两个队列，活动和过期 . 两个队列中的每一个都有140个优先级 . 因此，对于140个优先级中的每一个，将存在单独的进程队列 .
如果我必须使用这些数据，我会使用“for循环” . 话虽如此，for循环将是昂贵的，因为在140个队列中的任何一个中都可以有N个进程 . 因此，复杂性应该是O（N），这对于调度程序来说是不可接受的 .
那么linux调度程序是如何做到的呢？
1 回答
在2.6.23之前的Linux内核2.6版本中，使用的调度程序是IngoMolnár的O（1）调度程序 .
此后使用的调度程序是IngoMolnár的完全公平调度程序，它在O（log N）时间内运行 .
看看wikipedia article
以下两个教程完整地解释了O（1）调度Tutorial 1和Tutorial 2