深入理解Linux内核进程的创建、调度和终止（下）-阿里云开发者社区

三、进程调度

3.1吞吐率和响应

吞吐：单位时间内做的有用功；

响应：低延迟

吞吐追求的整个系统CPU做有用功，响应追求的是某个特定任务的延迟低；

1GHZ的CPU切换线程保存恢复现场约几个微妙级别，看似消耗不了太多时间，但是由于系统的局部性原理，会保存当前线程数据的缓存，切换线程会打乱局部性引起cache miss，而CPU访问cache速度远大于内存访问，这样综合看来上下文切换花销还是很大的。无用功占用较多CPU；

追求吞吐量和低延迟，这两个目标是矛盾的

编译内核选项有如下：

服务器版追求吞吐量，配置为不抢占，桌面版或手机更追求响应，配置为低延迟。调度器一般讲的是最后一种，低延迟抢占。

3.2Linux任务类型

问题2: 一个典型的系统内任务分两种：CPU消耗型和IO消耗型

CPU型的任务，通常要求高性能，但是不追求低延迟，优先级较低；

IO型的任务，通常优先级更高，追求低延迟，对CPU性能不敏感；

如下图，一个读IO循环过程，占用CPU时间极短（1ms），IO占用100ms，若CPU性能降一倍，执行CPU占用2ms对整体时间影响不大(总时间102ms)；但是如果CPU不能及时响应，一个读写周期响应延迟100ms，那整体时间变为约200ms，整体性能降低一半；

所以，IO型任务只关注响应速度，对CPU性能不敏感，基于此原理ARM公司设计了big.LITTLE架构，比如在手机上有8个核，设计为四大核，四小核；大小核指令集完全兼容，调度器调配IO型的任务跑在小核上(对CPU弱不敏感)，CPU型任务放在大核上跑。这样用4+1(四小核等效)核的功耗实现了8核的性能；

调度器要在吞吐和延迟之间找到某个均衡。

3.3任务调度

1）调度原理

涉及两个概念，策略和优先级；

内核所有进程优先级为0~139之间；

0~99：采用RT策略，常用的有SCHED_FIFO, SCHED_RR;

SCHED_FIFO, 属于霸占型的，高优先级执行完，才会执行低优先级；

SCHED_RR, 不同优先级与CHED_FIFO相同，属于霸占型，同等优先级轮转；

比如有4个进程：P1_FIFO_3, P2_CHED_RR_2, P3_CHED_RR_2, P4_FIFO_4

执行过程，P2/P3轮转执行完之后，执行P1, 最后执行P4。

100~139：普通线程，采用非RT策略，对应nice(-20, 19).

这里所有优先级都是可以抢占的，但nice 值越低，分配CPU资源越多。

2）所有调度，SCHER_FIFO/SCHER_RR或设置nice都是针对task_struct

3）将进程设置为FIFO策略:

修改进程25020的策略为FIFO, 优先级50

sudo chrt –f –a –p 50 25020

这样进程是按FIFO策略调度，占有CPU最高为80%(普通进程可以接近100%)，CPU占有率降低(但不可抢占)，此时IO延迟反而变大，鼠标操作变慢；

设置FIFO线程api

内核里优先级=99-50=49，内核态数字越低，优先级越高；用户态相反；

4）每个task_struct的nice都可以单独设置(所有普通线程)；

Nice值设置都是指普通线程，RT策略不支持nice

nice()默认是0，调度，在不同nice值进程间轮转，2.6早期内核对进程采取奖励和惩罚算法，越睡眠越奖励，越消耗CPU，越惩罚，动态调整nice值，实现极其复杂，后来升级两个补丁。

补丁1：RT熔断机制，设置rt门限值

默认runtime 0.95s，period 1s,1s内RT最多跑了0.95s自动熔断；

$cd /proc/sys/kernel
sudo sh -c ‘echo 800000 > sched_rt_runtime_us’

设置RR/FIFO策略熔断最高位800ms，RR/FIFO策略进程最多占用CPU 80%。(默认是95%)

补丁2：普通进程调度算法CFS（complete fare schedule）

虚拟运行时间，vtime = ptime * 1024/weight

ptime：物理时间

weight:权重参数

