基于时间触发机制的实时通信架构研究与设计

蒋笑寒，李 牧，孙思杰，冯逸骏

(1.北京航空航天大学 中法工程师学院，北京 100191；2.北京工业大学 樊恭烋学院，北京 100124；3.北京航空航天大学 宇航学院，北京 100191)

0 引 言

信息-物理系统(cyber physical systems，CPS)[1]是集成计算、通信与控制于一体的下一代智能系统，目前已广泛应用于各个安全攸关领域(safety-critical)，为提升智能系统的计算能力、安全性以及可靠性，亟需建立一套能够用于CPS系统的单节点多核心分布式实时操作系统。

时间触发理论作为一种高确定性的实时理论，已经在安全攸关领域[2,3]有了多年的应用。Pont MJ提出时间触发原理；Hermann Kopetz等设计了时间触发架构，并提出了时间触发协议TTP(time-triggered protocol)；Yan[4]基于传统TTP协议设计了C类时间触发协议TTP/C。在传统分布式实时操作系统领域，Kane Kim提出了基于NT和Linux的时间触发支持的操作系统架构；Giotto把时间触发架构提升到了编程语言的层面。此后，有关时间触发架构的研究大量涌现[5,6]。随着单机内计算核心数目的增多，传统操作系统会产生严重的性能下降，针对此，Andrew Baumann和Paul Barham等提出了Multikernel架构。Barrelfish作为开源的Multikernel操作系统，为分布式的多核异构系统提供了更高效的操作系统基础设施。

本文将时间触发架构的设计思想应用于以Barrelfish为代表的Multikernel系统中，依靠SMT[7]理论，对Barrelfish的消息进行建模，从而生成满足所有约束的消息调度表，设计和实现时间触发的任务调度模型、系统通信服务以及配套的时间触发任务和通信的配置管理工具，形成可用的Multikernel架构分布式硬实时系统。

1 基于Barrelfish的时间触发实时通信框架设计

基于Barrelfish的时间触发通信框架主要包含运行时和离线两部分，其中，运行时部分的架构如图1所示。运行时部分负责支撑Barrelfish在部署及启动后的时间触发实时消息通信。图1中描述了两个通过实时交换机相连的SoC节点，每个SoC节点共有两块通过TTNoC相连的多核CPU。每个多核CPU上需要抽调出一个单独的核心以运行时间触发实时消息服务，该消息服务是一个CPU上所有应用程序与其它CPU上的应用进行通信的网关[8]。此外，一些实时应用有并行多线程的需要，而Barrelfish本身并不支持同一个进程中的线程在多个CPU核心上运行，缺乏这种并行特性会导致一些消息无法及时生成，使得整个系统不可调度，因此，该运行时还包含有一个以Group为核心组件的动态SMP(symmetrical multi-processing)子系统。

图1 时间触发通信框架-运行时部分

消息服务是整个系统运行时的基础设施。该消息服务在系统启动时负责让系统到达一致状态，在系统运行期间，解析时间触发消息调度表，提供消息在SoC内部或跨SoC的消息转发功能，并以API的形式为时间触发实时应用程序提供通信接口。此外，消息服务不仅需要在系统运行期间进行各个节点时间的同步，还需要维护各个节点的组籍状态，在节点失效时，利用冗余备份机制恢复系统的可用性。以Group为核心的动态SMP子系统可以在运行时动态地改变某一系统分区的计算能力，提高此分区的多核并行计算能力，防止过多的分区和单核有限的计算能力对系统的可调度性产生影响。

基于Barrelfish的时间触发通信框架的离线部分包含一个时间触发消息调度器，在对整个时间触发系统完成设计，得到应用程序的消息规范之后，调度器可以根据硬件网络约束和应用程序约束得到一组满足系统整体约束的消息调度表。该消息调度表规定了在何时有什么消息从何发送节点发送到哪些接收节点。运行时中的消息服务会解析该调度表，并依据全局时间基，在调度表规定的时间槽执行相应的消息转发动作。图2展示了基于Barrelfish的时间触发通信框架的离线和运行时部分的关系。

图2 时间触发通信框架-离线和运行时部分的关系

下面分别从消息服务、动态SMP子系统和时间触发消息调度器等3个方面展开叙述。

1.1 消息服务设计

针对时间触发的实时消息通信，本文设计了一套称之为MDL(message description list)的领域特定的调度表格式。静态消息调度器负责生成MDL，消息服务通过解析MDL语句，按照MDL描述的调度时机和要采取的动作进行消息的调度。消息调度器在解析MDL的过程中，会保证数据帧的完整性和正确性，同时也会保证数据传输的时序正确。

