Linux内核简单分析（2）——进程调度与切换

https://blog.csdn.net/silence1772/article/details/89197654

进程的调度与切换是一个很复杂的话题，这里我更关心内核是如何实现的，而不是使用了什么策略，所以只讲进程的组织和切换方式，而对调度程序的实现和算法不作分析。
进程调度可参考：
Linux进程调度-------O(1)调度和CFS调度器
O(n)、O(1)和CFS调度器
进程调度综述

Linux内核在2.4版本以前的调度程序都十分简陋，但随着多核处理器和硬件的发展，对进程调度的要求也更高了，所以在2.5开发过程中开始采用一种叫O(1)调度器的调度程序，O(1)调度器得到了广泛使用，表现出近乎完美的性能和可扩展性，但是时间证明该调度器对于那些对响应时间比较敏感的程序不太友好，比如文本编辑器。在2.6内核的开发中开始引入一种公平调度的概念，并且最终在2.6.23内核版本中替代了O(1)调度算法，称为完全公平调度算法，简称CFS。

O(1)调度程序是将时间片分配给进程，而CFS是将处理器的使用比例划分给进程，这也是它们比较不同的一点。在实现上两者的数据结构也有很大不同，虽然O(1)调度器已经被CFS取代了，但是研究一下它们的结构对于我们程序开发来说还是有点用的。
O(1)调度器如何组织进程？

回顾一下进程的task_struct结构，在里面有一个struct list_head run_list;字段，内核通过这个run_list将处于TASK_RUNNING状态的进程连成一个链表。

list_head结构的定义如下：

struct list_head {
    struct list_head *next, *prev;
};

    1
    2
    3

那么现在我们从list_head出发，一步步往上探索。
首先处于活跃状态的进程通过其task_struct->run_list字段相连，如下图：
在这里插入图片描述
但是系统中这么多进程，简单地把它们都连在一起显然不是明智的选择，因为这样要查找进程的时间就无法保证了，而进程调度程序又要求快速完成，所以内核把这些进程按优先级分开了。

进程的优先权的取值范围为0到139，那么就可以分成140个运行队列链表，然后把进程按照优先权插入到对应的链表中，这样查找进程的效率可以有很大提高。

实现按优先权分开的是一个prio_array_t类型的数据结构，该结构的定义如下：

typedef struct prio_array prio_array_t;

struct prio_array {
    unsigned int nr_active;
    unsigned long bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];
};

    1
    2
    3
    4
    5
    6
    7

其中nr_active是链表中task_struct的数量，bitmap是一个位图，用来判断对应优先权的链表上是否为空，比如第0位为1，就说明优先权为0的链表上不为空。queue大小为140，存放各个优先权链表的表头。

在task_struct中有一个prio_array_t *array字段，指向的就是这个结构体，并且处于同一个prio_array结构体中的进程指向的array是一样的。
在这里插入图片描述

那么这个结构又是怎么给进程调度程序使用的呢？现在就轮到runqueue出场了，runqueue是一个pre_cpu变量的数据结构，即CPU的每个核有一个单独的runqueue，这样可以避免cpu之间产生竞争。
runqueue中的关键字段如下:

struct runqueue
{
    ......
    prio_array_t *active;
    prio_array_t *expired;
    prio_array_t[2] arrays;
    ...
}

    1
    2
    3
    4
    5
    6
    7
    8

runqueue中有两个队列，一个是活跃的进程active，一个是时间片耗尽的过期进程expired，它们指向arrays中相应的队列。如下图：
在这里插入图片描述
O(1)调度器在选择下一个调度进程时，不用遍历整个runqueue，而是直接从active数组中选择当前最高优先级队列中的第一个进程，时间复杂度为O(1)，这就是O(1)调度算法名称的由来。
CFS如何组织进程？

从2.6.23内核开始，调度器采用了模块化设计的思想，这种模块化结构被称为调度器类。每个进程只属于一个调度器类，在调度的时候会从这些调度器类中选择一个优先级最高的调度器类，再由这个调度器类去选择下一个要调度的进程。调度器类有针对实时进程的调度类，有针对普通进程的CFS调度类，实时进程调度类的优先级比CFS高，所以只要有实时进程，那么就总会调用它而不会使用CFS。

大体结构如下图，其中调度器模块通过调度器类选择出一个进程，投入cpu中运行。
在这里插入图片描述

回到如何组织进程这个话题来，上面O(1)调度的进程组织是由runqueue完成的，同样，CFS的进程组织也是一个runqueue，但是却有了许多不同。

首先，跟上文一样，一个cpu核有一个runqueue，该结构的定义如下：

