CBS算法的RTAI内核调度器设计

近年来基于双内核架构增强Linux操作系统实时性的RTAI[1]（RealTime Application Interface）在工业控制等硬实时领域已经得到了越来越多的应用。本文提出的调度器通过采用基于服务策略的CBS算法对RATI内核下的EDF调度器进行扩展，可以保证分配一定的CPU资源供Linux上的软实时应用，即使在有硬实时任务并发时也能得到处理器资源。实验结果证明了基于CBS算法扩展RTAI内核调度器的正确性。

关键词 RTAI Linux CBS算法 内核调度器

引言

　　嵌入式系统大多工作在有实时性要求的环境中，有些嵌入式设备可能需要软件在ms级时间单位内做出响应，而有些实时任务则要无任何延时地以几ms的周期执行，这就迫切需要一个功能强大、配置方便的实时操作系统来支持。一些商业的嵌入式实时操作系统（如Windows CE、VxWorks等）价格都比较昂贵，这就促使人们转向了改造通用嵌入式操作系统，使其满足实时性。这种改造要求源代码必须开放，而Linux是嵌入式应用中的通用嵌入式操作系统，源代码开放，满足改造研究上的需求。

　　对Linux实时化改造的方案很多，主要有两种：一种直接修改内核，另一种是采用双内核机制。第一种方法只能用于软实时应用，只有双内核架构的方案可以保障硬实时应用的截止期不被错过。但是，双内核架构在软、硬实时任务混合的应用环境中还存在一些问题。由于硬实时任务工作在RTAI实时内核空间中，而软实时任务工作在Linux内核空间中，Linux作为优先级最低的任务被顶层实时内核调度执行，在一段时间内可以分配给软实时任务的处理器时间依赖于RTAI硬实时应用对处理器带宽的要求，而且在不同的时间段内可用的处理器时间一般会有很大的不同。这就难以保障运行在Linux中的软时应用达到预先设定的服务质量水平。

1  基于服务策略算法的实时调度器

　　针对双内核架构下增强Linux实时性时存在的问题，本文提出一种实时调度器，采用基于服务策略的CBS算法对RTAI内核下的EDF调度器进行扩展，保证在有硬实时任务的同时满足Linux内核空间下软实时任务的周转时间。

1.1  实时调度器基于的CBS算法定义

　　为了缩短混合实时任务调度中软实时任务的响应时间，以及减少软实时任务错失截止期，人们提出了多种软实时任务的调度算法。典型的有基于服务策略的算法，又称“带宽预留算法”。该算法在保证硬实时周期任务满足截止期的前提下，预留出适当的处理器带宽作为服务器来处理软实时任务，常用的算法有CBS、TBS算法等。服务策略的含义是： 服务器把到达的任务放入一个非优先规则的队列中，该队列的第一个任务根据分配的截止期插入EDF调度队列中，如果队列的第一个任务被插入到调度队列等待调度，则称“服务器是合格的”，否则称“服务器是不合格的”；如果队列的第一个任务正在执行，则称“服务器为活动的”。下面给出了采用CBS算法时软实时任务在不影响硬实时任务截止期的情况下是否可以调度的判别准则。

　　假定某一实时任务Ti的处理器带宽记为（Ci,Pi），表示任务Ti在周期Pi内最多占用Ci的处理器时间。定义实时任务Ti的处理器利用率为：

　　现假定系统中n个实时任务，记为{T1,T2,…,Tn}，对应着n个处理器带宽参数，记为（Ci,Pi），其中i=1, 2,…,n。则此任务集可调度的条件为：

满足上式时任务集是可调度的。其中Umax是EDF算法调度时CPU处理器利用率的最大值。

　　CBS算法步骤详细定义如下：

