基于改进RMS算法的多核嵌入式系统总线周期调度表优化设计

于海心，王晶，李晓锋

(北京控制工程研究所，北京 100000)

高效、可靠的信息收集是远程指挥控制决策系统三大基本要素之一。如何实现高速有效可靠的信息采集一直是制约远程控制系统高效指挥的一个瓶颈。嵌入式系统是一种实时性系统，对于这类系统而言,系统的正确性包括逻辑计算结果以及结果产生的时间，即必须在规定的时间范围内正确地响应系统输入。随着技术进步以及应用需求的提升，嵌入式系统的结构和功能日益复杂，系统的集成度逐步提高，该现象直接导致嵌入式系统面临实时性约束和高集成度设计需求的双重压力，而多核处理器的出现使得上述矛盾的解决成为可能。尽管多核处理器可以解决时间约束和高集成度之间的矛盾，并为实时系统带来诸多改变和进步，但是多核体系结构因其固有属性，导致在设计和部署实时系统时会面临一些挑战，目前在实时系统中并未有效地发挥多核平台的高性能优势[1]。总线周期调度表是指一个周期内所有可能传输的总线命令集。一个优质的总线周期调度表可以使总线负载达到平衡，提高总线的利用率和数据传输的实时性。对于一般的现场总线,常见的周期调度表的构建算法主要包括单处理器中的静态单调速率算法(RMS)、动态最小截止期优先算法(EDF)和最短空闲时间优先算法(LLF)。随着多核处理器在高可靠控制领域的应用逐步广泛，传统的现场总线周期表构建算法已经不足以构建一个面向多核嵌入式系统的高效率且负载均衡的总线周期表。为提高总线周期表的效率，越来越多的科研工作者在该方面进行了优化和改进，文献[2]采用差分进化算法，文献[3]采用模拟退火算法，文献[4]采用粒子群优化算法，文献[5]采用Pareto蚁群优化算法对现场总线的调度表进行优化设计，文献[6-8]对资源调度算法的优化评价问题进行研究，而对于多核体系结构的资源分配和调度问题，文献[9-11]均进行了研究和探讨，上述各类方法均在其特定系统模型中取得了某一特性的最优。针对某高可靠性同构多核嵌入式系统总线周期表的优化设计问题，笔者分析了其任务特性，给出了该系统的周期调度模型，并提出了一种改进RMS算法。该算法应用于具有多核嵌入式系统的航天控制系统中，该系统能够为远程指挥决策系统提供空天资源的信息支持。

1 多核嵌入式系统概述

1.1 系统结构

多核嵌入式系统根据处理器核的封装类型不同可以分为同构多核系统和异构多核系统。同构多核指处理器芯片中内部所有核结构相同且各个核具有相同地位，支持相同的指令集；异构多核指处理器芯片中采用多种功能不同的核，处理不同功能且根据需要可能会支持不同的指令集。笔者重点研究同构多核处理器的总线周期调度表问题，讨论一种多核嵌入式系统，各个处理器为相同结构，彼此独立，通过共享二级内存彼此完成计算同步及信息交互，每个控制器独立控制一条总线，如图1所示。该结构可以增加系统的总线数据输入与输出能力，可以增加嵌入式系统的集成规模，同时各核之间耦合度不高，可以通过对总线上数据源的备份设计提高系统的稳定性和可靠性。

1.2 系统任务分析

针对多核处理器调度策略，主流分为全局方案和规划方案两种。全局调度策略是指相同的实时任务每次出现均不在同一处理器上执行，且该调度策略对处理器的同步要求较高，因此所有的处理器上只能使用一种调度算法，这种方案的优势在于多处理器系统可以统一协调分配资源，资源的使用效率较高。与全局调度策略不同，在规划调度策略中一个实时任务每次出现都在同一个处理器上执行，如图2所示，全部任务由任务分配算法预先划分到处理器，在这个策略下每一个处理器都可以运行不同的调度算法。规划策略的优势在于将多处理器的调度开销集中在处理器任务分配中，而这个分配仅执行1次且发生在第1次执行前，这样降低了调度策略的复杂性。

