调度器 schedule pelt 介绍【转】

转自:https://blog.csdn.net/liglei/article/details/82896765

  • 进程类型
    交互是进程:人机交互进程,如鼠标键盘,触摸屏,系统响应越快越好
    批处理进程:占用较多系统资源,如编译代码
    实时进程:对延时有严格要求
     
  • 调度策略与调度器
    用户进程的调度策略  调度器
    SCHED_NORMAL   cfs
    SCHED_BATCH    cfs
    SCHED_FIFO     realtime
    SCHED_RR      realtime
    SCHED_IDLE     idle
    SCHED_DEADLINE  deadline
     
  • 内核中进程的权重
    struct load_weight {
    unsigned long weight; //prio_to_weight[40]
    u32 inv_weight; //prio_to_wmult[40]
    };
     
  • 用户空间nice值、内核进程优先级和权重关系

调度器 schedule pelt 介绍【转】

prio 动态优先级 0~139 调度器最终使用的优先级值 

 

static const int 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, 
};
static const u32 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,
};

prio_to_wmult[i]=2^32/prio_to_weight[i]

nice_0_weight =1024, 每降低一个nice级别,优先级提高一个级别,相应进程多获得10% cpu时间;每升高一个nice级别,优先级降低一个级别,相应进程少获得10% cpu时间。如A和B进程的nice值为0,权重都是1024,各获得50%的cpu时间。如果A进程增加一个nice值,权重变为820,B进程nice不变,权重不变,则A进程获得cpu时间:820/(1024+820)≈44.5%,B进程获得cpu时间:1024/(1024+820)≈55.5%。cpu时间差约为10%
 

  • vruntime

在2.6.23版本引入cfs调度算法,引入虚拟时间:
vruntime = delta_exec * nice_0_weight / weight
OR
vruntime = (delta_exec * (nice_0_weight * inv_weight)) >> 32


nice_0_weight = 1024
weight = prio_to_weight[i]
inv_weight = prio_to_wmult[i]
inv_weight = 2^32/weight

进程优先级越大,进程权重weight值越大,对比经过实际运行时间来说,虚拟时间增长越慢(越小);cfs中的就绪队列以vruntime为键值的红黑树,按虚拟时间从小到大排序,虚拟时间最小的进程最先被调度,相互追赶,以达到虚拟运行时间相同的目的。因而优先级越大的进程,scale到真实时钟的时间更长,也可以理解为按weight比重给进程分配cpu时间。
 

  • 为什么引入PELT算法?
    调度算法需要尽量准确的推测每个进程对系统的需求,才能更好的完成调度任务。因此,只能通过进程过去的调度信息-即主要是进程的历史负载,作为该进程未来对CPU需求的依据。
    3.8版本之前的内核CFS调度器在计算CPU load的时候采用的是跟踪每个运行队列上的负载(per-rq load tracking)需要注意的是:CFS中的“运行队列”实际上是有多个,至少每个CPU就有一个runqueue。而且,当使用“按组调度”( group scheduling)功能时,每个控制组(control group)都有自己的per-CPU运行队列。对于per-rq的负载跟踪方法,调度器可以了解到每个运行队列对整个系统负载的贡献。这样的统计信息足以帮助组调度器(group scheduler)在控制组之间分配CPU时间,但从整个系统的角度看,我们并不知道当前负载来自何处。除此之外,per-rq的负载跟踪方法还有另外一个问题,即使在工作负载相对稳定的情况下,跟踪到的运行队列的负载值也会变化很大。

    per-entity load tracking有什么好处?
    有了Per-entity负载跟踪机制,在没有增加调度器开销的情况下,调度器现在对每个进程和“调度进程组”对系统负载的贡献有了更清晰的认识。有了更精细的统计数据(指per entity负载值)通常是好的,但人们可能会怀疑这些信息是否真的对调度器有用。
    我们可以通过跟踪的per entity负载值做一些有用的事情。最明显的使用场景可能是用于负载均衡:即把runnable进程平均分配到系统的CPU上,使每个CPU承载大致相同的负载。如果内核知道每个进程对系统负载有多大贡献,它可以很容易地计算迁移到另一个CPU的效果。这样进程迁移的结果应该更准确,从而使得负载平衡不易出错。目前已经有一些补丁利用per entity负载跟踪来改进调度器的负载均衡,相信这些补丁会在不久的将来进入到内核主线。
    small-task packing patch的目标是将“小”进程收集到系统中的部分CPU上,从而允许系统中的其他处理器进入低功耗模式。在这种情况下,显然我们需要一种方法来计算得出哪些进程是“小”的进程。利用per-entity load tracking,内核可以轻松的进行识别。
    内核中的其他子系统也可以使用per entity负载值做一些“文章”。CPU频率调节器(CPU frequency governor)和功率调节器(CPU power governor)可以利用per entity负载值来猜测在不久的将来,系统需要提供多少的CPU计算能力。既然有了per-entity load tracking这样的基础设施,我们期待看到开发人员可以使用per-entity负载信息来优化系统的行为。虽然per-entity load tracking仍然不是一个能够预测未来的水晶球,但至少我们对当前的系统中的进程对CPU资源的需求有了更好的理解。

    参考文章:http://www.wowotech.net/process_management/PELT.html
     
  • task负载描述符-struct sched_avg{}

