Linux 进程调度schdule过程详解

本篇文章是进程管理与调度的第一篇文章，进程管理与调度内容较多，后面会陆续更新，今天主要是讲进程（对于内核来说，叫任务 task 更好一点，下文我都用任务来代替进程）调度时要做哪一些事情，也就是schedule函数。至于为什么要先讲这个函数，因为我上一周都在看这部分代码的源码。

Linux内核版本：4.10.0 硬件平台：Intel X86_64

考虑到文章篇幅，在这里我只讨论普通进程，其调度算法采用的是CFS（完全公平）调度算法。 至于CFS调度算法的实现后面后专门写一篇文章，这里只要记住调度时选择一个优先级最高的任务执行

1.1 task_struct 结构体简介

对于Linux内核来说，调度的基本单位是任务，用 struct task_struct 表示，定义在include/linux/sched.h文件中，这个结构体包含一个任务的所有信息，结构体成员很多，在这里我只列出与本章内容有关的成员：

struct task_struct { 
    ......
    (1)
    volatile long state;
    
    (2)
    const struct sched_class *sched_class;
    
    (3)
    void *stack;
    struct thread_struct thread;
    struct mm_struct *mm, *active_mm;
    ......
}

（1）state ：表示任务当前的状态，当state为TASK_RUNNING时，表示任务处于可运行的状态，并不一定表示目前正在占有CPU，也许在等待调度，调度器只会选择在该状态下的任务进行调度。该状态确保任务可以立即运行，而不需要等待外部事件。 简单来说就是：任务调度的对象是处于TASK_RUNNING状态的任务。 处于TASK_RUNNING状态的任务，可能正在执行用户态代码，也可能正在执行内核态的代码。

（2）sched_class ：表示任务所属的调度器类，我们这里只讲CFS调度类。

// kernel/sched/sched.h

struct sched_class { 
    ......
    //将任务加入可运行的队列中
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    //将任务移除可运行的队列中
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
    //选择一下将要运行的任务
    struct task_struct * (*pick_next_task) (struct rq *rq,
                        struct task_struct *prev,
                        struct pin_cookie cookie);
    ......
}

extern const struct sched_class fair_sched_class;

// kernel/sched/fair.c
const struct sched_class fair_sched_class;

/* * All the scheduling class methods: */
const struct sched_class fair_sched_class = { 
    ......
    .enqueue_task        = enqueue_task_fair,    //CFS 的 enqueue_task 实例
    .dequeue_task        = dequeue_task_fair,    //CFS 的 dequeue_task 实例
    .pick_next_task        = pick_next_task_fair,    //CFS 的 pick_next_task 实例
    ......
}

（3）任务上下文：表示任务调度时要切换的任务上下文（任务切换只发生在内核态）。 stack：当前任务的内核态堆栈（用户态的sp，用户态的ip，在内核栈顶部的 pt_regs 结构里面） thread ：也叫任务的硬件上下文，主要包含了大部分CPU寄存器（如：内核栈sp）。 struct mm_struct *mm ：切换每个任务用户态的虚拟地址空间（每个任务的用户栈都是独立的，都在内存空间里面，切换任务的虚拟地址空间，也就切换了任务的用户栈）。

1.2 task_struct 结构体的产生

任务（task_struct) 的来源有三处： （1） fork()：该函数是一个系统调用，可以复制一个现有的进程来创建一个全新的进程，产生一个 task_struct，然后调用wake_up_new_task()唤醒新的进程，使其进入TASK_RUNNING状态。 （2） pthread_create()：该函数是Glibc中的函数，然后调用clone()系统调用创建一个线程（又叫轻量级进程），产生一个 task_struct，然后调用wake_up_new_task()唤醒新的线程，使其进入TASK_RUNNING状态。 （3）kthread_create()：创建一个新的内核线程，产生一个 task_struct，然后wake_up_new_task()，唤醒新的内核线程，使其进入TASK_RUNNING状态。

其实这三个API最后都会调用 _do_fork()，不同之处是传入给 _do_fork() 的参数不同（clone_flags），最终结果就是进程有独立的地址空间和栈，而用户线程可以自己指定用户栈，地址空间和父进程共享，内核线程则只有和内核共享的同一个栈，同一个地址空间。因此上述三个API最终都会创建一个task_struct结构。

备注：这里没有讨论vfok()。

总结：上述三个方式都产生了一个任务 task_struct，然后唤醒该任务使其处于TASK_RUNNING状态，然后这样调度器就可以调度 任务（task_struct)了。

关于上述三者的区别也就是进程，线程（轻量级进程），内核线程的区别我会在下一篇文章中进行解释，这一部分内容很多，在这里解释就占用了太多篇幅。

