在文章开始之前，首先做一个勘误，在文章（一）中有一段“关于pelt的计算非常复杂，在这里简化一下。

virtual runtime = physical runtime/ weight;

”

这里面的描述有误，virtual runtime跟pelt并没有关系。virtual runtime是量化不同CFS进程之间的调度竞争关系的。而pelt是用来量化负载的大小的。

看完上文，我们的内心应该是有点绝望的。因为负载的统计是基于历史的，不准确；频率的预测也不准确；功耗的模拟计算也不准确。啥都不准确， EAS到底在整啥呢。其最终的效果值得怀疑。 但是你以为这就完了吗？ 还远未结束。

在前文中，我们提到了pelt跟walt两种负载的量化方法，但是在前面的文章里，我们刻意回避了一个因素，就是CPU的频率。

1.任务负载归一化

为了简化一下，我们以walt为例，因为窗口内的负载计算相比pelt复杂的衰减计算，更加容易理解一些。

 在引入b-l之后，问题其实变得更加复杂。很显然，同样的运行5ms，在100MHZ频率下运行5ms跟在200MHZ的频率下运行5ms。它们对于算力的需求是不一样的，最后的量化结果也应该是不一样的。同理，在小核上运行5ms跟在大核上运行5ms。需求跟量化结果也应该是不一样的。

    因此我们不得不回过头来，把walt的剩余的部分补充一下，也就是load scale（负载的归一化）。比较细节的内容可以参考https://android.googlesource.com/kernel/msm/+/android-msm-bullhead-3.10-marshmallow-dr/Documentation/scheduler/sched-hmp.txt

假设我们认为整个CPU系统中，算力最大的CPU（通常是CPU7）处于最高频率下的算力（capacity）定义为1024（前面提到，1024在计算机系统中是个常用到的数值，主要是为了计算方便，因为1024是2^10，计算机计算起来比较方便高效）。同时在“算力线性”的假设下，我们可以计算出来任何一个CPU（不管是小核、大核还是超大核），在任意频率下的capacity。 我们假设超大核的IPC（instructions per cycle， 代表CPU的单个时钟周期的运行的指令数，是一个性能指标）是3，最高频率是3GHZ, 大核的IPC是2. 最大频率是2GHZ。

  那么我们可以计算出来，大核在2GHZ下的capacity是

1024 * (2/3) *(2GHZ/3GHZ) = 455.11

 因此我们在计算某个任务在某个窗口内的task load的时候，归一化的计算公式就变成了：

task_load = (running_time/window_size) * (f_curr/f_max) * capacity_max(cpu);

running_time代表线程在某个窗口周期内的运行时间，capacity_max代表某个CPU的最大能力，f_max代表这个CPU的最大频率。f_curr代表CPU的当前运行频率（因此f_curr是小于等于f_max的)，window size代表walt的窗口统计周期（这里提一句，这个统计周期在walt里面是随着屏幕刷新率变化的，但是又不是完全对齐的。 为了降低walt的开销， window size是tick的整数倍，因此120HZ的情况下，window size为8ms， 60HZ下，窗口周期为16ms，也就是4个tick周期。这其实也是个问题，因为window size跟vsync周期不完全对齐的话，会出现负载统计的跨窗口问题）。

在上面我们一直在讨论一个死循环进程的问题（模拟突发的高负载）， 那么runningtime == windowsize;

 task_load =  f_curr/f_max * capacity_max(cpu);

因此就算任务是一个死循环，其CPU使用占比很高，但是由于频率比较低，任务依然会被判定为一个小任务。 （有没有很熟悉 ？ 一个任务在小核上长时间运行，一直难以迁到大核上。其根本原因在于调度器在量化的时候，判定其是一个小任务）

  由于这个系列的文章主要讲任务调度器，所以内容尽可能限定在这个范围内，对于涉及到的其余领域的内容，基于最小化的原则进行讨论。 在本章中，我们不得不讨论到一个跟调度互相影响的模块，就是调频（cpufreq governor）

2.cpu调频

 CPU调频是一个跟调度互相影响的模块，因为根据上面我们讨论的内容，任务的归一化负载计算公式变成了。

  task load =  f_curr/f_max * capacity_max(cpu);

  那么很显然，任务的负载计算跟当前CPU的运行频率有着直接的关系。

 为了最大化的简化模型，认为调频的计算公式如下：

    f_next =  CPU_load / capacity_max * f_max *1.25；

