Linux内核之旅社区联合thoughtworks未济实验室在中科院开源之夏和CCF暑期夏令营活动中发布了13个题目，我们也一直在思考如何让大家通过这次暑期活动更好地提升自己。这次分享是通过具体的一个性能指标，利用现有的工具来定位内核代码，从而圈定学习 Kernel 的目标范围，因此这次分享是想给社区同学提供一种学习方法，因此可以将重点放在方法上，原理部分就交给社区同学深入挖掘了，而且根据目前社区同学的反馈，效果超出我的预期，期待社区同学后续精彩的分享。

同时我也在思考一个问题，就是怎么才能把 eBPF 的优势讲明白，或者说把eBPF 在某一个点上的应用优势是什么讲明白，社区的题目大部分都是围绕 eBPF 展开的，因此也是在尝试解释这件事情。

调度延迟

本次圈定的性能指标是调度延迟，那首要的目标就是看看到底什么是调度延迟，调度延迟是保证每一个可运行进程都至少运行一次的时间间隔，翻译一下，是指一个 task 的状态变成了 TASK_RUNNING，然后从进入 CPU 的 runqueue开始，到真正执行（获得 CPU 的执行权）的这段时间间隔。

需要说明的是调度延迟在 Linux Kernel 中实现的时候是分为两种方式的：面向task和面向rq，我们现在关注的是 task 层面。

那么 runqueue 和调度器的一个 sched period 的关系就显得比较重要了。首先来看调度周期，调度周期的含义就是所有可运行的 task 都在CPU上执行一遍的时间周期，而 Linux CFS 中这个值是不固定的，当进程数量小于8的时候，sched period 就是一个固定值6ms，如果 runqueue 数量超过了8个，那么就保证每个 task 都必须运行一定的时间，这个一定的时间还叫最小粒度时间，CFS的默认最小粒度时间是0.75ms，使用 sysctl_sched_min_granularity 保存， sched period 是通过下面这个内核函数来决定的：

/*
 * The idea is to set a period in which each task runs once.
 *  * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *  * p = (nr <= nl) ? l : l*nr/nl
*/
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 就是可执行 task 数量

那么一个疑问就产生了，这个不就是调度延迟 scheduling latency 吗，并且每一次计算都会给出一个确定的调度周期的值是多少，但是这个调度周期仅仅是用于调度算法里面，因为这里的调度周期是为了确保 runqueue 上的 task 的最小调度周期，也就是在这段时间内，所有的 task 至少被调度一次，但是这仅仅是目标，而实际是达不到的。因为系统的状态、task 的状态、task 的slice等等都是不断变化的，周期性调度器会在每一次 tick 来临的时候检查当前 task 的slice是否到期，如果到期了就会发生 preempt 抢，而周期性调度器本身的精度就很有限，不考虑 hrtick 的情况下，我们查看系统的时钟频率：

$ grep CONFIG_HZ /boot/config-$(uname -r) 
# CONFIG_HZ_PERIODIC is not set
# CONFIG_HZ_100 is not set
CONFIG_HZ_250=y
# CONFIG_HZ_300 is not set
# CONFIG_HZ_1000 is not set
CONFIG_HZ=250  
复制

仅仅是250HZ，也就是4ms一次时钟中断，所以都无法保证每一个 task 在CPU上运行的slice是不是它应该有的slice，更不要说保证调度周期了，外加还有wakeup、preempt等等事件。

1. atop的统计方法

既然不能直接使用计算好的值，那么就得通过其他方法进行统计了，首先Linux kernel 本身是有统计每一个 task 的调度延迟的，在内核中调度延迟使用的说法是 run delay ，并且通过 proc 文件系统暴露了出来，因此大概率现有的传统工具提取调度延迟的源数据是来自于 proc 的，例如 atop 工具。

run delay在 proc 中的位置：

进程的调度延迟：/proc/<PID>/schedstat
线程的调度延迟：/proc/<PID>/task/<TID>/schedstat
复制

现在的目标变为搞清楚 atop 工具是怎么统计调度延迟的。