struct rq {
    unsigned long nr_running;
    #define CPU_LOAD_IDX_MAX 5
    unsigned long cpu_load[CPU_LOAD_IDX_MAX];
    ...
    struct load_weight load;
    struct cfs_rq cfs;
    struct rt_rq rt;
    struct task_struct *curr, *idle;
    u64 clock;
    ...
};

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

但是该结构并不直接管理进程，而是内嵌了属于特定调度器类的子就绪队列，由该子就绪队列管理，比如其中的cfs_rq就是CFS调度器类使用的管理进程的就绪队列，rt_rq是实时进程调度器类使用的。我们关注的cfs_rq结构定义如下：

struct cfs_rq {
    struct load_weight load;
    unsigned long nr_running;
    u64 min_vruntime;
    struct rb_root tasks_timeline;
    struct rb_node *rb_leftmost;
    struct sched_entity *curr;
}

    1
    2
    3
    4
    5
    6
    7
    8

由该结构可以看到，CFS使用红黑树来组织进程，而不是O(1)调度所使用的链表。其中tasks_timeline指向红黑树的根，而rb_leftmost指向红黑树最左节点。

该红黑树以一个虚拟运行时间vruntime作为排序key，最左节点的vruntime最小，每次调度就是直接调度最左节点对应的那个进程。vruntime越小，表示对处理器需求越大。在进程被调度后，其vruntime会稳定地增加，那么他在红黑树中的位置也逐渐往右移。CFS的完成公平调度的关键在于：越重要的进程的vruntime增长的越慢，因而向右移动的速度也慢，这样被调度的机会要大于不重要的进程；其次是如果进程进入睡眠，其vruntime不会增加，但其他的仍在增长，所以当他醒来时在红黑树的位置会更加靠左。

那么现在已经知道CFS采用红黑树组织进程了，但是红黑树节点又如何与task_struct联系起来呢？

我们从进程的task_struct来看，在task_struct中有一个const struct sched_class *sched_class，这个sched_class指针就是指向进程所属的调度器类。sched_class的结构定义如下，里面都是一些函数指针，不同的调度器类就是通过调整函数指针的指向来实现的。

struct sched_class {
    const struct sched_class *next;
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
    void (*yield_task) (struct rq *rq);
    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);
    struct task_struct * (*pick_next_task) (struct rq *rq);
    void (*put_prev_task) (struct rq *rq, struct task_struct *p);
    void (*set_curr_task) (struct rq *rq);
    void (*task_tick) (struct rq *rq, struct task_struct *p);
    void (*task_new) (struct rq *rq, struct task_struct *p);
};

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

task_struct中还有另外一个字段struct sched_entity se，这是一个调度实体。因为调度器不限于调度进程，还可以处理更大的实体，所以抽象出一个可调用实体的结构，该结构定义如下：

struct sched_entity {
    struct load_weight load; /* 用于负载均衡 */
    struct rb_node run_node;
    unsigned int on_rq;
    u64 exec_start;
    u64 sum_exec_runtime;
    u64 vruntime;
    u64 prev_sum_exec_runtime;
...
}

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

其中第二个字段run_node是一个红黑树节点，这就是上面提到的CFS的红黑树里面的节点，注意这不是一个指针，而是内嵌在sched_enity结构里的。

从每个cpu上的runqueue -> cfs使用的rq -> 组织进程的红黑树 -> 红黑树节点 -> sched_entity 的结构大概如下图：
在这里插入图片描述
而从task_struct 到 红黑树节点的路径大概如下图：
在这里插入图片描述
如何切换进程？

当调度器选出下一个要运行的进程后，就要执行进程切换，切换到下一个进程运行。进程切换又称为上下文切换，上下文切换由context_switch()函数负责处理，主要包含两个步骤：
（1）切换页全局目录，即切换虚拟地址空间，由switch_mm()完成。
（2）切换内核堆栈和硬件上下文，即把上一个进程的堆栈和寄存器状态切换到新进程的状态，由switch_to()完成。
switch_mm()

switch_mm()完成的主要是虚拟地址空间的切换。之前说过了每个进程的task_struct里都有一个mm_struct，该结构就是管理虚拟地址空间的。那么究竟怎样才能切换呢？

首先虚拟内存机制主要靠页表实现，学过操作系统的应该知道页表是怎么回事，现在Linux一般使用多级页表，在cr3寄存器中保存了页全局目录（pgd）的地址，那么修改cr3寄存器的指向，就相当于修改页目录，也就是切换地址空间了。所以switch_mm()主要就是把新进程next->pgd加载到cr3寄存器中，实现地址空间的切换。

虽然切换地址空间后进程并没有马上完成切换，还是prev进程，但是并不会对prev造成影响，因为现在进程prev是处在内核态的，而内核空间的页表映射对于所有进程来说都是相同的。
switch_to()

