键值通过entity_key计算, 该函数在linux-2.6之中被定义, 但是后来的内核中移除了这个函数, 但是我们今天仍然讲解它, 因为它对我们理解CFS调度器和虚拟时钟vruntime有很多帮助,...我们也会讲到为什么这么有用的一个函数会被移除 我们可以在早期的linux-2.6.30(仅有entity_key函数)和linux-2.6.32(定义了entity_key和entity_befire...来实现此功能, 函数定义在linux+v2.6.32/kernel/sched_fair.c, line 269, 在我们新的linux-4.6内核中定义在kernel/sched/fair.c, line...而，CFS调度器中的权重在内核是对用户态进程的优先级nice值, 通过prio_to_weight数组进行nice值和权重的转换而计算出来的 虚拟时钟相关公式 linux内核采用了计算公式： 属性 公式...se.weight 当前进程的权重 cfs.weight 整个cfs_rq的总权重 这里se.weight和cfs.weight根据上面讲解我们可以算出, sum_runtime是怎们计算的呢，linux
linux内部则使用CFS作为另一种实现。 How can we design a scheduler to share the CPU in a proportional manner?...---- The Linux Completely Fair Scheduler (CFS) Linux使用了CFS作为调度算法，为了按比例分配CPU，它使用了基于计数的virtual runtime技巧...正常情况，进程vruntime增长将会和物理时间增长速度成正比，操作系统将会选择vruntime最小的进程进行调度，并对每个进程划分相应的time slice。...使用红黑树存储所有正在运行的进程的节点（不包含sleeping进程），目的是可以在找到vruntime最小的进程并调度后，插入时仍然可以 为了防止苏醒的进程的vruntime远远落后于其他进程而导致...starvation，当进程苏醒之后，vruntime将会是树中最小的vruntime。
调度类 CFS调度器是在Linux2.6.23引入的，在当时就提出了调度类概念，调度类就是将调度策略模块化，有种面向对象的感觉。...put_prev_task: 获得当前进程之前的那个进程 set_curr_task: 用来设置当前进程的调度状态等 task_tick: 在每个时钟tick的时候会调度各个调度类中的tick函数 Linux...在之前的O(1)算法中调度的单位都是task_struct，而在Linux2.6.23引入调度模块化后，调度的单位成为调度实体sched_entity load就是此进程的权重 run_node:CFS...其中的时间键值就是进程的vruntime。 CFS维护了一课以时间为排序的红黑树，所有的红黑树节点都是通过进程的se.vruntime来作为key来进行排序。...同时CFS也会维护这棵树上最小的vruntime的值cfs.min_vruntime，而且这个值是单调递增的。此值用来跟踪运行队列中最小的vruntime的值。 ?
1 Linux内核作为一个通用的操作系统（OS），需要兼顾各种各样类型的进程，包括实时进程、交互式进程、批处理进程等。...如图所示，进程存储在以vruntime排序的红黑树中，对处理器需求最多的任务 （vruntime最低）存储在树的左侧，处理器需求最少的进程（vruntime最高）存储在树的右侧。...CFS的内部原理大致为如图所示： Linux内的所有任务都由称为 task_struct 的任务结构表示，它位于调度的最顶端。该结构（在..../linux/include/linux/sched.h）完整地描述了任务并包括了任务的当前状态、其堆栈、进程标识、优先级（静态和动态）等等。...在时钟周期结束时，调度器调用entity_tick()函数来更新进程负载、进程状态以及vruntime（当前vruntime + 该时钟周期内运行的时间）。
pick_next_task全局的pick_next_task函数会从按照优先级遍历所有调度器类的pick_next_task函数, 去查找最优的那个进程, 当然因为大多数情况下, 系统中全是CFS调度的非实时进程, 因而linux...关于place_entity函数, 我们之前在讲解CFS队列操作的时候已经讲的很详细了 参见linux进程管理与调度之CFS入队出队操作 设想一下子如果休眠进程的vruntime保持不变,...se->vruntime -= cfs_rq->min_vruntime; 我们前面讲解place_entity的时候说到, 新创建的进程和睡眠后苏醒的进程为了保证他们的vruntime与系统中进程的vruntime...vruntime也走得有快有慢，比如我们对比每个运行队列的min_vruntime值，都会有不同, 如果一个进程从min_vruntime更小的CPU (A) 上迁移到min_vruntime更大的CPU...) 时，它的vruntime要加上该队列的min_vruntime值 当进程刚刚创建以某个cfs_rq的min_vruntime为基准设置其虚拟运行时间后，也要减去队列的min_vruntime值 这样
引言 Linux Kernel Development 一书中，关于 Linux 的进程调度器并没有讲解的很全面，只是提到了 CFS 调度器的基本思想和一些实现细节；并没有 Linux 早期的调度器介绍...所以在经过一番搜寻后，看到了这篇论文 A complete guide to Linux process scheduling，对 Linux 的调度器历史进行了回顾，并且相对细致地讲解了 CFS 调度器...Linux 调度器 早期版本: Linux 0.0.1 版本就已经有了一个简单的调度器，当然并非适合拥有特别多处理器的系统。...vruntime = min_vruntime(vruntime, se->vruntime); } // 这里之所以去二者之间的最大值，是为了保证 min_vruntime...cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime); } 最后，来总结下使用虚拟时钟的意义： 当任务运行时，它的虚拟时间总是会增加
本文是《Linux内核设计与实现》第四章的阅读笔记，代码则是摘自最新的4.6版本linux源码(github)，转载请注明出处。...Linux进程调度 发展历史 Linux从2.5版本开始引入一种名为的调度器，后在2.6版本中将公平的的调度概念引入了调度程序，代替之前的调度器，称为算法（完全公平调度算法）。...为了保证交互式应用和桌面系统的性能，一般Linux更倾向于优先调度I/O消耗型进程。 进程优先级 Linux采用了两种不同的优先级范围。 使用nice值：越大的nice值意味着更低的优先级。...Linux调度算法 调度器类 Linux的调度器是以模块的方式提供的，这样使得不同类型的进程按照自己的需要来选择不同的调度算法。...虚拟实时 (vruntime) 现在我们来谈谈上面结构体中的vruntime变量所表示的意义。我们称它为“虚拟运行时间”，该运行时间的计算是经过了所有可运行进程总数的标准化（简单说就是加权的）。
总的来说O(1)调度器的出现是为了解决O(n)调度器不能解决的问题，而O(1)调度器在Linux2.4内核的在服务器的变形是可行的，但是Linux2.4以后随着移动设备的逐渐普遍，面临的卡顿问题逐渐明晰...CFS引入 完全公平调度器(CFS)最早是在2017年merged进Linux2.6.23版本中的，一直到现在都是系统中默认的调度器。...CFS调度是通过进程的虚拟时间vruntime来选择要运行的进程。...当一个进程的weight越大，则对应的进程的vruntime就越小；当一个进程的weight越小，则对应的vruntime就越大。...CFS每次调度原则是，总是选择vruntime最小的进程来调度，vruntime最小的进程weight越大，优先级越高，则就需要更高的获取CPU的时间。
Linux内核中用来安排调度进程执行的模块称为调度器（Scheduler），它可以切换进程状态（执行、睡眠、退出等）。...CFS定义一种新调度模型，它给cfs_rq（cfs的run queue）中的每一个进程都设置一个虚拟时钟 - virtual runtime（vruntime），如果一个进程得以执行，随着执行时间的不断增长...，其vruntime也不断增大，没有得到执行的进程vruntime将保持不变。...Linux采用红黑树保存调度实体，按照虚拟时间从小到大存储在红黑树中。 调度器通过各个组件模块及一系列数据结构，来排序和管理系统中的进程。...; #ifndef CONFIG_64BIT u64 min_vruntime_copy; #endif; struct rb_root_cached
. */ } } linux对组调度的支持可以通过CONFIG_FAIR_GROUP_SCHED来启用, 在启用和不启用的条件下, 内核对很多函数的实现也会因条件而异, 这点对for_each_sched_entity...* 如果是唤醒已经存在的进程，则单调附值 */ se->vruntime = max_vruntime(se->vruntime, vruntime); } 我们可以看到enqueue_task_fair...因为进程睡眠后，vruntime就不会增加了，当它醒来后不知道过了多长时间，可能vruntime已经比 min_vruntime小了很多，如果只是简单的将其插入到就绪队列中，它将拼命追赶min_vruntime...当然如果进程没有睡眠那么多时间，我们只需保留原来的时 间vruntime = max_vruntime(se->vruntime, vruntime)。...但是，Linux内核需要根据新加入的进程的权重决策一下应该何时调度该进程，而不能任意进程都来抢占当前队列中靠左的进程，因为必须保证就绪队列中的所有进程尽量得到他们应得的时间响应， sched_vslice
Linux 系统为了提升响应的速度，倾向于优先调度 I/O 消耗型。...Linux 调度算法： Linux 中有一个总的调度结构，称之为 调度器类（scheduler class），它允许不同的可动态添加的调度算法并存，总调度器根据调度器类的优先顺序，依次去进行调度器类的中的进程进行调度...如果一个进程得以执行，那么他的 vruntime 将不断增大，直到它没有执行。没有执行的进程的 vruntime 不变。...既然所有进程的vruntime增长速度宏观上看应该是同时推进的，那么就可以用vruntime来选择运行的进程，vruntime值较小就说明它以前占用cpu的时间较短，受到了“不公平”对待，因此下一个运行进程就是它...Linux 调度时机： 1、进程切换： 从进程的角度看，CPU是共享资源，由所有的进程按特定的策略轮番使用。
多用户是指多个用户可以在同一时间使用同一个linux系统；多任务是指在Linux下可以同时执行多个任务，更详细的说，linux采用了分时管理的方法，所有的任务都放在一个队列中，操作系统根据每个任务的优先级为每个任务分配合适的时间片...Linux进程的结构 Linux中一个进程在内存里有三部分数据，就是“数据段”、“堆栈段”和“代码段”。...Linux的进程控制 1....子进程在创建的时候，vruntime的定义的步骤如下，首先vruntime被设置为min_vruntime。...Linux进程间通信 linux下的进程通信手段基本上是从Unix平台上的进程通信手段继承而来的。
CFS引入虚拟运行时间的概念，虚拟运行时间用task_struct->se.vruntime表示，通过它来记录和度量进程应该获得的CPU运行时间。...在理想的调度情况下，任何时候所有的进程都应该有相同的task_struct->se.vruntime值。因为每个进程都是并发执行，没有进程会超过理想状态下应该占有的CPU时间。...CFS选择需要运行的进程的逻辑基于task_struct->se.vruntime值，它总是选择task_struct->se.vruntime值最小的进程来运行（为了公平）。...所有的进程按task_struct->se.vruntime关键字排序。CFS从树中选择最左边的任务执行。...总的来说，CFS算法首先选一个进程，当进程切换时，该进程使用的CPU时间会加到该进程task_struct->se.vruntime里，当task_struct->se.vruntime的值逐渐增大到别的进程变成了红黑树最左边的进程时
vruntime是进程的虚拟运行时间，pruntime是物理运行时间，weight是权重，权重完全由nice决定，如下表： ?...在RT进程都睡过去之后（有一个特例就是RT没睡也会跑普通进程，那就是RT加起来跑地实在太久太久，普通进程必须喝点汤了），Linux开始跑NORMAL的，它倾向于调度vruntime（虚拟运行时间）最小的普通进程...比如有4个普通进程，如下表，目前显然T1的vruntime最小(这是它喜欢睡的结果)，然后T1被调度到。...*1024/weight（这里delta是12，weight是1024），于是T1的vruntime成为20，那么这个时候vruntime最小的反而是T2（为19），此后，Linux将倾向于调度T2（尽管...T2的nice值大于T1，优先级低于T1，但是它的vruntime现在只有19）。
一个进程的vruntime 等于进程实际运行时间 乘以 NICE0进程对应权重 除以 当前进程的权重。为了保证除法计算中不涉及浮点运算，linux内核通过先左移32位，然后右移32位来避免浮点运算。...(se->vruntime, vruntime); } 获取当前CFS运行队列的min_vruntime的值 当参数initial等于true时，代表是新创建的进程，新创建的进程则给它的vruntime...确保调度实体的vruntime不得倒退，通过max_vruntime获取最大的vruntime. update_curr update_curr函数用来更新当前进程的运行时间信息 static void..., se->vruntime); resched_curr(rq); } se->vruntime -= cfs_rq->min_vruntime; rq_unlock(rq, &rf);...vruntime。
Linux 系统为了提升响应的速度，倾向于优先调度 I/O 消耗型。...一、普通进程 在 Linux 中普通进程依赖称之为 nice 值 的东东来进行进程的优先级描述。nice 值的范围是 [-20, 19]。...—— 小结 实时进程优先级：value 越高，优先级越大 普通进程优先级：nice值越高，普通进程的优先级越小 任何实时进程的优先级 > 普通进程 Linux 调度算法 ---- Linux 中有一个总的调度结构...如果一个进程得以执行，那么他的 vruntime 将不断增大，直到它没有执行。没有执行的进程的 vruntime 不变。...Linux 调度时机 ---- 一、进程切换 从进程的角度看，CPU是共享资源，由所有的进程按特定的策略轮番使用。
所以，Linux 内核里的调度器，调度的对象就是 tark_struct，接下来我们就把这个数据结构统称为任务。...这个算法的理念是想让分配给每个任务的 CPU 时间是一样，于是它为每个任务安排一个虚拟运行时间 vruntime，如果一个任务在运行，其运行的越久，该任务的 vruntime 自然就会越大，而没有被运行的任务...，vruntime 是不会变化的。...你可以不用管 NICE_0_LOAD 是什么，你就认为它是一个常量，那么在「同样的实际运行时间」里，高权重任务的 vruntime 比低权重任务的 vruntime 少，你可能会奇怪为什么是少的？...在前面我们提到了，权重值与 nice 值的关系的，nice 值越低，权重值就越大，计算出来的 vruntime 就会越少，由于 CFS 算法调度的时候，就会优先选择 vruntime 少的任务进行执行，
Linux 进程调度算法经历了以下几个版本的发展： 基于时间片轮询调度算法。(2.6之前的版本) O(1) 调度算法。(2.6.23之前的版本) 完全公平调度算法。...为了解决上面两个问题，Linux内核的开发者创造了 完全公平调度算法。...把计算虚拟运行时间的结果添加到进程调度实体的 vruntime 字段。 我们接着分析怎么把进程添加到运行队列中。 2....= max_vruntime(cfs_rq->min_vruntime, se->vruntime); } // 这里是红黑树的平衡过程(参考红黑树数据结构的实现) rb_link_node...答案是由 Linux 内核的时钟中断触发的。 时钟中断 是什么？
Linux中的PCB是task_struct结构体。 ?...Linux同一进程的多线程，在内核视角实际上每个线程都有一个PID，但在用户空间需要getpid返回唯一值，Linux使用了一个小技巧，引入了TGID的概念，getpid()返回的的TGID值。...最小的进程 同时考虑了CPU/IO和nice 总是找vruntime最小的线程调度。...vruntime = pruntime/weight × 1024; vruntime是虚拟运行时间，pruntime是物理运行时间，weight权重由nice值决定(nice越低权重越高)，则运行时间少...、nice值低的的线程vruntime小，将得到优先调度。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