nice=0，虚拟时间等于物理时间；

nice值越小，对应weight分母越大，vtime增长越慢，实际对应ptime占用越多；

vtime机制很好的平衡了I/O型，CPU型任务；

I/O型喜欢睡眠，ptime比较小，所以vtime自然较小，会偏向于挂在树左边；

同理，优先级越高的CPU型，其weight值越大，vtime也会越小，亦偏向挂载树左边；

即CFS用很简单的方式实现了历史上复杂的睡眠补偿，消耗惩罚，动态调整等功能；

修改进程的nice值：

sudo renice -n -5 -g 24856 //24856进程的所有线程nice都设置为-5

综上，linux调度算法过程：

1.首先执行SCHECH_RR/SCHECH_FIFO进程，待他们执行到睡眠或者熔断，CPU切换到普通线程；

2.普通线程按CFS算法调度，在普通线程间轮转；

线程调度优先与线程是否在内核态无关，只由优先级和策略决定。用户态内核态只涉及权限问题；

四、进程调度CFS算法实现分析

网上讲CFS的文章很多，可能版本不一，理解不尽相同。我以问题追溯方式，跟踪源码写下我对CFS的理解，有的问题我也还没理解透，欢迎对内核有兴趣的朋友一起交流学习，源码版本是与LKD3配套的Linux2.6.34

背景知识：

(1) Linux的调度器类主要实现两类进程调度算法：实时调度算法和完全公平调度算法(CFS)，实时调度算法SCHED_FIFO和SCHED_RR，按优先级执行，一般不会被抢占。直到实时进程执行完，才会执行普通进程。而大多数的普通进程，用的就是CFS算法。

(2) 进程调度的时机：

①进程状态转换时刻：进程终止、进程睡眠；
②当前进程的”时间片”用完；
③主动让出处理器，用户调用sleep()或者内核调用schedule()；
④从中断，系统调用或异常返回时；

(3) 每个进程task_struct中都有一个struct sched_entity se成员，这就是调度器的实体结构，进程调度算法实际上就是管理所有进程的这个se。

结构任务结构{
    挥发性长状态；    / * - 1 不可运行， 0 可以运行， > 0 已停止* /
    无效*堆栈；
    atomic_t 用法；
    无符号整型标志；    / *每个进程标志，定义如下* /
    无符号整型ptrace ；
    int锁深度；        / * BKL锁定深度* /
#ifdef CONFIG_SMP
#ifdef __ARCH_WANT_UNLOCKED_CTXSW
    int oncpu ;
＃万一
＃万一
    int prio , static_prio ,正常_prio ;
    无符号整数rt_priority ；
    const struct sched_class * sched_class ;
    struct sched_entity se; //进程调度实体
    结构 sched_rt_entity rt ；
    ……
}

CFS基于一个简单的理念：所有任务都应该公平的分配处理器。理想情况下，n个进程的调度系统中，每个进程获得1/n处理器时间，所有进程的vruntime也是相同的。

CFS完全抛弃了时间片的概念，而是分配一个处理器使用比来度量。每个进程一个调度周期内分配的时间(类似于传统的“时间片”)跟三个因素有关：进程总数，优先级，调度周期

4.1理解CFS的首先要理解vruntime的含义

简单说vruntime就是该进程的运行时间，但这个时间是通过优先级和系统负载等加权过的时间，而非物理时钟时间，按字面理解为虚拟运行时间，也很恰当。

每个进程的调度实体se都保存着本进程的虚拟运行时间。

结构sched_entity {
    struct load_weight 负载；        / * 用于负载均衡* / _
    结构 rb_node run_node ;
    struct list_head group_node ;
    无符号整型        on_rq ；
    u64 exec_start ；
    u64 sum_exec_runtime ；
    u64            vruntime; //虚拟运行时间
    u64 prev_sum_exec_runtime ;
……
}

而进程相关的调度方法如下：