现有的工具 atop 是可以输出用户态每一个进程和线程的调度延迟指标的，在开启 atop 后按下 s 键，就会看到 RDELAY 列，这一列就是调度延迟了。我们来看看 atop 工具是怎么统计这个指标值的，clone atop工具的代码：

git@github.com:Atoptool/atop.git
复制

由于目前的目标是搞清楚 atop 对调度延迟指标的统计方法，因此我只关心和这个部分相关的代码片段，可视化展示的部分并不关心。

整体来说，atop 工作的大体流程是：

int
main(int argc, char *argv[])
{
···
    // 获取 interval
    interval = atoi(argv[optind]);

    // 开启收集引擎
    engine();
···
    return 0;    /* never reached */
}
复制

这里的 interval 就是我们使用atop的时候以什么时间间隔来提取数据，这个时间间隔就是 interval。
所有的计算等操作都在 engine() 函数中完成
engine()的工作流程如下：

static void
engine(void)
{
···
    /*
    ** install the signal-handler for ALARM, USR1 and USR2 (triggers
    * for the next sample)
    */
    memset(&sigact, 0, sizeof sigact);
    sigact.sa_handler = getusr1;
    sigaction(SIGUSR1, &sigact, (struct sigaction *)0);
···
    if (interval > 0)
        alarm(interval);
···
    for (sampcnt=0; sampcnt < nsamples; sampcnt++)
    {
···
        if (sampcnt > 0 && awaittrigger)
            pause();
        awaittrigger = 1;
···
        do
        {
            curtlen   = counttasks();    // worst-case value
            curtpres  = realloc(curtpres,
                    curtlen * sizeof(struct tstat));

            ptrverify(curtpres, "Malloc failed for %lu tstats\n",
                                curtlen);

            memset(curtpres, 0, curtlen * sizeof(struct tstat));
        }
        while ( (ntaskpres = photoproc(curtpres, curtlen)) == curtlen);

···
    } /* end of main-loop */
}
复制

代码细节上不再详细介绍，整体运行的大循环是在16行开始的，真正得到调度延迟指标值的是在34行的 photoproc() 函数中计算的，传入的是需要计算的 task 列表和 task的数量
来看看最终计算的地方：

unsigned long
photoproc(struct tstat *tasklist, int maxtask)
{
···
        procschedstat(curtask);        /* from /proc/pid/schedstat */
···
        if (curtask->gen.nthr > 1)
        {
···
            curtask->cpu.rundelay = 0;
···
            /*
            ** open underlying task directory
            */
            if ( chdir("task") == 0 )
            {
···
                while ((tent=readdir(dirtask)) && tval<maxtask)
                {
                    struct tstat *curthr = tasklist+tval;
                    ···
                    // totalize delays of all threads
                    curtask->cpu.rundelay +=
                        procschedstat(curthr);
                    ···
                }
                ···
            }
        }
    ···
    return tval;
}
复制

第5行的函数就是在读取 proc 的 schedstat 文件：

  static count_t
  procschedstat(struct tstat *curtask)
{
    FILE    *fp;
    char    line[4096];
    count_t    runtime, rundelay = 0;
    unsigned long pcount;
    static char *schedstatfile = "schedstat";
  
    /*
     ** open the schedstat file 
    */
    if ( (fp = fopen(schedstatfile, "r")) )
    {
        curtask->cpu.rundelay = 0;
  
        if (fgets(line, sizeof line, fp))
        {
            sscanf(line, "%llu %llu %lu\n",
                    &runtime, &rundelay, &pcount);
  
            curtask->cpu.rundelay = rundelay;
        }
  
        /*
        ** verify if fgets returned NULL due to error i.s.o. EOF
        */
        if (ferror(fp))
            curtask->cpu.rundelay = 0;
  
        fclose(fp);
    }
    else
    {
        curtask->cpu.rundelay = 0;
    }
  
    return curtask->cpu.rundelay;
  }
复制

