linux实时任务调度算法分析

winston

鉴于最近有关cpu占有率的一些问题涉及到linux内核的调度算法，有必要进行了解。因此，写了这篇文章。linux常见的任务有两种，实时任务与非实时任务。实时任务的调度算法是大家都非常熟悉的优先级抢占或优先级抢占加时间片两种，其主要思想是效率优先。非实时任务的调度算法是CFS(完全公平算法），从名字就可以知道，其思想是公平优先，兼顾效率。由于我们使用上，实时任务比较多，本篇就先介绍实时任务的调度机制。


一、UP（Uniprocess)下的优先级调度
熟悉vxworks的同学都非常清楚，vxworks使用的就是优先级抢占，从0-255，优先级高的抢占优先级低的。如果再加上时间片调度，则当任务运行完它的时间片后，会重新进行调度，这时候，如果有相同优先的任务，就可以得到运行。这点要注意，即使当前进程的时间片用完了，优先级比它低的任务还是不能得到CPU的，重新调度还是会调度到之前运行的任务的。所谓时间片，就是相同优先级的任务轮流占有CPU，不同优先级只有抢占。如果没有启用时间片调度，相同优先级的任务只有等待前面的任务运行完后才能得到CPU。
简单说：座位只有一个，谁坐？比拳头，大的先上，拳头一样大的，轮流上，小的靠边站。
非常好理解，实际上UP方式下linux的调度机制与vxworks并没有多大差异。差别的是内部代码实现及调度点。
在vxworks 5.5.1下，只维护了一个就绪队列，按优先级排序，优先级高的排在前面，优先级一样的，按先后顺序排列。每次调度时就从队列头取下一个任务运行。
而linux则按优先级维护了多个就绪队列，每个优先级都有一个就绪队列，任务入队列时会置队列位图表相应的bit位，表示该优先级有任务已经就绪，等待调度。调度时扫描队列位图表，从高优先级队列中取下一个任务运行。
另外一个差异就是vxworks作为一个实时操作系统，只有任务一就绪就会检查是否需要调度，而linux则需要等待调度点的到来才真正检查是否需要调度。
UP下的调度非常好理解，那么SMP下又如何呢？


二、SMP下的优先级调度
有钱了，买了好多凳子，甚至还是二人沙发，四人沙发，如何让合适的人，坐到合适的凳子上，反而变成了一件不容易的事情。
UP下大家的目标都很简单，就是抢同一个CPU，而SMP下，则是从多个CPU中抢一个CPU。一个常见的误区是：一说到SMP,就会想到负载均衡。实际上，实时任务的调度是不会考虑负载均衡的，其调度算法是抢占式的，既然是抢，当然是抢到一个算一个。实时任务的负载均衡应该是由设计者考虑的：核与任务的关系，如何更好的让实时任务都得到调度。
既然是从多个CPU中抢一个，那么抢那一个呢？当然是靠近你边上的座位（当前CPU)，如果能抢到的话，否则就挑最弱小的下手。所以，系统维护了一个当前所有CPU的优先级，实际就是每个CPU上当前运行任务的优先级全局表，每个cpu上进行任务调度时，都会更新此表。那么当一个任务就绪准备抢占运行时，就会从这里面挑优先级最低的下手。
看起来是如此的简单，但实际上，这只是个大原则，由于SMP下涉及到任务绑定，任务迁移，CPU状态（active变成inactive）、相关队列的操作，还是有很多细节需要考虑的。
1、CPU的优先级状态表
这个全局状态表的结构与就绪队列类似，每个优先级列表包含了该优先级的CPU位图，一个优先级列表的位图（该优先级是否有CPU的指示），一个CPU优先级数组。查找时通过位图操作以加快速度。


下面分3种场景来分析下SMP下如何调度实时任务的。


1、任务被唤醒

当一个任务就绪时（比如睡眠时间到了，或者等待的信号量已经空闲了等情况），任务会被唤醒，这时候需要挑选一个合适的CPU。

