多处理器下的硬实时操作系统研究

gujideshatan

0   引言
  Linux 是一个具有广阔前景的操作系统，从桌面工作站到低端服务器，处处都可见它的身影。现如今，Linux 正全力进军嵌入式系统和高端服务器系统领域，但它的技术缺陷却限制了它的竞争力：虽然Linux继承了传统Unix的公平调度机制即分时调度策略，提供了一个稳定的操作系统的管理系统，但是它仍然不能解决实时系统要求的纳秒级的中断延迟、任务切换时间，即便是当前的2.6内核，也只是在linux内核中添加了一些可抢占点，对实时性的支持也还是不尽人意。
  现如今提出了一种将实时任务与SMP体系结构相结合的方案，由于它将处理器以实时与非实时的方式进行了划分，所以称之为不对称的多处理器原则。尽管这种方案是可行的，但是它仍存在一个很大的弊端：在非实时处理器负载过重的情况下，实时处理器可能会处在空闲的状态，这样就造成了极大的资源浪费。于是一种对这种方案进行拓展的实时系统――ARTiS系统便应运而生。
  1    ATRiS简介
  ATRiS是一个以多处理器（SMP）架构为基础，对linux进行实时拓展的系统。它的核心思想是：“将多个处理器进行分类，即分为实时处理器（RT CPU）和非实时处理器（NRT CPU），在实际的运行当中，它将通过自身的迁移机制实现非实时任务在进入不可强占状态前迁移到非实时处理器，以便实时处理器及时响应实时任务。并通过改进的负载平衡机制使ATRiS系统充分发挥SMP架构的优势。
  1.1 ATRiS任务与处理器的划分
  在ATRiS系统中不仅将处理器分为了实时处理器与非实时处理器，而且将任务也分成了三种类型，分别是RT0任务、RT1+任务以及Linux任务，分别对应于现实中的硬实时任务，软实时任务和非实时任务。下面给出了处理器与任务之间的关系：
  RT0任务：对应于要处理的硬实时任务，具有最高的优先级。并且每一个RT0任务都会与唯一的一个实时处理器绑定，于是RT0任务就只能运行在实时的处理器上。
  RT1+任务：对应于要处理的软实时任务，可以运行在实时处理器，也可以运行在非实时处理器上。但是当它要运行在实时处理器上时，必须是处于可抢占的状态，否则就要迁移到非实时处理器上。
  Linux任务：即非实时的linux任务，与RT1+任务一样，它也可以运行在实时处理器上，并且当它执行到一段不可抢占的代码时需要迁移至非实时的处理器。
  1.2 迁移机制
  ARTiS中迁移机制的目标是：在保证可以实时响应RT0任务的前提下，尽可能多的发挥多处理器的并行特性。为了满足这一目标，它要求实时处理器上的非RT0任务在进入到不可抢占的代码段时必须自动迁移到非实时处理器。为了使迁移不受阻碍的发生，ARTiS去掉了处理器之间的共享锁，取而代之的是一个FIFO队列，用它来实现非实时处理器与实时处理器之间的交互。也就是说，ARTiS中的处理器将通过这个FIFO队列来存放或者取出需要迁移的非RT0任务。
  1.3 负载平衡机制
  通常的负载平衡机制是指：通过在多台计算机之间合理地分配负载，使各台计算机的负载基本均衡。但是在ARTiS系统中RT0任务是不可迁移的，而且linux原有的负载平衡机制只是针对于处理对称处理器（实时处理器与实时处理器，非实时处理器与非实时处理器）之间的负载平衡，并未设计不对称处理器之间平衡负载的方法。所以相对的负载平衡机制也更加复杂。
  2   ATRiS机制实现
  ATRiS系统的实现机制是通过改变内核源码实现的，由于它所要实现的只是在实时处理器空闲时将非实时任务迁移至实时处理器，而在非实时任务到达不可抢占代码时迁移出实时处理器，所以它所要执行的主要功能就是：在实时处理器空闲的状态下，通过自身的负载平衡机制将非实时处理器上的任务迁移至实时处理器。而当非实时任务执行到不可抢占的代码时，利用自身的迁移机制将非实时任务迁移至非实时处理器。
  尽管如此，ARTiS并不是完全另起炉灶，它只是在linux原有的任务迁移和负载平衡机制上添加一些自己的函数，由此来实现自身特有的任务迁移和负载平衡机制。
  2.1 任务迁移机制
  ATRiS系统的迁移机制的核心就是：当一个非RT0任务将要执行到不可抢占的代码部分时，将会自动的从实时处理器迁移至非实时处理器。可以将该机制看作两步：第一步是确定非RT0任务的不可抢占点，即确定迁移的时机；第二步则是要将任务从实时处理器迁移至非实时处理器，即实现迁移。
  l   确定迁移的时机
  在ARTiS系统中的任务是通过注册而产生的(RT0任务就是通过int artis_enter_rt0(pid_t pid, int rt_cpu)函数注册的，RT1+任务是通int artis_enter_rt1plus(pid_t pid, int policy, int priority)函数注册)，由于RT0任务是不存在被抢占的问题的，所以这里只考虑RT1+问题发生迁移的时机，ARTiS系统认为，如果一个任务执行了系统函数preempt_disable()或local_irp_disable()时，则表明他将要进入不可抢占状态，即需要进行任务的迁移。ARTiS系统在上述的两个函数中添加了函数artis_try_to_migrate()，该函数首先会判断是否满足迁移其他条件（例如：判断当前运行的处理器是否是实时处理器等），然后调用函数artis_request_for_migration()请求迁移。
  l    实现迁移
  当非RT0任务调用了函数artis_request_for_migration()时，它不能直接把自己插入到其他处理器的运行队列当中，因为这样就会造成多处理器在同一时间运行同一任务的情况，所以在ARTiS系统中，是通过与当前处理器上的下一个任务来插入迁移任务的，总的来说可以分为三步：首先，迁移进程会调用artis_request_for_migration()，设置迁移标志，并将自身的亲和CPU设置为本地CPU，然后使自身再次进入可抢占状态，调用调度函数。然后，新调度的任务将执行函数artis_complete_megration()，该函数将调用函数finish_task_swith()完成调度，选择一个非实时处理器把迁移任务插入到其上的RT-FIFO队列，并通过产生一个进程间的中断信号来强制目标处理器产生一轮新的调度。最后，目标处理器上的调度程序将通过调用函数artis_fetch_migration()从RT-FIFOs队列中取出迁移任务。
  2.2 负载平衡机制
  在ARTiS系统中，当涉及对称处理器之间的负载平衡时，直接沿用原有的负载平衡机制。而对于不对称处理器上的负载平衡，则通过修改原linux的负载平衡机制来实现。由于非实时任务从实时处理器到非实时处理器的迁移是强制的。所以不存在负载平衡的问题，所以这里只考虑如何将非实时处理器上的非实时任务迁移至实时处理器。可以从两个方面进行分析：一个是确定迁移的目标处理器，一个是确定要迁移的任务。
  l    确定迁移的目标处理器
  CPU的负载指的就是该CPU运行队列的长度（在该CPU上等待运行的程序个数），Pairing policy首先计算各个CPU运行队列的长度，然后把负载最重的CPU上的任务分配到负载较轻的CPU上。当各个CPU处理的都是非实时的任务时，该策略则运作的很好，因为非实时的任务将平分CPU的时间，但是在有实时任务的情况下，由于实时任务具有绝对的优先级，它将独占CPU，所以不能再简单的只用运行队列的长度来衡量负载的大小。
  在ARTiS系统中，在原有的策略上，添加了一个由实时任务的运行时间构成的负载参数，这时将通过公式L× 1/1?RT (L表示某个CPU上非实时任务的个数，RT表示实时任务需要占用CPU的时间)计算各个处理器上的负载。例如：假设在双CPU的情况下有6个任务（包括实时任务），实时任务需占用CPU时间的3/4的，对于通常的分派策略，一个处理器分三个任务，那么在一个处理器上，每个非实时任务将占用1/3的CPU时间，而在另一个处理器上，非实时任务占用的时间只有1/8，显然分配很不均等。在ARTiS中，它首先会统计每个处理器上的非实时任务的个数，并利用公式L× 1/1?RT计算出每个处理器的负载，然后选择负载较轻的处理器作为目标处理器，这时每个非实时任务将都会占有1/4的处理器时间，达到了负载均衡的目的。参照下图：

