一种分区操作系统实时任务调度方法

周霆　胡宁　任晓瑞

摘 要：本文以提高在综合化航空电子系统混合任务场景中的实时任务响应性能和解决遗产代码重用问题为目标，提出一种具备虚拟化支持能力的分区操作系统实时任务调度方法。该方法通过建立全局调度队列，并对任务状态进行合理控制，相比已有分区操作系统两级调度模型更为灵活，并且保证了虚拟化分区中客户操作系统自身的调度策略不被破坏，能够满足分区操作系统对任务调度实时性和虚拟化支持能力的需求。

关键词：分区操作系统；任务调度；全局调度队列；虚拟化支持

中图分类号：TP316.2

随着航空电子技术的发展，机载电子系统综合化模块化（Integrated Modular Avionics，简称IMA）成为必然发展趋势，一个物理平台可能承担来自多个系统的不同类型的任务，这些任务对基础平台的处理特性有着极为不同的需求。例如，机电应用可能需要快速处理多个外部事件，飞控应用可能需要根据当前传感器数据及时进行舵面控制，而航电应用可能需要进行复杂计算以完成某种功能，这些应用综合在一起，提出了强实时任务与一般任务共存的需求。如图1所示的操作系统（简称OS）架构所示[1]，目前为了解决综合化带来的故障隔离和信息安全问题，现有的高安全机载操作系统都采用了分区机制，提供分区间隔离与分区间通信能力。现有的典型分区操作系统，如VxWorks653等采用两级任务调度策略，分区调度凌驾于分区内的任务调度之上，任务响应难以逾越分区时间窗口的限制，虽然能够确保任务的确定性实时响应，但是无法对任务从全局层面提供以任务为单位的统一调度，需要进行大量的前期任务规划，缺乏灵活性。

另一方面，机载软件的开发和验证成本相对较高，业界一直在探索降低机载软件成本的途径。系统综合中重用遗产代码可以有效降低成本，提高系统的安全性。虚拟化能够为代码重用提供有效支持[2]，支持虚拟化也成为机载操作系统发展的一个新的方向。如何在不破坏虚拟化分区中客户OS自身调度策略的前提下进行全局统一调度，也是综合化调度算法亟待解决的问题。

面对上述问题，需要通过在软件架构层面优化，提出新的综合化任务调度方法[3]，使含有虚拟化分区的混合任务环境下的强实时任务调度成为可能。

1 强实时全局统一调度算法

如图2所示，为了从根本上提高系统混合任务场景中实时任务的响应性能，必须减少调度层次，给分区操作系统所有分区内的每个任务赋予全局统一优先级，在分区管理程序中维护一个全局优先级调度队列，进行全局统一调度。具体来说就是将所有任务的当前优先级都映射为全局的统一优先级，然后在时间片耗尽和实时事件触发时，由分区管理程序的调度器进行统一调度。

在图2中，以分区中分别运行包含大量非实时应用的普通OS（例如Linux）和实时OS（简称RTOS，例如μC/OS）为例，虽然运行在RTOS上的实时任务通常具有最高的调度优先级，然而每个RTOS中也有低优先级的后台活动，它们不应该抢占运行在普通OS之下的用户前台任务。同样的，普通OS也会运行一些软实时活动（比如媒体播放器），而这些软实时活动可能会抢占RTOS中别的实时活动。很明显，使用现有分区操作系统那种分散的、层次性的调用模型，需要进行大量的前期任务规划来应对这种复杂的混合任务场景。

本文中分区管理程序中的调度器提供的综合化调度算法是一种抢占式、严格优先级、在最高优先级任务之间进行时间片轮转的调度算法。如图2所示，调度器维护一个包含255个优先级的全局就绪任务队列，调度器总是选择队列中具有最高优先级的任务获得处理器，如果处于最高优先级的有多个任务，则进行时间片轮转（RR，Round-Robin）调度。

本调度方法也提供了足够的用户可控支持[4]。用户可以通过系统服务动态的改变任何一个任务的以下3个基本调度参数：（1）优先级，0-255；（2）时间片长度；（3）处理器的编号。从而，任务的时间片通过在调度前对优先级的进行计算由系统缺省配置，也可以由用户通过系统服务进行修改。

出于调度开销和效率的考虑，本方法通过分析各种调度时机，可以在确认不会有更高优先级任务就绪的情况下不触发调度器而直接进行切换。