MDL通过全局时间基给出的时间槽为最小时隙单位。MDL设计了一种多等级的结构：最上层为集群描述符，一个集群描述符可以包含多个节点描述符，一个节点描述符又由多个时隙描述符组成。为了保证MDL语言的二进制兼容性，MDL在所有架构上都采用小端模式储存。

为了简化基本消息服务的设计，保证整个系统的一致性，无论是SoC内部还是SoC间的消息传输皆使用同一套数据帧格式。本节所采用的数据帧格式由帧头和数据体构成，其结构如图3所示。

图3 实时消息帧格式

帧头主要包含协议相关的语义属性，数据校验位等。数据帧的类型由帧头中的相关位确定。数据帧一共有两种类型：一种称为普通帧，搭载用户数据的帧属于此种类型；第二种帧称为节点控制帧，用于节点间维护在线关系，同步时钟等；此外，帧头中还包括校验位，为了减少校验算法带来的额外开销，本框架采用CRC校验法作为消息完整性的检查算法。

1.2 动态SMP子系统设计

Barrelfish无法利用多核并行能力的原因是其CPU Driver与CPU Core的对应关系高度耦合，在目前的实现中，CPU Driver与CPU Core为多对一关系。SpaceJMP[9]提出把虚拟地址空间当作操作系统的一种头等对象，允许一个进程可以在多个地址空间中快速切换，从而实现共享大段内存的目的。这种编程模型可以模拟出传统的Unix线程，但是由于添加了特殊的编程语言，需要特殊的编译器。频繁的切换地址空间对TLB和Cache都不友好，软硬件兼容性方面都不是非常优秀。我们可以通过设计一种新的消息传递基础设施，开发了一种基于任务派生—合并的并行任务模型(类似于MapReduce算法)，但由于涉及了大量小任务的迁移、调度和同步，这种编程框架本身会产生较大的消息通信开销和同步等待的开销，此外，该编程模型只适用于解决分治算法，无法使用常规并行多线程算法。

为了解决这个问题，本文设计了一个称为Group的核心系统组件，其架构如图4所示。

图4 Barrelfish的Group架构

为了减少对已有服务程序的更改，需要考虑到现有的服务程序都以线程不安全的方式实现，无法并行执行多线程，因此需要提供一种机制，在执行线程不安全的服务程序时，禁用并行的特性，只允许一个CPU Core串行的执行程序。本文采用如下方案解决这个问题。当Group中包含多个Core时，选取其中一个核心为主核心，负责Group的合并和拆分以及系统进程的运行；其它的Core则成为成员核心，负责运行其它的进程。主核心不可以脱离当前Group，成员核心则可以自由地附着到其它的核心。

1.3 时间触发消息调度器设计

本文定义了一个时间触发实时网络中的所有约束条件。为了简化约束的书写，本节做了如下假定：

(1)整个集群的超周期被划分为长度相等的时间片，该时间片的长度为全局时间基的时间粒度的整数倍，称之为集群超周期。超周期的值可用所有帧的周期的最小公倍数计算得到。

(2)每个节点在发送或者中继消息时，发送一个数据帧只占用一个时间槽。

(3)对于同一个应用发送的消息，将以相同的路径到达接收者。

在此基础上，可以对约束条件进行简化的表示。本文把约束条件分为硬件约束条件和软件约束条件两类进行描述：

(1)硬件约束条件

硬件约束条件中最基础的是发送端口独占约束，即无竞争约束。该条件意味着一个发送节点或者一个中继节点只有在前一条数据帧完全发送完毕之后，才可以开始发送下一条数据帧。

(2)软件约束条件

端到端消息传输约束描述了应用程序要求的数据帧端到端传输的最大时延，该最大延迟必须小于应用发送帧的周期。对于多播传输，假设所有的接收者都具有相同的端到端传输时延要求。

求解最优数据虚链路时，本文采用以下目标函数

(1)

该目标函数要求整个系统调度数据帧的最大延迟最小，最大数据帧延迟越小，总体延迟越小，系统利用率越高。

最优解算法在面对较大规模数据集时，无法在可以接受的时间内得到一个解[10]，因此本文不采用最优解算法，而是使用目前比较成熟的近似算法(如Wang[11]、Lee[12]等)，在多项式时间内，求出该问题的近似最优解。

2 基于Barrelfish的时间触发实时通信框架实现

2.1 消息服务实现

时间触发实时通信框架提供的消息服务API接口见表1。

表1 Barrelfish实时通信框架操作接口

其中，最核心的功能是消息收发接口，时间触发的实时应用程序可以调用这两个接口进行消息的收发。当发送消息时，调用该接口后，应用程序将要发送的消息数据会被复制到相应消息通道的缓冲区内，当调度表规定的消息传输时刻到来时，消息服务会把该消息从缓冲区中取出，并复制到目标缓冲区中。当接收消息时，调用该接口后，会根据调度表的时刻，等待到消息到来的时刻。在此期间，消息服务会把要接收的消息从发送者的缓冲区复制到接收者消息通道缓冲区内，当时刻到来后，该接口会将消息从消息通道中复制到应用程序的数据缓冲区，供应用程序使用，然后唤醒应用程序进行后续的计算操作。

