首页 文章

了解linux调度程序

提问于
浏览 次
6

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

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

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

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

linux linux-kernel scheduling

2 回答

  • 4

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

    17 (decimal) = 00010001 (binary)

    这表示第4和第8个布尔值为true，其中所有其他布尔值均为false . 总共可以跟踪8个布尔状态，因为有8位 .

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

    回复于
  • 0

    像这样的东西：

    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

    回复于

相关问题