本篇文章是进程管理与调度的第一篇文章,进程管理与调度内容较多,后面会陆续更新,今天主要是讲进程(对于内核来说,叫任务 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