我是linux内核和低级编程的新手.我想知道linux调度程序在时间复杂度上应该是O(1).
我看到下面的文章非常有用,但我在理解下面转载的段落时遇到了问题
http://www.ibm.com/developerworks/linux/library/l-scheduler/
The job of the scheduler is simple: choose the task on the highest
priority list to execute. To make this process more efficient,a
bitmap is used to define when tasks are on a given priority list.
Therefore,on most architectures,a find-first-bit-set instruction is
used to find the highest priority bit set in one of five 32-bit words
(for the 140 priorities). The time it takes to find a task to execute
depends not on the number of active tasks but instead on the number of
priorities. This makes the 2.6 scheduler an O(1) process because the
time to schedule is both fixed and deterministic regardless of the
number of active tasks.
为什么140个队列中有5个32位的字？ find-first-bit-set指令有助于选择140个队列中的一个？
位字段使用单个值来表示多个布尔状态,例如,如果我们使用的是8位整数,那么我们可以这样说：
17 (decimal) = 00010001 (binary)
这表示第4和第8个布尔值为true,其中所有其他布尔值均为false.总共可以跟踪8个布尔状态,因为有8位.
由于我们希望跟踪140个状态(每个队列1个,true表示队列包含任务),需要140位,因此140/32 = 4.375,我们需要至少5个32位整数来存储所有布尔状态.
