linux 2.6内核O(1)调度分析

         在2.6早期的版本使用的调度是O（1）调度，这也算是针对2.4在调度这块做了
一次大的手术，当然现在O（1）也被完全公平调度CFS调度给取代了。CFS调度也是
针对O(1)的不足而提出来的，所以分析O(1)还是很有意义的。
以下代码取自linux-2.6.15
-------------------------------------------------------------------------------------
一，可运行队列。
        内核中为每个CPU设置了一个就绪队列，该结构就是struct runqueue{};。

200 struct runqueue {
 201     spinlock_t lock;
 207     unsigned long nr_running;
 208 #ifdef CONFIG_SMP
 209     unsigned long prio_bias;
 210     unsigned long cpu_load[3];
 211 #endif
 212     unsigned long long nr_switches;
 220     unsigned long nr_uninterruptible;
 221
 222     unsigned long expired_timestamp;
 223     unsigned long long timestamp_last_tick;
 224     task_t *curr, *idle;
 225     struct mm_struct *prev_mm;
 226     prio_array_t *active, *expired, arrays[2];
 227 int best_expired_prio;
 228     atomic_t nr_iowait;
 229
 230 #ifdef CONFIG_SMP
 231     struct sched_domain *sd;
 232
 233 /* For active balancing */
 234 int active_balance;
 235 int push_cpu;
 236
 237     task_t *migration_thread;
 238     struct list_head migration_queue;
 239 #endif
 240
 241 #ifdef CONFIG_SCHEDSTATS
 242 /* latency stats */
 243     struct sched_info rq_sched_info;
 244
 245 /* sys_sched_yield() stats */
 246     unsigned long yld_exp_empty;
 247     unsigned long yld_act_empty;
 248     unsigned long yld_both_empty;
 249     unsigned long yld_cnt;
 250
 251 /* schedule() stats */
 252     unsigned long sched_switch;
 253     unsigned long sched_cnt;
 254     unsigned long sched_goidle;
 255
 256 /* try_to_wake_up() stats */
 257     unsigned long ttwu_cnt;
 258     unsigned long ttwu_local;
 259 #endif
 260 }；

该结构中重点字段分析。
unsigned long nr_running：该CPU上当前就绪任务的数目，active和expired队列任务之和；
task_t * curr：该指针指向当前正在运行的进程；
prio_array_t *active：指向可运行队列中活动链表；
prio_array_t *expired：指向可运行队列中过期链表；
prio_array_t arrays[2]：为上面的两个指针开辟静态的空间；
---------------------------------------------------------------------------------------
二，优先级数组。

 183 #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
 184
 185 typedef struct runqueue runqueue_t;
 186
 187 struct prio_array {
 188     unsigned int nr_active;
 189     unsigned long bitmap[BITMAP_SIZE];
 190     struct list_head queue[MAX_PRIO];
 191 };
 192

该数组比较核心，MAX_PRIO的值为140，所以无论是active还是expired都是140个队列，一共
有280个队列。active表示活动进程，还有时间片。而expired表示过期进程，时间片已经运行完了
而CPU要找进程运行，会去active队列找，不会区expired队列中去找，而且找的过程的时间复杂度
是O(1),这也是为什么该调度的名字为O(1)调度。里面用了位图来描述每一个级别的队列，如果某一个
级别的队列有“队员”，也就是存在PCB，那么位图上会显示1，否则会显示0，在pick next的时候，会
从位图中计算出具有“队员”的最高优先级那一队，然后取其第一个“队员”作为调度对象。
示意图如下：

------------------------------------------------------------------------------------------
三，调度程序schedule是如何调度下一个程序的。

3049 array = rq->active;
3050 if (unlikely(!array->nr_active)) {
3051 /*
3052 * Switch the active and expired arrays.
3053 */
3054         schedstat_inc(rq, sched_switch);
3055         rq->active = rq->expired;
3056         rq->expired = array;
3057 array = rq->active;
3058         rq->expired_timestamp = 0;
3059         rq->best_expired_prio = MAX_PRIO;
3060 }
3061
3062     idx = sched_find_first_bit(array->bitmap);//获取active数组的下标索引。
3063     queue = array->queue + idx;//获取数组的表项。
3064 next = list_entry(queue->next, task_t, run_list);//获取该队列的第一个PCB

sehed_find_first_bit()用于在位图中快速查找第一个被设置的位。可以由上面给出的
图很轻松理解。

参考：
http://edsionte.com/techblog/archives/2851