Linux 进程调度schdule过程详解

本文阅读 15 分钟
首页 Linux,系统 正文

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

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

img

(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;
}

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

这篇文章主要讲了任务调度时所做的一些事情,总结来说就是: (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

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://blog.csdn.net/weixin_45030965/article/details/123855487
-- 展开阅读全文 --
BUUCTF Web [极客大挑战 2019]Knife
« 上一篇 06-24
安全面试之XSS(跨站脚本攻击)
下一篇 » 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复