还有一个来源就是0号进程（又叫 idle 进程），每个逻辑处理器上都有一个，属于内核态线程，只有在没有其他的任务处于TASK_RUNNING状态时（系统此时处于空闲状态），任务调度器才会选择0号进程，然后重复执行 HLT 指令。 HLT 指令 ：停止指令执行，并将处理器置于HALT状态。简单来说让该CPU进入休眠状态，低功耗状态。 （该指令只能在 privilege level 0执行，且CPU指的是逻辑CPU而不是物理CPU，每个逻辑CPU都有一个idle进程）。

1.3 struct rq 结构体

目前的x86_64都有多个处理器，那么对于所有处于TASK_RUNNING状态的任务是应该位于一个队列还有每个处理器都有自己的队列？ Linux采用的是每个CPU都有自己的运行队列，这样做的好处： （1）每个CPU在自己的运行队列上选择任务降低了竞争 （2）某个任务位于一个CPU的运行队列上，经过多次调度后，内核趋于选择相同的CPU执行该任务，那么上次任务运行的变量很可能仍然在这个CPU缓存上，提高运行效率。

在这里我只讨论普通任务的调度，因为linux大部分情况下都是在运行普通任务，普通任务选择的调度器是CFS完全调度。

在调度时，调度器去 CFS 运行队列找是否有任务需要运行。

struct rq { 
    .......
    unsigned int nr_running;   //运行队列上可运行任务的个数
    struct cfs_rq cfs;         // CFS 运行队列
    struct task_struct *curr,  //当前正在运行任务的 task_struct 实例
    struct task_struct *idle,  //指向idle任务的实例，在没有其它可运行任务的时候执行
    ......
}

2.1 schedule函数简介

上文说到任务调度器是对于可运行状态（TASK_RUNNING）的任务进行调度，如果任务的状态不是TASK_RUNNING，那么该任务是不会被调度的。

调度的入口点是schedule()函数，定义在 kernel/sched/core.c 文件中： 删掉了很多代码，只留了重要的代码：

asmlinkage __visible void __sched schedule(void)
{ 
    ......
    preempt_disable();        //禁止内核抢占
    __schedule(false);        //任务开始调度，调度的过程中禁止其它任务抢占
    sched_preempt_enable_no_resched();        //开启内核抢占
    ......
}

2.2 __schedule 代码解图

//__schedule() is the main scheduler function.
static void __sched notrace __schedule(bool preempt)
{ 
    (1)
    struct task_struct *prev, *next;
    unsigned long *switch_count;
    struct pin_cookie cookie;
    struct rq *rq;
    int cpu;

    (2)
    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    prev = rq->curr;
    
    (3)
    deactivate_task(rq, prev, DEQUEUE_SLEEP);
    prev->on_rq = 0;

    (4)
    next = pick_next_task(rq, prev, cookie);
    clear_tsk_need_resched(prev);

    (5)
    if (likely(prev != next)) { 
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;

        rq = context_switch(rq, prev, next, cookie); /* unlocks the rq */
    } else { 
        lockdep_unpin_lock(&rq->lock, cookie);
        raw_spin_unlock_irq(&rq->lock);
    }
}

（1）prev局部变量表示要切换出去的任务，next局部变量表示要切换进来的任务。

struct task_struct *prev, *next;

（2）找到当前CPU的运行队列 struct rq，把当前正在运行的任务curr 赋值给 prev。

int cpu = smp_processor_id();
    struct rq = cpu_rq(cpu);
    struct task_struct *prev = rq->curr;

（3） 将当前运行的任务prev(即curr)从运行队列struct rq 移除出去，并表示不在运行队列中。

deactivate_task(rq, prev, DEQUEUE_SLEEP);
        -->dequeue_task(rq, p, flags);
            -->p->sched_class->dequeue_task(rq, p, flags);
    prev->on_rq = 0;

（4）选择下一个将要执行的任务，通过CFS调度算法选择优先级最高的一个任务。 并且将被抢占的任务prev需要被调度的标识为给清除掉。

next = pick_next_task(rq, prev, cookie);
        --> next = fair_sched_class.pick_next_task(rq, prev, cookie);
    
    clear_tsk_need_resched(prev);

（5）如果选择的任务next和 原任务prev不是同一个任务，则进行任务上下文切换 如果是同一个任务，则不进行上下文切换。 注意这里是 用 likely()修饰（这是gcc内建的一条指令用于优化，编译器可以根据这条指令对分支选择进行优化），表示有很大的概率 选择的任务next 和 原任务prev不是同一个任务。 由我们程序员来指明指令最可能的分支走向，以达到优化性能的效果。

