低并发编程

战略上藐视技术，战术上重视技术

进程调度想必大家都有所了解，又都不太了解。

有所了解是因为这个概念被提到太多次，不太了解是因为总觉得不直观，浮于概念层。

今天我们从三个视角来看看进程调度究竟是怎么回事，启车了请扶好。

小贴士：本文讲述的是 linux-0.11 版本的进程调度机制，学习其骨干和框架，不要钻入细节。

1

滴答视角

滴答

#define HZ 100

时钟中断

set_intr_gate(0x20, &timer_interrupt);

_timer_interrupt:
    ...
    // 增加系统滴答数
    incl _jiffies
    ...
    // 调用函数 do_timer
    call _do_timer
    ...

void do_timer(long cpl) {
    ...
    // 当前线程还有剩余时间片，直接返回
    if ((--current->counter)>0) return;
    // 若没有剩余时间片，调度
    schedule();
}

进程的调度

void schedule(void) {
    int i, next, c;
    struct task_struct ** p;
    ...
    while (1) {
        c = -1;
        next = 0;
        i = NR_TASKS;
        p = &task[NR_TASKS];
        while (--i) {
            if (!*--p)
                continue;
            if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
                c = (*p)->counter, next = i;
        }
        if (c) break;
        for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
            if (*p)
                (*p)->counter = ((*p)->counter >> 1) +
                        (*p)->priority;
    }
    switch_to(next);
}
别看一大坨，我做个不严谨的简化，你就懂了。
void schedule(void) {
    int next = get_max_counter_from_runnable();
    refresh_all_thread_counter();
    switch_to(next);
}

1. 拿到剩余时间片（counter的值）最大且在 runnable 状态（state = 0）的进程号 next。

2. 如果所有 runnable 进程时间片都为 0，则将所有进程（注意不仅仅是 runnable 的进程）的 counter 重新赋值（counter = counter/2 + priority），然后再次执行步骤 1。

3. 最后拿到了一个进程号 next，调用了 switch_to(next) 这个方法，就切换到了这个进程去执行了。

切换进程

#define switch_to(n) {\
struct {long a,b;} __tmp; \
__asm__("cmpl %%ecx,_current\n\t" \
    "je 1f\n\t" \
    "movw %%dx,%1\n\t" \
    "xchgl %%ecx,_current\n\t" \
    "ljmp %0\n\t" \
    "cmpl %%ecx,_last_task_used_math\n\t" \
    "jne 1f\n\t" \
    "clts\n" \
    "1:" \
    ::"m" (*&__tmp.a),"m" (*&__tmp.b), \
    "d" (_TSS(n)),"c" ((long) task[n])); \
}

1. 通过 ljmp 跳转指令跳转到新进程的偏移地址处。

2. 将当前各个寄存器的值保存在当前进程的 TSS 中，并将新进程的 TSS 信息加载到各个寄存器。（这部分是执行 ljmp 指令的副作用，并且是由硬件实现的）

上图来源于《Linux内核完全注释V5.0》

数据结构视角

struct task_struct * task[64] = {};

struct task_struct {
    long state; 
    long counter;
    long priority;
    struct tss_struct tss;
};

#define TASK_RUNNING  0
#define TASK_INTERRUPTIBLE  1
#define TASK_UNINTERRUPTIBLE  2
#define TASK_ZOMBIE  3
#define TASK_STOPPED  4

struct tss_struct {
    ...
    long    eip;
    long    eflags;
    long    eax,ecx,edx,ebx;
    long    esp;
    long    ebp;
    ...
};

操作系统启动流程视角

void main(void) {
    ...
    // 第一步：进程调度初始化
    sched_init();
    ...
    // 第二步：创建一个新进程并做些事
    if (!fork()) {
        init();
    }
    // 第三步：死循环，操作系统正式启动完毕
    for(;;) pause();
}

void sched_init(void) {
    // 初始化第一个进程的 tss
    set_tss_desc(...);
    // 将进程数组清零
    for(i=1;i<64;i++) {
        task[i] = NULL;
        ...
    }
    // 设置始终中断(滴答)
    set_intr_gate(0x20,&timer_interrupt);
    ...
}

后记

以上，分别从滴答视角、数据结构视角、操作系统启动流程视角，来讲解来进程调度的细节。

所谓滴答视角，可以理解为常说的进程调度视角。所谓数据结构视角，可以理解为常说的进程管理视角。

但我更喜欢我起的这两个名字，尤其是滴答视角，好可爱有木有！

不过本文是以 linux 最早的版本 linux-0.11 为例，在后来的操作系统演进过程中，进程调度的细节也在不断添枝加叶，比如选出下一个要调度的进程不再是简单地比较时间片大小，比如进程实际发生切换的时机改到了系统调用返回前，再比如对页表切换的变化等等。

但整个骨架和流程都是一样的，也即你再去研究更为复杂的现代操作系统进程调度原理时，只要按照这三个视角去分析，总是可以把握主干。