linux kernel基础系列之（一）调度原理

1. 数据结构：

• 优先级队列

struct prio_array {

    unsigned int nr_active;    表示等待执行的进程总数

    unsigned long bitmap[BITMAP_SIZE];    一个unsigned long在内核中只有32位哈，大家要跟64位OS上的C程序中的long区分开，那个是64位的。那么这个bitmap是干什么的呢？它是用位的方式，表示某个优先级上有没有待处理的队列，是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级，我只需要四位就能表示某个优先级上有没有进程要运行，例如优先级是2和3上有进程，那么就应该是0110.......非常省空间，效率也快，不是吗？

    struct list_head queue[MAX_PRIO];     与上面的bitmap是对应的，它存储所有等待运行的进程。

};

• 运行队列

struct runqueue {

    spinlock_t lock;   这是个自旋锁，nginx里解决惊群现象时也是用这个。与普通锁的区别就是，使用普通锁时，你去试图拿一把锁，结果发现已经被别人拿走了，你就在那睡觉，等别人锁用完了叫你起来。所以如果有一个人拿住锁了，一百个人都在门前睡觉等。当之前的人用完锁回来后，会叫醒所有100个等锁的人，然后这些人开始互相抢，抢到的人拿锁进去，其他的人继续等。自旋锁不同，当他去拿锁发现锁被别人拿走了，他在那不睡觉的等，稍打个盹就看看自己主动看看锁有没有还回来。大家比较出优劣了吗？

    unsigned long nr_running;

#ifdef CONFIG_SMP

    unsigned long cpu_load;

#endif

    unsigned long long nr_switches;

    unsigned long nr_uninterruptible;

    unsigned long expired_timestamp;

    unsigned long long timestamp_last_tick;

    task_t *curr, *idle;

    struct mm_struct *prev_mm;

    prio_array_t *active, *expired, arrays[2];上面说了半天的优先级队列在这里，但是在runqueue里，为什么不只一个呢？这个在下面讲。

    int best_expired_prio;

    atomic_t nr_iowait;

    ... ...

};

Reference:

1. linux内核调度算法（1）--快速找到最高优先级进程
2. Linux 2.6 调度系统分析
3. https://elixir.bootlin.com/linux/v2.6.11/source/include/linux/sched.h
4. https://elixir.bootlin.com/linux/v2.6.11/source/kernel/sched.c