if (likely(prev != next)) { 
            //大概率事件，进行任务切换
            rq->nr_switches++;  //可运行队列切换次数更新
            rq->curr = next;    //将当前任务curr设置为将要运行的下一个任务 next 
            ++*switch_count;    //任务切换次数更新
            
            //任务上下文切换
            rq = context_switch(rq, prev, next, cookie); /* unlocks the rq */
        } else { 
             //小概率事件，不进行任务切换
            lockdep_unpin_lock(&rq->lock, cookie);
            raw_spin_unlock_irq(&rq->lock);
        }

2.3 context_switch 代码解读

任务切换主要是任务空间即虚拟内存（用户态的虚拟地址空间，包括了用户态的堆栈）、CPU寄存器、内核态堆栈。

后面context_switch 还会专门一篇进行描述，这里限于篇幅，只是简单描述一下。

用伪代码表示：

switch_mm();
    switch_to(){ 
        switch_register();
        switch_stack();
    }

/* * context_switch - switch to the new MM and the new thread's register state. */
static __always_inline struct rq * 
context_switch(struct rq *rq, struct task_struct *prev,
           struct task_struct *next, struct pin_cookie cookie)
{ 
    struct mm_struct *mm, *oldmm;
    (1)
    prepare_task_switch(rq, prev, next);

    (2)
    mm = next->mm;
    oldmm = prev->active_mm;

    if (!mm) { 
        next->active_mm = oldmm;
        atomic_inc(&oldmm->mm_count);
        enter_lazy_tlb(oldmm, next);
    } else
        switch_mm_irqs_off(oldmm, mm, next);

    (3)
    /* Here we just switch the register state and the stack. */
    switch_to(prev, next, prev);

    (4)
    return finish_task_switch(prev);
}

（1）开始任务切换前,需要做的准备工作，这里主要是提供了2个接口给我们内核开发者，当任务切换时我们可以自己添加一些操作进去，任务被重新调度时我们也可以自己添加一些操作进去。 同时通知我们任务被抢占（sched_out）。

prepare_task_switch(rq, prev, next);
        -->fire_sched_out_preempt_notifiers(prev, next);
           -->__fire_sched_out_preempt_notifiers(curr, next);
              -->hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
                                    notifier->ops->sched_out(notifier, next);

这里的 sched_in()函数和 sched_out函数是内核提供给我们开发者的接口。我们可以通过在这两个接口里面添加一些操作。 sched_in ：任务重新调度时会通知我们。 sched_out：任务被抢占时会通知我们。 我们可以在这两个函数里面添加简单的打印消息，这样我们就可以实时的知道任务重新调度或者被抢占了，当然你也可以添加其它的一些操作，在第三节我们会给出一个实例。

struct preempt_ops { 
    void (*sched_in)(struct preempt_notifier *notifier, int cpu);
    void (*sched_out)(struct preempt_notifier *notifier,
              struct task_struct *next);
};

struct preempt_notifier { 
    struct hlist_node link;
    struct preempt_ops *ops;
};

(2) 切换任务的用户虚拟态地址（不切换内核态的虚拟地址），也包括了用户态的栈，主要就是切换了任务的CR3， CR3寄存器放的是 页目录表物理内存基地址。

mm = next->mm;
    oldmm = prev->active_mm;

    if (!mm) {    
        // mm == NULL,代表任务是内核线程
        // 直接用 被切换进程prev的active_mm
        next->active_mm = oldmm;
        atomic_inc(&oldmm->mm_count);
        //通知处理器不需要切换虚拟地址空间的用户空间部分，用来加速上下文切换
        enter_lazy_tlb(oldmm, next);
    } else
        //不是内核线程，那么就要切换用户态的虚拟地址空间，也就是切换任务的CR3
        switch_mm_irqs_off(oldmm, mm, next);
            -->load_cr3(next->pgd); //加载下一个任务的CR3

（3）切换任务的寄存器和内核态堆栈，保存原任务（prev）的所有寄存器信息，恢复新任务（next）的所有寄存器信息，当切换完之后，并执行新的任务。

switch_to(prev, next, prev);
        -->__switch_to_asm((prev), (next)))
                -->ENTRY(__switch_to_asm)
                    /* switch stack */
                    movq    %rsp, TASK_threadsp(%rdi)
                    movq    TASK_threadsp(%rsi), %rsp
                    
                    jmp    __switch_to
                    END(__switch_to_asm)
                        -->__switch_to()

(4) 完成一些清理工作，使其能够正确的释放锁。这个清理工作的完成是第三个任务，系统中随机的某个其它任务。同时通知我们任务被重新调度（sched_in）。 这里其实也有点复杂，我们后面在 context_switch 篇重点描述。

