基于时空隔离原则的列车控制软件集成方法的研究

景 浩，马连川

（1. 北京交通大学 轨道交通运行控制系统国家工程研究中心，北京 100044；2. 北京交通大学 电子信息工程学院，北京 100044）

基于时空隔离原则的列车控制软件集成方法的研究

景 浩1,2，马连川1,2

（1. 北京交通大学 轨道交通运行控制系统国家工程研究中心，北京 100044；2. 北京交通大学 电子信息工程学院，北京 100044）

针对CTCS-3设备硬件资源浪费、通信复杂和容易出故障的问题，参考ARINC 653标准中时空隔离的思想，目的是实现一台设备集成多台设备的功能，提高设备效率和可靠性。文中运用两级调度结构，根据VXWORKS操作系统的特性计算程序运行时间，确定隔离时间和周期；运用开发平台工具测量单个任务所需内存，确定隔离内存大小。用实例验证本方法的正确性。

时空隔离；RM调度算法；隔离时间；隔离内存；CTCS-3

现在的CTCS-3级列车控制系统（以下简称：列控系统）基于叠加原则实现完整功能，有降低工作量和费用的优点，但也会导致整个系统结构复杂、设备量多，设备间的通信和连接复杂，造成系统平均无故障时间（MTBF）降低，会导致比较频繁地出现故障而使系统恢复时间变长，不仅降低系统运行效率，而且还容易诱发其它重大事故。

此外，CPU正朝着多核化、低功耗化和支持虚拟化等方向发展，其处理速度和综合处理能力越来越强，同时，随着内存、磁盘和网络等技术的飞速发展，以前需要多个计算机处理的功能现在已经可以由单个计算机完成。因此，传统的基于叠加原则实现列控系统的方法实际上也造成了硬件处理能力和资源的浪费。

要解决上述问题，可参考航空电子行业为解决航空电子设备集成问题所制定的ARINC 653标准。它在高安全性的实时操作系统中提出了分区的概念，原有的子系统概念已由硬件实体变为软件。分区是运行于一个处理机模块上的多个应用程序（或子系统），它们在时间和空间上彼此隔离，互不影响，当一个分区内的应用发生错误时，在时间和空间上都不会影响到其它分区[1][8]。

ARINC 653标准需要特定软硬件的配合，实现难度和成本都很高。本文借鉴其思想，以较低成本在安全计算机平台上实现子系统之间的时（间）空（间）隔离以保证安全，同时子系统内部使用优先级调度算法以提高效率，重点在于如何实现时空隔离。针对时间参数确定基本靠经验和不断试验的现状，结合软件测试、调度算法、系统应用等多方面的方法，利用实时操作系统精确测量软件运行时间，从而准确确定时间参数。针对软件内存保护方面的不足[1]，通过与时间参数结合实现内存的静态分配，从而在时间域和存储空间域对安全计算机平台所集成的多套列控软件实现确定性安全保护。

1 两级调度结构

本文使用两级调度结构[1]，在操作系统之上，用时间触发来分离各子系统模块，如临时限速服务器（TSRS）、无线闭塞中心、列控中心等。这样，各个子系统在时间上实现了隔离，一个子系统的内部错误（如单个任务长时间占用处理器）只会影响自己内部，不会对其它子系统造成影响。在子系统模块内部，各任务用RM算法来调度。如无线闭塞中心（RBC）中的列车注册、列车注销和行车许可（MA）生成3个任务，每个任务可能不会每个周期都要运行一次，用RM调度算法[2]可提高资源的利用率。这样既实现了设备的集成，又保证了安全性，同时提高了资源的利用率。

当时间上具有确定性以后，为了提高系统的安全性和可靠性，需要在空间上也具有确定性，即对内存分配进行管理[7]。时间确定性表示方法如图1所示。

本文将内存分为系统内存区、任务代码区、任务结果保留区、内存分块区和I/O内存区。

基于时间触发机制的安全相关软件内存分配模型如图2所示。

对本文来说，重点在于内存分块区的分配，采用一种循环分配法，可以在满足任务正常运行的内存需要的同时，有效提高内存利用率。

下面本文将分别阐述时间参数（总周期和各子系统隔离时间）和空间参数（各子系统隔离内存大小）的确定方法。

图1 时空确定性

图2 安全相关软件内存分配模型图

2 时间参数的确定方法

时间参数有两个，即分配给每个子系统的隔离时间和每个程序执行所需时间，前者可以通过后者计算出来，而后者可利用软件测试的方法和VXWORKS的特性来确定。由于VXWORKS操作系统具有良好的实时性、优秀的集成开发环境，是功能强大的分析工具，在本文中选用它作为开发平台。

2.1 程序执行时间的确定

在以前的时间触发方法中，分配给各任务的时间是由主观经验或不断试验得到的，没有统一的方法。本文使用软件测试中的方法，可较精确地测得各任务的执行时间，按此分配时间可提高系统的效率。

