基于RMA的嵌入式系统代理调度模型设计

罗 奕 何振林 孟 丽 张庆蓉

（成都中医药大学管理学院，成都610075）

随着嵌入式系统的应用日益广泛，以及应用领域的不断拓宽，其应用环境和运行状态也随之变得更加复杂。为了适应嵌入式应用不断发展的需求，基于对实时性、并发性以及效率等因素的考虑，需要对传统的嵌入式系统的设计架构进行更加完善的设计［1］。在目前的嵌入式系统中，融合了传统硬件架构和软件计算功能的综合式设计方法已逐渐成为发展趋势。嵌入式系统能够支持更多的应用模块，各模块由相对独立的进程或线程控制，它们有机地结合在一起形成完整的系统［2～4］。具有多外设接口对于嵌入式系统是非常普遍的情况，外设的活动通常是由设备驱动程序控制。这些外设的工作相对独立于中央处理模块，同时，外设所负责的工作内容也可能存在较大的差异。例如数据采集、数据处理和状态控制等，都可能会导致处理延迟的不确定性。设备驱动程序则将负责有效保持外设与中央处理模块之间的联系。在传统的嵌入式体系设计中，设备驱动进程通常被设计成与中央处理模块直接交互［5，6］。当这类驱动进程数量增大，同时在这些进程之间存在较多的协作或同步关联时，这种直接耦合的设计模式可能会导致嵌入式系统的性能受到较大的影响。因此，需要对系统的体系结构作细致考虑，以保证系统的整体性能。

既然直接耦合设计的架构无法对上述情况提供好的解决方法，则适于并发和多道控制的软件代理结构是有效的可选设计方案［7，8］。软件代理［8］可描述为软件或硬件的组件，可用于为被代理用户完成特定的事务。在本文中，软件代理被设计用于代理多外设驱动模块实现对并发及同步处理事务的调度管理。该代理根据一定时间段内发生的并发和同步请求情况，采用单调速率调度算 法 （Rate Monotonic Scheduling， 简 称RMS）［12～14］对请求响应进行重新排序，使被代理模块在串行化的调度处理后，能够更合理地使用共享资源，提高多事务并发执行的性能。

本文包括下述内容：对嵌入式应用系统的代理设计体系结构进行了描述，讨论了代理采用RMS算法实现请求的接入控制，并在此基础上实现对并发事务的重调度。在上述基础上对一个典型的嵌入式应用系统的并发处理场景进行了用例分析，验证了该代理设计方法的有效性。最后，总结全文并展望今后进一步的研究工作。

1 嵌入式系统的代理体系结构设计

嵌入式系统的体系结构通常包含了可编程的软件组件和客户订制的集成单芯片硬件组件2个部分。嵌入式系统常见为异构式的体系结构，该设计架构可有效地将软硬件组件结合起来，实现一些常见或特定的计算目标［4］。虽然根据不同的应用需求，嵌入式应用系统可能会包含不同的组件和集成方式，但从架构上仍然体现出一定的相似性，如图1所示。

图1 异构嵌入式系统设计架构Fig.1 Heterogeneous embedded system architecture

图1中，DSP是嵌入式系统的核心组件。随着技术发展和应用需求的提高，目前也出现了多处理器的设计架构。除了核心组件之外，对其他硬件模块的集成以及复杂软件与硬件模块的有效交互，是嵌入式设计中非常耗时和易于出错的工作内容。尤其在这些集成的软件与硬件部件之间，存在着如时间约束、资源共享或并发与同步的要求时，更需要进行仔细的设计考虑以保证嵌入式系统的各类性能需求。

在传统的设计架构中，上述资源共享、时间约束问题常采用在各模块设备驱动之间的直接耦合实现方式。例如，在各驱动中使用多线程编程工具，通过对共享资源采用互斥或信号量等方式来实施存取保护来实现。但这样的设计方式更多是一种局部冲突的解决办法，对于系统的整体性能相对缺乏控制力。软件代理的设计模式则能够很好地适用于这类应用场景。既然对共享资源的存取操作始终是串行化的处理过程，那么，以代理方式对多道事务请求进行接入控制，是一种合理的设计思路。

软件代理设计架构在并发或协同计算中具有很好的控制潜力。根据文献［6］的研究结果，上述直接的内核通信设计模式可以采用软件代理架构的中间调度层来替代，以实现更好的系统性能。在软件代理模块中包含了一个事务调度器，用以决定被代理事务的活动顺序。图2是采用了代理架构的设计模型，由代理模块负责与不同被代理事务的通信，以及资源分配和协调各被代理事务之间的协同工作。

图2 采用代理的异构嵌入式系统架构Fig.2 Agent－based heterogeneous embedded system architecture

图2的设计是基于软件层面的，这样可以尽可能小地避免改变嵌入式系统的硬件结构。代理模块主要包含了事务调度器和同步通信控制组件两个部分。有并发和时间约束需求的被代理事务需要首先在代理模块处进行注册，提交基本的事务处理信息。