通过对图1所示系统进行分析可知，该系统各处理器独立控制一条总线，而每条总线的负载不相同，即每个处理器所处理的总线任务不相同。因此，该种类型多核系统在各总线负载不相同的前提下，更适合使用规划调度策略。在该系统执行任务的过程中，对于单处理器而言，由于总线上负载运行状态可能发生变更，如负载通信故障等，会导致每周期执行任务发生改变，针对此类多核系统仅采用静态调度策略是不满足系统的要求的，还需考虑因总线负载动态均衡的问题。

1.3 系统周期调度模型

分析如图1所示系统P的周期调度模型。该实时系统P包含有m个同构处理器，P={p1，p2，…，pm}，假定每个处理器pi所处理的总线任务集ti不同，且各处理器的总线任务间不存在任何共享资源和依赖关系。系统P的总线任务集合Ta={t1，t2，…,tm}，各单核处理器pi的任务集ti可以用三元组来描述：

ti=(Ei，Di，Ti)，

(1)

式中：Ei表示任务ti最长完成时间；Di表示任务ti的相对截止期；Ti表示任务ti的周期。

本文仅考虑任务周期和相对截止期相等并且任务执行时间小于等于周期的情况，则：

Di=Ti， 0≤Ei≤Ti.

(2)

各处理器pi任务集ti的资源使用效率为

ui=Ei/Ti.

(3)

对于多核系统P的总线资源使用效率用U表示，用来衡量系统P各总线周期表的资源调度效率：

(4)

则系统P的总线资源使用负载平衡度为

(5)

该指标可以用来衡量系统P的总线负载均衡。

2 改进RMS算法

2.1 RMS算法概述

单调速率调度(Rate Monotonic Schedule，RMS)算法是最优的静态优先级调度算法，采用非抢占的静态优先级的策略调度周期性任务。该策略的原理是更频繁地使用处理器资源的任务应该获得更高的优先级，因此周期越短优先级越高，周期越长优先级越低。RMS算法的假设理论前提：各个任务之间没有资源共享，没有忙等，没有互斥，也没有信号量；每个任务的最后期限是周期性的；优先级分配的原则是，周期越短的任务优先级越高。

在使用RMS调度算法生成总线周期表进行总线消息调度时，总线消息不能被抢占，一旦发生消息资源被抢占，则会破坏消息数据的完整性，导致数据污染，进而导致系统处理错误。笔者将讨论使用RMS调度算法进行1553B总线任务的可调度性分析，如无特殊说明文中所指的现场总线为1553B总线。

2.2 RMS算法可调度性分析

算法的可调度性分析是指在给定的任务模型中，算法能否在规定时间内完成现有的任务。文献[6]给出了调度性判定的定义，“检查一个任务集Ta在指定算法中是否可调度”，“如果任务集中每个作业执行完成时都不会错过截止期，则称这个任务集在指定算法下是可调度的”，文献[6]中也给出了该定义的证明过程。

总线传输消息任务包括周期消息和随机消息。周期消息是指总线上以固定的顺序、周期和相位出现的消息，而随机消息是事件触发，不以固定时间出现的消息。对周期消息的调度是一种周期任务的调度，消息发生的周期是固定的，被调度的时间是明确的，多条消息不可同时占用总线和处理器的资源。对于单处理器来讲，使用RMS算法对总线周期任务的调度不存在问题，所有的总线周期任务均能在最坏截止期之前完成。针对图1中所述系统P，假定处理器pi管理的总线Bi上存在周期任务t1、t2，其中任务周期T1=αT2，其中α为整数且α≥1。假设在总线Bi上仅存在上述两个任务，则对于总线Bi来讲，T2为最小周期采用Δ来表示，T1为最大周期，T1=kΔ，k>1且k∈N。对于系统P，为保证所有处理器pi同步，则在所有的总线Bi上σ是相同的。对于在所有的总线Bi上所有周期任务均能在T1前完成。在实时嵌入式系统中，对于总线上的随机消息而言，其周期未知，发生时间不明确，但是对其响应时间却有着明确的要求。因此，仅采用RMS算法对其在系统P中进行调度是不可行的。笔者针对这个问题以及系统P的多核体系结构，对RMS算法进行了改进，使其能够完成多核系统P的总线所有类型消息的任务调度。

2.3 改进RMS算法及可调度性分析

