CBS算法的RTAI内核调度器设计哈尔滨理工大学李兰英张向国摘要近年.PDF

电子发烧友 电子技术论坛 CBS 算法的 RTAI 内核调度器设计 哈尔滨理工大学 李兰英 张向国 摘要 近年来基于双内核架构增强 Linux 操作系统实时性的 RTAI[1] （RealTime Application Interface ）在工业控制等硬实时领域已经得到了越来越多的应用。本文提出的调度器通过采 用基于服务策略的 CBS 算法对 RATI 内核下的EDF 调度器进行扩展，可以保证分配一定的 CPU 资源供 Linux 上的软实时应用，即使在有硬实时任务并发时也能得到处理器资源。实 验结果证明了基于 CBS 算法扩展 RTAI 内核调度器的正确性。 关键词：RTAIinux ，BS 算法，内核调度器 引言 嵌入式系统大多工作在有实时性要求的环境中，有些嵌入式设备可能需要软件在 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 都以相同