一种提高构件化嵌入式操作系统性能的方案

摘 要：本文分析了现有构件化嵌入式操作系统所用调度算法存在的缺点，提出抢占阈值调度算法是更为合适的算法。通过仿真实验比较抢占阈值调度算法、非抢占式调度算法和FIFO（First-In-First-Out）调度算法的性能，证明了上述结论。通过分析现有嵌入式系统构件模型的特点，提出了一种构件模型以及将构件映射成任务的方式，还提出了一种设计方法。整个方案能提高构件化嵌入式操作系统的性能。
   关键词：构件化嵌入式操作系统; 抢占阈值调度; FIFO调度; 构件模型
   1 前言
   　　如何将构件技术成功地应用到嵌入式操作系统开发中得到越来越多的重视。现有的工作大部分着重于从结构的角度分解系统成若干构件，并重用构件。实际嵌入式实时系统的处理器资源和内存资源是有限的，同时系统还有实时性需求。另外，当前成熟的实时调度算法都是基于任务模型分析系统的可调度性。所以，在嵌入式实时系统中应用构件技术时，还需要研究如何从时间（运行）的角度将构件映射成任务，以及为底层构件化嵌入式实时操作系统选择合适的调度算法。
   　　本文首先分析了现有构件化嵌入式操作系统的特点，着重分析了TinyOS[1]的调度内核。通过仿真实验比较了抢占阈值（简称PT）调度算法[2]、非抢占式（简称NP）调度算法和FIFO调度方式的性能，证明了当任务之间无共享资源时，抢占阈值调度算法适合作为构件化嵌入式操作系统的实时调度算法。之后，本文论述了嵌入式实时系统对构件模型的需求，提出了一种构件模型。通过分析比较现有的映射方式，提出了一个将构件映射成任务的方式和一种设计方法。
   2 适合构件化嵌入式操作系统的调度算法
   　　首先定义单处理器静态优先级实时系统的任务模型，定义G=｛t1,t2,…,tn｝为一个包含n个相互独立的周期性或者偶发性（sporadic）任务的集合，集合中的任务用ti=（Ti,Ci,Di）（i=1,2,…n）表示，其中，Ti表示ti的周期（对于偶发性任务就是最小到达间隔），Ci表示ti的最坏情况执行时间，Di表示ti的相对截止期。我们假定大的数值表示高的优先级，对于集合G，最小的优先级是1，最大的优先级是n。周期任务的一次执行，称作任务的一个实例。任务实例从进入系统到结束执行所用的时间称作实例的响应时间（response time）。在一个系统的整个运行过程中，任务的最坏情况响应时间等于其所有实例中最大的响应时间。
   　　2.1 TinyOS存在的问题
   　　当前的构件化嵌入式操作系统主要有TinyOS和Echidna[5]两种。TinyOS是为无线传感器网络（Wireless Sensor Network，简称WSN）开发的构件化嵌入式操作系统，适用于内存资源和处理能力有限，电池供电的嵌入式系统。其内核支持两级调度，任务按照FIFO的方式执行，目的是减少对内存的使用量，但造成系统实时性差。Echidna与TinyOS一样使用FIFO的方式调度任务，因此存在相同的缺点。
   　　V. Subramonian等人在文献[6]中研究了FIFO调度方式对TinyOS系统性能的影响。在使用TinyOS的系统中，当需要处理的数据量较大时，如果超过其计算能力，则会出现过载（overload）现象。处理过载的较好方式一般是保证关键任务的执行，放弃非关键任务。而FIFO调度方式不能做到这一点，因为这种方式无法区分关键任务和非关键任务。下面通过分析TinyOS对通信数据包的处理来说明其缺点。
   　　发送数据包由应用层产生并传递给底层发送构件，当成功发送后，后者会触发一个任务实例来通知应用层发送完毕。应用层在收到这一事件之前将一直等待，不能继续发送数据。即，只有通知任务实例得到执行，应用层才能继续发送数据。如果TinyOS当前需要处理的数据量较大，有较多的任务实例需要执行，则通知任务实例会排在FIFO队列的最后，等到前面的任务实例执行完才得以执行。这样就延缓了发送数据的过程，降低了通信数据包的吞吐量。在极端情况下，其它任务实例会将整个FIFO队列占满，通知任务实例到达时会被调度内核放弃，造成应用层发送数据的终止。从无线信道接收数据时同样会出现这种情况。
   　　文献[6]中提出了一种改进措施，给任务分配优先级，将调度内核升级为优先级驱动的非抢占式调度。这样与FIFO调度方式相比，能提高任务集合的可调度性，但仍会出现任务集合不可调度的情况。
   　　2.2 抢占阈值调度算法适合构件化嵌入式操作系统
   　　利用抢占阈值进行任务调度时，不但给集合G中的任务ti分配任务优先级piÎ[1,2,…,n]，还分配抢占阈值gi，并且pi£gi，即，giÎ[pi,…,n]。这样就实现了一个双优先级系统。其中的pi用于抢占其它的任务，而gi是任务运行中的有效优先级。如果当前正在运行的任务是ti，那么对于就绪任务tj，必须有pj>gi， tj才能抢占ti。对于周期任务ti，每次开始执行后，其优先级将从pi提升为gi，执行完后，优先级再从gi下降为pi。
   　　当任务的抢占阈值等于其任务优先级时，就是抢占式调度;当任务的抢占阈值是系统最高优先级时，就是非抢占式调度。所以抢占调度和非抢占调度是使用抢占阈值调度模型的两个特例。实际中，抢占阈值调度能同时利用抢占式调度和非抢占式调度的优点，通过调节任务抢占阈值，减少不必要的任务抢占，提高整个任务集合的可调度性。能运行抢占和非抢占式调度算法都不能调度的任务集合[2]。在文献[3]描述的仿真环境下，抢占阈值调度算法与抢占式调度算法相比，处理器利用率提高15%-20%。抢占阈值调度模型中，任务集合被分割成数目很少的非抢占组（Non-Preemptive Group，简称NPG）。组内任务之间是非抢占的，能共享一个栈空间，减少了任务集合对内存资源的消耗。在文献[4]的仿真环境下，当任务最大周期为100时，平均100个任务被分割成14.3个NPG。
   　　在构件化嵌入式操作系统的应用环境中，希望能在提高任务集合可调度性的同时，使用尽可能少的内存资源。根据这一要求，本文提出了在实时调度内核中使用抢占阈值调度算法。为了说明该算法较其它调度算法更适于构件化嵌入式操作系统，提出了如下的指标，以比较各种算法的性能：非抢占式调度中，所有任务共享一个线程栈空间，节省了内存资源。对于抢占阈值调度，如果任务集合生成一个非抢占组，则会使用与非抢占式调度相同的内存资源。为此，在每个测试点，针对相同一组随机产生的任务集合，比较抢占阈值调度生成一个非抢占组的次数除以整个产生的任务集合个数（用NAT表示）得到的百分率，与非抢占式调度以及FIFO调度方式下可调度任务集合个数除以NAT得到的百分率，称作单线程比率（One Thread Rate，简称OTR）。来说明不同算法在保证任务集合可调度的前提下，只使用一个线程的能力。
   　　使用随机产生的任务集合。生成任务时，任务个数totalTasks从2开始，以2为步长递增到50;任务集合的最大周期maxPeriod取为1000。任务个数和最大周期的取值构成一个测试点。在每个测试点，任务集合按如下规则产生：（1）在[1, maxPeriod]之间均匀、随机地选择任务周期Ti。（2）在[0.1/totoalTasks, 2.0/totalTask]之间均匀、随机地选择任务利用率Ui，任务执行时间Ci=Ui＊Ti。用任务个数来调整取值，以免产生过多的不可调度任务集合。（3）任务截至期Di=Ti。
   　　在每个测试点，从100次独立仿真实验中获得各调度算法的性能指标值，以进行性能比较。
   　　图1给出了针对相同一组任务集合，抢占阈值、非抢占式和FIFO等3种调度算法下产生的单线程比率。可以看出，FIFO调度方式的性能最差。在大部分测试点，抢占阈值调度下产生的使用一个线程的任务集合个数等于非抢占调度下生成的可调度任务集合个数。只在少数几个测试点，前者产生的OTR值略低于后者。所以，在此指标下，抢占阈值调度具有与非抢占式调度接近的性能。但抢占阈值调度能提高任务集合的可调度性。总之，抢占阈值调度能在提高任务集合可调度性的同时，使用较少的内存资源。与其它两种调度算法相比，更适合作为构件化嵌入式操作系统的实时调度算法
   