15行是在判断是不是有多个thread，如果有多个thread，那么就把所有的thread的调度延迟相加就得到了这个任务的调度延迟。

所以追踪完 atop 对调度延迟的处理后，我们就可以发现获取数据的思路是开启 atop之后，按照我们指定的 interval，在大循环中每一次 interval 到来以后，就读取一次 proc 文件系统，将这个值保存，因此结论就是目前的 atop 工具对调度延迟的提取方式就是每隔 interval 秒，读取一次 proc下的 schedstat 文件。

因此 atop 获取的是每 interval 时间的系统当前进程的调度延迟快照数据，并且是秒级别的提取频率。

2. proc的底层方法—面向task

那么数据源头我们已经定位好了，就是来源于 proc，而 proc 的数据全部都是内核运行过程中自己统计的，那现在的目标就转为内核内部是怎么统计每一个 task 的调度延迟的，因此需要定位到内核中 proc 计算调度延迟的地点是哪里。

方法很简单，写一个读取 schedstat 文件的简单程序，使用 ftrace追踪一下，就可以看到 proc 里面是哪个函数来生成的 schedstat 文件中的数据，ftrace的结果如下：

2)   0.125 us    |            single_start();  
2)               |            proc_single_show() {  
2)               |              get_pid_task() {  
2)   0.124 us    |                rcu_read_unlock_strict();  
2)   0.399 us    |              }  
2)               |              proc_pid_schedstat() {  
2)               |                seq_printf() {  
2)   1.145 us    |                  seq_vprintf();  
2)   1.411 us    |                }  
2)   1.722 us    |              }  
2)   2.599 us    |            }
复制

很容易可以发现是第六行的函数：

#ifdef CONFIG_SCHED_INFO
/*
* Provides /proc/PID/schedstat
*/
static int proc_pid_schedstat(struct seq_file *m, struct pid_namespace *ns,
                              struct pid *pid, struct task_struct *task)
{
    if (unlikely(!sched_info_on()))
        seq_puts(m, "0 0 0\n");
    else
        seq_printf(m, "%llu %llu %lu\n",
                   (unsigned long long)task->se.sum_exec_runtime,
                   (unsigned long long)task->sched_info.run_delay,
                   task->sched_info.pcount);

    return 0;
}
#endif
复制

第8行是在判断一个内核配置选项，一般默认都是开启的，或者能看到 schedstat 文件有输出，那么就是开启的，或者可以用 make menuconfig 查找一下这个选项的状态。

可以发现 proc 在拿取这个调度延迟指标的时候是直接从传进来的 task_struct 中的 sched_info 中记录的 run_delay ，而且是一次性读取，没有做平均值之类的数据处理，因此也是一个快照形式的数据。

首先说明下 sched_info 结构：

struct sched_info {#ifdef CONFIG_SCHED_INFO
    /* Cumulative counters: */

    /* # of times we have run on this CPU: */
    unsigned long            pcount;

    /* Time spent waiting on a runqueue: */
    unsigned long long        run_delay;

    /* Timestamps: */

    /* When did we last run on a CPU? */
    unsigned long long        last_arrival;