finish_task_switch(prev)
        -->fire_sched_in_preempt_notifiers(current);
            -->__fire_sched_in_preempt_notifiers(curr)
                -->hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
                                notifier->ops->sched_in(notifier, raw_smp_processor_id());

创建一个字符设备驱动，名字为my_dev，设备节点的创建将由设备文件系统负责，不需要我么来手动创建，并注册调度抢占通知机制，当被抢占和调度时打印简单的信息。

//schdule.c

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/fs.h>
#include <linux/preempt.h>
#include <linux/device.h>
#include <linux/cdev.h>

#define DEVICE_NAME "mydev"
#define CLASS_NAME "hello_class"

static struct class *helloClass;
static struct cdev my_dev;
struct preempt_notifier hello_preempt;
dev_t dev;

//任务被重新调度时通知机制操作
static void hello_sched_in(struct preempt_notifier *notifier, int cpu)
{ 
    printk("task is about to be rescheduled\n");
    printk("\n");
}

任务被抢占时通知机制操作
static void hello_sched_out(struct preempt_notifier *notifier,
    struct task_struct *next)
{ 
    printk("task is just been preempted\n");
}

//注册通知回调函数
struct preempt_ops hello_preempt_ops = { 
    .sched_in = hello_sched_in,
    .sched_out = hello_sched_out,
};

static int my_dev_open(struct inode *inode, struct file *file){ 

    preempt_notifier_init(&hello_preempt, &hello_preempt_ops);
    preempt_notifier_inc();

    preempt_notifier_register(&hello_preempt);

    printk("open!\n");

    return 0;
}

static int my_dev_close(struct inode *inode, struct file *file){ 

    preempt_notifier_unregister(&hello_preempt);

    preempt_notifier_dec();


    printk("close!\n");

    return 0;
}

static const struct file_operations my_dev_fops = { 
    .owner              = THIS_MODULE,
    .open               = my_dev_open,
    .release            = my_dev_close,
};

static int __init hello_init(void)
{ 
    int ret;
    dev_t dev_no;
    int Major;
    struct device *helloDevice;

    //动态地分配设备标识
    ret = alloc_chrdev_region(&dev_no, 0, 1, DEVICE_NAME);

    Major = MAJOR(dev_no);
    dev = MKDEV(Major, 0);

    //初始化字符设备
    cdev_init(&my_dev, &my_dev_fops);
    //将字符设备注册到内核
    ret = cdev_add(&my_dev, dev, 1);

    //创建类别class
    helloClass = class_create(THIS_MODULE, CLASS_NAME);
    if(IS_ERR(helloClass)){ 
        unregister_chrdev_region(dev, 1);
        cdev_del(&my_dev);
        return -1;
    }

    //创建设备节点
    helloDevice = device_create(helloClass, NULL, dev, NULL, DEVICE_NAME);
    if(IS_ERR(helloDevice)){ 
        class_destroy(helloClass);
        unregister_chrdev_region(dev, 1);
        cdev_del(&my_dev);

        return -1;
    }

    return 0;

}

static void __exit hello_exit(void)
{ 
    device_destroy(helloClass, dev);
    class_destroy(helloClass);
    cdev_del(&my_dev);
    unregister_chrdev_region(dev, 1);
}

module_init(hello_init);
module_exit(hello_exit);

MODULE_LICENSE("GPL");

//Makefile 文件

obj-m := schdule.o

all:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

//用户层测试文件 test.c

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/ioctl.h>

int main()
{ 
    //打开字符设备驱动程序
    int fd = open("/dev/mydev", O_RDWR);
    if(fd < 0) { 
        perror("open");        
    }

    //调用三次sleep,主动进行调度，让出CPU
    for(int i = 0; i<3; i++) { 
        sleep(1);
    }

    printf("success!!\n");

    close(fd);
    return 0;
}

让我们来看看最后的结果把： 从结果中可以看到该任务被抢占和重新调度各有三次。

这篇文章主要讲了任务调度时所做的一些事情，总结来说就是： （1）通过调度算法选择一个优先级最高的任务。 （2）进行任务上下文切换，切换用户态的虚拟地址空间。 保存原任务的所有寄存器信息，恢复新任务的所有寄存器信息，并执行新的任务。 （3）上下文切换完后，新的任务投入运行

Linux内核源码 4.10.0 深入理解Linux内核 深入Linux内核架构 Linux内核设计与实现 Linux环境编程：从应用到内核 嵌入式Linux设备驱动程序开发指南 Linux内核分析及应用 极客时间：趣谈Linux操作系统 https://kernel.blog.csdn.net/article/details/51872594 https://blog.csdn.net/bin_linux96/article/details/105341245