Linux如何实现O(1)进程调度(bitmap方法)

Linux调度主要是在一个runqueue结构体上操作。runqueue结构体有一个prio_array结构体数组，该数组中有个两个prio_array结构体。prio_array结构体的定义如下：

struct prio_array 
{ 
  int nr_active /* number of tasks in the queue */; 
  unsigned long bitmap[BITMAP_SIZE]; /* priority bitmap */ 
  struct list_head queue[MAX_PRIO]; /* priority queue */ 
}

这两个prio_array，一个挂着expired task（时间片已经用完的task），另一个挂着active task（时间片尚未用完的task）。当active task为空时，就交换这两个prio_array的指针值就OK了。

接下来讲解prio_array中的成员

nr_active：就不用多说了，就表示该prio_array结构体上挂着多少个任务。

struct list_head queue[MAX_PRIO]：这是一个指针数组，每个数组标记一个链表头，每个链表头上挂着一串相同优先级的task。

unsigned long bitmap[BITMAP_SIZE]：这个成员的每一个表示对应的优先级的task链表上是否为空。

有了上面的基础，接下来就讲解如何实现O(1)调度，当要调度程序时，

1）首先找到bitmap成员上第一个为 1 的bit位置，比如说bitmap的第8位为1，则表示前面0~7高优先级的task链表上没有task。

2）然后访问struct list_head queue[MAX_PRIO]数组的第八个成员，该成员是优先级为8的task链表的表头，

3）最后通过表头取下第一个task，再将其调度上CPU，这样就实现了O(1)调度。