O(1)调度器的重要数据结构
(1)就绪队列 struct runqueue
runqueue 的设计是 O(1)调度器的关键技术所在,它用于存放特定 CPU 上的就绪进程队列信息,其中包含每个 CPU 的调度信息。该结构在 /kernel/sched.c 中的定义如下:
struct runqueue {
...
prio_array_t *active, *expired, array[2];
active 是指向活动进程队列的指针
expired 是指向过期进程队列的指针
array[2]是实际的优先级进程队列，其中一个是活跃的一个是过期的，过期数组存放时间片耗完的进程
...
}
在 2.6 中,每个 CPU 单独维护一个就绪队列,每个就绪队列都有一个自旋锁,从而解决了 2.4 中因只有一个就绪队列而造成的瓶颈。
(2)task_struct 结构
Linux2.6 内核使用 task_struct 结构来表示进程。2.6 对 task_struct 也做了较大的改动,
该结构定义在/include/linux/sched.h 中:
struct task_struct{
...
int prio,static_prio;
prio 是动态优先级,static_prio 是静态优先级(与最初nice相关)
...
prio_array_t *array;
记录当前 CPU 的活跃就绪队列
unsigned long sleep_avg;
进程的平均等待时间,取值范围[0,MAX_SLEEP_AVG],初值为0。sleep_avg 反映了该进程需要运行的紧迫性。进程休眠该值增加，如果进程当前正在运行该值减少。是影响进程优先级最重要的元素。值越大,说明该进程越需要被调度。
...
};
(3)优先级数组
每个处理器的就绪队列都有两个优先级数组（acitve数组和expired数组）,它们是 prio_array 类型的结构体。Linux2.6内核正是因为使用了优先级数组,才实现了 O(1)调度算法。该结构定义在 kernel/sched.c 中:
struct prio_array{
...
unsigned int nr_active;
/**相应 runqueue 中的进程数
unsigned long bitmap[BITMAP_SIZE];
/**索引位图，BITMAP_SIZE 默认值为 5,5个long(32位)类型，每位代表一个优先级，可以代表160个优先级，但实际中只有140。
与下面的queue[]对应。
分布0-99对应为实时进程，100-140对应为普通的进程
struct list_head queue[MAX_PRIO];
/**每个优先级的进程队列,MAX_PRIO 是系统允许的最大优先级数,默认值为 140,数值越小优先级越高bitmap每一位都与 queue[i]相对应,当 queue[i]的进程队列不为空时,bitmap 相应位为 1,否则就为 0。
}
O(1)调度算法实现的简单介绍
(1)选择并运行候选进程 next它确定下一个应该占有 CPU 并运行的进程,schedule()函数是完成进程调度的主要函数,并完成进程切换的工作。schedule()用于确定最高优先级进程的代码非常快捷高效,其性能的好坏对系统性能有着直接影响,它在/kernel/sched.c 中的定义如下:
...
int idx;
...
preempt_disable();
...
idx = sched_find_first_bit( array -> bitmap);
queue = array -> queue + idx;
next = list_entry( queue -> next, task_t, run_list);
...
prev = context_switch( rq, prev, next);
...
}
其中,sched_find_first_bit()能快速定位优先级最高的非空就绪进程链表,运行时间和就绪队列中的进程数无关,是实现 O(1)调度算法的一个关键所在。
schedule()的执行流程:首先,调用 pre_empt_disable(),关闭内核抢占,因为此时要对内核的一些重要数据结构进行操作,所以必须将内核抢占关闭;其次,调用sched_find_first_bit()找到位图中的第1个置1的位,该位正好对应于就绪队列中的最高优先级进程链表;再者,调用 context_switch()执行进程切换,选择在最高优先级链表中的第 1个进程投入运行;
详细过程如图 1 所示：
图 1
图中的网格为 140 位优先级数组,queue[7]为优先级为 7 的就绪进程链表。
此种算法保证了调度器运行的时间上限,加速了候选进程的定位过程。