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

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

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内核空间下的应用调度器针对不同的软实时应用算法也很多，且软实时任务之间的相互依赖关系本文也没有考虑。这些是今后工作中着重研究并加以解决的问题。李兰英(副教授)，主要研究方向为工业企业自动化、计算机控制和嵌入式系统。