极简cfs公平调度算法

这篇具有很好参考价值的文章主要介绍了极简cfs公平调度算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 说明
1> linux内核关于task调度这块是比较复杂的,流程也比较长,要从源码一一讲清楚很容易看晕
2> 本篇文章主要是讲清楚cfs公平调度算法如何将task在时钟中断驱动下切换调度,所以与此无关的代码一律略过
3> 本篇只讲最简单的task调度,略过组调度,组调度在下一篇《极简组调度-CGroup如何限制cpu》中讲解
4> 本篇源码来自CentOS7.6的3.10.0-957.el7内核
 
2. 极简task调度核心思想
1> linux采用cfs公平调度算法,其用vruntime记录task运行的cpu时长,每次用重新调度时,总是选择vruntime最小的task进行调度
2> 所有Ready状态的task会分配到不同cpu的rq队列上,等待调度运行
3> 时钟中断中,++当前task运行时间vruntime,并检测当前task运行时间是否超过一个时间片,或者其vruntime比当前cpu rq队列中最小的vruntime task大一个时间片,则设置resched标记(但并不立马进行task切换,因为此时仍在中断上下文中)
4> 所有中断返回后(当然也包括时钟中断),都会jump到ret_from_intr,这里会检查resched标记,如果置位,则调用schedule()选择vruntime最小的task进行调度
极简cfs公平调度算法
 
3. 极简task调度相关数据结构

3.1 名词解释

 
全称
说明
se schedule entity 调度实例,可以是一个task,也可以是一个group(当使用组调度时),linux支持组调度后,将调度实例从原来的task,抽象为se
rq run queue cpu的运行队列,每个cpu一个,处于Ready状态的se挂在对应的cpu运行队列上后,才会被选择投入运行 
cfs_rq cfs rq 公平调度运行队列,因为一般进程都是用cfs调度算法,一般进程的se都是挂在rq.cfs_rq上的
vruntime virtual runtime se的一个重要成员,记录调度实例的cpu运行时长,schedule时,cfs调度每次都选取vruntime最小的se投入运行,这就是cfs调度算法的核心原理

 
 
3.2 数据结构
struct sched_entity
{
    unsigned int    on_rq;                           // se是否在rq上,不在的话即使task是Ready状态也不会投入运行的
    u64             vruntime;                        // cpu运行时长,cfs调度算法总是选择该值最小的se投入运行
};
 
struct task
{
    struct sched_entity se;                        // 调度实例
};
 
struct rq
{
    struct cfs_rq cfs;                          // 所有要调度的se都挂在cfs rq中
    struct task_struct* curr;                   // 当前cpu上运行的task
};
 
struct cfs_rq
{
    struct rb_root tasks_timeline;              // 以vruntime为key,se为value的红黑树根节点,schedule时,cfs调度算法每次从这里挑选vruntime最小的se投入运行
    struct rb_node* rb_leftmost;                // tasks_timeline红黑树最左的叶子节点,即vruntime最小的se,直接取这个节点以加快速度
    sched_entity* curr;                         // cfs_rq中当前正在运行的se
    struct rq* rq;                              /* cpu runqueue to which this  cfs_rq is attached */
    unsigned int nr_running;                    // cfs_rq队列上有多少个se
};

 

3.3 数据结构关系
极简cfs公平调度算法
 
2.3 极简task调度code
2.3.1 时钟中断
1> task调度的发动机时钟中断触发后,会在smp_apic_timer_interrupt()中处理,经过层层调用,最终会到entity_tick()
entity_tick()
{
    update_curr();
    // 如果当前cfs_rq上的se大于1,则检查是否要重新调度
    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);
}

2> update_curr()主要是++当前task se的vruntime(当然这里还对组调度进行了处理,这里不讲组调度,先略过)

void update_curr(struct cfs_rq* cfs_rq)
{
    struct sched_entity* curr = cfs_rq->curr;
    curr->vruntime += delta_exec;                   // 增加se的运行时间
}

 3> check_preempt_tick()判定当前运行的时间大于sched_slice时,即超过了时间片,或者其vruntime比当前cpu rq队列中最小的vruntime task大一个时间片,就会标记resched,然后等中断返回后会调用schedule()进行task切换

void check_preempt_tick()
{
    // 如果运行时间大于sched_slice,则resched
    if (delta_exec > ideal_runtime)
        resched_task(rq_of(cfs_rq)->curr);
        
    // 如果比最小vruntime大一个sched_slice,则resched
    se = __pick_first_entity(cfs_rq);                // 选择cfs.rb_leftmost的se,即vruntime最小的se
    delta = curr->vruntime - se->vruntime;
    if (delta > ideal_runtime)
        resched_task(rq_of(cfs_rq)->curr);
}

 4> resched_curr()非常简单,就是设置一个resched标记位TIF_NEED_RESCHED

void resched_curr(struct rq* rq)
{
    struct task_struct* curr = rq->curr;
    set_tsk_thread_flag(curr, TIF_NEED_RESCHED);
}

 