软件测试中有一种基于路径的测试，重点在于研究出一组输入，使得可遍历一条指定的路径。在本文的研究中，由于程序比较简单，可列出程序中所有的路径，得出各自的输入，再在VXWORKS系统中得到执行每条路径所需的时间，从中选取最大值作为分配给程序的时间。若程序复杂，不能列出所有路径，也可只测试最重要的几条路径，同时在程序中加入超时处理机制。

面向路径的测试数据自动生成方法有随机法，静态法，动态法和试探法等。其中随机法又包括符号执行，区间算术法；动态法包括直线式程序法，松弛迭代法，试探法包括遗传算法，模拟退火算法等。比较约束完备性、实现复杂性、效率和工具支持等方面后，选定松弛迭代法[4]作为本文使用的方法。

2.2 VXWORKS中测量指定路径的执行时间

在VXWORKS中提供了丰富的时间操作功能，获得时间的方法主要有系统时钟，看门狗定时器，时间戳，tickGet()函数等方法[5]，经过方便性和准确性各方面的衡量，如表1所示，选择tickGet()函数测量系统时钟来确定时间。

表1 时间测量方法比较

在VXWORKS中，tick指的是时钟中断的频率，tick为100表示每秒钟时钟中断100次。通过sysClkRateGet()函数可以得到当前的tick数，如果不满意可以使用sysClkRateSet()函数来修改，系统中默认的是60，即1/60=16.67 ms为一个tick，若设为1 000则一个tick刚好为1 ms。

通过上述方法可知指定路径的输入，在路径入口处加入tickGet()函数来得到当前值tick1，出口再加入tickGet()来得到一个值tick2，加上此前由sysClkRateGet()得到的值clkRate，计算(tick2-tick1)/clkRate即可得到经过测试路径所需的时间。对每条路径反复执行上述步骤即可得到所有路径各自所需的时间，从中选择最大值作为任务的最坏执行时间。

2.3 隔离时间的确定

设有一个任务集S＝{t1, t2, t3,……, tn}，其中ti（1≤i≤n）都是周期任务，每个任务可用式（1）表示：

其中，Ci表示任务的最大计算时间，Di表示任务的时限，Ti表示任务的周期[6]。

假设分配给子系统k的处理器能力是αk，此时各任务的处理时间变为

定义1：

表示此时[0,t]时间内处理优先级高于或等于i的所有任务的时间。

定义2：

表示[0,Di]时间内运行完优先级大于等于i的任务所剩余的时间，其中Ei={kTj|j=1, 2,…, |Ti/ Tj|}。

定义3：

关键参数αk和ηk可用式（5）、式（6）求出：

这里求出的ηk就是子系统k的周期，αk是分配给子系统k的处理器能力。取min(k)ηk作为隔离时间，乘以αk就是分配给子系统k的时间[3]。

3 内存管理机制

对任务集R={γi|1≤i≤m}（m表示系统含有m个任务，γi表示第i个任务）的内存集 {Mi|1≤i≤m}，该内存集主要是用于存储任务运行过程中的一些中间数据和程序或者用于存储需要进行通信的数据。Min{Mi|1≤i≤m}取出最小的任务内存Mmin，以Mmin大小为内存块的基本单位，将内存划分为若干内存块，以后系统分配内存时都是以该内存块大小为基本单位进行连续的分配。当分配到最后时再返回头部重新开始。

内存分配算法描述：

（1）已知任务内存集合{Mi|1≤i≤m}为任务正常运行时所需要的内存大小，已经经过适当的放大处理，使得每个任务都能在对应大小的内存中正常运行。

（2）令∆M=Min{Mi|1≤i≤m}，取出最小任务内存记为∆M。

（3）以∆M为基准对内存集{Mi|1≤i≤m}进行归一化处理，任务τi的内存Mi进行归一化处理后的结果是ni。定义ni=[Mi/∆M]，处理后的结果为{ni|1≤i≤m} 。

（4）计算

取最大值N=Max{ni+ni+1}。

（5）计算出所需内存的总大小为L=∆M·N，划分成N个∆M大小的内存块。

根据该算法，可以减少对内存的浪费。例如某安全设备具有4个任务，所需内存分别为100 k，150 k，50 k，200 k。根据循环内存分配法，只需要300 k的内存，而传统的静态内存分配法则需要500 k，由此可以看到该内存分配法可以减少内存的使用。

4 在CTCS-3列控软件中的应用

为了说明问题，本文仅使用简化的RBC、列车控制中心（TCC）、TSRS进行集成。其中RBC由3个任务组成：列车注册、列车注销和MA生成。TCC有一个任务：发送调度信息。TSRS由两个任务组成：临时限速提示激活和重复提示。

根据文献[9]，若RBC从CTC接受的消息包含反馈请求，则RBC应在1 000 ms内向CTC发送一条包含反馈码的反馈消息。若RBC接受一条CTC命令，则RBC应在1 000 ms内响应该命令。而最坏情况是上一周期刚开始接收到的命令要在下一周期才能进行处理，因此选取RBC的周期为1 000/2=500 ms。

