红黑树存储着系统中所有就绪进程（处于可运行状态但未在运行的进程），按照每个进程的虚拟运行时间（vruntime）排序。vruntime是一个概念上的时间度量，用来衡量进程在系统中运行了多长时间。...更新 vruntime：时钟中断发生时，CFS 会更新当前正在运行的进程的vruntime，因为该进程已经使用了一段 CPU 时间。...比较 vruntime：调度器将当前运行进程的vruntime与红黑树根节点（下一个要运行的进程）的vruntime进行比较。...如果当前运行的进程的vruntime显著大于红黑树中的最小vruntime，调度器会认为需要进行进程切换，以确保系统中的所有进程都能公平地获得 CPU 资源。...vruntime：是调度决策的核心指标，反映进程的 CPU 使用时间。 公平性：通过不断地选择vruntime最小的进程，CFS 尽可能地实现 CPU 时间分配的公平性。
(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。...+= cfs_rq->min_vruntime; 将调度实体的虚拟时间添加回去，之前在fork的时候减去了min_vruntime,现在需要加回去，现在的min_vruntime比较准确 update_curr
se->vruntime -= cfs_rq->min_vruntime; 我们前面讲解place_entity的时候说到, 新创建的进程和睡眠后苏醒的进程为了保证他们的vruntime与系统中进程的vruntime...差距不会太大, 会使用place_entity来设置其虚拟运行时间vruntime, 在place_entity中重新设置vruntime值，以cfs_rq->min_vruntime值为基础，给予一定的补偿...vruntime也走得有快有慢，比如我们对比每个运行队列的min_vruntime值，都会有不同, 如果一个进程从min_vruntime更小的CPU (A) 上迁移到min_vruntime更大的CPU...) 时，它的vruntime要加上该队列的min_vruntime值 当进程刚刚创建以某个cfs_rq的min_vruntime为基准设置其虚拟运行时间后，也要减去队列的min_vruntime值 这样...(flags & DEQUEUE_SLEEP)) se->vruntime -= cfs_rq->min_vruntime; task_fork_fair(): se->vruntime
每一个进程拥有一个vruntime, 每次需要调度的时候就选运行队列中拥有最小vruntime的那个进程来运行, vruntime在时钟中断里面被维护, 每次时钟中断都要更新当前进程的vruntime,...else /* 此时vruntime的原值为cfs_rq->curr->vruntime*/ vruntime = min_vruntime(vruntime...curr, 以此设置vruntime的值 如果cfs就绪队列上没有活动进程curr, 就设置vruntime为curr->vruntime; 否则又活动进程就设置为vruntime为cfs_rq的原min_vruntime...单调不减, 只有在vruntime超出的cfs_rq->min_vruntime的时候才更新 update_min_vruntime依据当前进程和待调度的进程的vruntime值, 设置出一个可能的vruntime...->min_vruntime vruntime-cfs_rq->min_vruntime) 进一步化简为 if (se->vruntime vruntime) 即整个过程等价于比较两个调度实体
，这个是红黑树的节点 on_rq: 此值为1时，代表此进程在运行队列中 exec_start: 记录这个进程在CPU上开始执行任务的时间 sum_exec_runtime: 记录这个进程总的运行时间 vruntime...其中的时间键值就是进程的vruntime。 CFS维护了一课以时间为排序的红黑树，所有的红黑树节点都是通过进程的se.vruntime来作为key来进行排序。...随着时间的推移，之前在最左边的节点随着运行，进程的vruntime也随之增大，这些进程慢慢的会添加到红黑树的右边。循环往复这个树上的所有进程都会被调度到，从而达到的公平。...同时CFS也会维护这棵树上最小的vruntime的值cfs.min_vruntime，而且这个值是单调递增的。此值用来跟踪运行队列中最小的vruntime的值。 ?...: 此值代表的是CFS运行队列中所有进程的最小的vruntime 看下运行队列的关系图 ?
* 如果是唤醒已经存在的进程，则单调附值 */ se->vruntime = max_vruntime(se->vruntime, vruntime); } 我们可以看到enqueue_task_fair...因为进程睡眠后，vruntime就不会增加了，当它醒来后不知道过了多长时间，可能vruntime已经比 min_vruntime小了很多，如果只是简单的将其插入到就绪队列中，它将拼命追赶min_vruntime...当然如果进程没有睡眠那么多时间，我们只需保留原来的时 间vruntime = max_vruntime(se->vruntime, vruntime)。...对于新进程创建时initial为1，所以它会执行vruntime += sched_vslice(cfs_rq, se);这句，而这里的vruntime就是当前CFS就绪队列的min_vruntime，...如果se->vruntime比先前的差值更大, 则将其作为进程的vruntime, 这会导致高进程在红黑树中处于靠左的位置, 而具有较小vruntime值得进程可以更早调度执行. 2.6 __enqueue_entity
正常情况，进程vruntime增长将会和物理时间增长速度成正比，操作系统将会选择vruntime最小的进程进行调度，并对每个进程划分相应的time slice。...尽管实际运行时间不一定是整数倍，但是因为vruntime的存在，记录的时间还是精确的。 weighting（Niceness） 每个进程的nice值从-19到20，并被映射到不同的权重。...70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, }; R-B Tree linux使用红黑树存储所有正在运行的进程的节点（不包含sleeping进程），目的是可以在找到vruntime...最小的进程并调度后，插入时仍然可以 为了防止苏醒的进程的vruntime远远落后于其他进程而导致starvation，当进程苏醒之后，vruntime将会是树中最小的vruntime。
在运行队列中，各个任务按照 vruntime 值的大小从小到大排列，即vruntime越小的进程，越靠近队首。...当进程得到调度并运行时，其vruntime就会根据单次运行时长进行累加，另外，为了支持进程优先级，CFS在vruntime的累加时长上引入了 权重 (weight) 的概念，因此vruntime的计算公式如下...： vruntime = vruntime_{old} + \Delta t\times \frac {1024}{weight} vruntime=vruntimeold+Δt×weight1024...当得出CFS对于vruntime的计算方式之后，CFS对于进程优先级的支持，是基于vruntime的增量比例控制上的，但不管如何偏袒高优进程，缩小其vruntime增量，只要进程运行，在当前CPU上，vruntime...而低优进程虽然大部分时间得不到调度执行，但是只要不执行，其vruntime将不会改变，总有一个时间点，高优任务的vruntime会超过低优任务的vruntime从而排到低优任务的后面，而下次调度的时候将会选择出
CFS为每个进程定义一个虚拟运行时间vruntime，每次总是选择vruntime最小的那个进程，进程得到处理机后变随着其运行时间的增加 增加其vruntime。...对于优先级的问题，对于高优先级的进程，vruntime增加慢一点，对于低优先级任务vruntime增加快一点，如此每次还是选择最小vruntime的那个进程，体现了其优先级。...vruntime = 实际运行时间 * NICE_0_LOAD / 权重 使用调度算法首先得有包含vruntime的调度实体，task_struct中有如下调度实体的成员变量： struct sched_entity...完全调度实体 struct sched_rt_entity rt; // 实时调度实体 struct sched_dl_entity dl; // deadline调度实体 CFS算法中将se以其中的vruntime
CFS调度是通过进程的虚拟时间vruntime来选择要运行的进程。...vruntime的计算公式如下： vruntime = (wall_time * NICE0_TO_weight) / weight 其中,wall_time代表的是进程实际运行的时间，NICE0_TO_Weight...当一个进程的weight越大，则对应的进程的vruntime就越小；当一个进程的weight越小，则对应的vruntime就越大。...CFS每次调度原则是，总是选择vruntime最小的进程来调度，vruntime最小的进程weight越大，优先级越高，则就需要更高的获取CPU的时间。...当进程加入到运行队列，调度器会时刻来更新进程的vruntime，来达到公平 调度器每次调度的时候只选择运行队列中虚拟时间最小的进程，当此进程运行一段时间后，vruntime就会变大 这时候就需要调度时候就需要重新选择新的最小
: 353989 cfs_rq[0]:/ .exec_clock : 5324597.435447 .MIN_vruntime...: 0.000001 .min_vruntime : 4449136.507675 .max_vruntime...: 347894 cfs_rq[1]:/ .exec_clock : 5318544.561997 .MIN_vruntime...: 0.000001 .min_vruntime : 4390944.446853 .max_vruntime
假设min_vruntime是公平运行队列中的所有进程的虚拟运行时间的最小值，那么cfs_rq.min_vruntime的计算方法如下，即取自己和min_vruntime的较大值。...cfs_rq.min_vruntime = max(cfs_rq.min_vruntime, min_vruntime) 在创建新进程、睡眠进程被唤醒和进程从一个处理器迁移到另一个处理器这些情况，会以公平运行队列的最小虚拟运行时间为基础设置进程的虚拟运行时间...（2）如果进程长时间睡眠，它的虚拟运行时间小于“cfs_rq.min_vruntime - 补偿值”，那么把它的虚拟运行时间修改为“cfs_rq.min_vruntime - 补偿值”。...（1）当进程p退出一个处理器的公平运行队列的时候，把它的虚拟运行时间减去公平运行队列的最小虚拟运行时间，即p->se.vruntime = p->se.vruntime - cfs_rq.min_vruntime...（2）当进程p加入一个处理器的公平运行队列的时候，把它的虚拟运行时间加上公平运行队列的最小虚拟运行时间，即p->se.vruntime = p->se.vruntime + cfs_rq.min_vruntime
- se->vruntime; if (delta < 0) return; if (delta > ideal_runtime) resched_curr(rq_of(cfs_rq)...将当前进程的vruntime和se的vruntime做比值 如果delta小于0，则说明当前进程vruntime比最新的vruntime还小，则不调度，继续运行 如果大于ideal_runtime， 如果大于理想时间...- se->vruntime; if (vdiff <= 0) return -1; gran = wakeup_gran(se); if (vdiff > gran) return...，则不抢占 wakeup_gran是用来计算唤醒的调度实体在sysctl_sched_wakeup_granularity时间内的vruntime。...的值 此时需要将进程添加到就绪队列中，对于CFS就绪队列，则需要添加到CFS红黑树中，跟踪进程的vruntime为键值添加。
CFS通过虚拟运行时间（vruntime）来实现平衡，维护提供给某个任务的时间量。进程的虚拟时间是指实际运行时间相对于权重为0的进程的比例值。...在CFS调度器中有一个计算虚拟时间的核心函数calc_delta_fair(),它的计算公式为： vruntime = 实际运行时间*1024 / 进程权重 因此，进程按照各自不同的速率在物理时钟节拍内前进...如图所示，进程存储在以vruntime排序的红黑树中，对处理器需求最多的任务 （vruntime最低）存储在树的左侧，处理器需求最少的进程（vruntime最高）存储在树的右侧。...; ... }; sched_entity包含负载权重、各种统计数据以及vruntime（任务运行的虚拟时间量，并作为红黑树的索引）。...在时钟周期结束时，调度器调用entity_tick()函数来更新进程负载、进程状态以及vruntime（当前vruntime + 该时钟周期内运行的时间）。
虚拟实时 (vruntime) 现在我们来谈谈上面结构体中的vruntime变量所表示的意义。我们称它为“虚拟运行时间”，该运行时间的计算是经过了所有可运行进程总数的标准化（简单说就是加权的）。...进程选择 这里便是调度的核心部分，用一句话来梗概CFS算法的核心就是选择具有最小vruntime的进程作为下一个需要调度的进程。...* 然后更新当前任务的运行时统计数据 */ if (renorm && curr) se->vruntime += cfs_rq->min_vruntime; update_curr...curr) se->vruntime += cfs_rq->min_vruntime; /* * 更新对应调度器实体的各种记录值 */ update_load_avg(cfs_rq...(flags & DEQUEUE_SLEEP)) se->vruntime -= cfs_rq->min_vruntime; /* return excess runtime on last dequeue
所以在实践中，CFS 会保证所有线程之间的 vruntime 之差低于抢占时间（6ms），它是通过如下两点来保证的： 当线程创建时，它的 vruntime 值等于运行队列中等待执行线程的最大 vruntime...； 当线程从睡眠中唤醒时，它的 vruntime 值会被更新为大于或等于所有待调度线程中最小的 vruntime。...，就更新最小运行时间为当前任务的 vruntime vruntime = cfs_rq->curr->vruntime; if (cfs_rq->rb_leftmost)...vruntime = min_vruntime(vruntime, se->vruntime); } // 这里之所以去二者之间的最大值，是为了保证 min_vruntime...cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime); } 最后，来总结下使用虚拟时钟的意义： 当任务运行时，它的虚拟时间总是会增加
CFS定义一种新调度模型，它给cfs_rq（cfs的run queue）中的每一个进程都设置一个虚拟时钟 - virtual runtime（vruntime），如果一个进程得以执行，随着执行时间的不断增长...，其vruntime也不断增大，没有得到执行的进程vruntime将保持不变。...int idle_h_nr_running; u64 exec_clock; u64 min_vruntime...; #ifndef CONFIG_64BIT u64 min_vruntime_copy; #endif; struct rb_root_cached
如果一个进程得以执行，那么他的 vruntime 将不断增大，直到它没有执行。没有执行的进程的 vruntime 不变。...他们被维护到一个以 vruntime 为顺序的红黑树 rbtree 中，每次去取最小的 vruntime 的进程来投入运行。...实际运行时间到 vruntime 的计算公式为： [ vruntime = 实际运行时间 * 1024 / 进程权重 ] 这里的1024代表nice值为0的进程权重。...所有的进程都以nice为0的权重1024作为基准，计算自己的vruntime。上面两个公式可得出，虽然进程的权重不同，但是它们的 vruntime增长速度应该是一样的 ，与权重无关。...既然所有进程的vruntime增长速度宏观上看应该是同时推进的，那么就可以用vruntime来选择运行的进程，vruntime值较小就说明它以前占用cpu的时间较短，受到了“不公平”对待，因此下一个运行进程就是它
Scheduler) 调度器[1]追求的是对所有进程的全面公平，实际上它的做法就是在一个特定的调度周期内，保证所有待调度的进程都能被执行一遍，主要和当前已经占用的 CPU 时间经权重除权之后的值 (vruntime...，见下面公式) 来决定本轮调度周期内所能占用的 CPU 时间，vruntime 越少，本轮能占用的 CPU 时间越多；总体而言，CFS 就是通过保证各个进程 vruntime 的大小尽量一致来达到公平调度的效果...： 进程的运行时间计算公式为: 进程运行时间 = 调度周期 * 进程权重 / 所有进程权重之和 vruntime = 进程运行时间 * NICE_0_LOAD / 进程权重 = (调度周期...* 进程权重 / 所有进程总权重) * NICE_0_LOAD / 进程权重 = 调度周期 * NICE_0_LOAD / 所有进程总权重 通过上面两个公式，可以看到 vruntime...---------------------------- se.exec_start : 20229360324.308323 se.vruntime
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