由于我们讨论的是一个CPU 100%满载的情况，因此  CPU_load = f_curr/f_max * capacity_max(cpu);

那么f_next 就变成：

  f_next    =  （CPU_load / capacity_max） * f_max * 1.25   

           = （f_curr/f_max * capacity_max(cpu)）/ capacity_max(cpu) * f_max  * 1.25 

           =  f_curr * 1.25;

其中1.25又是一个magic number，其实就是除以0.8。 基于经验，大家认为CPU的使用率维持在80%是一个比较理想的情况，既可以保障性能留有富余，又能节省功耗。至于为什么选择80%， 我猜可能跟国人煮大米饭一样，插上电饭锅，放入大米，放入水。然后用食指插入水中，看到水刚好过手指的某条线，perfect，可以煮出完美的大米饭。当然，这个80%的值是经验的，可以调整修改。（事实上不是，可以搜索一下性能拐点， 这个数值的选择其实也很有意思）

 因此，在CPU满载的情况下，下个频率是当前频率的1.25倍。记住这个结论就行了。

一个很奇怪的事情就出现了, 负载计算依赖于频率，频率的调节又反过来依赖于负载的输入。它们两个就变成了鸡跟蛋的问题，互相影响。

 以 fnext =  fcurr * 1.25的这种极端情况为例，我们会的出来一个结论，就是CPU在频率低的时候，它的调频速度会非常慢。因为基数低，增加的0.25倍的频率值其实也很低。

  而频率低，会导致我们对于任务的负载的准确量化的时间变得更长。

因此这里面存在一个极其根本的难题，就是对于一个任务的负载量化，不够准确，而且存在很长时间的delay。 这个delay会在性能上导致很多的问题，如下图，qq主线程，因为业务实现的一些问题（我们先不谈论业务中不合理点，因为改变不了三方的业务行为），主线程的负载不够均匀，会出现负载的跳变的情况。 而调度器对于这个负载的跳变，显得无能为力。万幸的是，大部分情况下，负载还是相对均匀的。

当然，虽然从调度器机制本身上这个问题看起来无解，但是结合用户业务，这个问题依然是可以得到缓解的。笔者之前写过一篇文章《利用ADPF性能提示优化Android应用体验》 

前面我们介绍了Linux的RT\CFS调度类，任务负载的量化算法，以及大小核的算力的归一化，EAS等等。下面我们再次回到RT\CFS调度类，大家最关心的是任务的调度延迟（runnable）。因为在实际的性能分析的时候，大家遇到最多的反而是调度延迟导致的流畅性卡顿。

以上图为例，内核线程kworker的runnable最终导致了掉帧。

但是我们也提到了，RT是基于优先级选核的，而且RT也是严格按照高优先级抢占低优先级来设计的，但是CFS的进程，优先级priority字段其实是代表的一个权重weight，表示在一定时间内占用资源的比重。

在上面的例子里面，特别是在之前cgroup份额的例子上，我们都是以死循环为例。为什么呢？这里有必要说明一下。

当我们说到资源分配的比重为题时，是有一个前提的，即任务出现资源竞争时的资源分配比重问题。这里突出一个竞争。当没有资源竞争时，也有不存在这个比重问题。或者当我们说weight权重的比例问题时，也只能限定在竞争的环境下。

举一个例子，有两个任务，task1跟task2. 其中task2的权重是task1的两倍。但是task1全程都是处于active的状态，参与到资源竞争，task2只有后面一段时间处于active的状态参与竞争，前面大部分时间处于inactive，可能是因为某个条件未满足而处于sleeping的状态。