　　①  一个CBS服务器用预留执行能力cs和有序对（Qs，Ts）来表示。其中，Qs表示服务器的最大执行能力补充值，Ts表示服务器周期。服务器带宽Us=Qs/Ts。服务器截止期的初始值ds,0=0，而任意时刻，服务器的修正截止期ds,k和服务器相关联。
　　②  被服务器服务的任务（队列的第一个任务）被分配一个动态截止期di,j，该截止期等于当前服务器截止期ds,k。
　　③  不管一个任务什么时候执行，服务器的预留执行能力cs都以相同的数量递减。
　　④  当预留执行能力cs递减到零时，马上被重置为最大执行能力补充值Qs，同时产生新的服务器截止期ds,k+1=ds,k+Ts。
　　⑤  在时刻t，如果存在一个服务的任务Ji,j(ri,j≤t≤fi,j)，那么称“CBS处于活动状态”，否则称为“空闲状态”。
　　⑥  当一个作业Ji,j到达时，如果此时服务器处于活动状态，那么任务的服务请求进入挂起任务队列，此队列需是非抢先原则的队列（如先进先出队列）。
　　⑦  当一个任务Ji,j到达，且服务器处于空闲状态时，如果cs≥（ds,k-ri,j）Us，那么服务器产生一个新的服务器截止期ds,k+1=ri,j+Ts，并且把预留执行能力cs重置为最大执行能力补充值Qs，否则服务器使用当前的服务器截止期ds,k和当前的预留执行能力cs来对任务进行服务。
　　⑧  当一个任务完成时，服务器利用当前的预留执行能力和截止期继续为挂起任务队列中的任务服务。如果挂起任务队列中没有任务，那么服务器变成空闲状态。
　　⑨  在任何时刻，服务器分配给任务的截止期为最后生成的服务器截止期。

1.2  EDF调度器的CBS算法扩展设计

1.2.1  EDF调度器的总体结构设计

　　先引入一种“虚拟任务”的概念。所谓“虚拟任务”，就是指由RTAI底层实时小内核按EDF算法直接调度执行的一种特殊的硬实时任务，对应于Linux用户空间的某一软实时应用。其任务截止期由RTAI内核下的CBS服务器计算得出。

　　本文将RATI内核下的EDF调度器进行了以下扩展：

　　①  在EDF调度层，仍然采用原RTAI内核下调度器采用的EDF调度算法，对硬实时周期任务和虚拟任务集合进行调度；而CBS服务器则按一定的比例占用处理机时间，同时通过服务器接口与一个实时应用相对应，为其提供资源服务。
　　②  在服务器层有CBS服务器核和CBS服务器接口。

　　CBS服务器核的主要功能是根据传入的相关调度信息维护底层实时小内核中的可用CBS服务器队列，在任务开始、挂起、终止等调度时执行相应的事件处理函数来调整CBS服务器的属性参数，实现CBS算法。

　　EDF调度器扩展如图1所示。

图1  EDF调度器扩展

　　在服务器接口中，由于硬实时任务工作在RTAI实时内核下，而软实时任务一般工作在Linux内核下，因此服务器维护的虚拟任务为了与实际的实时任务建立对应，就需要一个接口来实现它们的映射关系。本文通过这个接口层来为Linux内核中的实时任务和RTAI内核下的虚拟任务提供映射实现。

1.2.2  EDF调度器扩展后调度主要算法步骤

　　①  不同类型的新应用程序到达时，通过服务器接口层中的系统调用对其进行判别控制检查，主要通过式（2）来进行。如果通过检查，则说明调度新到达的应用程序不会影响硬实时任务的截止期。
　　②  通过判别检查之后，CBS服务器为其创建一个与新应用程序对应的虚拟任务，并根据新应用程序传入的调度参数和自己的调度策略，计算得到虚拟任务的任务截止期。如果此时服务器是活动的，将此新虚拟任务挂入服务器维护的先进先出队列。取出服务器的先进先出队列队首虚拟任务，并根据任务截止期大小进入RTAI实时内核的EDF就绪队列；同时，新应用程序也加入到Linux内核下相应的调度对象集合中，调度对象集合是一个由与新任务相匹配的具体调度器调度的集合，这个调度器基于某种调度算法，不是本文的讨论重点，但是如果从整个系统的实现来说，这些都是必不可少的部分。本文重点实现的是RTAI内核下对软硬实时混合调度的支持。
　　③  虚拟任务与RATI下的硬实时周期任务一起由EDF调度器统一调度分配。

