了解linux调度程序

Question

我是linux内核和低级编程的新手.我想知道linux调度程序在时间复杂度上应该是O(1).

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

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

为什么140个队列中有5个32位的字？find-first-bit-set指令有助于选择140个队列中的一个？

Answer 1

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

17 (decimal) = 00010001 (binary)

这表明第四个和第八个布尔值是 true，而所有其他布尔值都是 false。由于有 8 个位，总共可以跟踪 8 个布尔状态。

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