静态常量结构 sched_class fair_sched_class = {
    。下一个            = & idle_sched_class ，
    。 enqueue_task         = enqueue_task_fair ,
    。出队任务        =出队任务公平,
    。产量任务        =产量任务公平，
    。 check_preempt_curr     = check_preempt_wakeup ,
    。 pick_next_task         = pick_next_task_fair ,
    。 put_prev_task         = put_prev_task_fair ,
#ifdef CONFIG_SMP
    。 select_task_rq         = select_task_rq_fair ，
    。 rq_online         = rq_online_fair ,
    。 rq_offline         = rq_offline_fair ,
    。任务唤醒        =任务唤醒公平，
＃万一
    。 set_curr_task = set_curr_task_fair ,
    。任务滴答        =任务滴答公平,
    。任务分叉        =任务分叉公平,
    。 prio_changed         = prio_changed_fair ,
    。 Switched_to         = Switched_to_fair ，
    。 get_rr_interval     = get_rr_interval_fair ,
#ifdef CONFIG_FAIR_GROUP_SCHED
    。任务移动组    =任务移动组公平,
＃万一
} ;

4.2vruntime的值如何跟新？

时钟中断产生时，会依次调用tick_periodic()-> update_process_times()->scheduler_tick()

无效调度程序_tick （无效）
{
……
    raw_spin_lock ( & rq- > lock ) ; _
    update_rq_clock ( rq ) ;
    update_cpu_load ( rq ) ;
    curr->sched_class->task_tick(rq, curr, 0); //执行调度器tick，更新进程vruntime
    raw_spin_unlock ( & rq- > lock ) ; _
……
}
task_tick_fair ()调用entity_tick()如下：
静态无效entity_tick （结构cfs_rq * cfs_rq ，结构sched_entity * curr ， int排队）
{
    update_curr ( cfs_rq ) ;
……
    if ( cfs_rq - > nr_running > 1 | | ! sched_feat ( WAKEUP_PREEMPT ) )
        check_preempt_tick(cfs_rq, curr); //检查当前进程是否需要调度
}

这里分析两个重要函数update_curr()和check_preempt_tick()

静态无效 update_curr (结构 cfs_rq * cfs_rq )
{
    struct sched_entity * curr = cfs_rq - > curr ;
    u64现在 = rq_of ( cfs_rq ) - >时钟;
    无符号长 delta_exec ；
    如果 （不太可能（！ curr ））
        返回；
// delta_exec获得最后一次修改后，当前进程所运行的实际时间
    delta_exec = ( unsigned long ) ( now - curr - > exec_start ) ;
    如果 （！ delta_exec ）
        返回；
    __update_curr ( cfs_rq , curr , delta_exec ) ;
    curr->exec_start = now; //运行时间已保存，更新起始执行时间
    如果 （ entity_is_task （当前）） {
        struct task_struct * curtask = task_of ( curr ) ;
        trace_sched_stat_runtime ( curtask , delta_exec , curr - > vruntime ) ;
        cpuacct_charge ( curtask , delta_exec ) ;
        account_group_exec_runtime ( curtask , delta_exec ) ;
    }
}

主要关心__update_curr()函数

静态内联 void __update_curr （ struct cfs_rq * cfs_rq ， struct sched_entity * curr ， unsigned long delta_exec ）
{
    无符号长 delta_exec_weighted ；
    schedstat_set ( curr - > exec_max , max ( ( u64 ) delta_exec , curr - > exec_max ) ) ;
    curr->sum_exec_runtime += delta_exec;//累计实际运行时间
    schedstat_add ( cfs_rq , exec_clock , delta_exec ) ;
    delta_exec_weighted = calc_delta_fair ( delta_exec , curr ) ; //对delta_exec加权
    curr->vruntime += delta_exec_weighted;//累计入vruntime
    update_min_vruntime(cfs_rq); //更新cfs_rq最小vruntime(保存所有进程中的最小vruntime)
}

关注calc_delta_fair()加权函数如何实现

/ *
 * δ / = w
 * /
静态内联无符号长整型
calc_delta_fair ( unsigned long delta , struct sched_entity * se )
{
    if (不太可能( se - > load .weight ! = NICE_0_LOAD ) )
        delta = calc_delta_mine ( delta , NICE_0_LOAD , & se - >负载) ;
    返回增量；
}

若当前进程nice为0，直接返回实际运行时间，其他所有nice值的加权都是以0nice值为参考增加或减少的。

/ *
 * delta * =重量/ lw
 * /