代理模块使用调度器为被代理事务计算出合理的执行序列，并使用同步通信控制组件完成对被代理事务的调度结果通告。代理设计的方式可有效减少被代理事务间因资源共享及自同步过程中所产生的冲突，降低由此而导致的系统开销。同时，能够针对全局性能实现优化配置。代理模块对并发性事务的管理是动态的，当并发事务的请求到达时，代理服务进程被自动激活，并重新计算当前的调度队列情况，用以确定新的事务请求能否加入当前的调度序列。

目前，基于网络的分布式应用日益广泛。采用代理架构的设计方法可有效扩展嵌入式系统的应用领域。Steven描述了一种可提供高度并发服务的可编程模型［15］。而这种代理架构的设计模型，也比较易于扩展到网络与分布式应用的场景。

2 调度支持

如前所述，软件代理依靠调度器来实现对被代理事务的调度管理工作。单调速率优先（RMS）算法［16］是一种实时应用中所广泛采用的调度算法。本文采用RMS来实现代理模块中的调度器。

在RMS中，设需调度的事务个数为n，可表示为S＝｛t1，t2，…，tn｝。并假定这些被调度事务之间相互独立。这是调度中最简单的一种情况。则这组被调度事务可满足的调度条件为

其中，是Ci执行事务i的最坏执行时间，Ti是该事务的执行周期。

在实际情况中，一组事务之间往往并非完全不相关，在事务之间存在着同步和协作的需求。这种情况下，RMS算法适当松弛式（1）中的约束条件，得到下式

Ci和Ti与式（1）中相同，Bi是事务i被同组中更低优先级事务所阻塞的时间。低优先级阻塞更高优先级的情况称为优先级反转。若该组事务符合公式（2）的约束条件，则这组事务能够满足RMS的实时调度需求。

Sprunt与Lehoczky对实时事务调度作了进一步的改进，改进后的一组事务中可以存在非周期性的事务情况［17］。对于两类非周期性的事务TE与TR，TE是突发性的临时事务，该事务的时间约束为DE。另一类事务TR也是非周期性事务，但此类事务没有或仅有很弱的时间约束要求。实际上，可将TR看作非周期性事务。因此，事务的平均响应时间可由队列的平均等待时间Wq和平均执行时间We构成。

Dq是队列中任意连续事务完成后移出队列的时间间隔。f是事务的发生频率，用于评估平均CPU的占用率。I为事务的平均发生间隔时间。可得到下式的队列平均等待时间

用TR替代Dq，队列的平均等待时间为

因此，可以用下式进行估计

上式改进后的计算公式可保证应用事务能够满足实时时间约束的要求。在上述公式中，仅是给出了可满足调度管理事务组的一种充分条件。即使在不满足上述约束条件时，调度组仍然是有可能保证满足每个进程的时间约束要求。

使用上述RMS调度算法，可帮助代理对并发事务进行管理。当多道接入控制请求在一定的时间间隔内产生，代理采用RMS调度算法计算该组事务的时间约束满足情况，并根据计算结果调整对控制请求的响应顺序。若当前调度组能够接纳新的请求事务，则将该新事务归并入当前的调度组进行管理。否则，需要启动新的事务组来进行接入控制管理。图3是对代理的调度管理流图的描述。

由图3可见，该调度管理中没有采用抢占式的调度管理模式，因此软件代理在对事务的调度管理中并没有采用硬实时的方式，可能存在事务不能保证时间约束的情况。上述采用代理进行调度管理的情况，可以避免强耦合设计方式所导致事务资源竞争所导致的冲突避免或解除等开销，有助于提高系统的整体性能。

图3 代理工作流图Fig.3 Agent work flow diagram

3 试验

试验是在一个典型的嵌入式组态软件系统下设计并执行。该组态软件系统最初是采用了中央集中控制的组织结构。系统中每个分散的受控节点由相对独立的事务进行管理，并由其负责对各节点数据的采集和局部操作的控制。各个分布节点之间存在着存储资源和总线资源的共享。同时，各分布节点与中央控制节点之间存在直接的通信，以保证中央节点对各分布节点的有效监控。分布式节点中存在部分PLC控制设备，这些设备以固定的周期完成特定的工作。试验采用软件代理方式控制各个分布式节点的并发执行，对共享资源的请求和存取进行统一的调度管理。表1中给出了组态软件中5个并发处理事务的基本参数，图4则是采用了软件代理管理的时间序列图。

表1 并发事务的基本参数Table 1 Concurrency tasking arguments design

图4 多事务并发处理软件代理的序列图Fig.4 Sequential diagram for multi－tasking concurrency time

由表1中所示，事务T1具有较高的时间约束要求的周期性的监控数据采集事务，T5是较低时间约束要求的显示数据更新事务。T2，T3，T4是具有一般时间约束要求的设备数据采集事务。为了保证这组并发事务的有效执行，采用软件代理方式进行分组管理。

