加载中……
Linux进程调度的实现

算法

Linux调度算法迭代大致有三种:

 

O(n)调度:在每次进程切换时,内核依次扫描就绪队列上的每一个进程,计算每个进程的优先级,再选择出优先级最高的进程来运行,花费的时间相对较大,时间复杂度为O(n);

O(1)调度:在数据结构设计上采用了一个优先级数组,进程采用两个优先级,一个是静态优先级,一个是动态优先级。静态优先级是用来计算进程运行的时间片长度的,动态优先级是在调度器进行调度时用到的,调度器每次都选取动态优先级最高的进程运行。

CFS公平调度:这里涉及到思考对象的转变,不再一味强调进程本身的优先级,而是面向CPU资源,通过计算进程占用CPU的相对时间来调度进程,且占用CPU时间最少的,拥有最先被调度的权利。

 

本文主要围绕CFS调度算法展开学习。

CFS公平调度

两个因素

  1. 权重:进程根据nice值获得权重,nice值范围为[-20,+20],值越小,权重越大
  2. 实际运行时间:进程已经运行的时间(CPU占用时间)。

两个公式

  • 分配给进程的运行时间 = 调度周期 * 进程权重 / 所有进程权重之和
  • 虚拟运行时间(vruntime) = 实际运行时间 * 1024 / 进程权重

虚拟运行时间(vruntime)是系统对CPU资源占用的标准化,也是系统调用的主要依据,如若一个进程的vruntime值最小,则代表它消耗的CPU资源最少,讲享有最高的调度权利。

即:假设两个进程A,B,权重分别为1和2,假设调度周期设为30ms,那么分配给A的CPU时间为:30ms * (1/(1+2)) = 10ms;而B的CPU时间为:30ms * (2/(1+2)) = 20ms。那么在这30ms中A将运行10ms,B将运行20ms。再这之后,A的vruntime = 10*1024/1,B的vruntime = 20*1024/2,在下个周期时两个进程的调度权限等同。这里,即满足了重要进程的效率,又满足了调度层面的公平公正原则,大大降低了进程饿死情况的出现。

其他细节

  • 新进程的默认vruntime为min_vruntime。
  • 进程从休眠状态唤醒,会以min_vruntime为基础,获得一定的vruntime补偿。防止持续抢占CPU。
  • 进程
  • 因为不同CPU的min_vruntime不同,进程从一个CPU转移到另一个CPU时会进行min_vruntime修正:减去原先的min_vruntime,加上现在的min_vruntime。
  • CFS设定了进程占用CPU的最小时间值,sched_min_granularity_ns。

调度的实现

时间记账

所有的调度器都必须对进程运行时间做记账。多数Unix系统,会分配一个时间片给每一个进程。那么当每次系统时钟节拍发生时,时间片都会被减少一个节拍周期。当一个进程的时间片被减少到0时,它就会被另一个尚未减到0的时间片可运行进程抢占。

CFS使用调度器实体结构来跟踪进程运行记账,嵌入在进程描述符中,结构体为sched_entity。

另,如前面提到的,CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久,在update_curr()函数中实现了该记账功能。

进程选择

即CFS使用红黑树来组织可运行进程队列,并利用其迅速找到最小vruntime值的进程。在Linux中,红黑树称为rbtree,它是一个自平衡二叉搜索树。红黑树是一种以树节点形式存储的数据,这些数据都会对应一个键值。我们可以通过这些键值来快速检索节点上的数据(重要的是,通过键值检索到对应节点的速度与整个树的节点规模成指数比关系)。

 

不急,被红黑树吸引到了,先去学习红黑树去了…嘿嘿,嘿嘿嘿

版权声明: 若无特殊说明,文章均为原创,版权归本文作者所有,转载请保留出处和此说明!
本文链接: Linux进程调度的实现
本文作者: Jan.
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