CFS----------------完全公平调度算法_cfs算法-程序员宅基地

技术标签: Linux内核  

调度器

调度器是一个操作系统的核心部分。可以比作是CPU时间的管理员。调度器主要负责选择某些就绪的进程来执行。不同的调度器根据不同的方法挑选出最适合运行的进程。目前Linux支持的调度器就有RT scheduler、Deadline scheduler、CFS scheduler及Idle scheduler等。

首先要明白为什么要引入虚拟时间

完全公平调度算法CFS依赖于虚拟时钟

CFS通过每个进程的虚拟运行时间(vruntime)来衡量哪个进程最值得被调度。CFS中的就绪队列是一棵以vruntime为键值的红黑树,虚拟时间越小的进程越靠近整个红黑树的最左端。因此,调度器每次选择位于红黑树最左端的那个进程,该进程的vruntime最小。

虚拟运行时间是通过进程的实际运行时间和进程的权重(weight)计算出来的。在CFS调度器中,将进程优先级这个概念弱化,而是强调进程的权重。一个进程的权重越大,则说明这个进程更需要运行,因此它的虚拟运行时间就越小,这样被调度的机会就越大。

进程分类

对于调度问题,传统上进程分为"I/O受限(I/O-bound)"或“CPU受限(CPU-bound)”。前者频繁地使用I/O设备(数据库服务器,想想索引,树的高度不就是io访问吗),并花费很多时间等待IO操作完成,后者需要大量CPU时间的数值计算应用程序(图像绘制)。

另一种分类法把进程区分为3类:

交互式进程:这些进程经常与用户经行交互,因此要花很多时间等待键盘鼠标操作

批处理进程:这些进程不必与用户交互,因此经常在后台运行。因为这样的进程不必被很快的响应,因此常受到调度程序的慢待

典型批处理进程是程序设计语言的编译程序、数据库搜索引擎及科学计算。

实时进程:这些进程有很强的调度需要。这样的进程绝不会被低优先级的进程阻塞。典型有视频音频应用程序、机器人控制,传感器收集。

O(n)调度 

O(n)调度:内核调度算法理解起来简单:在每次进程切换时,内核依次扫描就绪队列上的每一个进程,计算每个进程的优先级,再选择出优先级最高的进程来运行;尽管这个算法理解简单,但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多,花费的时间就越大,时间复杂度为O(n)

O(1)调度

O(1)调度:其基本思想是根据进程的优先级进行调度。进程有两个优先级,一个是静态优先级,一个是动态优先级.静态优先级是用来计算进程运行的时间片长度的,动态优先级是在调度器进行调度时用到的,调度器每次都选取动态优先级最高的进程运行.由于其数据结构设计上采用了一个优先级数组,这样在选择最优进程时时间复杂度为O(1),所以被称为O(1)调度。

静态优先级的计算:

nice值和静态优先级之间的关系是:静态优先级=100+nice+20
nice值的范围是-20~19所以普通进程的静态优先级的范围是100~139

进程运行的时间片长度的计算:

静态优先级<120,基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)
静态优先级>=120,基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

其中MIN_TIMESLICE为系统规定的最小时间片.从该计算公式可以看出,静态优先级越高(值越低),进程得到的时间片越长

动态优先级的计算:

动态优先级=max(100 , min(静态优先级 – bonus + 5 , 139))

从上面看出,动态优先级的生成是以静态优先级为基础,再加上相应的惩罚或奖励(bonus).这个bonus并不是随机的产生,而是根据进程过去的平均睡眠时间做相应的惩罚或奖励.交互性强的进程会得到调度程序的奖励(bonus为正),而那些一直霸占CPU的进程会得到相应的惩罚(bonus为负).

总结:就是费时间的优先级会变大,省时间的会变小

普通进程的动态优先级的范围是100~139,实时进程的动态优先级的范围是0~99

普通进程的优先级

CFS是Completely Fair Scheduler简称,即完全公平调度器。CFS的设计理念是在真实硬件上实现理想的、精确的多任务CPU。CFS调度器和以往的调度器不同之处在于没有时间片的概念而是分配cpu使用时间的比例。例如:2个相同优先级的进程在一个cpu上运行,那么每个进程都将会分配50%的cpu运行时间。这就是要实现的公平。