1.3  EDF调度器的扩展实现

　　根据扩展设计方案，下面讨论在对EDF调度器进行扩展时所涉及的关键问题及解决途径。

1.3.1  EDF调度层扩展的关键问题

　　首先是实时内核的虚拟任务和Linux用户空间中的软实时任务的映射问题。软实时任务是运行在用户空间的Linux进程中。它通过CBS服务器接口层中的新增系统调用rt_schedule_test()进入准入测试后，调用CBS服务器接口层的新增系统调用rt_create_virtual_task()创建虚拟任务，并且传入软实时应用的进程ID，应用调度器ID在虚拟任务结构体中保存下来。当虚拟任务被EDF算法调度执行时，它通过实时内核中的软中断模拟机制保存对应的进程ID，应用调度器ID到中断暂存表，然后调用rt_switch_to_linux切换到Linux内核。Linux内核通过应用调度器ID找到调度器，将要调度执行的进程ID传给此调度器，由调度器调度此进程执行，这就实现了虚拟任务与软实时应用的对应。

1.3.2  服务器核实现的关键问题

　　①  为减少系统中的全局数据结构种类，虚拟任务与实时任务使用同样的数据结构定义。为此，修改了RTAI的实时任务的rt_task_struct结构定义：添加了与虚拟任务相关的属性，如对应的具体软实时任务的ID、软实时任务调度器ID、任务截止期和指向CBS服务器的指针；定义了服务器数据结构体rt_CBSServer，属性参数有服务器的预留执行能力计算值、已使用的服务器预留的计算值、周期、开始时间、截止时间以及服务器先进先出队列VTQueue。
　　②  CBS服务器算法的实现。CBS服务器算法需要在虚拟任务到达事件、虚拟任务完成事件以及服务器预留执行能力耗尽事件发生时刻，及时对服务器的相关属性和虚拟任务属性进行调整，特别是虚拟任务的截止期和服务器的截止期。

　　下面介绍基于服务策略的CBS算法的伪代码实现。[!--empirenews.page--]

　　虚拟任务到达事件发生时的处理：

if（虚拟任务到达事件发生） {
　　把该虚拟任务加入到服务器的先进先出队列；
　　N=N+1；//服务器的先进先出队列任务数加1
　　if（此时服务器空闲&&N==1） {
　　　　if(c>=(dk-rj)Us) {
　　　　　　ak=rj;
　　　　　　dk=ak+Ts;
　　　　　　c=Qs;//计算服务器预留执行能力和截止期
　　　　}
　　　　else{
　　　　　　ak=rj;
　　　　　　dk=dk-1;//设置截止期
　　　　}
　　}
}

　　虚拟任务完成事件发生时的处理：

if(任务完成事件发生) {
　　从EDF调度器就绪任务队列和服务器先进先出队列中删除该虚拟任务；
　　N=N-1;
　　if（N!=0）{
　　　　利用当前的服务器截止期dk调度服务器先进先出任务队列中的下一个任务到EDF调度器就绪队列中；
　　}
　　if（任务执行了一个时间片） {
　　　　c=c-1;//服务器预留执行能力减1
　　}
}

　　服务器预留执行能力耗尽事件发生时的处理：

if（服务器执行能力==0） {
　　dk=dk-1+Ts;
　　c=Qs;//计算截止期,并补充预留执行能力
}

