技术标签: 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(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
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;
}
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;
};
系统中每个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;
};
红黑树:
能保证在最坏情况下,基本的动态几何操作的时间均为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
文章浏览阅读942次。删除 List 中的元素会产生两个问题:删除元素后 List 的元素数量会发生变化;对 List 进行删除操作可能会产生并发问题;_java synchronized list 元素删除
文章浏览阅读3.7k次。 D语言通过模板,很好的支持泛型编程。与C++的模板相比较,各有优略。总体上说,D语言的模板在很多方面还是很方便的。 D语言还支持模板的混入(mixin),简单的讲就是把模板实例化之后,将模板中的代码插入到当前的位置。这是一个非常方便的工具! 具体的,请看下面的演示代码。import std.stdio;void main()...{ tryTemplate();_d语言 模板实例化
文章浏览阅读364次。(Linux)的提权是怎么一回事:收集 – 枚举,枚举和一些更多的枚举。过程 – 通过数据排序,分析和确定优先次序。搜索 – 知道搜索什么和在哪里可以找到漏洞代码。适应 – 自定义的漏洞,所以它适合。每个系统的工作并不是每一个漏洞“都固定不变”。尝试 – 做好准备,试验和错误。系统类型系统是什么版本?cat /etc/issuecat /etc主机上有哪些工作计划?crontab -lls -al..._linux服务器被提权如何解决
文章浏览阅读5.8k次。stackoverflow 针对Device token 什么时候会发生变化有个很棒的解答。在一台设备中, device token 是系统级别的,不同 App 获得的 device token 是相同的。假如我的手机安装了 Angry Bird 和 Evernote ,这两个应用获得 device token 一模一样。device token 并不会因为单个 app 的_苹果手机恢复出厂设置token会不会变
文章浏览阅读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
文章浏览阅读1.8w次,点赞14次,收藏12次。一、背景: 翻看着差不多去年这时候写的《痴迷Linux(一)—初识篇》不禁感慨时光飞逝,转眼间已一年闪过。。。回想这一年与Linux交往之路,发现与她也仅仅是停留在表面上的!回想原因:自己现在还没到和她深交的阶段(正所谓距离产生美嘛)同时由于一些原因(比如:这次实训、装服务器等)自己也并一直和她有来往。 这次实训是学校为大三计算机专业安排历时三天;主要讲课内容: ①..._深入理解linux系统
文章浏览阅读403次。RDD与DataFrame与Dataset之间的转换关系:_dataframe、dataset、rdd之间的转换
文章浏览阅读2.2k次。数据库一、概念数据库是以一定方式储存在一起、能与多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。数据库管理系统是一种操纵和管理数据库的大型软件,用于建立、使用和维护数据库,简称DBMS。它对数据库进行统一的管理和控制,以保证数据库的安全性和完整性。二、分类关系型数据库NOSQL三、NoSQL与关系型数据库的区别存储方式传统的关系型数..._谈谈关系型数据库与非关系型数据库的联系和区别
文章浏览阅读253次。承接上一章,项目还是使用之前的两个已经创建好的spring boot项目!这一节主要是学习Eureka的注册和使用!跟上一章一样,我们在父模块下继续创建一个module,这次创建一个Eureka项目!第一,先创建一个Eureka项目,并成功启动1,new module2,创建一个Eureka项目,跟上一节有一点点的小区别,注意一下3,直接下一步下一步到结束,完了删除多余的文..._eureka注册其他机器的微服务
文章浏览阅读2.1k次。当使用VCS 仿真是,如果需要dump 波形,可以使用:1,fsdbdumpfile xxx.fsdb或者使用fsdbAutoSwitchDumpfile < size> name < barksize>2, 通过fsdbDumpvars < depth> 设置波形深度,默认设置0 全dump;_vcs $dumpports
文章浏览阅读202次。XamarinAndroid组件教程设置自定义子元素动画(一)如果在RecyclerViewAnimators.Animators中没有所需要的动画效果,就可以自定义一个。此时,需要让自定义的动画继承BaseItemAnimator抽象类。【示例1-2】下面以RecylerViewAnimatorsItemAnimator项目为基础,在RecylerView子元素进行添加/删除操作时,实现透明动画..._xamarin imageview 动画
文章浏览阅读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_最小乘积生成树 注释