静态无符号长整型
calc_delta_mine (无符号长 delta_exec ,无符号长权重,
        结构 load_weight * lw )
{
    u64 tmp ；
    if ( ! lw - > inv_weight ) {
        if ( BITS_PER_LONG > 32 & &不太可能( lw - >权重> = WMULT_CONST ) )
            lw - > inv_weight = 1 ;
        别的
            lw- > inv_weight = 1 + ( WMULT_CONST - lw- >权重/ 2 ) _
                / (lw->weight+1);//这公式没弄明白
    }
    tmp = ( u64 ) delta_exec *权重；
    / *
     *检查64位乘法是否溢出：
     * /
    如果 （不太可能（ tmp > WMULT_CONST ））
        tmp = SRR ( SRR ( tmp , WMULT_SHIFT / 2 ) * lw - > inv_weight ,
            WMULT_SHIFT / 2 ) ;
    别的
        tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);//做四舍五入
    返回（无符号长）分钟（ tmp ， （ u64 ）（无符号长） LONG_MAX ）；
}

当nice!=0时，实际是按公式delta *= weight / lw来计算的weight=1024是nice0的权重，lw是当前进程的权重，该lw和nice值的换算后面介绍，上面还书的lw计算公式没弄明白，总之这个函数就是把实际运行时间加权为进程调度里的虚拟运行时间，从而更新vruntime。

更新完vruntime之后，会检查是否需要进程调度

返回 static voidentity_tick ( struct cfs_rq * cfs_rq , struct sched_entity * curr , int排队)
{
    update_curr ( cfs_rq ) ;
……
    if ( cfs_rq - > nr_running > 1 | | ! sched_feat ( WAKEUP_PREEMPT ) )
        check_preempt_tick(cfs_rq, curr); //检查当前进程是否需要调度
}

更新完cfs_rq之后，会检查当前进程是否已经用完自己的“时间片”

/ *
 *如果需要，用新唤醒的任务抢占当前任务：
 * /
静态无效
check_preempt_tick ( struct cfs_rq * cfs_rq , struct sched_entity * curr )
{
    无符号长的 Ideal_runtime ， delta_exec ；
    ideal_runtime = sched_slice(cfs_rq, curr);//ideal_runtime是理论上的处理器运行时间片    
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;//该进程本轮调度累计运行时间
    if (delta_exec > ideal_runtime) {// 假如实际运行超过调度器分配的时间，就标记调度标志
        resched_task ( rq_of ( cfs_rq ) - > curr ) ;
        / *
         *当前任务运行足够长的时间，确保它不会得到
         *由于好友的青睐而再次当选。
         * /
        清除好友( cfs_rq , curr ) ;
        返回；
    }
    / *
     *确保错过唤醒抢占的任务
     *窄边距不必等待完整的切片。
     *这也减少了负载下好友引起的延迟。
     * /
    if ( ! sched_feat ( WAKEUP_PREEMPT ) )
        返回；
    if ( delta_exec < sysctl_sched_min_capsularity )
        返回；
    如果 （ cfs_rq - > nr_running > 1 ） {
        struct sched_entity * se = __pick_next_entity ( cfs_rq ) ;
        s64 delta = curr - > vruntime - se - > vruntime ;
        if (增量>理想运行时间)
            resched_task ( rq_of ( cfs_rq ) - > curr ) ;
    }
}

当该进程运行时间超过实际分配的“时间片”，就标记调度标志resched_task(rq_of(cfs_rq)->curr);，否则本进程继续执行。中断退出，调度函数schedule()会检查此标记，以选取新的进程来抢占当前进程。

4.3如何选择下一个可执行进程

CFS选择具有最小vruntime值的进程作为下一个可执行进程，CFS用红黑树来组织调度实体，而键值就是vruntime。那么CFS只要查找选择最左叶子节点作为下一个可执行进程即可。实际上CFS缓存了最左叶子，可以直接选取left_most叶子。

上面代码跟踪到timer tick中断退出，若“ideal_runtime”已经用完，就会调用schedule()函数选中新进程并且完成切换。

