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

　　引言

　　嵌入式系统大多工作在有实时性要求的环境中，有些嵌入式设备可能需要软件在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的处理器利用率为：