2.2 动态SMP子系统实现

系统的实现主要可分为两部分，一方面是对CPU Dri-ver 的更改，将CPU Driver对CPU Core的依赖，更改为对Group的依赖，并将CPU Driver修改为线程安全的实现。另一方面是对libbarrelfish的更改。libbarrelfish把各个系统服务提供的各项功能整合到了一起，封装成为易用的API，应用程序借助该库能获得完备的操作系统功能。

(1)针对CPU Driver的SMP实现

CPU Driver中的数据段，根据数据使用者的不同，可分为两类。一类数据代表了CPU Core的状态，另一类数据则代表了该CPU Driver本身的状态。

对于前者，代表CPU Core状态的数据由Group组件统一管理，Group组件会将这些数据项复制多份，保证每个核心都有相对应的唯一的数据，并由Group组件为CPU Driver提供相关的读取、写入接口。

对于后者，考虑到需要保护的关键代码段通常不是很大，可以使用自旋锁对这部分数据进行保护。在多核并行场景下，自旋锁可以保证核间临界资源的正确性[13]。自旋锁与互斥锁、信号量类似，只是自旋锁不会引起调用者阻塞。如果自旋锁已经被其它执行体占有，调用者就一直循环检测自旋锁是否被释放，是否处于空闲状态，这个循环过程就是自旋。自旋锁的占有时间非常短，因此调用者不被阻塞而在那自旋，比上下文切换节省时间开销，效率远高于互斥锁、信号量。但普通自旋锁具有随机占有的特性，这带来了调度上的不公平。为了避免这个不公平问题，本文使用了被称为轮转自旋锁的技术，与普通自旋锁的随机占有锁的方式不同，每个核心采用排队的方式获取自旋锁，这样每个CPU核心都有相同的概率获得锁的使用权。

(2)针对libbarrelfish的SMP实现

本文采用一种称为代理执行的方法来解决libbarrelfish中存在的数据竞争问题。这种方法的核心在于，在一个Group中，只允许主核心执行Disabled状态的Dispatcher。成员核心只允许执行用户创建的线程的代码和线程调度器。当成员核心上的线程需要切换到Disabled状态时，会首先将线程迁移到主核心上，其中，线程的迁移可以利用线程对处理器核心的亲和性来完成。

另一个需要改动的点是Barrelfish的消息机制，Barrelfish系统中的LMP消息是基于Upcall实现的，UMP消息则是通过轮询实现。为了避免在消息处理相关的代码中产生数据竞争，新的消息机制只允许Group内的主核心执行相关的代码，负责所有消息的转发和轮询。

2.3 时间触发消息调度器实现

本文设计了两种实时调度器，一种是基础时间触发实时消息调度器，另一种是增量时间触发实时消息调度器。SMT求解器选用微软的开源求解器Z3，并使用它提供的Python API进行编写。增量时间触发实时消息调度器会在两个求解阶段间多次切换，并使用Z3提供的回溯功能。

(1)基础时间触发实时消息调度器实现

基础求解器的实现较为简单，在基础求解器中，会首先把所有数据帧的约束条件添加到SMT求解器上下文中，然后调用SMT求解器的求解函数，SMT求解器会首先检查这些约束条件是否具有一致性，若满足一致性，便可以计算得到本组约束的解。这组解可以通过SMT求解器提供的API函数得到。

(2)增量时间触发实时消息调度器实现

由于SMT求解器对一次求解的约束条件数目有所限制，当约束规模较大时，无法将全部约束一次性全部添加到求解器中。为了解决这个问题，本文设计的增量调度器不会一次性生成全部的约束条件，而是逐次地将约束条件的子集加入到SMT求解器中并进行多次求解。在每次子集的求解完成之后，会按照这一部分的求解结果，把数据帧的偏移固定下来，作为下一次求解的约束输入。这样的方案可能会导致求解器在中间某次求解过程中返回失败，对于错误的处理，本文采用回溯的方法，逐步增大之前的约束子集的数目。当SMT求解器无法在规定的时间内得到一组解，或是约束子集的数目超过了预先设定的阈值，则认为调度失败。

增量调度算法开始时，首先生成这一数据帧范围内的约束，并检查是否存在针对这一部分的可行解。若存在可行解，则从求解器中获取解，并把这些解保存到本地变量中，作为新的常量约束并用于下一轮的约束。最后，把输入的帧集合更新为下一轮的集合。