asmlinkage void __sched 时间表( void )
{
    if ( prev - > state && ! ( preempt_count ( ) & PREEMPT_ACTIVE ) ) { _
        if (不太可能( signal_pending_state ( prev - > state , prev ) ) )
            上一个 - >状态= TASK_RUNNING ;
        别的
            deactivate_task(rq, prev, 1);//如果状态已经不可运行，将其移除运行队列
        switch_count = &上一个- > nvcsw ;
    }
    pre_schedule ( rq ,上一个) ;
    if (不太可能( ! rq - > nr_running ) )
        空闲平衡（ CPU ， RQ ）；
    put_prev_task(rq, prev); //处理上一个进程
    next = pick_next_task(rq);//选出下一个进程
……
    context_switch(rq, prev, next); /* unlocks the rq *///完成进程切换
……
}

如果进程状态已经不是可运行，那么会将该进程移出可运行队列，如果继续可运行put_prev_task()会依次调用put_prev_task_fair()->put_prev_entity()

静态无效put_prev_entity （结构cfs_rq * cfs_rq ，结构sched_entity * prev ）
{
    / *
     * 如果仍在运行队列中，则deactivate_task ( )
     *没有被调用并且update_curr ( )必须被完成：
     * /
    if (上一个- > on_rq )
        update_curr ( cfs_rq ) ;
    check_spread ( cfs_rq ,上一个) ;
    如果 （上一个- > on_rq ） {
        update_stats_wait_start ( cfs_rq ,上一个) ;
        / *将“当前”放回树中。 * /
        __enqueue_entity ( cfs_rq ,上一个) ;
    }
    cfs_rq - > curr = NULL ;
}

__enqueue_entity(cfs_rq, prev) 将上一个进程重新插入红黑树(注意，当前运行进程是不在红黑树中的)pick_next_task()会依次调用pick_next_task_fair()

静态结构task_struct * pick_next_task_fair （结构rq * rq ）
{
    结构任务结构* p ;
    struct cfs_rq * cfs_rq = & rq - > cfs ;
    结构 sched_entity * se ;
    if ( ! cfs_rq - > nr_running )
        返回空值；
    做 {
        se = pick_next_entity(cfs_rq);//选出下一个可执行进程
        set_next_entity(cfs_rq, se); //把选中的进程(left_most叶子)从红黑树移除，更新红黑树
        cfs_rq = group_cfs_rq （ se ）；
    } while ( cfs_rq ) ;
    p = task_of ( se ) ;
    htick_start_fair ( rq , p ) ;
    返回 p ；
}

set_next_entity()函数会调用__dequeue_entity(cfs_rq, se)把选中的下一个进程即最左叶子移出红黑树。最后context_switch()完成进程的切换。

4.4何时更新rbtree

①上一个进程执行完ideal_time，还可继续执行时，会插入红黑树；
②下一个进程被选中移出rbtree红黑树时；
③新建进程；
④进程由睡眠态被激活，变为可运行态时；
⑤调整优先级时也会更新rbtree；

4.5新建进程如何加入红黑树

新建进程会做一系列复杂的工作，这里我们只关心与红黑树有关部分

Linux使用fork，clone或者vfork等系统调用创建进程，最终都会到do_fork函数实现，如果没有设置CLONE_STOPPED，do_fork会执行两个与红黑树相关的函数: copy_process()和wake_up_new_task()

(1)copy_process()->sched_fork()->task_fork()

static void place_entity ( struct cfs_rq * cfs_rq ， struct sched_entity * se ， int初始值)
{
    u64 vruntime = cfs_rq->min_vruntime;//以cfs的最小vruntime为基准
    / *
     * “当前”期间已承诺当前任务， _
     *然而，新任务的额外重量会减慢他们的速度
     *小，放置新任务，使其适合该插槽
     *最后保持打开状态。
     * /
    if (初始&& sched_feat ( START_DEBIT ) ) _
        vruntime += sched_vslice(cfs_rq, se);// 加上一个调度周期内的"时间片"
    / *休眠至单个延迟不计算在内。 * /
    if ( ! initial & & sched_feat ( FAIR_SLEEPERS ) ) {
        无符号长阈值= sysctl_sched_latency ；
        / *
         *将休眠阈值转换为虚拟时间。
         * SCHED_IDLE是一个特殊的子类。我们关心
         *公平性仅相对于其他 SCHED_IDLE 任务，
         *所有这些都具有相同的重量。
         * /
        if ( sched_feat ( NORMALIZED_SLEEPER ) & & ( ! entity_is_task ( se ) | |
                 task_of ( se ) - >策略！= SCHED_IDLE ) )
            thresh = calc_delta_fair ( thresh , se ) ;
        / *
         *将睡眠时间的影响减半， 以允许
         * 为睡眠者带来更温和的效果：
         * /
        如果 （ sched_feat （ GENTLE_FAIR_SLEEPERS ））
            脱粒> > = 1 ;
        vruntime - = 阈值；
    }
    / *确保我们永远不会因为被排在后面而赢得时间。 * /
    vruntime = max_vruntime ( self - > vruntime , vruntime ) ;
    se - > vruntime = vruntime ;
}

