一文搞懂 | Linux内核 CFS 调度器
1
Linux内核作为一个通用的操作系统(OS),需要兼顾各种各样类型的进程,包括实时进程、交互式进程、批处理进程等。而调度器(Scheduler)作为OS的核心组件——CPU时间的管理器,主要负责选择某些就绪的进程来执行。不同的调度器根据不同的方法挑选出最适合运行的进程。目前,在Linux内核中支持的调度器有CFS调度器、Realtime调度器、Deadline调度器和Idle调度器 。本篇将简单介绍CFS调度器的设计原理。
CFS (完全公平调度器)实现的主要思想是维护为任务提供处理器时间方面的平衡(公平性),这意味着应给进程分配相当数量的处理器。分给某个任务的时间失去平衡时(意味着一个或多个任务相对于其他任务而言未被给予相当数量的时间),应给失去平衡的任务分配时间,让其执行。
CFS通过虚拟运行时间(vruntime)来实现平衡,维护提供给某个任务的时间量。进程的虚拟时间是指实际运行时间相对于权重为0的进程的比例值。在CFS调度器中有一个计算虚拟时间的核心函数calc_delta_fair(),它的计算公式为:
vruntime = 实际运行时间*1024 / 进程权重
因此,进程按照各自不同的速率在物理时钟节拍内前进,优先级高则权重大,其虚拟时钟比真实时钟跑得慢,但获得比较多的运行时间;反之,优先级低则权重小,其虚拟时钟比真实时钟跑得快,反而获得比较少的运行时间。CFS调度器总是选择虚拟时钟跑得慢的进程来运行,从而让每个调度实体(sche_entity)的虚拟运行时间互相追赶,进而实现进程调度上的平衡。
CFS调度器没有将进程维护在运行队列中,而是维护了一个以虚拟运行时间为顺序的红黑树。红黑树的主要特点有:
- 自平衡,树上没有一条路径会比其他路径长出俩倍。
- O(log n) 时间复杂度,能够在树上进行快速高效地插入或删除进程。
如图所示,进程存储在以vruntime排序的红黑树中,对处理器需求最多的任务 (vruntime最低)存储在树的左侧,处理器需求最少的进程(vruntime最高)存储在树的右侧。为了保证公平性,调度器每次选取红黑树最左端的进程进行调度。
CFS的内部原理大致为如图所示:
Linux内的所有任务都由称为 task_struct 的任务结构表示,它位于调度的最顶端。该结构(在./linux/include/linux/sched.h)完整地描述了任务并包括了任务的当前状态、其堆栈、进程标识、优先级(静态和动态)等等。
struct task_struct
{
...
volatile long state;
void *stack;
unsigned int flags;
int prio;
int static_prio;
int normal_prio;
struct sche_entity se;
...
};
但是,由于不是所有任务都是可运行的,所以在task_struct中不会发现任何与CFS相关的字段。因此,需要通过一个名为 sched_entity 的新结构来跟踪调度信息。
struct sched_entity
{
...
struct load_weight load;
struct rb_node run_node;
struct list_head group_node;
u64 vruntime;
...
};
sched_entity包含负载权重、各种统计数据以及vruntime(任务运行的虚拟时间量,并作为红黑树的索引)。同时,sched_entity还包含红黑树的节点rb_node。
struct rb_node
{
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
};
红黑树的每个节点都由 rb_node 表示,它只包含子引用和父对象的颜色。红黑树的叶子不包含信息,但是内部节点代表一个或多个可运行的任务。红黑树的根通过rb_root_cached结构中的rb_root引用,而该结构同时包含了红黑树的最左节点rb_leftmost的指针。
struct rb_root_cached
{
struct rb_root rb_root;
struct rb_node *rb_leftmost;
};
在运行过程中,__schedule()(在./kernel/sched/core.c中)是CFS调度器的核心函数,其作用是让调度器选择和切换到一个合适的进程运行。
在时钟周期开始时,调度器调用__schedule()函数来开始调度的运行。
然后,__schedule()函数调用pick_next_task()让进程调度器从就绪队列中选择一个最合适的进程next,即红黑树最左边的节点。
接着,通过context_switch()切换到新的地址空间,从而保证next进程运行。
在时钟周期结束时,调度器调用entity_tick()函数来更新进程负载、进程状态以及vruntime(当前vruntime + 该时钟周期内运行的时间)。
最后,将该进程的虚拟时间与就绪队列红黑树中最左边的调度实体的虚拟时间做比较,如果小于坐左边的时间,则不用触发调度,继续调度当前调度实体。否则,则表明最左边的调度实体更需要调度。因此,调度器将当前调度实体放回红黑树,并选择红黑树中最左边的调度实体作为next在下一个时钟周期进行调度。
通过以上的结构和调度方式,Linux内核保证了操作系统中进程调度的公平性。
原文:https://www.cnblogs.com/XiaoliBoy/p/10410686.html
相关文章
- Linux基础:linux内核copy_{to, from}_user()的介绍
- 软件Linux安装客户端软件的指南(linux如何安装客户端)
- 管理Linux下用户权限管理:创建用户、设置权限(linux创建用户和权限)
- Linux基本磁盘管理:解析实现磁盘控制(linux基本磁盘管理)
- Linux 掌控特殊权限的能力(linux的特殊权限)
- 实现Linux编译可执行文件的突破性方法(linux编译可执行文件)
- Linux内核中实现流量控制的策略(linux内核流量控制)
- 新版Linux内核:开创技术未来(最新的linux内核版本)
- Facebook 开源的一组 Linux 内核组件与工具
- 精通Linux内核:基础配置必备(配置linux内核)
- 文件监控实时Linux文件监控实现全面可控(实时linux)
- Linux 启动过程及内核加载分析(linux启动内核)
- 界面图形界面下 Linux 网卡配置简易指南(linux配置网卡图形)
- Linux下运算之王:加减乘除(linux加减乘除)
- 安卓:藉Linux立足(安卓与linux的关系)
- 深入浅出 Linux 线程概念.(linux线程概念)
- 关闭Linux系统的防火墙(关闭linux的防火墙)
- Linux分支:探索操作系统未知领域(linux的分支)
- Linux内核编程进阶:深入理解内核机制(linux内核编程进阶)
- 探索Linux内核,解开谜题(研究linux内核)
- 如何在 Linux 上安装显卡驱动?(linux安装显卡驱动)
- 基于QEMU调试Linux内核(qemu 调试linux)
- Linux下如何实现互斥锁读写?(linux互斥锁读写)
- Linux内核SMP技术革命:开启多核新时代(linux 内核 smp)
- Linux内核移植的技巧与方法(如何移植linux内核)
- 智慧引领,Linux下智能DNS指引你的网络之旅(智能dns linux)
- 深入Linux内核:移植实践之路(linux 内核 移植)
- Linux内核网络协议栈:针对网络优化的极致体验(linux内核网络协议栈)
- Linux内核查看之旅(linux 内核 查看)