本篇文章是进程管理与调度的第一篇文章，进程管理与调度内容较多，后面会陆续更新，今天主要是讲进程（对于内核来说，叫任务 task 更好一点，下文我都用任务来代替进程）调度时要做哪一些事情，也就是schedule函数。至于为什么要先讲这个函数，因为我上一周都在看这部分代码的源码。
Linux内核版本：4.10.0
硬件平台：Intel X86_64
考虑到文章篇幅，在这里我只讨论普通进程，其调度算法采用的是CFS（完全公平）调度算法。
至于CFS调度算法的实现后面后专门写一篇文章，这里只要记住调度时选择一个优先级最高的任务执行
对于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;
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 ：切换每个任务用户态的虚拟地址空间（每个任务的用户栈都是独立的，都在内存空间里面，切换任务的虚拟地址空间，也就切换了任务的用户栈）。
任务（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进程）。
目前的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任务的实例，在没有其它可运行任务的时候执行
......
}
二、schedule函数详解
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);
} 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);
} 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();
}
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)
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) 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#include #include #include #include #include #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 rescheduledn"); printk("n"); } 任务被抢占时通知机制操作 static void hello_sched_out(struct preempt_notifier *notifier, struct task_struct *next) { printk("task is just been preemptedn"); } //注册通知回调函数 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#include #include #include 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