以上举例是基于同等优先级的情况下。但是现实却并非如此,有些任务优先级就是比较高。那么CFS调度器的优先级是如何实现的呢?首先,我们引入权重的概念,权重代表着进程的优先级。各个进程之间按照权重的比例分配cpu时间。例如:2个进程A和B。A的权重是1024,B的权重是2048。那么A获得cpu的时间比例是1024/(1024+2048) = 33.3%。B进程获得的cpu时间比例是2048/(1024+2048)=66.7%。我们可以看出,权重越大分配的时间比例越大,相当于优先级越高。在引入权重之后,分配给进程的时间计算公式如下:

分配给进程的时间 = 总的cpu时间 * 进程的权重/就绪队列(runqueue)所有进程权重之和

CFS调度器针对优先级又提出了nice值的概念,其实和权重是一一对应的关系。nice值就是一个具体的数字,取值范围是[-20, 19]。数值越小代表优先级越大,同时也意味着权重值越大,nice值和权重之间可以互相转换内核提供了一个表格转换nice值和权重。

nice值共有40个,与权重之间,每一个nice值相差10%左右。
const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
}; 

数组的值可以看作是公式:weight = 1024 / 1.25^nice计算得到。公式中的1.25取值依据是:进程每降低一个nice值,将多获得10% cpu的时间。公式中以1024权重为基准值计算得来,1024权重对应nice值为0,其权重被称为NICE_0_LOAD。默认情况下,大部分进程的权重基本都是NICE_0_LOAD。

调度延迟

什么是调度延迟?调度延迟就是保证每一个可运行进程都至少运行一次的时间间隔。例如,每个进程都运行10ms,系统中总共有2个进程,那么调度延迟就是20ms。如果有5个进程,那么调度延迟就是50ms。如果现在保证调度延迟不变,固定是6ms,那么系统中如果有2个进程,那么每个进程运行3ms。如果有6个进程,那么每个进程运行1ms。如果有100个进程,那么每个进程分配到的时间就是0.06ms。随着进程的增加,每个进程分配的时间在减少,进程调度过于频繁(调度延时时间少每个进程的),上下文切换时间开销就会变大。因此,CFS调度器的调度延迟时间的设定并不是固定的。当系统处于就绪态的进程少于一个定值(默认值8)的时候,调度延迟也是固定一个值不变(默认值6ms)。当系统就绪态进程个数超过这个值时,我们保证每个进程至少运行一定的时间才让出cpu。这个“至少一定的时间”被称为最小粒度时间在CFS默认设置中,最小粒度时间是0.75ms。用变量sysctl_sched_min_granularity记录。因此,调度周期是一个动态变化的值。调度周期计算函数是__sched_period()。

static u64 __sched_period(unsigned long nr_running)
{
	if (unlikely(nr_running > sched_nr_latency))
		return nr_running * sysctl_sched_min_granularity;
	else
		return sysctl_sched_latency;
} 

nr_running是系统中就绪进程数量,
当超过sched_nr_latency时,我们无法保证调度延迟,
因此转为保证调度最小粒度。
如果nr_running并没有超过sched_nr_latency,
那么调度周期就等于调度延迟sysctl_sched_latency(6ms)。

总结: 就绪态超过或等于8,每个进程时间为最小粒度时间,0.75,少于8固定值6ms

虚拟时间(virtual time)

CFS调度器的目标是保证每一个进程的完全公平调度。CFS调度器就像是一个母亲,她有很多个孩子(进程)。但是,手上只有一个玩具(cpu)需要公平的分配给孩子玩。假设有2个孩子,那么一个玩具怎么才可以公平让2个孩子玩呢?简单点的思路就是第一个孩子玩10分钟,然后第二个孩子玩10分钟,以此循环下去。CFS调度器也是这样记录每一个进程的执行时间,保证每个进程获取CPU执行时间的公平。因此,哪个进程运行的时间最少,应该让哪个进程运行。

                                 NICE_0_LOAD
vriture_runtime = wall_time * ----------------
                                    weight 

1024权重对应nice值为0,其权重被称为NICE_0_LOAD。默认情况下,大部分进程的权重基本都是NICE_0_LOAD。

进程A的虚拟时间3.3 * 1024 / 1024 = 3.3ms,我们可以看出nice值为0的进程的虚拟时间和实际时间是相等的。进程B的虚拟时间是2.7 * 1024 / 820 = 3.3ms。我们可以看出尽管A和B进程的权重值不一样,但是计算得到的 虚拟时间是一样的。因此CFS主要保证每一个进程获得执行的虚拟时间一致即可。在选择下一个即将运行的进程的时候,只需要找到虚拟时间最小的进程即可。为了避免浮点数运算因此我们采用先放大再缩小的方法以保证计算精度。内核又对公式做了如下转换。

                                 NICE_0_LOAD
