了解linux调度器

Question

我是linux内核和底层编程新手。我想知道linux调度程序如何在时间复杂度上应该是0(1)。

我看到了下面的文章，内容非常丰富，但我在理解下面我复制的段落时遇到了问题http://www.ibm.com/developerworks/linux/library/l-scheduler/

调度程序的工作很简单:选择最高的任务要执行的优先级列表。为了使这个过程更有效，a位图用于定义任务何时在给定的优先级列表上。因此，在大多数体系结构中，查找第一个位集指令是用于查找设置在五个32位字中的一个中的最高优先位(对于140个优先事项)。查找要执行的任务所需的时间不取决于活动任务的数量，而是取决于优先级。这使得2.6调度器成为一个O(1)进程，因为日程安排的时间既是固定的，又是确定的，无论时间如何活动任务数。

为什么为140个队列提供5个32位的字?find-first-bit-set指令帮助谁从140个队列中选择一个?

Answer 1

位字段使用单个值来表示多个布尔状态，例如，如果我们使用8位整数，那么我们可能会说:

17 (decimal) = 00010001 (binary)

表示第4和第8个布尔值为真，而其他所有布尔值为假。总共可以跟踪8个布尔状态，因为有8位。

由于我们希望跟踪140个状态(每个队列1,true表示队列包含一个任务)，因此需要140位，因此140/32 = 4.375，我们需要至少5个32位整数来存储所有布尔状态。

Answer 2

像这样:

int bitmap_idx = priority/BITS_PER_WORD;
int bitmap_bit = priority%BITS_PER_WORD;
isSet = ( bitmap[bitmap_idx]&(1<<bitmap_bit) );  //test
bitmap[bitmap_idx] |= 1<<bitmap_bit;             //set

用于到达具有优先级数组的特定进程，这就是调度程序中使用位图的方式，这反过来取决于struct prio_array

你指出的那篇文章已经过时了，看看这篇http://www.informit.com/articles/article.aspx?p=101760& seqNum = 2