图4中标记了软件代理对并发事务进行统一管理的过程。在主控程序中初始化阶段启动各个分布节点上的处理事务。随后，每个独立的事务完成对所控设备的初始状态和控制参数的设置。当设备启动后，对应的控制事务作为被代理客户，向主控程序的代理模块注册相关的事务参数信息，例如注册的定式器、共享资源请求、时间约束条件等。软件代理在每当有新的事务请求接入时触发。软件代理调用调度程序计算接入新事务是否能够满足整体的时间约束要求。如果能够满足时间约束条件，则该事务被接入当前的调度队列中，并将调度后的结果告知当前管理组中的事务。如果计算结果不能满足时间约束条件，则最新的事务将激活新的调度组管理。当被代理事务获得了代理模块的响应后，将根据响应信息独立进行事务操作。并发的一组软件事务在软件代理调度后成为序列化的独立进程依次执行。

表2是在使用和不使用软件代理方式下分别对组态软件一段时间内的性能进行统计得到的结果。

表2 采用与不采用软件代理的性能比较Table 2 Performance comparison of agent method

在记录的一段时间内，采用了软件代理实现的系统可多接入13%左右的并发请求，并且事务处理不能满足时间约束条件的发生频率也比不采用代理时有所下降。显然，在使用了代理调度后，虽然损失了部分调度计算时间，使得事务的平均响应等待时间有所增加，但可获得更好的执行序列，减少了由资源竞争冲突所导致的额外时间开销。

4 结论

本文采用软件代理的架构的设计方式来管理嵌入式应用系统中的并发事务处理。该设计模型比事务间直接耦合的并发处理方式更加合理，通过采用软件代理的设计模式，可有效地管理事务组间的资源共享，提高事务的并发处理能力，进而改善系统的整体性能。

［1］FRANK V，TONY G.Embedded System Design：A Unified Hardware／Software Introduction［M］.California：John Wiley ＆Sons，2004：14－22.

［2］LIN B，VERCAUTEREN S.Synthesis of concurrent system interface modules with automatic protocol conversion generation［C］／／ Proc of IEEE International Conference on Computer Aided Design.Belgium：IEEE Press，1994：101－108.

［3］LIN B，VERCAUTEREN S，DE MAN H.Embedded architecture co－synthesis and system integration［C］／／Proc of the Fourth International Workshop on Hardware／Software Co－Design.Pittsburgh，PA，USA，1996：2－9.

［4］BROOKS R A.A Robust Layered control system for a mobile robot［J］.IEEE Journal of Robotics and Automation，1986，2（1）：14－23.

［5］KARKOWSKI I.Computer aided embedded systems design［C］／／Proc of the Third Annual Conf of ASCI.Heijen：The Netherlands，Pittsburgh，PA，USA，1997：2－4.

［6］VERCAUTEREN S，LIN B，DE MAN H.Constructing application －specific heterogeneous embedded architectures from custom HW／SW applications［C］／／ Proc of the 33rdInternational Conference on Design Automation.Las Vegas，NV，USA，1996：521－526.

［7］EDWARD A L，STEPHEN N.Actor－oriented design of embedded hardware and software systems［J］.Journal of Circuits，Systems，and Computers，2003，2（3）：231－260.

［8］DICK R P，NIRAJ K.CORDS：hardware－software co－synthesis of reconfigurable real－time distributed embedded systems［C］／／IEEE／ACM International Conference on Computer Aided Design，1998：62－68.

［9］NWANA H S，WOOLDRIDGE M.Software agent technologies［J］.British Telecommunications Technology Journal，1996，14（4）：79－88.

［10］MONTE J D，KRISHNA R.Scheduling paralleliz－able tasks to minimize make－span and weighted response time［J］.IEEE Trans on Systems，Man，and Cybernetics－Part A：Ststemns and Humans，2002，32（3）：335－345.

［11］VERCAUTEREN S，LIN B，DE MAN H.A strategy for real－time kernel support in application －specific HW／SW embedded architectures［C］／／Proc of the 33rdInternational Conference on Design Automation，Las Vegas，NV，USA，1996：678－683.

［12］FOWLER P，LEVINE L.Technology transition push：a case study of rate monotonic analysis（Part 1）［R］.Technical Report CMU／SEI－93－TR－29ESCTR－93－203，1993.

［13］KLEIN M.A Practitioner’s Handbook for Real－Time Analysis：Guide to Rate－Monotonic Analysis for Real－Time Systems［M］.Santa Monica：Kluwer Academic Publishers，1993.

［14］LEHOCZKY J，SHA L，YE D.The rate monotonic scheduling algorithm：exact characterization and average case behavior［C］／／Proc IEEE 10thReal－Time Systems Symposium.Santa Monica：Kluwer Academic Publishers，1989：166－171.

［15］STEVEN D G，MATT W.The ninja architecture for robust internet－scale system and services［J］.Computer Networks，2001，35：473－497.

［16］LIU C L，JAMES W.Scheduling algorithms for multiprogramming in a hard real－time environment［J］.Journal of the ACM，1973，20（1）：46－61.

［17］SPRUNT B，SHA L，LEHOCZKY J.Aperiodic task scheduling for hard－real－time systems［J］.Real－Time Systems，1989，1（1）：261－270.