switch_to()是一个宏，其内容是特定于体系结构的汇编代码，下面我们讨论的是基于X86体系的代码。switch_to()的参数为三个task_struct指针prev、next、last，前两个分别是当前执行进程、选出来的下一个执行进程，之所以有第三个参数是因为新进程需要知道是从哪个进程切换进来的，所以要设法保存上一个进程描述符的指针，具体的做法就不说了，避免纠结于这些细节。switch_to()执行的操作大致如下：
（1）将prev、next分别保存在eax、ebx寄存器。这样做主要是为了后面的传参。

（2）将eflags、ebp寄存器内容保存在prev内核栈中。切换进程时已经由用户态陷入内核态了，用户态的寄存器信息已经保存在内核栈中了，而这里保存的这两个应该是内核态的寄存器信息。

（3）将esp寄存器内容保存到prev->thread.esp中，然后把next->thread.esp写入esp寄存器中。因为esp寄存器是内核栈的栈顶指针，所以修改esp就相当于切换了内核栈，现在修改后esp就指向了next进程的内核栈了。而把旧进程prev的栈顶指针保存到task_struct中的thread字段中，thread是一个thread_struct结构类型的指针，该结构主要保存寄存器信息，其中就包括了esp。

（4）将后面某条指令的地址保存到prev->thread.eip中，然后把next->thread.eip压入next内核栈中。这个指令的地址将会是当前进程被切换出去，再被切换回来后指行的指令地址。同理，next->thread.eip也是next进程即将执行的指令地址，注意这里esp已经是next的栈指针了，所以压入的是next的内核栈。

（5）调用__switch_to()，完成进程切换。执行汇编指令jmp __switch_to，这条指令使代码执行跳转到__switch_to()处，__switch_to()的参数为prev和next，不过不同于函数调用，该宏将直接从eax、ebx寄存器去参数，这也是（1）的原因。__switch_to()完成的任务主要是修改TSS段。

TSS称为任务状态段（Task State Segment），原本是intel设计用来完成进程硬件上下文切换的，设计是每个进程都有一个TSS，其中保存进程的寄存器等状态信息。但Linux并不采用，而是只让每个CPU使用一个TSS，由tr寄存器指向，因为tr始终指向一个TSS，不用像intel设计的那样随进程的切换而不断切换，所以开销相对也小了。并且因为Linux另外使用了一个结构thread_struct保存寄存器信息（参见上文），所以对于TSS也只是使用其中很少的一部分内容。Linux系统主要是在两个方面用到了TSS：

    进程从用户态陷入到内核态时需要从TSS中取得内核栈的栈顶指针放到esp中。
    用户态读写IO需要访问TSS的权限位图。

所以，在切换进程时，需要更新TSS里的esp0和IO权位图，这就是__switch_to()完成的内容。（之所以是esp0是因为TSS里有为多种特权级别设计的esp0，esp1，esp2，而Linux只使用esp0）

具体的操作就是用next->thread.esp去更新TSS.esp0，在有必要的时候去修改io_bitmap。当然，__switch_to()做的工作远远不止这些，还有许多操作比如更新线程的局部存储段（thread local storage），关于段的内容以后有机会再来分析一下。

当__switch_to()执行结束，准备返回时，会从栈中弹出返回地址，装入eip程序计数器中。注意，这里的esp已经指向新进程next的内核栈了，所以弹出的地址就是刚才压入的next->thread.ei（见（4）），也就是说，现在执行的代码已经是新进程的了，进程切换完成了。

（6）从prev栈中恢复到ebp、eflags寄存器。虽然（5）已经完成了进程切换，但是switch_to()实际上并没有结束，而是当该进程重新被调度，切换回来时，继续执行剩下的代码，也就是恢复寄存器信息，而这里也就是之前（4）所提到的某条命令的地址。

单看文字描述很容易看晕，可以结合下图理解：

首先开始的时候esp执行进程A的内核堆栈。
在这里插入图片描述
当要开始切换进程时，先将eflags、ebp寄存器内容保存到A的内核栈中。
在这里插入图片描述
接着将进程B的task_struct->thread.esp的值放到esp寄存器中，内核栈切换完成。
在这里插入图片描述
这时执行的代码仍然是进程A的switch_to，它把进程B的eip（B的task_struct->thread.eip）压入B的内核栈中，然后就跳转到__switch_to执行。注：eip就是切换到进程B后执行的代码地址。
在这里插入图片描述
当__switch_to执行完返回时，会从栈中弹出返回地址填入eip寄存器，然后从该地址处开始执行。那么这里就完成了进程的切换。进入B进程后，他会继续之前switch_to后面的操作，即出栈恢复eflags、ebp寄存器，到这里就是真正完成了。
在这里插入图片描述

代码的执行流大概如下：
在这里插入图片描述