其中触发调度器调度的时机如下：（1）当前线程的时间片耗尽；（2）当前线程主动放弃时间片；（3）分区间通信（IPC，Inter-Partition Communication）操作阻塞当前线程或激活另一个线程。

不激活调度器，直接触发任务切换将减少系统开销，增加执行效率[5]。任务直接切换的时机如下：（1）中断发生时，通过全局优先级决定获取执行权的是当前线程或用户级中断服务线程；（2）IPC机制触发多个接受线程就绪，则在发送方和多个接受方之间选择一个优先级高的任务直接切换，此时可以不考虑优先级，而选用其他策略。

相比现有的两级调度算法，依据上述调度策略，借助合理的优先级部署，可以有效提高关键任务的实时响应性能，但是单级的综合化调度如何保证在虚拟化条件下分区中客户OS原有的调度策略不被破坏，是一个必须要解决的问题。

2 维护客户OS的自有调度策略

对于图2所示的全局调度策略，对于同一类型的任务全部给定相同的全局优先级，相同优先级的任务在全局实时调度中是以轮转Round-Robin方式进行调度。这种优先级配置策略在系统存在虚拟化分区的情况下将破坏客户OS原本的调度策略（比如Linux的普通用户级任务使用CFS调度策略），违反虚拟化的原则[6]。因此，分区管理程序和客户OS必须采取必要的措施，在无其它分区更高优先级任务抢占时采取合理的配合机制，保留客户OS自身的调度策略。

本文提出的调度方法解决此问题的基本原理是：首先，限制单个客户OS上应用级任务在全局调度队列中同时出现，从而使全局调度策略无法影响到客户OS内部的任务调度；其次，在触发调度的时机，全局调度器优先调度，如果没有当前运行客户OS之外的更高优先级的任务就绪，则将调度控制权交给当前客户OS的客户级调度器，此时激活客户级调度策略。

如图3所示，如果能够保证在每一时刻所有的客户OS应用级任务只有一个处于全局就绪队列中，就可以避免多个同等全局优先级的用户级线程按照全局调度策略进行轮转调度。在创建客户OS的任务时通过分区管理器系统服务修改任务在分区管理器中的系统状态，使其一经创建就处于未激活状态，不进入全局调度队列。在客户OS分区中创建一个高优先级的定时器处理线程timer_thread[7]，这个线程处理所有的客户级时间中断（真实时间中断在分区管理器的预处理中已经判断了在全局队列中是否有其他更高优先级线程就绪的情况，有则调用分区管理器的全局调度器进行调度），否则唤醒客户OS的调度器，依据客户OS的调度策略进行调度，启动获取CPU的新任务，将其加入全局队列，更改被剥夺CPU的上一个任务的状态（将其屏蔽出全局队列），从而保证了同一时刻所有的客户OS用户级线程只有一个处于就绪状态。

通过上述机制，可以在确保实时性和坚持虚拟化原则的基础上，完成分区管理器和客户OS的调度配合，达到在虚拟化分区内维护客户OS自有调度策略的目标。

3 结论

本文针对航空电子系统综合化产生的实时任务和非实时任务共存的混合调度需求，以及遗产代码继承产生的虚拟化需求，能够在不破坏虚拟化原则的前提下，对实时任务和非实时任务进行全局统一的单级调度，改进实时任务的响应性能，解决全局调度策略破坏客户OS自有调度策略的问题，突破现有两级调度策略的瓶颈。

参考文献：

[1]Alves-Foss J，Oman P W，Taylor C，et al.The MILS Architecture for High-assurance Embedded System.International Journal of Embedded Systems，2006，2（3/4）：239-247.

[2]Gernot Heiser，PhD.Virtualization for Embedded Systems.

[3]Sergio Ruocco，Real-Time Programming and L4 Microkernels.

[4]J. Kamada， M.Yuhara， and E.Ono.User-level real-time scheduler exploiting kernel-level fixed priority scheduler.In Multimedia Japan，Mar，1996.

[5]M. Hohmuth and H.H¨artig.Pragmatic nonblocking synchronization for real-time systems.In 2001 USENIX Techn.Conf.，Boston，MA，USA，2001.

[6]U.A.Steinberg.Quality assuring scheduling.Diploma thesis，Dresden University of Technology，Mar，2004.

[7]National ICT Australia.NICTA L4-embedded Kernel Reference Manual Version N1，Oct 2005.http：//ertos.nicta.com.