2.3.2 schedule
1> 时钟中断返回后,会jump到ret_from_intr(有兴趣可以去分析这段汇编),如果resched标记被置位,就会调用schedule()进行调度
void schedule()
{
    prev = rq->curr;
    put_prev_task_fair(rq, prev);        // 对当前task进行处理,如果该task属于一个group,还要对组调度进行处理,这里不展开
    // 选择下一个task并切换运行
    next = pick_next_task(rq);           // 选择一个vruntime最小的task进行调度
    context_switch(rq, prev, next);
}

2> pick_next_task() → pick_next_task_fair() → pick_next_entity() → __pick_first_entity(),__pick_first_entity()选择vruntime最小的cfs_rq->rb_leftmost节点se进行调度

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;
    return rb_entry(left, struct sched_entity, run_node);
}

 文章来源地址https://www.toymoban.com/news/detail-413453.html

 

到了这里,关于极简cfs公平调度算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 01.4进程原理和系统调用--->经典的CFS调度器

    进程的一些正常状态 什么是进程 操作系统作为硬件的使用层,提供使用硬件资源的能力,进程作为操作系统使用层, 提供使用操作系统抽象出的资源层的能力。 进程:是指计算机中已运行的程序。进程本身不是基本的运行单位,而是线程的容器。 程序本身只是指令、数据

    2024年02月10日
    浏览(34)
  • Linux--2.6内核调度和环境变量

    📘北尘_ :个人主页 🌎个人专栏 :《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》 ☀️走在路上,不忘来时的初心 上图是Linux2.6内核中进程队列的数据结构,之间关系也已经给大家画出来,方便大家理解 如果有多个CPU就要考虑进程个数的负载均衡问题 普通

    2024年02月05日
    浏览(58)
  • 《深入Linux内核架构》第2章 进程管理和调度 (2)

    目录 2.4 进程管理相关的系统调用 2.4.1 进程复制 2.4.2 内核线程 2.4.3 启动新程序 2.4.4 退出进程 本专栏文章将有70篇左右,欢迎+关注,订阅后续文章。 1. _do_fork函数         fork vfork clone都最终调用_do_fork                 clone:通过CLONE_XX标志精确控制父子进程共享哪

    2024年04月11日
    浏览(36)
  • Linux2.6内核配置说明

    maturity level options 代码成熟度选项 Prompt for development and/or incomplete code/drivers 显示尚在开发中或尚未完成的代码与驱动.除非你是测试人员或者开发者,否则请勿选择 setup 常规设置 Local version - append to kernel release 在内核版本后面加上自定义的版本字符串(小于64字符),可以用\\\"uname

    2024年02月14日
    浏览(36)
  • 【linux 多线程并发】多任务调度器,调度策略时间片轮转,先进先出,多种实时任务的策略,内核级最高优先级调度策略

    ​ 专栏内容 : 参天引擎内核架构 本专栏一起来聊聊参天引擎内核架构,以及如何实现多机的数据库节点的多读多写,与传统主备,MPP的区别,技术难点的分析,数据元数据同步,多主节点的情况下对故障容灾的支持。 手写数据库toadb 本专栏主要介绍如何从零开发,开发的

    2024年02月03日
    浏览(52)
  • Linux 内核调优部分参数说明

    表示尽量使用内存,减少使用磁盘 swap 交换分区,内存速度明显高于磁盘一个数量级。 内存分配策略,Redis 持久化存储需设置值为1。 0:表示内核将检查是否有足够的可用内存供应用进程使用;如果有足够的可用内存,内存申请允许;否则,内存申请失败,并把错误返回给应

    2023年04月25日
    浏览(58)
  • 频繁设置CGroup触发linux内核bug导致CGroup running task不调度

    1. 说明 1 本篇是实际工作中linux上碰到的一个问题,一个使用了CGroup的进程处于R状态但不执行,也不退出,还不能kill,经过深入挖掘才发现是Cgroup的内核bug 2发现该bug后,去年给RedHat提交过漏洞,但可惜并未通过,不知道为什么,这里就发我博客公开了 3 前面的2个帖子《极简

    2023年04月15日
    浏览(58)
  • 【Linux内核解析-linux-5.14.10-内核源码注释】关于Linux同步机制知识点整理

    在Linux系统中,同步机制是操作系统中非常重要的一部分,以下是一些基本要点: 什么是同步机制?同步机制是一种操作系统提供的机制,用于协调多个进程或线程之间的访问共享资源,防止出现竞态条件和死锁等问题。 Linux中常用的同步机制有哪些?Linux中常用的同步机制

    2024年02月04日
    浏览(47)
  • 极简组调度-CGroup如何限制cpu

    1. 说明 1 linux内核关于task调度这块是比较复杂的,流程也比较长,要从源码一一讲清楚很容易看晕,因此需要简化,抓住主要的一个点,抛开无关的部分才能讲清楚核心思想 2 本篇文章主要是讲清楚在cfs公平调度算法中,CGroup如何限制cpu使用的主要过程,所以与此无关的代码

    2023年04月15日
    浏览(32)
  • 编译linux内核模块时的make -C M= modules的参数说明

            在linux下编译可加载内核模块形成.ko文件的makefile中的核心语句是: 这句是Makefile的规则:这里的 $(MAKE)就相当于make ; -C 选项的作用是指将当前工作目录转移到你所指定的位置,一般都是内核源代码目录或者内核headers目录,如/usr/include/linux-5.1.1-headers/类似的位置

    2024年02月04日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包