vriture_runtime = wall_time * ----------------
                                    weight
  
                                   NICE_0_LOAD * 2^32
                = (wall_time * -------------------------) >> 32
                                        weight
                                                                                        2^32
                = (wall_time * NICE_0_LOAD * inv_weight) >> 32        (inv_weight = ------------ )
                                                                                        weight 




//右移一位除2

权重的值已经计算保存到sched_prio_to_weight数组中,根据这个数组我们可以很容易计算inv_weight的值。内核中使用sched_prio_to_wmult数组保存inv_weight的值。计算公式是:sched_prio_to_wmult[i] = 232/sched_prio_to_weight[i]。

笔记:这样得到的是inv_weight,虚拟时间后面计算就可以(wall_time * NICE_0_LOAD * inv_weight) >> 32 

const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
}; 

系统中使用struct load_weight结构体描述进程的权重信息。weight代表进程的权重,inv_weight等于232/weight。

struct load_weight {
	unsigned long		weight;
	u32			inv_weight;
}; 

实际时间转换成虚拟时间的实现函数是calc_delta_fair()。calc_delta_fair()调用__calc_delta()函数,__calc_delta()主要功能是实现如下公式的计算。

__calc_delta() = (delta_exec * weight * lw->inv_weight) >> 32
 
                                  weight                                 2^32
               = delta_exec * ----------------    (lw->inv_weight = --------------- )
                                lw->weight                             lw->weight 

和上面计算虚拟时间计算公式对比发现。如果需要计算进程的虚拟时间,这里的weight只需要传递参数NICE_0_LOAD,lw参数是进程对应的struct load_weight结构体。

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
	u64 fact = scale_load_down(weight);
	int shift = 32;
 
	__update_inv_weight(lw);
 
	if (unlikely(fact >> 32)) {
		while (fact >> 32) {
			fact >>= 1;
			shift--;
		}
	}
 
	fact = (u64)(u32)fact * lw->inv_weight;
 
	while (fact >> 32) {
		fact >>= 1;
		shift--;
	}
 
	return mul_u64_u32_shr(delta_exec, fact, shift);
} 

按照上面说的理论,calc_delta_fair()函数调用__calc_delta()的时候传递的weight参数是NICE_0_LOAD,lw参数是进程对应的struct load_weight结构体。

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
	if (unlikely(se->load.weight != NICE_0_LOAD))             /* 1 */
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);  /* 2 */
 
	return delta;
} 
  • 按照之前的理论,nice值为0(权重是NICE_0_LOAD)的进程的虚拟时间和实际时间是相等的。因此如果进程的权重是NICE_0_LOAD,进程对应的虚拟时间就不用计算。
  • 调用__calc_delta()函数。

Linux通过struct task_struct结构体描述每一个进程。但是调度类管理和调度的单位是调度实体,并不是task_struct。在支持组调度的时候,一个组也会抽象成一个调度实体,它并不是一个task。所以,我们在struct task_struct结构体中可以找到以下不同调度类的调度实体。

struct task_struct {
         struct sched_entity		se;
	struct sched_rt_entity		rt;
	struct sched_dl_entity		dl;
    /* ... */
} 

se、rt、dl分别对应CFS调度器、RT调度器、Deadline调度器的调度实体。

struct sched_entity结构体描述调度实体,包括struct load_weight用来记录权重信息。除此以外我们一直关心的时间信息,肯定也要一起记录。struct sched_entity结构体简化后如下:

struct sched_entity {
	struct load_weight		load;
	struct rb_node		run_node;
	unsigned int		on_rq;
	u64			sum_exec_runtime;
	u64			vruntime;
}; 
  • load:权重信息,在计算虚拟时间的时候会用到inv_weight成员。
  • run_node:CFS调度器的每个就绪队列维护了一颗红黑树,上面挂满了就绪等待执行的task,run_node就是挂载点。
  • on_rq:调度实体se加入就绪队列后,on_rq置1。从就绪队列删除后,on_rq置0。
  • sum_exec_runtime:调度实体已经运行实际时间总合。
  • vruntime:调度实体已经运行的虚拟时间总合。

就绪队列(runqueue)