调度器 schedule pelt 介绍【转】 

 

  • Linux kernel v3.8
    sched_avg->runnable_avg_sum:调度实体在就绪队列里可运行状态下总的衰减累加时间
    sched_avg->runnable_avg_period:调度实体在系统中总的衰减累加时间
    sched_avg->load_avg_contrib:进程平均负载的贡献度
    cfs_rq->runnable_load_avg:用于累加在该就绪队列上所有调度实体的load_avg_contrib总和,在smp负载均衡调度器中用于衡量CPU是否繁忙
    task负载计算:load_avg_contrib=runnable_avg_sum*weight/runnable_avg_period
     
  • Linux kernel v4.18
    struct sched_avg {
    u64 last_update_time
    u64 load_sum 
    u64 runnable_load_sum
    u32 util_sum
    u32 period_contrib
    unsigned long load_avg
    unsigned long runnable_load_avg
    unsigned long util_avg
    struct util_est util_est
    } ___cacheline_aligned

    load_sum: 调度实体衰减累加负载
    load_avg: 调度实体的平均负载 
    runnable_load_sum:调度实体在runnable时的衰减累加负载
    runnable_load_avg: 调度实体在runnable时的平均负载

    PELT代码在v4.18.rc5之后单独迁移到kernel/sched/pelt.c文件中
     
  • 调度实体负载总和
    进程运行的时间横轴,以1ms为一个period周期,Li是一个调度实体在i个时间周期内的负载,虽然进程已经又运行了i个周期,它对当前系统负载仍有贡献 Li*y^i,y是衰减系数, y^32=0.5,距离当前时间点越远,衰减系数越大,对调度实体总的负载影响越小。
    统计多个PI周期内调度实体对系统负载的贡献 L=L0+L1*y+L2*y^2+L3*y^3+......L32*y^32+...... (y^32=0.5

调度器 schedule pelt 介绍【转】
   调度实体某一个历史period周期的负载,每经过32ms,都会衰减一半,后边也使用此方法计算经过32ms整数倍的负载衰减。

 

  • 衰减因子

[kernel/sched/sched-pelt.h]
static const u32 runnable_avg_yN_inv[] = { 
0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6, 
0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581, 
0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9, 
0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80, 
0x85aac367, 0x82cd8698, 
};
runnable_avg_yN_inv[i]=(2^32-1) * y^i
y^32=1/2
i=0~31
y~=0.9785

Static const u32 runnable_avg_yN_org[] = {
0.999, 0.978, 0.957, 0.937, 0.917, 0.897,
……
0.522, 0.510
}
runnable_avg_yN_org[i]=runnable_avg_yN_inv[i]>>32

 

  • 计算第n个周期的衰减值

static u64 decay_load(u64 val, u64 n)
val表示n个周期前的负载值,n表示第n个周期
t0时刻负载为val,t1时刻,红色历史时间区域衰减负载值是:val*y^n=val* runnable_avg_yN_inv[n]>>32

调度器 schedule pelt 介绍【转】 

 

  • 查询连续n个周期的累加衰减负载(1<=n<=32)[v4.12中删除 (05296e7535)]

static const u32 runnable_avg_yN_sum[] = { 
0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103, 9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082, 17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
};
runnable_avg_yN_sum[n]=1024*(y^1+y^2+y^3+……+y^n)
1024:1ms 
period=1024us
y~=0.9785; y^32=1/2

调度器 schedule pelt 介绍【转】 

 

  • task负载计算:

 *           d1          d2           d3
 *           ^           ^            ^
 *           |           |            |
 *         |<->|<----------------->|<--->|
 * ... |---x---|------| ... |------|-----x (now)
 *
 *                                          p-1
 * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
 *                                          n=1
 *     = u y^p +   (Step 1)
 *              p-1
 *        d1 y^p + 1024 \Sum y^n + d3 y^0   (Step 2)
 *              n=1

 
  *                    p-1
  * c2 = 1024 \Sum y^n
  *                    n=1
  *
  *                    inf              inf
  *    = 1024 ( \Sum y^n - \Sum y^n - y^0 )
  *                    n=0            n=p

 

调度器 schedule pelt 介绍【转】 

u´= (u+delta1)*y^p + 1024* (y^1+y^2+……+y^(p-1))  + delta3*y^0

   = u*y^p + delta1*y^p + 1024* (y^1+y^2+……+y^(p-1))  + delta3*y^0

   = decay_load(u, p)+ decay_load(delta1, p)+ LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, p)-1024 + delta3