针对图1所示多核结构系统P，每个处理器pi在系统运行时单独控制一条总线Bi且各总线任务间无资源共享问题。在系统P进行总线任务调度时，为保证系统运行正确，各处理器采集的负载数据时序正确，各总线任务的最小周期σ必须保持一致，如图3所示。各总线的任务周期不同，但系统P的所有总线任务存在一个最小周期σ，其他任务的周期Ti是整数倍数。

在系统P中，除周期任务外还存在非周期任务，即随机任务。对于随机任务的调度，存在两种处理思路，一种是建立基于马尔可夫链的消息队列，随时刷新总线调度周期表；一种是将非周期消息周期化。第1种思路的优势在于总线调度表灵活，资源使用率高，缺点在于调度算法复杂，占用处理器资源，不断进行总线调度表的生成，这对于实时性很强的嵌入式系统来讲，过于浪费处理器资源。笔者采用第2种思路建立对RMS算法进行改进。总线进行周期消息传输时存在资源占用期和资源闲置期，在每个周期消息之间存在一个寂静期。在寂静期内总线上无消息传送，采用RMS算法生成的总线调度策略，寂静期内无法进行消息传输。改进RMS算法的核心思想是利用这段寂静期，将这段时间作为随机消息的时间窗口。当一个随机消息到来，该算法会在随机消息要求响应时间给这个消息选择一个最优时间窗口，让该消息在最坏截止期之前完成传输。

对于处理器Pi管理的总线Bi上存在的随机任务ti，也可采用三元组方法来表示，ti=(Ei，Di，Ti)，与周期任务不同的是Ti表示该任务的最大响应时间，即任务ti必须在Ti时间内开始执行。总线使用率U和负载均衡度σ2的计算方法与周期任务相同。

假定，系统P中处理器pi管理的总线Bi上存在周期消息t1、t2，随机消息t3需要进行资源调度。其中，t1、t2消息已知发送周期，t3仅在事件X发生时才发送，且其最坏执行时间E3和任务执行时间D3已知。改进算法对上述消息的调度表设计如图4所示。改进算法通过分析周期消息t1、t2的调度周期，找出其可调度随机消息的时间发送窗口W1，W2，W3，并根据随机消息t3的资源占用情况，在下一个最小周期T2中选择合适的时间窗口对t3进行调度，将时间窗口W2作为随机消息t3的保留时间窗口。该时间窗口在总线的最大周期中至少出现一次，因此当t3的响应时间满足T2≤T3≤T1时，且存在窗口Wi>t3时，该算法能够保证所有任务在最坏截止期内完成。

3 仿真实验与分析

为验证改进RMS算法对多核嵌入式系统的总线周期调度表优化效果，与RMS调度算法进行比较。假定针对系统P，一组待调度总线消息如表1所示。

表1 待通信总线数据

将表1所列总线消息，采用改进RMS算法进行调度。生成图1中系统P的各总线B1～B4的总调度任务集TA={Ta1，Ta2，Ta3，Ta4}。各总线周期调度表如表2所示，可以看出改进后的RMS算法在将随机任务的资源开销考虑进去，随机任务增加在总线的资源调度表中，增加了系统的资源使用率。随机任务出现越多，系统的资源使用率越高。

表2 总线任务周期调度表

与RMS调度算法比较结果如表3所示，可以看出该算法可以提高总线负载均衡度、提高总线传输效率，同时能够适用于多核嵌入式系统。

表3 改进的RMS算法与RMS算法比较

4 结束语

为提高远程指挥控制决策系统的信息采集效率和可靠性，提出了一种改进RMS算法。笔者给出了一种多核处理器的体系结构，在该系统中各处理器单独管理一条总线，处理器间通过二次共享缓存进行信息交互。在总线周期表设计中采集改进RMS算法为非周期任务设计时间窗口，有效避免了总线上存在非周期消息时出现总线饱和或者堵塞的现象。该方法通过排队论对非周期消息进行建模，将非周期消息周期化并利用改进RMS 调度算法对其进行合理调度。算法的实现条件为随机消息的响应时间，即消息触发事件到消息执行时间大于系统最小周期且小于系统最大周期，同时总线表中存在大于随机消息的最坏截止期的时间窗口。在实现周期消息和非周期消息混合传输的情况下，保证了非周期消息的实时性，实现了数据在总线上的实时、可靠的传输。