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来对任务进行服务。
　　⑧ 当一个任务完成时，服务器利用当前的预留执行能力和截止期继续为挂起任务队列中的任务服务。如果挂起任务队列中没有任务，那么服务器变成空闲状态。
　　⑨ 在任何时刻，服务器分配给任务的截止期为最后生成的服务器截止期。