图1比较3种算法得到的OTR值
   3 构件模型和映射成任务的方式
   　　一般基于构件的软件开发中，使用已生成并被证明是可靠的构件来”建造”整个系统软件。这需要一个定义构件的方法，即，构件模型。研究和实践证明，构件模型必须有信息隐藏的能力和明确定义的接口。前者使构件能在不同的系统中替换和重用，而后者是构件与环境交互的通道。外界只能通过接口访问构件，这也是对信息隐藏的辅助支持。对于实时系统来说，构架模型还应包含时间属性，例如：构件执行时间、最终截止期和周期等，从而能在构造完系统后，进行可调度性分析。通常的实时软件开发中，任务是构造系统的基本单元，因此模型还应定义将构件映射成任务的方式。与桌面/企业级应用不同，开发嵌入式系统适合用源代码级构件。因为：（1）开发者可以访问构件源码（不是修改构件），通过”白盒”测试来发现错误。而使用二进制代码构件进行”黑盒”测试，将减弱开发者对系统行为的控制能力。（2）嵌入式系统是在资源有限的节点上运行复杂可靠的控制应用，不需动态配置，只需在一组静态配置的模式间切换。所以为了更好地支持系统的可分析性、可测试性和减少内存消耗，应该在运行前（编译时）配置构件的行为和相互之间的连接。这也需要使用源代码级构件。
   　　因为管道和过滤模型[7]适于控制应用，而大部分嵌入式系统是控制系统。所以，我们基于管道和过滤模型为构件化嵌入式操作系统的应用层定义一种实时构件模型。该构件模型是源代码级的，每个构件包括：（1）名称，作为构件的身份标识。（2）一组输入和输出端口，前者用于接收数据，后者用于产生数据，端口不会缓存数据，构件之间通过端口通信。（3）一组构件属性，存储构件的元数据信息，包括构件所用内存大小、执行时间、最终截至期、释放时间和周期等。（4）一个行为体，实现构件功能，被输入端口数据（事件）触发，根据当前操作模式处理数据，并产生触发下一构件的输出数据（事件）。通信数据在构件之间传递，由底层调度内核通过对行为体的逻辑调用来引导。
   　　当前存在将多个构件映射成一个任务[8]和将一个构件映射成多个任务[9]的方式，我们考虑这些映射方式的目的都是希望能在简化结构分析和减少运行时系统开销之间获得一个适当的折中。将一个构件映射成一个任务能简化结构分析，但可能造成系统运行时任务较多，如果底层实时操作系统采用抢占式调度算法，则会增加任务之间相互抢占的次数，从而增加现场切换等系统开销，降低处理器的利用率，影响任务集合的可调度性。另外，还会增加对系统内存的消耗。所以我们提出了一种设计方法：构件是被动的，不包含自己的线程，装配时才将构件分配到线程，每个构件映射成一个任务，这使系统结构清晰，并能简化分析过程;而系统运行时出现的上述问题，通过为底层构件化嵌入式实时操作系统选择合适的调度模型来解决，例如选择非抢占式调度算法能减少内存消耗，而选择抢占阈值调度算法既能提高任务集合的可调度性，又能减少对系统内存的使用。
   　　映射完成后，构件属性就成为任务的属性。执行期间，系统保证输入端口上的数据不会改变，以避免数据的不一致。对于相互连接的构件，利用编译程序创建系统任务，以完成构件之间的数据通信，并根据互连构件的特性指定这些任务的释放时间、周期、执行时间和最终截止期等参数。图2给出了构件模型的示例图。图2的右侧表示了任务（构件）执行体包含的程序结构。
   