那么在时间(T1,T2）内，task1是独占CPU的，因为不存在资源竞争；在（T2, T3）之间，task1跟task2之间处于资源竞争关系，由于权重比例为2:1， 所以他们在这段时间内，TASK2因为权重较高，占有的资源比task1要高。

我们不应该认为在(T1, T3）的时间内，一定要让task1跟task2之间的资源配比为1:2 。这是不对的。（试想在一个服务器上，一个线程已经运行了几个月了，如果这时候有新的进程创建，这个运行了几个月的进程是不是就基本没机会运行了？），当然实际情况并不是像我上面讲的那么简单。

3.sys.use_fifo_ui

https://source.android.com/docs/core/tests/debug/jank_jitter?hl=zh-cn

在android里面，有一个sys.use_fifo_ui的property，通过设置这个property，可以将页面的主线程以及渲染线程设为 SCHED_FIFO 而非 SCHED_OTHER。这种方法可以有效地消除界面线程和 RenderThread 造成的抖动。那么为什么google不默认这么做呢？我猜可能存在以下的一些原因：

1.RT 负载均衡器不具备容量（capacity，直接翻译成容量的话，差点意思。cpu capacity即CPU的能力)感知能力 ,也就是说Linux RT调度类在设计之初就“假设RT的线程是负载很轻，同时对于调度延迟非常敏感”。因为负载很轻，所以RT线程不能对算力有要求，跑在哪个CPU上都可以，只需要解决掉RT之间的互斥或者高低抢占即可。但是Android里面存在，应用的主线程跟渲染线程经常负载很大。缺乏负载感知能力的话，很容易调度到小核上，导致算力不足。又比如一些平台上出现GPU合成时，SF\RE\Composer等线程出现跑小核的一些卡顿问题。

2.RT调度类过于霸道，前面提到了调度类也是有优先级之分的。RT调度类的优先级大于CFS调度类

 for_each_class(class) {

  p = class->pick_next_task(rq);

  if (p)

  return p;

  }

那么只要有RT线程，那么CFS线程就得不到运行的机会。系统很容易ANR掉了。为此RT调度类不得不设计了一个定时器timer来周期性的采样。当RT线程出现异常时，进行限制。当在一个sched_rt_period_us的周期里面，RT线程的运行累计时间不能超过sched_rt_runtime_us。这两个参数都是可以调整的。

3.一个RT线程fork出来的新进程也是RT优先级的，会导致权限失控。

因此各家平台厂商都设计了不同的特权CFS线程的策略，如高通平台的MVP线程，MTK平台的VIP线程等等。有兴趣的同学可以看一下高通walt （msm-kernel/kernel/sched/walt/）或者MTK EAS （kernel_device_modules-6.6/drivers/misc/mediatek/sched/eas/）的代码。

当一个CFS类的线程被标记为VIP（特权CFS进程我们统一用VIP来代称）线程的话，会得到优先调度，类似于CFS里面的RT线程。原理比较简单，当没有RT线程时，调度器执行CFS的选任务逻辑，这时候先从VIP队列里面选择一个没有“超时”的有效的VIP线程，如果没有。那么就fallback到原生的cfs的选任务逻辑上去。

8375  struct task_struct *

8376  pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)

8377  {

8378  struct cfs_rq *cfs_rq = &rq->cfs;

8379  struct sched_entity *se = NULL;

8380  struct task_struct *p = NULL;

8381  int new_tasks;

8382  bool repick = false;

8383  

8384  again:

8385  if (!sched_fair_runnable(rq))

8386  goto idle;

8387  

...中间代码跳过

8434  

8435  p = task_of(se);

8436  trace_android_rvh_replace_next_task_fair(rq, &p, &se, &repick, false, prev);

由于google GKI的限制，这段UX选任务的逻辑写在trace_android_rvh_replace_next_task_fair这个hook函数里面。

其中针对不同的类型的UX线程，各大产商设置了超时机制，来避免VIP线程运行时间过多占用系统资源导致整机卡顿或者系统ANR的情况发生。

其实整个android系统中的RT线程数量越来越多，比如audio service的部分线程设置为96， surfaceflinger的线程优先级为98，内核的部分threaded irq的线程优先级为49 等等。这些线程都对于调度延迟有非常高的要求。

那么是不是把系统的关键线程都设置为RT或者VIP线程就万事大吉了？

4.优先级反转（Priority Inversion）

事情还远没有结束。

关于优先级反转，知乎上有篇文章，还算讲的比较详细，https://zhuanlan.zhihu.com/p/146132061

这里我们先描述现象，不急着去找方案。

上图是一个卡顿的trace截图，其中kgsl_worker _thr是高通GPU驱动里面的一个RT线程。但是它处于D状态（也就是Uninterruptble sleep)状态在等某个锁，但是锁被kworker/u24:8线程持有，但是kworker/u24:8只是一个普通的CFS进程，前面我们提到了CFS本质上是一种比例分配的调度策略，那么在高负载情况下，必然会出现runnable的延迟，只不过是这个延迟的长与短的问题。