根据文献[10]，临时限速服务器应根据临时限速调度命令提前一定时间（30 min）提示调度员进行激活，并可间隔一定时间（10 min）重复提示直至确认或超出该限速命令计划结束时间。相比其他任务，10 min的周期太长，为简便起见，设定为1 s（不代表实际情况，只是为了说明问题）。类似的，设定列控中心的周期为600 ms。

用前文所述的方法测得各个任务的最坏执行时间，得到表2。

表2 子系统任务执行时间

为了在RM算法中区分优先级（Ti越小优先级越高），表2中子系统中的各任务周期适当缩小。

根据RM可调度性判定[2]，若满足：

则任务集S可由RM算法调度。

根据表2：

ρ1=20/400+20/450+60/500≈0.22，L(3)=0.78，ρ2=8/600≈0.02，L(1)=1，ρ3=5/900+8/1000≈0.02，L(2)=0.83，各子系统可用RM调度。

由式（8）：

计算α1min=0.22/(3×(21/3-1))=0.28，α2min=0.02，α3min=0.02。

在保证Σαk＜1的情况下，可适当放大α，这里取α1=0.5，α2=0.1，α3=0.1。计算出αk，即可算出相应的ηk。

取ηk中的最小值可知周期是440 ms，一个周期内分配给RBC的时间为440×0.5=220（ms），分配给TCC的时间为440×0.1=44（ms），分配给TSRS的时间为440×0.1=44（ms)。

利用VXWORKS集成开发环境WorkBench的memory analyzer工具，可知每个子系统的最大内存使用情况，测得表3。

表3 子系统内存占用

根据内存分配算法，放大到20 kB，40 kB，10 kB。选取min{Mi}=10 kB，计算ni={2,4,1}，max{ni+ni+1}=max{6,5,3}=6，则所需全部内存为6×10=60(kB)。

从时间和空间两方面都知道具体分配参数后，就可以编程实现,编程结果如图3所示。

图3 编程结果

5 结束语

本文利用时空分区的原则，提出了一套列控软件的集成方法：（1）确定程序的最坏执行时间；（2）计算出总周期和各子系统的隔离时间；（3）按照所需内存安排静态内存分配。这样，处理后的程序在时间和空间上都有良好的确定性，保证了较好的安全性。

需要进一步研究的工作是：（1）需要研究对多核处理器的优化方法；（2）当程序很大、分支很多的时候测试每条路径的执行时间几乎是不可能的，需要一种更先进的方法；（3）本文计算执行时间依赖于VXWORKS操作系统的实时性，需要研究平台通用的方法。

[1]谢克嘉.ARINC653规范与机载实时操作系统发展趋势[C].全国抗恶劣环境计算机第十四届学术年会论文集，2004：56-58.

[2]王永吉，陈秋萍. 单调速率及其扩展算法的可调度性判定[J]. 软件学报，2004，15（6）.

[3]杨仕平.分布式任务关键实时系统的防危（Safety）技术研究[D].成都：电子科技大学，2004.

[4]Gupta N, Mathur A P, Soffa M L. Automated test data genera tion using an iterative relaxation method[J]. ACM SIGSOFT Software Engineering Notes. ACM, 1998, 23(6): 231-244.

[5]程敬原. VxWorks 软件开发项目实例完全解析[M]. 北京：中国电力出版社，2005.

[6]Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the ACM (JACM), 1973, 20(1): 46-61.

[7]李慧璐.对VxWorks中内存管理和定时器模块的改进[D].西安：西安电子科技大学，2009.

[8]徐晓光，叶 宏.分区间通信在航空电子系统中的设计与实现[J].航空计算技术，2005，35（1）： 45-47.

[9]中华人民共和国铁道部. 无线闭塞中心(RBC)技术规范[S]. 北京：中华人民共和国铁道部，2009，10.

[10]中华人民共和国铁道部. 科技运[2008]151号—客运专线列控系统临时限速技术规范[S]. 北京：中华人民共和国铁道部，2008.

责任编辑 杨利明

Method of train control software integration based on principle of temporal and spatial isolation

JING HAO1,2, MA Lianchuan1,2
( 1. National Engineering Research Center of Rail Transportation Operation and Control System, Beijing Jiaotong University, Beijing 100044, China; 2. School of Electronics and Information Engineering, Beijing Jiaotong University, Beijing 100044, China )

This paper discussed the problem that CTCS-3 devices faced about hardware resources waste, communication complexity and fault-prone. The thought of temporal and spatial isolation in ARINC 653 was referenced. The aim was to perform that a single device integrated the fuction of multiple devices, improved eff i ciency and reliability. The paper used two-level scheduling structure in the discussion, calculated routine running time according to characteristics of VXWORKS Operation System, determined the isolating time, implemented IDE tools to calculate memory size, then determin the size of isolating space. An example was used to prove the correctness of the method.

temporal and spatial isolation; Rate Monotonic(RM) Dispatching Algorithm; isolating time; isolating space; CTCS-3

U84.482∶TP39

：A

1005-8451（2014）06-0001-05

2013-11-26

景 浩，在读硕士研究生；马连川，副教授。