系统中每个CPU都会有一个全局的就绪队列(cpu runqueue),使用struct rq结构体描述,它是per-cpu类型,即每个cpu上都会有一个struct rq结构体。每一个调度类也有属于自己管理的就绪队列。例如,struct cfs_rq是CFS调度类的就绪队列,管理就绪态的struct sched_entity调度实体,后续通过pick_next_task接口从就绪队列中选择最适合运行的调度实体(虚拟时间最小的调度实体)。struct rt_rq是实时调度器就绪队列。struct dl_rq是Deadline调度器就绪队列。

struct rq {
         struct cfs_rq cfs;
	struct rt_rq rt;
	struct dl_rq dl;
};
 
struct rb_root_cached {
	struct rb_root rb_root;
	struct rb_node *rb_leftmost;
};
 
struct cfs_rq {
	struct load_weight load;
	unsigned int nr_running;
	u64 min_vruntime;
	struct rb_root_cached tasks_timeline;
}; 
  • load:就绪队列权重,就绪队列管理的所有调度实体权重之和。
  • nr_running:就绪队列上调度实体的个数。
  • min_vruntime:跟踪就绪队列上所有调度实体的最小虚拟时间。
  • tasks_timeline:用于跟踪调度实体按虚拟时间大小排序的红黑树的信息(包含红黑树的根以及红黑树中最左边节点)。

红黑树:

能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)

红黑树是牺牲了严格的高度平衡的优越条件为代价,它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。

为什么要用红黑树:CFS使用红黑树主要还是调度是一个动态的东西,完全静态就用散列表了

CFS维护了一个按照虚拟时间排序的红黑树,所有可运行的调度实体按照p->se.vruntime排序插入红黑树。如下图所示。

CFS选择红黑树最左边的进程运行。随着系统时间的推移,原来左边运行过的进程慢慢的会移动到红黑树的右边,原来右边的进程也会最终跑到最左边。因此红黑树中的每个进程都有机会运行。

现在我们总结一下。Linux中所有的进程使用task_struct描述。task_struct包含很多进程相关的信息(例如,优先级、进程状态以及调度实体等)。但是,每一个调度类并不是直接管理task_struct,而是引入调度实体的概念。CFS调度器使用sched_entity跟踪调度信息。CFS调度器使用cfs_rq跟踪就绪队列信息以及管理就绪态调度实体,并维护一棵按照虚拟时间排序的红黑树。tasks_timeline->rb_root是红黑树的根,tasks_timeline->rb_leftmost指向红黑树中最左边的调度实体,即虚拟时间最小的调度实体(为了更快的选择最适合运行的调度实体,因此rb_leftmost相当于一个缓存)。每个就绪态的调度实体sched_entity包含插入红黑树中使用的节点rb_node,同时vruntime成员记录已经运行的虚拟时间。我们将这几个数据结构简单梳理,如下图所示。

 

 

学习博客:https://www.cnblogs.com/linhaostudy/p/10298511.html

                  https://blog.csdn.net/liuxiaowu19911121/article/details/47010721

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_42269817/article/details/108229723

智能推荐

Java编程:删除 List 元素的三种正确方法_java synchronized list 元素删除-程序员宅基地

文章浏览阅读942次。删除 List 中的元素会产生两个问题:删除元素后 List 的元素数量会发生变化;对 List 进行删除操作可能会产生并发问题;_java synchronized list 元素删除

D语言游戏编程(11):D语言基础之模板和混入(mixin)技术_d语言 模板实例化-程序员宅基地