在最坏情况下，回溯过程有可能回溯到数据帧序列的第一帧。在这种情况下，增量调度器等价于基础调度器。当调度器没有能在合理时间内得到解时，便会终止求解算法，回溯到前面得到部分解的步骤，并返回当前已经得到的时间表。调度算法求解的中断可采用封装好的信号中断函数。

至此，基于Barrelfish的时间触发实时通信框架的设计与实现已经完成。

3 基于Barrelfish的时间触发实时通信框架实验结果与分析

本文先分别针对如下3个部分做了验证和测试：消息通信服务的正确性及其功能实现的完整性、时间触发通信消息调度算法及调度器的正确性、Barrelfish的动态SMP子系统的性能，最后对整个框架进行综合测试。

为了对通信框架和动态SMP子系统两部分的结果进行验证，本文采用了软件模拟和真实硬件两套环境开展实验。其中，软件模拟部分使用QEMU，硬件部分使用NVIDIA Jetson TK1作为实验平台。两者皆以ARM为计算平台架构。具体的硬件参数见表2。

表2 实验平台硬件参数

对于调度算法的验证，本文首先通过一定规则生成了一个测试集合，然后对调度算法的性能、正确性和调度结果的质量做了评测。

(1)消息服务性能测试

本部分主要测量了时间触发通信的延迟，该延迟是SMT调度表求解的重要参数。测试时，在系统的两个核心上分别建立服务端和客户端两个进程，客户端向服务端发送请求后，服务端立刻返回一条消息。通过消息的往返发送，可以测量出延迟。本次测试中，每经过一万个消息往返，记录一次时延，测试结果如图5所示。

图5 Barrelfish实时通信延迟

从图5中可以看出，SMP通信机制容易受到内核调度器和其它系统进程的影响，消息的时延抖动相对较大，但是依然满足实时应用的要求。对于通过消息转发服务收发的SoC内部消息，由于采取了轮询机制，平均延迟较小，且抖动较小。对于跨SoC的消息，由于目前采用普通TCP/IP网络进行测量，抖动比较严重。

(2)调度算法性能测试

本文一共测试了3种网络拓扑，分别是星状网络，树状网络和雪花状网络。针对每种网络拓扑，随机生成一系列的帧集合，并随机生成一定比例的约束条件(本文使用帧数的20%作为应用级约束)，然后使用求解器进行求解。调度器求解时间的统计结果如图6所示。

图6 各种网络拓扑数据帧调度耗时

(3)动态SMP子系统测试

动态SMP子系统本质上是实现了共享地址空间的并行方案。共享内存实际上是共享部分物理内存，而动态SMP子系统则是共享整个虚拟地址空间，本质上来看两者区别只是共享空间的大小不同，但是动态SMP子系统提供了一个更友好的编程接口。为了验证两种方案对性能的影响，本文通过矩阵相乘算法，对两种方法的性能进行了测试。

测试结果如图7和图8所示。

图7 Qemu中共享内存与动态SMP子系统性能对比

图8 Jetson TK1中共享内存与动态SMP子系统性能对比

由测试结果可以看出，共享内存方案由于存在通信延迟，其性能比动态SMP子系统方案要略微差一些。但是两者都能起到并行执行的效果，相比于单核心执行，并行执行能够明显地提高性能。

(4)综合测试

为了对整个系统进行验证，本文设计了如图9所示的网络结构，由于缺乏时间触发实时网络硬件的支撑，本节将使用Qemu搭建虚拟网络进行模拟验证。

图9 综合实验组网

网络中，每个节点上运行有X64架构的四核心处理器，节点间通过Qemu虚拟交换机相连。每个节点内部的通信不受限制，相当于CPU内部的核心间有两两相连的通信链路，节点间产生通信时，每个节点在一个时间槽只能发出一条消息。每个有依赖应用的应用，只有在接收到依赖应用发来的消息之后间隔一个时间槽，才可以发送消息。

本文设计了如表3所示的综合实验应用。

表3 综合实验应用设计

由表3可知，集群的超周期为24。针对应用的周期，调度器生成了实时调度表，如图10所示。

图10 实时调度器生成调度表

调度表的成功生成表明了基于Barrelfish的时间触发实时通信框架的正确性与可行性。

4 结束语

本文在Barrelfish的基础上设计与实现了一套基于时间触发机制的实时通信架构，该架构包括一套独立的时间触发实时消息服务、接口以及用于时间触发实时系统消息调度的静态离线调度算法和调度器。该通信架构为Multikernel架构在分布式CPS实时系统上的应用打下了基础。

该通信架构仍有如下地方有待改进：

(1)每个SoC上都需要分出单独核心运行时间触发实时消息服务，对CPU资源产生了较大浪费。

(2)目前尚未给出综合消息调度与任务调度的完整解决方案。

(3)当前测试所使用的硬件系统规模较小。