图2 构件模型示例图
   4 总结
   　　嵌入式系统开发使用构件技术时，不但要从结构的角度将系统分解成若干构件;还要从运行的角度将构件映射成任务，为底层内核选择适当的实时调度算法，根据算法给任务分配优先级，并判定任务集合的可调度性。当前对后者研究较少。针对这一问题，本文首先通过比较3种调度算法，得出抢占阈值调度更适合构件化嵌入式操作系统的结论。仿真实验证明了这一观点。然后根据已有工程实践，提出一种适合于嵌入式实时系统的软件构件模型以及将构件映射成任务的方式。本文论述的模型和算法构成了一个较完整的方案，对构件化嵌入式实时系统的开发有一定参考价值。
   参考文献：
   　　[1] Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David E. Culler, and Kristofer S. J. Pister. System architecture directions for networked sensors. In Architectural Support for Programming Languages and Operating Systems, pages 93-104, 2000.
   　　[2] Y. Wang, M. Saksena. Scheduling fixed-priority tasks with preemption threshold. In: Gakkai JS, ed. Proc. of the 6th Int’l Conf. on Real-Time Computing Systems and Application. Los Alamitos: IEEE Computer Society, 1999. 328～335.
   　　[3] Y. Wang and M. Saksena. Scheduling fixed-priority tasks with preemption threshold: an attractive technology? http://www.expresslogic.com/wpall.html
   　　[4] Manas Saksena and Yun Wang. Scalable real-time system design using preemption threshold. In Proceedings of the Real Time Systems Symposium, December 2000
   　　[5] Echidna: a real-time operating system to support reconfigurable software on microcontrollers and digital signal processors. http://www.ee.umd.edu/serts/research/echidna/index.shtml
   　　[6] V. Subramonian, H.-M. Huang, S. Datar, and C. Lu. Priority scheduling in tinyos - a case study. Department of Computer Science, Washington University, St. Louis. MO
   　　[7] Anders Möller, Mikael Åkerholm, Johan Fredriksson, Mikael Nolin. An industrial evaluation of component technologies for embedded systems. MRTC Report ISSN 1404-3041 ISRN MDH-MRTC-155/2004-1-SE
   　　[8] Shige Wang, Kang G. Shin. An architecture for embedded software integration using reusable components. CASES 2000: 110-118
   　　[9] Hideyuki Tokuda, Clifford W. Mercer. ARTS: a distributed real-time kernel. Operating Systems Review, 1989, 23（3）: 29-53