理解 Linux 调度程序

Question

我对Linux内核和低级编程还不熟悉。我想了解Linux调度程序如何实现O（1）时间复杂度。

我找到了以下非常有用的文章，但我无法理解下面重现的段落：http://www.ibm.com/developerworks/linux/library/l-scheduler/ 调度程序的工作很简单：选择最高优先级列表上的任务执行。为了使这个过程更加高效，位图被用来定义任务在给定优先级列表上的位置。因此，在大多数架构中，使用“查找第一个设置位”指令来查找在五个32位字（140个优先级）中设置了最高优先级位的任务。找到要执行的任务所需的时间取决于优先级数量，而不是活动任务数量。这使得2.6调度程序成为O（1）进程，因为无论活动任务数量如何，调度时间都是固定和确定的。

为什么140个队列需要5个32位字？“查找第一个设置位”指令如何帮助选择其中一个140个队列？

- Eastern Monk

Answer 1

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

17 (decimal) = 00010001 (binary)

这意味着第4个和第8个布尔值为真，而所有其他布尔值都为假。总共可以跟踪8种布尔状态，因为有8位。

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

- Justin

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

- Registered User

---

谢谢。我的问题很久以前就得到了很好的答案。 - Eastern Monk