计算新进程的vruntime值，加上一个“平均时间片”表示刚执行完，避免新建进程立马抢占CPU。

(2)调用wake_up_new_task函数

无效wake_up_new_task （ struct task_struct * p ，无符号长clone_flags ）
{
……
    rq = task_rq_lock ( p , & flags ) ;
    update_rq_clock ( rq ) ;
    activate_task(rq, p, 0);//激活当前进程，添加入红黑树
check_preempt_curr(rq, p, WF_FORK);//确认是否需要抢占
    ……
}

更新时钟，激活新建的进程activate_task()会调用

static void enqueue_task ( struct rq * rq , struct task_struct * p , intwakeup , bool head )
{
    如果 （唤醒）
        p- > se 。_ start_runtime = p - > se 。 sum_exec_运行时；
    sched_info_queued ( p ) ;
    p- > sched_class- > enqueue_task ( rq , p ,唤醒, head ) ; _ _
    p- > se 。_ on_rq = 1 ;
}

将新建的进程加入rbtree；

4.6唤醒进程

调用try_to_wake_up()->activate_task()->enqueue_task_fair()->enqueue_entity()注意enqueue_entity 函数调用place_entity对进程vruntime做补偿计算，再次考察place_entity(cfs_rq, se, 0)

static void place_entity ( struct cfs_rq * cfs_rq ， struct sched_entity * se ， int初始值)
{
    u64 vruntime = cfs_rq->min_vruntime;//以cfs的最小vruntime为基准
    / *
     * “当前”期间已承诺当前任务， _
     *然而，新任务的额外重量会减慢他们的速度
     *小，放置新任务，使其适合该插槽
     *最后保持打开状态。
     * /
    if (初始&& sched_feat ( START_DEBIT ) ) _
        vruntime += sched_vslice(cfs_rq, se);//一个调度周期内的"时间片"
    / *休眠至单个延迟不计算在内。 * /
    if ( ! initial & & sched_feat ( FAIR_SLEEPERS ) ) {
        无符号长阈值= sysctl_sched_latency ；
        / *
         *将休眠阈值转换为虚拟时间。
         * SCHED_IDLE是一个特殊的子类。我们关心
         *公平性仅相对于其他 SCHED_IDLE 任务，
         *所有这些都具有相同的重量。
         * /
        if ( sched_feat ( NORMALIZED_SLEEPER ) & & ( ! entity_is_task ( se ) | |
                 task_of ( se ) - >策略！= SCHED_IDLE ) )
            thresh = calc_delta_fair ( thresh , se ) ;
        / *
         *将睡眠时间的影响减半， 以允许
         * 为睡眠者带来更温和的效果：
         * /
        如果 （ sched_feat （ GENTLE_FAIR_SLEEPERS ））
            脱粒> > = 1 ;
        vruntime -= thresh;//对于睡眠进程唤醒，给予vruntime补偿
    }
    / *确保我们永远不会因为被排在后面而赢得时间。 * /
    vruntime = max_vruntime(se->vruntime, vruntime);//避免通过睡眠来获得运行时间
    se - > vruntime = vruntime ;
}

当initial=1时，新建进程vruntime=cfs最小vruntime值+时间片，放入红黑树最右端。

当initial=0时，表示唤醒进程，vruntime要减去一个thresh.这个thresh由调度周期sysctl_sched_latency加权得到虚拟时间，这样做可以对睡眠进程做一个补偿，唤醒时会得到一个较小的vruntime, 使它可以尽快抢占CPU(可以快速响应I/O消耗型进程)。

