不浮躁
分类: LINUX
2014-11-15 12:54:53
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)调度。