Linux 2.6 内核的调度程序分析

在Linux 的2.6的内核中，使用了一种O(1)的调度算法，使得Linux的调度程序能够在O(1)的时间复杂度内完成。

每个处理器都含有一个运行队列，运行队列中保存的是可运行的进程，处理器调度程序每次的调度都是从可运行队列当中取出一个当前优先级最高的进程(线程)来投入运行的。

运行队列的结构体如下：

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the thread migration code), lock
 * acquire operations must be ordered by ascending &runqueue.
 */
struct runqueue {
    spinlock_t lock;//自旋锁，用于锁定运行队列

    /*
     * nr_running and cpu_load should be in the same cacheline because
     * remote CPUs use both these fields when doing load calculation.
     */
    unsigned long nr_running;//可运行的的任务数目
#ifdef CONFIG_SMP
    unsigned long cpu_load[3];
#endif
    unsigned long long nr_switches；//上下文切换数目

    /*
     * This is part of a global counter where only the total sum
     * over all CPUs matters. A task can increase this counter on
     * one CPU and if it got migrated afterwards it may decrease
     * it on another CPU. Always updated under the runqueue lock:
     */
    unsigned long nr_uninterruptible;//处于不可中断或者睡眠状态的任务数目

    unsigned long expired_timestamp;//队列最后被换出的时间
    unsigned long long timestamp_last_tick;//最后一个调度程序的节拍
    task_t *curr, *idle;//当前运行的任务和空闲的任务
    struct mm_struct *prev_mm;//最后运行任务的mm_struct结构体。
    prio_array_t *active, *expired, arrays[2];//1.活动优先级队列2.超时优先级队列，3.实际优先级数组
    int best_expired_prio;//最适宜换出的优先级队列
    atomic_t nr_iowait;//等待I/O操作的任务数目

#ifdef CONFIG_SMP
    struct sched_domain *sd;//多处理器相关

    /* For active balancing */
    int active_balance;//活动的需要负载平衡进程个数
    int push_cpu;//哪个CPU需要进行负载平衡？

    task_t *migration_thread;//换出任务
    struct list_head migration_queue;//换出队列
#endif

#ifdef CONFIG_SCHEDSTATS
    /* latency stats */
    struct sched_info rq_sched_info;

    /* sys_sched_yield() stats */
    unsigned long yld_exp_empty;
    unsigned long yld_act_empty;
    unsigned long yld_both_empty;
    unsigned long yld_cnt;

    /* schedule() stats */
    unsigned long sched_switch;
    unsigned long sched_cnt;
    unsigned long sched_goidle;

    /* try_to_wake_up() stats */
    unsigned long ttwu_cnt;
    unsigned long ttwu_local;
#endif
};

每个运行队列里面会有个优先级数组，优先级数组里面优先级高的进程能够得到优先执行。

 prio_array_t *active, *expired, arrays[2];//1.活动优先级队列2.超时优先级队列，3.实际优先级数组

这地方我们可以看到实际的优先级数组是arrays[2]，也就是表明有两个：一个是活跃的，一个是过期的。

struct prio_array {
    unsigned int nr_active;//可执行的进程个数
    unsigned long bitmap[BITMAP_SIZE];//为每个优先级定义个一个位图
    struct list_head queue[MAX_PRIO];//每个位图都对应一个优先级，该优先级对应一个进程链表（struct list_head类型），表明处于该优先级的所有进程链表
};

其中：MAX_PRIO定义了最大优先级的格式，默认是140，所以BITMAP_SIZE最低为140，我们每个long int型是32位，所以需要5个long int型才能表达所有的优先级（5*32 = 160）。