图一：ARTiS负载平衡算法
  l         确定迁移的任务
  当确定了迁移的处理器之后，接下来要确定的就是要迁移的任务。选择的标准就是尽量选择那些可以在实时处理器上可以较长保持可抢占状态的非RT0任务，如果一个非RT0任务迁移的频率过高，那么就会造成非RT0任务在实时处理器与非实时处理器之间推来推去，即所谓的乒乓效应。这样不仅没有达到负载平衡的目标，反而降低了改任务执行的效率。
为了避免乒乓效应，ARTiS采用统计的方式来预估一个任务可能的迁移频率（在任务属性中添加两个变量，分别用来保存迁移请求的时间间隔平均值和上一次迁移发生的时间），并通过该预估的频率与当前迁移任务发生的时机相比较，由此来决定当前的任务是否可以迁移。对于一个请求迁移的任务，由于它的请求点有可能发生在预估请求之前，也有可能发生在预估请求之后，所以分两种情况：当请求点发生在预估点之前时（如图2中的第五个迁移点所示），如果它离预估的迁移点很近，那么说明它马上又要迁移了，所以应当被阻止，而如果离预估点较远的话（如图2中的第4个迁移点）。同样对于请求点发生在预估点之后的迁移请求，如果离预估点很近的话（如图2中的第一个迁移点），那么认为它刚刚发生过迁移，所以不允许短时间内再次迁移，所以也会被阻止，而与之较远的（3）、（4）迁移点则可进行迁移。由此可见，在设计的同时设定的偏差范围将直接影响ARTiS的性能，所以应当通过多次的试验来选取一个合适的偏差。