那么上面的这种情况，就被称为优先级反转。

Linux内核提供了一种解决优先级反转的方法，rtmutex （kernel-6.6/kernel/locking/rtmutex.c）。

rtmutex的时间比较复杂，但是原理比较简单，从一些函数名字诸如 rt_mutex_adjust_priochain，可以看到当一个RT线程因为锁的原因进入D状态等待的时候，它会把自己的优先级（RT优先级）传递给锁的持有者，也就是上面截图的kworker/u24:8线程，这时候kworker/u24:8会被短暂的提升到RT的优先级，得到优先调度，等到kworker/u24:8线程释放锁（rtmutex_unlock)的时候，kworker/u24:8会被恢复成原始的CFS进程。

通过这种优先级传递，临时提升优先级的方法，来优化优先级反转的问题。既然Linux有这种机制，为什么我们还会在android系统上遇到上面提到的问题呢？

答案是只有rtmutex才能解决这个问题，但是整个Linux系统中，锁的类型非常多，如mutex、futex、rwsem等等。

如果要解决优先级反转的问题，就必须显式的采用rtmutex锁，这样出现RT线程被blocked的情况，才能有效的进行优先级传递。这些优先级反转的机制的覆盖范围太少了。

类似的例子，我们可以在binder里面看到，可以参考 binder_transaction_priority函数，我们看到当一个RT线程发起binder请求时。客户端可以临时继承发起端的RT优先级来短暂的提升优先级，保证得到优先级调度，防止发起端被阻塞住。

在整个Linux的系统设计里面，存在几种不同的考虑：

一种是偏向调度延迟，高优先级的线程会被优先调度，能够保障调度延迟latency。如RT调度类、rtmutex等等。这些机制偏向延迟，引入不少额外的开销，比如上面的rtmutex，需要找到owner，如果存在锁的嵌套，需要遍历链表，调整相关线程的优先级。这些开销都会降低系统的整体throughout。

另外一种更加偏向公平、均衡，比如CFS这种比例分配的调度策略，mutex这种按照FIFO先入先出顺序的策略管理pending在同一个锁上的相关线程，又或者cpufreq进行CPU调频时，都是以CPU的使用率为输入来均衡性能与功耗。

Linux是一个开源操作系统。高度兼容性是它的一个特点，低到MCU、单片机如STM32， 中间到工业控制器、电视机顶盒、手机，上到服务器。都可以支持。因此Linux为了兼容这多设备的不同业务需求，在不停的进行中和与均衡，有点变成一个四不像了。只能做到“基本能用”，离“极致”还差十万八千里。

这里不得不提到，windows（参考《深入解析windows操作系统》）跟IOS都只有一种调度类（Linux有stop、deadline、rt、CFS以及idle这几种，典型的既要又要），比较类似于linux的RT调度类，高优先级抢占低优先级，他们都会基于系统状态来动态调整线程的优先级，比如解决优先级反转、io阻塞提权等等。如同我们上面提到的，当高优先级的线程对于资源的占用过多后，可能会导致系统中低优先级的饿死，进而导致ANR。比如windows系统，虽然操作比较流畅，响应很快，但是经常会抽风卡主一会儿，很可能就是这种情况。为此windows中不得不搞了一个balance-set manager的线程，周期性的扫描，找到可能会被饿死的线程，提升它的优先级。

之前网上有一篇文章《为什么Windows/iOS操作很流畅而Linux/Android却很卡顿呢》 ，可以了解一下。

由于这个系列的文章来自于内部的一些科普小作文，考虑到文章篇幅的不至于过短，有些文章是由多个小作文拼凑的，如果出现一些不统一，还望大家见谅。这个系列的小作文到现在暂时断货了，本意是在公司内部各业务之间统一认识，并没有继续写下去。因此需要暂停一段时间来补货。如果想看绿厂怎么优化此类问题的，敬请期待后续更新。

往

期

推

荐

任务调度器：从入门到放弃（一）

任务调度器：从入门到放弃（二）

任务调度器：从入门到放弃（三）