文章浏览阅读3.7k次。 D语言通过模板,很好的支持泛型编程。与C++的模板相比较,各有优略。总体上说,D语言的模板在很多方面还是很方便的。 D语言还支持模板的混入(mixin),简单的讲就是把模板实例化之后,将模板中的代码插入到当前的位置。这是一个非常方便的工具! 具体的,请看下面的演示代码。import std.stdio;void main()...{ tryTemplate();_d语言 模板实例化

目标 linux 服务器提权,史上最全Linux提权后获取敏感信息方法 (zhuan)-程序员宅基地

文章浏览阅读364次。(Linux)的提权是怎么一回事:收集 – 枚举,枚举和一些更多的枚举。过程 – 通过数据排序,分析和确定优先次序。搜索 – 知道搜索什么和在哪里可以找到漏洞代码。适应 – 自定义的漏洞,所以它适合。每个系统的工作并不是每一个漏洞“都固定不变”。尝试 – 做好准备,试验和错误。系统类型系统是什么版本?cat /etc/issuecat /etc主机上有哪些工作计划?crontab -lls -al..._linux服务器被提权如何解决

Device token 什么时候会发生变化_苹果手机恢复出厂设置token会不会变-程序员宅基地

文章浏览阅读5.8k次。stackoverflow 针对Device token 什么时候会发生变化有个很棒的解答。在一台设备中, device token 是系统级别的,不同 App 获得的 device token 是相同的。假如我的手机安装了 Angry Bird 和 Evernote ,这两个应用获得 device token 一模一样。device token 并不会因为单个 app 的_苹果手机恢复出厂设置token会不会变

IO流——文件操作流之字符输入流FileReader-程序员宅基地

文章浏览阅读1.9k次。package com.io.ioDemo;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;//字符流读文件public class FileReaderDemo { public static void mai_字符输入流filereader

Linux深入理解_深入理解linux系统-程序员宅基地

文章浏览阅读1.8w次,点赞14次,收藏12次。一、背景: 翻看着差不多去年这时候写的《痴迷Linux(一)—初识篇》不禁感慨时光飞逝,转眼间已一年闪过。。。回想这一年与Linux交往之路,发现与她也仅仅是停留在表面上的!回想原因:自己现在还没到和她深交的阶段(正所谓距离产生美嘛)同时由于一些原因(比如:这次实训、装服务器等)自己也并一直和她有来往。 这次实训是学校为大三计算机专业安排历时三天;主要讲课内容: ①..._深入理解linux系统

随便推点

RDD与DataFrame与Dataset之间的关系及转换关系_dataframe、dataset、rdd之间的转换-程序员宅基地

文章浏览阅读403次。RDD与DataFrame与Dataset之间的转换关系:_dataframe、dataset、rdd之间的转换

关系型数据库和非关系型数据库的区别与联系_谈谈关系型数据库与非关系型数据库的联系和区别-程序员宅基地

文章浏览阅读2.2k次。数据库一、概念数据库是以一定方式储存在一起、能与多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。数据库管理系统是一种操纵和管理数据库的大型软件,用于建立、使用和维护数据库,简称DBMS。它对数据库进行统一的管理和控制,以保证数据库的安全性和完整性。二、分类关系型数据库NOSQL三、NoSQL与关系型数据库的区别存储方式传统的关系型数..._谈谈关系型数据库与非关系型数据库的联系和区别

基于Eureka的微服务注册与使用_eureka注册其他机器的微服务-程序员宅基地

文章浏览阅读253次。承接上一章,项目还是使用之前的两个已经创建好的spring boot项目!这一节主要是学习Eureka的注册和使用!跟上一章一样,我们在父模块下继续创建一个module,这次创建一个Eureka项目!第一,先创建一个Eureka项目,并成功启动1,new module2,创建一个Eureka项目,跟上一节有一点点的小区别,注意一下3,直接下一步下一步到结束,完了删除多余的文..._eureka注册其他机器的微服务

VCS dump 波形的函数_vcs $dumpports-程序员宅基地

文章浏览阅读2.1k次。当使用VCS 仿真是,如果需要dump 波形,可以使用:1,fsdbdumpfile xxx.fsdb或者使用fsdbAutoSwitchDumpfile < size> name < barksize>2, 通过fsdbDumpvars < depth> 设置波形深度,默认设置0 全dump;_vcs $dumpports

XamarinAndroid组件教程设置自定义子元素动画(一)_xamarin imageview 动画-程序员宅基地

文章浏览阅读202次。XamarinAndroid组件教程设置自定义子元素动画(一)如果在RecyclerViewAnimators.Animators中没有所需要的动画效果,就可以自定义一个。此时,需要让自定义的动画继承BaseItemAnimator抽象类。【示例1-2】下面以RecylerViewAnimatorsItemAnimator项目为基础,在RecylerView子元素进行添加/删除操作时,实现透明动画..._xamarin imageview 动画

【BZOJ】【P2395】【Balkan 2011】【Timeismoney】【题解】【最小乘积生成树】_最小乘积生成树 注释-程序员宅基地

文章浏览阅读1.3k次。传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2395其实还不太会写……Code:#include#include#includeusing namespace std;typedef long long LL;struct edge{ int u,v,w,c,t; bool operator<(const edg_最小乘积生成树 注释

推荐文章

热门文章

相关标签