了解Linux调度程序
我是Linux内核和低级编程的新手。 我想知道linux调度程序在时间复杂度上应该是O（1）。
我遇到以下文章，内容非常丰富，但是我在理解下面转载的章节时遇到了问题：http://www.ibm.com/developerworks/linux/library/l-scheduler/
调度程序的工作很简单：选择要执行的最高优先级列表上的任务。 为了使此过程更高效，使用位图来定义任务何时位于给定的优先级列表中。 因此，在大多数体系结构中，使用find-first-bit-set指令来查找五个32位字中的一个（140个优先级）中设置的最高优先级位。 找到要执行的任务所需的时间不取决于活动任务的数量，而取决于优先级的数量。 这使2.6调度程序成为O（1）进程，因为无论活动任务的数量如何，调度时间既是固定的也是确定性的。
为什么在140个队列中有5个32位的字？ 谁是find-first-bit-set指令有助于选择140个队列之一？
位字段使用单个值来表示多个布尔状态，例如，如果我们使用8位整数，那么我们可以这样说：
17 (decimal) = 00010001 (binary)
这将表明第4和第8个布尔值是true，其中所有其他布尔值都是false。 总共有8个布尔状态可以跟踪，因为有8个位。
由于我们希望跟踪140个状态（每个队列1个，true表示队列包含一个任务），所以需要140个比特，因此我们需要至少5个32位整数来存储所有布尔状态。
像这样的东西：
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
链接地址: http://www.djcxy.com/p/84789.html