什么是合适的CPU，其判断标准如下：

1）、当前任务为非实时任务，则不费心找了，抢占当前CPU正合适。

2）、被唤醒任务优先级大于当前任务，且当前任务允许在多个CPU允许，则不费心找了，抢占当前CPU正合适。

3）、被唤醒任务优先级大于当前任务，但当前任务只绑定了当前CPU,则需要进一步查找一个合适的CPU.

4）、被唤醒任务允许在多个CPU上运行，且其优先级比当前任务低，则需要进一步查找一个合适的CPU.



后面两种情况需要查找CPU的优先级状态表，找出与任务相匹配的优先级最低的CPU列表（如任务绑定了某些CPU，虽然目前还是优先级更低的CPU,还是不能选），然后再从列表中选择一个，其标准是：如被唤醒任务上一次运行的CPU在列表中，则选它；如果当前Cpu在列表中，则选它；否则根据调度域，选择一个。调度域简单说，就是根据远近亲疏关系，对CPU进行分组，后面讲负载均衡的时候再详细了解。

总的来说，第一，二种情况是尽可能快的响应（实时任务嘛），挑当前CPU下手，可以认为是fastpath；实在没办法了，查找优先级最低的CPU集合,并考虑cache和内存的利用率，从中挑选一个,可以认为是slowpath。

选择好目的CPU之后，则入该CPU的就绪队列，等待调度运行，同时把任务挂入待push队列（任务不是只绑定到目的CPU情况下）。



检查是否可以抢占当前任务，如果可以，置调度标志。特别情况，如果当前运行任务与被唤醒任务优先级相同，则需要判断运行任务是否可以在其他CPU上运行（比如被唤醒任务绑定了当前CPU,而运行任务没有绑定当前CPU，则可以让当前任务在其他CPU上运行，这样，皆大欢喜），可以的话把唤醒任务入队列头，置调度标志。



如果没有办法抢占，这时候会尝试把该任务推到其他的CPU上运行，此为所谓的"PUSH"机制。这时候挑选CPU与任务被唤醒时的处理是类似的，挑优先级最低的CPU列表，并考虑调度域，cache利用率等因素选择合适的CPU.

相应地，“PULL"机制，就是准备调度时，或者当前任务状态发生变化（优先级调整变低了，从实时任务变成非实时任务等），从其他CPU的可PUSH队列上拉任务过来运行。



到这里，任务已经放入合适的就绪队列，等待调度运行。


2、当前运行任务放弃CPU

当任务消亡、自愿（如sleep）或者被迫（如获取不到信号量）放弃CPU时，会触发调度，这时候需要挑选一个合适的任务来运行。

如果当前任务为实时任务，且就绪队列中没有比当前任务优先级高的任务，则系统可能还存在比当前任务优先级低的实时任务，这时候会触发PULL操作。这个操作主要解决如下场景：假设系统有两个CPU,4个任务，优先级分别为T1>T2>T3>T4，T1为CPU1的当前任务，T3在CPU1的就绪队列中，T2为CPU2的当前任务，T4在CPU2的就绪队列中。如果T2很快执行完毕，触发调度，则不能选T4，必须从CPU1中把T3给拉过来（如果T3是可push的，即T3没有绑定到CPU1去）。从这里也可以看出，PUSH和PULL机制实际就是为了解决任务第一次入队有可能并不是最佳的情况。如果系统只有一个就绪队列，那么每次都从队列头取任务，肯定就不会错了，虽然简单，但却造成了各个CPU都需要竞争同一个队列，各CPU的调度必须串行处理，性能上是不可接受的。因此，修改为各个CPU都有自己的就绪队列，但又可能导致了排错队，就引入了PUSH和PULL处理。



然后根据优先级位图的指示，从最高优先级队列中取出下一个待运行的任务。


3、任务被创建

对实时任务，会把当前的CPU作为任务初始运行的CPU；

任务状态置为就绪态，并入当前CPU的就绪队列；