    /* When were we last queued to run? */
    unsigned long long        last_queued;#endif /* CONFIG_SCHED_INFO */};
复制

和上面proc函数的宏是一样的，所以可以推测出来这个宏很有可能是用来开启内核统计 task 的调度信息的。每个字段的含义代码注释已经介绍的比较清晰了，kernel 对调度延迟给出的解释是在 runqueue 中等待的时间。

现在的目标转变为内核是怎么对这个 run_delay 字段进行计算的。需要回过头来看一下sched_info 的结构，后两个是用于计算 run_delay 参数的，另外这里就需要Linux调度器框架和CFS调度器相关了，首先需要梳理一下和进程调度信息统计相关的函数，其实就是看 CONFIG_SCHED_INFO 这个宏包起来了哪些函数，找到这些函数的声明点，相关的函数位于 kernel/sched/stats.h 中。

涉及到的函数如下：

sched_info_queued(rq, t)
sched_info_reset_dequeued(t)
sched_info_dequeued(rq, t)
sched_info_depart(rq, t)
sched_info_arrive(rq, next)
sched_info_switch(rq, t, next)
复制

BTW，调度延迟在rq中统计的函数是：

rq_sched_info_arrive()
rq_sched_info_dequeued()
rq_sched_info_depart()
复制

注意的是这些函数的作用只是统计调度信息，查看这些函数的代码，其中和调度延迟相关的函数有以下三个：

sched_info_depart(rq, t)
sched_info_queued(rq, t)
sched_info_arrive(rq, next)
复制

并且一定是在关键的调度时间节点上被调用的：

1. 进入runqueue
   task 从其他状态（休眠，不可中断等）切换到可运行状态后，进入 runqueue 的起始时刻；
2. 调度下CPU，然后进入runqueue
   task 从一个 cpu 的 runqueue 移动到另外一个 cpu 的 runqueue 时，更新进入新的 runqueue
   的起始时刻；
   task 正在运行被调度下CPU，放入 runqueue 的起始时刻，被动下CPU；
3. 产生新task然后进入runqueue；
4. 调度上CPU
   进程从 runqueue 中被调度到cpu上运行时更新last_arrival；
   可以这么理解要么上CPU，要么下CPU，下CPU并且状态还是 TASK_RUNNING 状态的其实就是进入 runqueue 的时机。
   进入到 runqueue 都会最终调用到 sched_info_queued ，而第二种情况会先走 sched_info_depart 函数：

static inline void sched_info_depart(struct rq *rq, struct task_struct *t)
{
    unsigned long long delta = rq_clock(rq) - t->sched_info.last_arrival;

    rq_sched_info_depart(rq, delta);

    if (t->state == TASK_RUNNING)
        sched_info_queued(rq, t);
}
复制

• 第3行的代码在计算上次在CPU上执行的时间戳是多少，用现在的时间减去 last_arrival（上次被调度上CPU的时间）就可以得到，然后传递给了 rq_sched_info_depart() 函数
• 第2种情况下，在第8行，如果进程这个时候的状态还是 TASK_RUNNING ，那么说明这个时候 task 是被动下CPU的，表示该 task 又开始在 runqueue 中等待了，为什么不统计其它状态的 task，因为其它状态的 task 是不能进入 runqueue 的，例如等待IO的 task，这些task只有在完成等待后才可以进入 runqueue，这个时候就有变成了第1种情况；第1种情况下会直接进入 sched_info_queued() 函数；因此这两种情况下都是task进入了runqueue 然后最终调用 sched_info_queued() 函数记录上次（就是现在）进入runqueue 的时间戳 last_queued
• sched_info_queued() 的代码如下：

  static inline void sched_info_queued(struct rq *rq, struct task_struct *t)
  {
    if (unlikely(sched_info_on())) {
        if (!t->sched_info.last_queued)
            t->sched_info.last_queued = rq_clock(rq);
    }
  }
复制

然后就到了最后一个关键节点，task被调度CPU了，就会触发 sched_info_arrive() 函数：

static void sched_info_arrive(struct rq *rq, struct task_struct *t)
  {
    unsigned long long now = rq_clock(rq), delta = 0;
  
    if (t->sched_info.last_queued)
        delta = now - t->sched_info.last_queued;
    sched_info_reset_dequeued(t);
    t->sched_info.run_delay += delta;
    t->sched_info.last_arrival = now;
    t->sched_info.pcount++;
  
    rq_sched_info_arrive(rq, delta);
  }
复制

这个时候就可以来计算调度延迟了，代码逻辑是如果有记录上次的 last_queued 时间戳，那么就用现在的时间戳减去上次的时间戳，就是该 task 的调度延迟，然后保存到 run_delay 字段里面，并且标记这次到达CPU的时间戳到 last_arrival 里面，pcount 记录的是上cpu上了多少次。
公式就是：

该task的调度延迟 = 该task刚被调度上CPU的时间戳 - last_queued(该task上次进入runqueue的时间戳)