由此可见,进程负载=历史负载衰减+本次更新的负载累加衰减=udecay+contrib

LOAD_AVG_MAX=47742= 1024+1024*y+1024*y^2+……+y^n+…+y^inf  (n>345)

LOAD_AVG_MAX=1024+1024* (y^1+y^2+…+y^(p-1)) + 1024* (y^p+…+y^inf)

1024* (y^p+…+y^inf) =1024*y^p(1+y+y^2+…+y^inf)=y^p*LOAD_AVG_MAX=decay_load(LOAD_AVG_MAX, p)

load_avg = load.weight * load_sum/(LOAD_AVG_MAX-1024+period_contrib)

runnable_load_avg = runnable_weight * runnable_load_sum/(LOAD_AVG_MAX-1024+period_contrib)

util_avg=util_sum/(LOAD_AVG_MAX-1024+period_contrib)

  • task负载计算实例

 调度器 schedule pelt 介绍【转】

 

divider = LOAD_AVG_MAX - 1024 + sa->period_contrib

t1时刻平均负载的计算:

load_avg={decay(t0) + contrib(t1-t0)*weight}/divider
runnable_load_avg={decay(t0) + contrib(t1-t0)*weight}/divide
util_avg={decay(t0) + contrib(t1-t0)*weight}/divider

t2时刻平均负载的计算:

load_avg={decay(t1) + contrib(t2-t1)*weight}/divider
runnable_load_avg={decay(t1) + contrib(t2-t1)*weight}/divider
util_avg=decay(t0) /divider  (contrib=0)

t4时刻平均负载的计算:

load_avg=decay(t3)/divider
runnable_load_avg=decay(t3)/divider
util_avg=decay(t3) /divider

 

  • task与cfs-rq平均负载的计算 调度器 schedule pelt 介绍【转】

 

  • Question:

V4.15-rc1 Commit: 1ea6c46a23 对task平均负载的计算发生了变化:

se->avg=

上一篇:MongoDB聚合(aggregate)


下一篇:SQL查询小案例