其中，dk为服务器的截止期；ak表示服务器下次执行的起始时刻；rj表示任务到达时刻；c表示服务器剩余执行能力。Qs和Ts分别为CBS的最大容量预算补充值和周期；Us是这个服务器的利用率。

1.3.3  服务器接口实现的关键技术

　　该层主要在RTAI内核下增加一些新的系统调用供Linux内核使用。

　　rt_create_virtual_task()： 创建虚拟任务。首先在系统内存中为服务器分配所需的内存空间；然后根据传入参数填写rt_task_struct{}结构,特别是与服务器相关的几种变量值；最后将其放入系统任务队列中。

　　rt_schedule_test()： 对新到来的应用进行准入测试。主要是通过CBS算法进行测试，如果不能通过准入测试，则失败退出；否则调度rt_create_virtual_task()创建虚拟任务，将任务挂入相应的服务器队列中，等待调度。

　　rt_delete_VTtask()： 在Linux内核下可调度这个函数来实现对RTAI内核下的虚拟任务的删除。

2  验证

　　本文通过在硬件配置为CPU AMD Duron 1.10G、256 Mb内存，操作系统为Fedora core5、编译器为gcc的环境下分两次安装RTAI内核包（分别为EDF调度器扩展前和扩展后），对软硬实时任务并发时软实时任务的周转情况进行记录并进行分析。软实时任务采用Linux操作系统下的多媒体播放器，硬实时任务采用通过编程实现的周期性实时计算任务，运行周期为10 ms。硬实时负载由编程实现的硬实时负载程序精确得到，本实验中进行了3种负载的测试，分别为轻负载、中度负载和重负载。

　　多媒体播放器是否正常播放可用下式衡量：

式中： ei为第i帧图像数据解码时产生的时间偏差，ti为第i帧图像解码完成时刻，ti-1为第i-1帧图像解码完成时刻，40 ms是正常情况下MPEG4相邻帧图像的标准解码时间间隔。若时间偏差小于或等于0，则mplayer可正常播放；否则，将出现图像抖动和断续现象，偏差越大，异常越明显。本实验主要分析了时间偏差大于0时的情况。

　　使多媒体播放器运行大于30 s的时间，获取750帧的数据。分别得到的EDF调度器扩展前和扩展后的实验数据，如表1和表2所列。

表1  EDF调度器扩展前Linux调度下的多媒体播放器播放情况

表2  EDF调度器扩展后Linux调度下的多媒体播放器播放情况

　　对表1和表2中的数据进行分析。在轻度负载0.3时，时间偏差10 ms以下的帧数占总帧数的累计百分比基本相同，分别为99.6%和99.7%；说明对EDF调度器进行扩展前后，对多媒体播放器播放效果基本没有差别。在中等负载0.53时，扩展前播放器解码时间偏差在20 ms以下的帧数占总帧数的44.65%，播放效果出现异常，人眼能感觉到；扩展后，偏差在20 ms以下的帧数占总帧数的99.82%，人眼不容易觉察播放的异常。在重负载0.81下，扩展前时间偏差在20 ms以下的帧数占总帧数的0%，也就是说时间偏差都会大于20 ms，这样每一帧图像数据很大程度上将被延迟播放；扩展后时间偏差在20 ms以下的帧数占总帧数的99.57%，仍然可以满足播放器的播放效果。

3  结论

　　本文提出的基于CBS算法的EDF调度器，实现了RTAI实时内核的资源预留，可为Linux内核空间下的软实时应用保留一定的处理器带宽，较好地解决了双内核架构下软实时和硬实时混合的应用环境中软实时应用因错过截止期得不到响应的问题。本文重点讨论了对RTAI下的EDF调度器在CBS算法上的扩展实现，而Linux内核空间下的应用调度器针对不同的软实时应用算法也很多，且软实时任务之间的相互依赖关系本文也没有考虑。这些是今后工作中着重研究并加以解决的问题。李兰英(副教授)，主要研究方向为工业企业自动化、计算机控制和嵌入式系统。