linux当中的进程调度

在linux当中，调度器面临的问题是：在程序之间共享CPU，创造并行执行的错觉。这个任务可以分为两个不同的部分：调度策略和上下文切换。

调度器使用一系列的数据结构来管理系统中的进程，这些组件之间的交互关系大致如下图所示：



实际进程的调度可以发生在两种情况下：1). 进程调用休眠类函数或者主动放弃CPU；2). 通过周期机制，以防单个进程一直占用CPU。

调度器类：用于判断接下来运行哪个进程。内核支持不同的调度策略，调度类是这些策略的具体实现，各个策略之间互不影响，按照优先级排好在一个链表中，当调度发生的时候，就会遍历这个链表，从第一个非空的调度类中拿出下一个要运行的进程，如果结果为空，下一个调度类。

选中进程之后就要做进程的上下文切换了，task_struct中调度相关的成员如下：

struct task_struct{
    ...
    const struct sched_class *sched_class;// 进程所属的调度类
    struct sched_entity      se;// 调度器的能力不限于进程，也可以通过cgroup等调度容器这种东西，所以单个进程里面嵌入了一个调度实体
    ...
};

其中调度类的模板如下：

struct sched_class {
    const struct sched_class *next;
...
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*yield_task) (struct rq *rq);
    bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);
    void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
    struct task_struct *(*pick_next_task)(struct rq *rq);
    void (*put_prev_task)(struct rq *rq, struct task_struct *p);
    void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
...
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*task_fork)(struct task_struct *p);
    void (*task_dead)(struct task_struct *p);
...
};

另外，在每个CPU上，还会存储一个就绪队列，供各个调度器类进行选择新进程，其结构如下：

struct rq {
..
    unsigned int        nr_running;
...
    struct cfs_rq        cfs;
    struct rt_rq        rt;
    struct dl_rq        dl;
...
    unsigned long        nr_uninterruptible;

    struct task_struct __rcu    *curr;
    struct task_struct    *idle;
    struct task_struct    *stop;
    unsigned long        next_balance;
    struct mm_struct    *prev_mm;
...
};

可以看见，在就绪队列中，对应不同的调度器类，会有不同的子就绪队列，实际上，调度器类就是操纵这些子队列来完成调度的。

由于调度器可以操作比进程更一般的实体（cgroup），就需要一个适当的数据结构来描述：

struct sched_entity {
    /* For load-balancing: */
    struct load_weight        load;
    unsigned long            runnable_weight;
    struct rb_node            run_node;// 挂载的红黑树节点
    struct list_head        group_node;
    unsigned int            on_rq;// 是否在就绪队列上接受调度
    u64                exec_start;
    u64                sum_exec_runtime;
    u64                vruntime;
    u64                prev_sum_exec_runtime;
    u64                nr_migrations;
    struct sched_statistics        statistics;
...
};

有了调度实体之后，调度器就会在自己被调用的时候，先选定进程，然后执行上下文切换了。
进程的上下文切换会涉及到用户态和内核态，由于切换是在内核态发生的，用户态的切换，只需要切换调对应的内存映射即可。但是，由于用户空间进程的寄存器内容在进入内核态的时候是保存在内核栈上的，在返回用户空间时，会使用内核栈上保存的值自动恢复寄存器的数据。
在切换内核栈的时候，内核用了一个switch_to的宏进行的实现，它由具体的体系结构来实现，而且遵循了一个调用约定，即三个参数传递两个变量，其调用形式是prev=switch_to(prev, next); 其中返回的prev并不是用作参数的prev(参数的prev可以理解成cur)，而是上一个调用switch_to这个宏的进程，当switch_to执行完毕后，就处在调用参数next的进程当中了，这时的prev就是通过switch_to切换到next进程的进程，这样，内核就可以知道当前进程之前运行的进程是哪一个了