注意注释/* ensure we never gain time by being placed backwards. */这个设计是为了给睡眠较长时间的进程做时间补偿的，既使其可以快速抢占，又避免因太小的vruntime值而长期占用CPU。但有些进程只是短时间睡眠，这样唤醒时自身vruntime还是大于min_vruntime的，为了不让进程通过睡眠获得额外运行时间补偿，最后vruntime取计算出的补偿时间和进程本身的vruntime较大者。从这可以看出，虽然CFS不再区分I/O消耗型，CPU消耗型进程，但是CFS模型对IO消耗型天然的提供了快速的响应。

4.7改变进程优先级，如何调整rbtree

Linux中改变进程优先级会调用底层的set_user_nice()

void set_user_nice （ struct task_struct * p ，长nice ）
{
……
    dequeue_task(rq, p, 0); //把进程从红黑树中取出
……
    p->static_prio = NICE_TO_PRIO(nice);//将nice(-20~19)值映射到100~139,0~99是实时进程优先级
    设置负载重量（ p ）；
……
    enqueue_task ( rq , p , 0 , false ) ;
}

set_user_nice把进程从红黑树取出，调整优先级(nice值对应权重)，再重新加入红黑树

set_load_weight()函数是设置nice值对应的权重

静态无效set_load_weight （结构task_struct * p ）
{
    如果 （ task_has_rt_policy （ p ）） {
        p- > se 。_负载。重量= 0 ；
        p- > se 。_负载。 inv_weight = WMULT_CONST ;
        返回；
    }
    / *
     * SCHED_IDLE 任务获得最小权重：
     * /
    如果 （ p - >政策== SCHED_IDLE ）{ _
        p- > se 。_负载。重量= WEIGHT_IDLEPRIO ；
        p- > se 。_负载。 inv_weight = WMULT_IDLEPRIO ;
        返回；
    }
    p- > se 。_负载。权重= prio_to_weight [ p - > static_prio - MAX_RT_PRIO ] ;
    p- > se 。_负载。 inv_weight = prio_to_wmult [ p - > static_prio - MAX_RT_PRIO ] ;
}

数组prio_to_weight[]是将nice值(-20~19)转化为以nici 0(1024)值为基准的加权值,根据内核注释每一个nice差值，权重相差10%，即在负载一定的条件下，每增加或减少一个nice值，获得的CPU时间相应增加或减少10%

静态常量 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 ,
} ;

上面calc_delta_mine()函数用到这个数组加权值，这个转化过程还没弄明白，有明白的朋友，指点一二，不胜感激

/ *
 * prio_to_weight [ ]数组的反( 2^32 / x )值，预先计算。
 *
 * 在重量不经常变化的情况下，我们可以使用
 *预先计算逆数以通过转动除法来加速算术
 *转化为乘法：
 * /
静态常量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 、 _ _ _ _ _ _ _ _
} ;

最后，说下对CFS “完全公平” 的理解：

①不再区分进程类型，所有进程公平对待
②对I/O消耗型进程，仍然会提供快速响应(对睡眠进程做时间补偿)
③优先级高的进程，获得CPU时间更多(vruntime增长的更慢)

可见CFS的完全公平，并不是说所有进程绝对的平等，占用CPU时间完全相同，而是体现在vruntime数值上，所有进程都用虚拟时间来度量，总是让vruntime最小的进程抢占，这样看起来是完全公平的，但实际上vruntime的更新，增长速度，不同进程是不尽一样的。CFS利用这么个简单的vruntime机制，实现了以往需要相当复杂算法实现的进度调度需求，高明！

精品文章推荐阅读：

深入理解Linux内核进程的创建、调度和终止（下）

三、进程调度

3.1吞吐率和响应

3.2Linux任务类型

3.3任务调度

四、进程调度CFS算法实现分析

4.1理解CFS的首先要理解vruntime的含义

4.2vruntime的值如何跟新？

4.3如何选择下一个可执行进程

4.4何时更新rbtree

4.5新建进程如何加入红黑树

4.6唤醒进程

4.7改变进程优先级，如何调整rbtree

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像