检查是否可抢占当前任务，若是的话置调度位。



所谓调度，就是对资源的管理与分配。不同的是UP只需要关心管理任务资源，而SMP下还需要管理CPU资源，并且在这两者获得最佳配合，其复杂程度也就成倍的扩大。



到这里，实时任务的调度过程已经分析了清楚了。

下面我们来看看最近发生的有关调度的问题：


三、一个调度的问题

测试通过tesgine向8个收包任务发同样流量的报文，发现各任务的占用的CPU并不相近，相差接近20%，而且CPU占有率高的任务反而丢包；另外，发现有两个核的CPU占有率一直相对其他的核高，一个各核的CPU占有率不相近。我们的系统为6核12个VCPU。



通过上面的分析，应该可以很容易的解释这个现象：

一个房间里有6张二人沙发，每张沙发前有一个茶几，茶几上放着糖果。先来了6个人，则每个人刚好坐一张沙发，后来的两个人，只能和其他人挤一挤，这样就有两张沙发坐满了人，另外4张沙发只坐一个人（核间不均衡）。一个人独坐一张沙发的人就比较爽了，想吃茶几上的那个糖果，就能拿那个；而合坐同一张沙发的人，出手时还要看看不要碰到旁边的人，假如大家都对果冻感兴趣，还必须等另外一个人拿完你才能拿。所以，消耗同样的糖果下，合坐的人肯定要比独坐一张沙发的人时间长了（CPU占有率高）。勤快的菲佣不停的给每个人上糖果，合坐沙发的人由于吃的慢，慢慢的糖果就堆满了茶几，最后再也放不下了（丢包）。

合坐沙发的人为什么不移动到其他沙发去呢？移动到其他沙发又有啥好处呢，在这张沙发屁股刚刚坐热（cache hot), 到另外一张沙发还是要跟别人合坐，没啥好处。

另外一个小问题：内核是以座位为管理对象，而不是沙发为对象进行分配的，为什么先来的6个人，每个人坐一张沙发，而不是先安排2个人同坐一张沙发？实际上，内核在对座位进行编号时，使了个小花招，6张2人沙发其编号如下：沙发1有两个座位，座位号为0,6，沙发2的座位号为1,7，...所以，只需要按座位号对号入座就可以了。

任务一开始启动就是这样子吗？实际也不是的，这是稳定状态下的现象（在我们这个系统中，达到这个状态非常快）。前面说了，任务创建时赋予了初始的运行CPU就是当时创建代码所运行的CPU。收包任务的优先级为30，当时测试环境有比收包任务高的只有定时器任务（20）。假当时创建运行的CPU为0，收包任务分别为R1-R8，定时器任务为T1-T8,定时器任务肯定会抢占收包任务，但定时器任务运行时间很快，大部分都在睡眠，收包任务处理非常繁忙，当时的观察是70-90%的CPU占有率。假设R1先运行，紧接着其他收包任务也就绪，由于R1正在运行，其他收包任务只能迁移到其他CPU上运行，于是R2到了VCPU6(调度域的原因），R3->VCPU1,R4->VCPU2,R5->CPU3,R6->VCPU4,R7->VCPU5,R8->VCPU7.(上面假设收包任务按顺序R1->R8就绪调度运行, 每个收包任务就绪时编号在它前面的收包任务在运行，系统没有其他任务),实际运行情况稍微复杂，但不会影响最终的结果，通这时候定时器任务被唤醒抢占R1，于是R1被迁移到VCPU8。由于定时器任务大部分都在睡眠，因此，T1-T8任务很大概率都在VCPU0上运行，即使定时器任务运行时，另外一个定时器任务也就绪了，它只会被迁移到优先级最低的VCPU上（VCPU9,VCPU10,VCPU11),而不会抢占收包任务的VCPU。这样过几次的调度后很快就达到了稳定状态，由于收包任务在它运行的CPU上已经是最高优先级了，它也就不会被迁移，也就我们看到的最后现象。