3  多种实时方案比较
  目前增强Linux实时性的方法有两大类。一类是以RT-Linux，RTAI为代表的改造内核的方法：写一个专用的实时微内核，让传统的Linux做为一个优先级最低的进程，这种方法的优点是可以提供象专用RTOS一样的硬实时性，缺点是不能保证Linux应用和设备驱动程序的完全兼容，加上实时任务只能享有实时内核提供的有限服务（缺少了强大的网络实时功能），所以代价也是相当大的。一类是以MontaVista公司的Linux为代表的可抢占的Linux内核方式，这种可抢占的Linux内核是使用SMP(对称多处理器)技术在单个X86、PPC、ARM等RISC CPU以补丁形式加在内核上，这种方法的优点是与任何Linux应用和设备驱动程序兼容，缺点是并未达到严格意义上的硬实时，而且在实时任务很少的情况下，会造成实时处理器空闲而非实时处理器超载的情况。
  ATRiS系统是一个以第二类方案为基础的实时操作系统，针对于第一类的实时方案，它不仅达到了对硬实时的支持，而且在可以充分利用linux所提供服务的同时，实现了linux应用和设备驱动程序的完全兼容，即在与第一类实时方案举案齐眉的情况下，还弥补了它的不足之处。而相对作为第二类方案的拓展，它在原有的基础上实现了真正意义上的硬实时，而且充分发挥了多处理器的高效特性。虽然它也是建立在修改内核代码的基础之上，开发起来有一定的难度，但是相对与它在linux实时方面所表现出来的几乎完美的特性，还是很值得推广的！
  4   结论
  本文论述了一种新型的提高linux实时性的方案。由于ARTiS是一个专门针对对多处理器的实时操作系统，它的出现及时的填补了当前多处理器与实时任务时间的鸿沟，为实时操作系统提供了一个新的发展方向。
  参考文献
[1]      Eric Piel, Philippe Marquet, Julien Soula, and Jean-Luc Dekeyser , Asymmetric Scheduling and Load Balancing for An asymmetric model for real-time and load balancing on Linux SMP, LIFL Reseach Report 2004-04, April 2004.
[2]      Eric Piel, Philippe Marquet, Julien Soula, and Jean-Luc Dekeyser. Load-balancing for a real-time system based on asymmetric multiprocessing.In 16th Euromicro Conference on Real-Time Systems, Catania, Italy, June 2004.
[3]       ITEA Hyades Project. Linux for high performance and real-time computing on SMP systems. In Sixth Realtime Linux Workshop, Singapore, November 2004.
[4]       Victor Yodaiken. RTLinux beyond version 3. In Third Real-Time Linux Workshop, Milano, Italy, November 2001.
[5]       Sillicon Graphics, Inc. REACT: Real-time in IRIX. Technical report, Sillicon Graphics, Inc., Mountain View, CA, 1997.
[6]       Kevin Morgan. Linux for real-time systems: Strategies and solutions. White paper, MontaVista Software, Inc., 2001.
[7]     李小群,赵慧斌,叶以民,孙玉芳.RFRTOS:基于Linux的实时操作系统.2003,14(7):1203-1212
[8]     吴姣梅,李红艳,吴保荣,严明.改善嵌入式Linux实时性能的方法研究. 微计算机信息，2006，1-2：72-74