实时机模型及时间语义指令集研究*

陈香兰，李 曦，汪 超，周学海

(中国科学技术大学计算机科学与技术学院，安徽 合肥 230027)

1 引言

航空航天、汽车电子和轨道交通等硬实时HRT(Hard Real-Time)系统需要严格的时域控制，要求系统设计满足时间可预测性，以保证时序行为确定性和安全隔离。所谓“时间可预测性”一般指静态地计算程序执行时间(Execution Time)的安全和精确上界的能力，与计算机体系结构和任务执行机制密切相关。现代的计算机系统通过在各个层次引入计算并行化和访存缓存化等优化机制，虽然有效提升了系统的平均性能，却也带来了严重的时序不确定性问题。另一方面，传统实时系统设计采用优先级调度策略，依赖定时器尽力而为地满足任务执行的时间约束，但定时器为处理器外设，与指令执行异步，且优先级调度可能存在时序异常等问题。这两方面的原因导致程序执行时间在设计阶段难以紧致确定，且平台依赖，难以验证。因此，现有设计方法只能基于保守设计思想，以最坏情况执行时间WCET(Worst-Case Execution Time)分析理论为基础，采用时序相对简单的系统架构或过量资源预留策略，导致实际应用中的资源利用率甚至不足30%。即便如此，在设计时仍然无法保证可预测性，操作的正确性只能事后验证。

未来的实时系统具有混合关键系统MCS(Mixed Critical System)特征，要求为时序关键(Timing Critical)应用提供实时性保证，为安全关键(Safety Critical)应用提供时空隔离能力，为其他应用提供高性能算力。因此，需要构建严格的紧致时间MTTT(Multi-Tier Tight Timing)设计方法，需要突破现有计算机体系结构理论和方法的局限，建立软硬件混合系统的建模方法。

自20世纪90年代起，实时系统研究者认识到时间可预测性对硬实时系统设计的重要性，以构造时间行为可预测的实时系统为目标，从计算机系统结构、处理器微结构、编程模型和编程语言等方面展开了广泛而深入的研究。研究表明，采用构件化软件体系结构、基于时间触发执行机制和LET(Logical Execution Time)编程模型[1]构建时序关键系统是实现MCS系统时序隔离、可预测、可组合和可扩展(Extensibility)的可行技术路线。

但是，受上述体系结构和任务执行机制限制，LET模型系统执行效率低下。为此，本文认为必须解决2个关键问题：(1)建立操作的时间语义模型，明确其时间行为、时间属性和时间约束等要求；(2)突破现有计算机系统结构限制，提出具有时间语义的实时计算基础架构模型(处理器体系结构、编程语言、分布式通信)和编程范式。目前广泛应用的建模方法只提供了描述时序约束的语法糖，缺少时间语义，无法在设计时进行时序验证和组合。

本文提出一种具有时间语义的处理器体系结构模型——实时机RTM(Real-Time Machine)，和时间触发指令集TTI(Time-Triggered Instruction set)[2]，作为构建多层次协同的紧致时间MTTT设计方法的重要基础。

2 相关研究

本节对当前支持实时计算的处理器体系结构和高级编程语言的研究现状进行梳理。

2.1 实时计算处理器体系结构

实时处理器研究工作可分为3类：时间可预测处理器TPP(Time/Temporal/Timing Predictable Processor)、RTOS(Real-Time Operating System)加速器和反应式处理器。

LEOPARD(LEOn-based Probabilictically Analyzable processor Design)[3]基于通用处理器LEO，增加低开销机制，支持基于测量的时序分析MBTA(Measurement-Based Timing Analysis)WCET时捕捉抖动(延时变化)资源的影响。在计算核级，分别控制Cache、TLB和延时可变的浮点计算单元的抖动。在芯片级，控制竞争，保证时间可组合。

DMT(Dominant Meta Thread)[4]为同步多线程SMT(Simultaneous MultiTreading)处理器。处理器中存在多个硬实时(HRT)和软实时SRT(Soft Real-Time)或非实时线程。主线程DMT以看起来是处理器中的唯一线程的方式执行，因此可以采用单线程WCET分析技术。通过主时间共享技术DTS(Dominant Time Sharing)，多个HRT线程共享DMT的执行时间。各线程的时间片长度和周期可以在运行时调整。

FlexPRET[5]处理器为SMT处理器，采用特殊前推通路避免数据依赖，采用细粒度多线程技术通过并发降低不使用动态分支预测和Cache所导致的性能损失，达到WCET计算的复杂度与平均计算性能之间的平衡。同时执行HRT任务和SRT任务。流水线使用线程隔离技术(HRT线程时分多址)消除线程间干扰。指令调度对SRT任务透明，不影响HRT任务。

同时，FlexPRET以所谓PRET(PREcision-Timed)机模型[6]——一种提供可重复和可控制时序的处理器微结构模型——为基础，针对时序可重复性问题进行指令集扩充，增加了一些时序控制指令，包括设定代码段的执行时间下界指令delay_until、设定跳转时间下界指令branch_expire以及设定在某个时刻抛出异常的指令interrupt_expire。PRET机采用物理与逻辑混合的时间概念。在FlexPRET中，时间表示为相对于系统加电或复位开始的纳秒值而不是时钟滴答数，时序精度为一个时钟周期，时钟宽度为32位，更长的相对时间需要软件实现。这种表示方式使程序的时间值与处理器时钟频率无关，保证了二进制代码的可移植性，并支持动态频率调节技术。对分布式系统，可以通过调整定时器的增加值来实现时间同步，并维持亚纳秒定时精度。FlexPRET将具有明确时序约束的硬实时线程(HRT)和传统的软实时线程(SRT)组合在一起，由应用程序平衡共享处理器资源，将HRT不占用的流水线周期让给SRT使用。硬件多线程技术显示，确定性随着应用中并发性增加而增加，与传统处理器差别显著。只要有足够的并发性，流水线停顿和访存延迟较小，线程执行的时序更加规则和可预测，中断响应延迟也降低几个数量级，处理器利用率可达100%，但线程交替访问，难以确定截止时间。

ARPRET(Auckland Reactive PRET)[7]处理器用于执行PRET-C程序。PRET-C是C语言的宏扩展，支持同步并发和表达逻辑时间的高级结构。ARPRET基于3级流水线软核Microblaze和1个硬件调度器PFU(Predictable Functional Unit)。只使用片上存储器，因此其读写访存指令为1个时钟周期。ARPRET以吞吐率和简化最坏情况响应时间WCRT(Worst-Case Response Time)分析为目标。采用逻辑时间概念，通过静态代码分析实现逻辑时间和物理时间的映射。

JOP(Java Optimized Processor)处理器[8]使用2级栈缓存架构实现Java虚拟机的栈架构。采用3级流水线，使用2个寄存器存储2个栈顶对象，栈的其他部分在SRAM中。由于分支延迟开销很小，因此不使用分支预测。JOP中的所有字节码被转换为固定长度的微指令，每个微指令的执行周期数固定，独立于其周围的指令。

ARPA-MT(Advanced Real-time Processor Architecture-MultiThreaded)[9]是一种基于MIPS32架构的SMT处理器，针对多任务实时系统进行了优化。ARPA-MT的协处理器0负责内存管理、异常和中断处理，协处理器2则实现了实时系统的硬件支持，如定时、任务调度、同步和切换，以及时序约束检测。这些功能的硬件实现能够更快、更加可预测地执行任务，减少了RTOS开销，并改善其确定性。

与环境高效和可靠地交互(称“反应”)是面向控制的嵌入式系统应用的关键特征，往往采用同步语言(如Esterel)和编程范式。反应式处理器不使用中断而是使用ISA(Instruction-Set Architecture)指令与环境交互，且执行机制采用时间触发而非事件触发。REMIC(REactive MICroprocessor)[10]是带有同步反应式功能单元和控制单元的反应式处理器，EMPEROR(Embedded MultiProcessor supporting Esterel Reactive OpeRations)[11]提供在多处理器之间分配同步线程的方法。

可以看出，TPP处理器通过限制使用分支预测、乱序执行和Cache等造成时序不确定的技术，提高WCET分析的紧致性。但是，TPP主要以满足WCET分析紧致性要求为目标，损失了计算性能。RTOS加速器通过硬件实现任务调度和关键服务原语，降低RTOS的运行开销和时间抖动，提升了可预测性，利于系统验证(硬件执行时序是完全确定的)，但受硬件实现复杂度和资源限制，灵活性不佳，通信接口效率低、时延高。反应式处理器仅支持特定的同步编程语言和范式，通用性不佳，且计算性能有限。

2.2 实时计算高级语言和编程模型

现代编程语言反映了计算机体系结构的特征。面向通用计算的编程语言描述了操作的执行顺序，操作的时间属性与程序的逻辑正确性无关。实时系统编程可以基于同步范式(使用同步编程语言，如Esterel)或异步范式(使用异步编程语言，如Ada)。

同步模型基于逻辑时间模型和同步假设，即动作是原子的且瞬间完成，并发动作间无交互，动作与逻辑Tick同一时刻发生，无抖动。该抽象为确定性模型，利于系统行为分析验证。同步语言中，逻辑Tick是语言语义的组成成分，用于事件定序，与实际物理时间无关。Esterel等同步语言基于虚拟时间抽象，与平台的物理时间无关，其逻辑行为总是可预测的。实现时采用时钟驱动的静态调度技术，利于响应时间分析和因果关系保证，但表达复杂交互行为的能力不足。

异步语言基于物理时间的实时钟模型，一般提供时钟访问、进程延迟、同步与通信超时等实时控制设施(包括原语与结构)。Ada编程语言基于物理时间概念提供了量化描述时序约束的语言结构，需要借助定时器中断或操作系统所提供的时间服务控制程序的时序行为。Ada采用中断驱动的优先级调度技术，利用定时器控制任务执行时间，且中断是一种异步并发机制，必然导致应用程序的时间行为不确定和不可重复。因此，采用Ada等高级语言进行实时软件编程是低效的，一方面其时序约束定义的粒度过粗(以任务为最小实体)，另一方面，这些语言的编程模型所表达的时序约束仅为程序中位置相邻的前后2个任务之间的时序关系，无法表达任意操作(可能并行)的时间约束。由于没有支持通过合适的方法定义时间需求和进行高精度时序分析的实时语言，实践中HRT系统仍然只能采用低级编程语言，并手工对时间需求进行调优。

Chung等[12]针对静态调度方法，对C语言进行扩展，基于所谓时间有向图(Directed Timed Graph)模型，给出表达时序约束和优先约束的语言结构，包括时序块(Timing Block)和Temporal表达式，描述操作的开始时间、完成时间和周期。

ZET(Zero Execution Time)模型是同步反应式编程的基础抽象，BET(Bounded Execution Time)模型是实时调度理论的基础抽象。实时程序的相关行为由输入输出时刻决定，而非程序代码的执行时刻。因此，Henzinger等[1]结合ZET和BET模型，在2000年提出了实时编程范式LET模型。采用LET模型时，任务总是在其激活区间的开始处读数据，结束处写数据，使其可观察的时态行为独立于任务的物理执行。LET确定了读程序输入到写程序输出之间所需的时间，而不考虑执行程序所需的时间，具有平台可移植性。虽然实际应用时LET模型的资源(缓存、时间)利用率较低，但LET为控制工程师和软件工程师提供了清晰的时序模型接口。2017年以来，随着多核平台下可预测性(Predictability)成为关键问题，工业界认为LET对于解决多核MCS应用和分布式实时系统的通信确定性问题极具吸引力，甚至可能与Autosar相结合而成为新的工业标准。

3 实时机模型

计算机科学领域的时间概念相当原始。图灵机和冯·诺依曼机模型基于顺序控制抽象，指令一条接一条执行，时间先后关系(Temporal Succession)是当前机器语言级唯一可用的时序关系。虽然定义冯·诺依曼机的程序逻辑行为无需显式地引用时间概念，但无法满足实时系统所需要的实时间约束。

在时态逻辑、进程代数、自动机和断言等形式化建模方法中，时间概念在模型语义中是隐式的，所考虑的唯一时间属性是顺序，不考虑绝对时间(时间点)或相对时间(持续时间)，因此只能表达和验证离散事件系统行为的时态顺序正确性，欠缺足够的实时表达能力。它们的基本假设是程序代码的执行速度足够快，程序的时间属性与其功能正确性无关。为了适应实时系统规约的需要，人们试图扩展传统的形式化方法，以允许定量地表达定时特性，如时间自动机和实时时态逻辑(Real-Time Temporal Logic)等。这些方法可应用于简单系统的可调度性分析或时间行为验证，但难以应用于具有严格时序行为约束的复杂实时系统。

现代计算机系统依赖基于定时器的时钟中断机制提供定时服务。定时器作为处理器外设，通过轮询或中断方式访问。时钟中断是一种异步并发机制，精度低，开销大，且存在副作用——中断当前任务将导致其执行时间延长，可能产生危害性后果。基于优先级的任务调度策略以中断机制为基础，行为难以预测，且验证困难，平台依赖性高。

可以看出，由于当前处理器体系结构不显式地提供时间语义支持，系统模型和基础设施缺乏时间语义，或仅基于逻辑时间，或仅基于物理时间。虽有研究者提出了一些引入时间概念的高级语言，但底层没有时间语义而仅仅从高层引入是有问题的，导致系统设计、分析、验证与实现的时间语义不一致。现有时间可预测性保证依赖基于WCET的可调度分析，但由于系统行为内在的异步并发性，执行时间有界并不能保证操作的执行顺序，因此不能保证时序行为可预测。

传统的保守方法只适合简单实时系统设计，MCS系统需要紧致时间设计方法。2005年以来，Bensalem等[13]多认识到当前研究的局限性，在不同场合提出实时计算需要重新思考甚至发展计算机科学的理论基础。但迄今为止，由于实时应用涉及控制工程、电子工程、计算机工程和软件工程等多学科交叉，各领域之间存在理论方法甚至文化差异，这一问题远未解决。

本文认为，任务、动作和操作的时间语义应包含时间行为和时间属性。前者与硬件实现无关，不应依赖于底层实现；后者与硬件实现相关，即具有平台依赖性。前者为语义确定性问题，后者为可预测性问题。LET模型通过解耦计算与通信，保证了时态确定性，具有时域控制与值域控制相分离、时序行为可预测可组合且平台无关等特点。另一方面，时间触发TT(Time-Triggered)执行机制具有时序可预测性和时间隔离(分区)的特性。但是，两者都需要具有确定时间行为的处理器架构和时间语义指令集支持，并以此为基础形成紧致时间设计方法。

定义1实时机RTM模型对冯·诺依曼机进行以下扩充：

(1)计算机系统由运算器、控制器、存储器、时钟设备和I/O设备等功能部件构成；

(2)指令时钟部件用于操作定时，与CPU的指令数据通路和控制器紧耦合，在保持冯·诺依曼机指令的逻辑功能不变的同时，增加特定操作的执行时刻和限定操作序列(动作)的执行时间等时间语义；

(3)RTM的指令字由操作码、地址码和定时码构成，操作码定义操作的功能，地址码指定操作数和下一条指令的地址，定时码指定操作的时间约束。

RTM如图1所示，以支持紧致时间设计为目标，其核心思想不是仅仅在CPU中增加了时钟部件，而在于明确了时间行为控制的概念，并通过提供时间语义指令集，使上层应用的时间行为与指令周期同步，实现了时域控制的原子性，减小了定时抖动。RTM以“关注分离(Separation of Concerns)”和“构建正确(Correct-by-Construction)”为设计原则，区分逻辑控制与时域控制，为实现从时序可预测设计到时序确定性设计转变奠定了理论基础，利于实时程序代码自动生成和降低系统验证的复杂度。

Figure 1 RTM architecture图1 RTM结构

以RTM为基础，时间语义指令集可提供at、delay-until和timestamp等控制时间行为的指令，支持逻辑执行时间(LET)模型和时间触发等应用模式。

4 应用示例

本节对RISC-V[14]指令集进行时间语义扩展，定义时间触发指令集TTI，并给出一个直升机飞控应用实例。

4.1 TTI指令集

TTI时间语义指令集扩展主要包含时间模型、时间寄存器和时间语义指令3个部分。其中，时间模型规范该指令集扩展时间相关的概念和应用方法；时间寄存器是在通用寄存器之外添加的新寄存器，用于存放时间值，该时间值符合时间模型规范；时间语义指令包括时钟管理指令、时间寄存器管理指令和时间语义操作指令。

本文采用基于时间点(时刻)的绝对时间模型，即处理器时钟的时间从设定时刻开始，一直以一定的速率增长。描述操作的时间时，采用某时刻的方式；描述一个时间段时，采用从某时刻开始到某时刻结束的方式。时间寄存器存放绝对时间模型的一个时间点。

时间语义指令功能如表1所示，包括：

(1)时间管理指令：setti/getti指令用于设置/获取系统当前时间；settg指令用于设置系统当前时间粒度，即时间向前自增的单位。

(2)时间寄存器管理指令：tmove指令用于通用寄存器和时间寄存器之间的数据传输。

(3)实时操作指令：ttiat/ttoat指令用于在指定时刻I/O端口输入输出。

Table 1 Function of extend instructions

表1中，rs1、rs2和rd为通用寄存器，trs为时间寄存器地址，tg为系统当前时间粒度寄存器，ti为当前时间寄存器。

RISC-V是一个典型的三操作数、加载-存储形式的RISC指令集架构，由基础指令集和扩展指令集组成。基础指令由基本整数指令构成，扩展指令分为标准扩展和非标准扩展2大类。现阶段已经完成的标准扩展为一个包含标准乘法和除法(M)、原子(A)、单精度(F)和双精度(D)运算的通用标量指令集。非标准扩展作为一个高度特殊化的扩展，由用户根据功能需求自定义完成。TTI指令集基于RISC-V非标准扩展进行定义，如图2所示。

Figure 2 Format extension for TTI instructions图2 TTI扩展指令指令字格式

4.2 直升机飞控

直升机飞控系统的需求如图3所示。若采用传统的前后台编程范式或轮询范式实现飞控软件，其架构和时序分别如图4a和图4b所示。可以看出，当某时刻需要执行多个动作时，采用这种编程模式必然存在定时抖动，如图4b中时刻0,2和6。

Figure 3 Requirements of a helicopter flight control system

Figure 4 Software architecture and timing

LET编程模型将任务的逻辑行为“输入-计算-输出”过程相分离，如图5所示，定义了严格的输入输出时刻，要求在指定时刻输入，在输出时刻之前计算出结果，并能够将输出结果保持到指定时刻输出，具有时间行为可预测、可组合和平台无关性等重要特征，利于设计时进行系统行为验证。

Figure 5 LET programming model图5 LET编程模型

基于LET编程模型的飞控系统的实现代码如下所示：

1Init(); // init the system

2time_t1 =time_t2 =time_t3 =time_t4 = 0;/*suppose all tasks start at 0*/

3flag_t1 =TTI(all_sensor_data,time_t1);

4flag_t2 =TTI(keyboard_data,time_t2);

5flag_t3 =TTI(sensor_data,mode_data,time_t3);

6flag_t4 =TTI(loop_data1,loop_data2,loop_data3,time_t4);

7SetIntertup();/*set a interrupt, and only enable it to interrupt*/

8 /*t1～t4, every 1/180 second, when occur, store*/

9 /*context for current task and go to INT_LABEL*/

10while(TRUE) {

11 INT_LABEL:

12if(flag_t1) {

13load_context();

14t1();

15store_context();

16time_t1 += 1;

17TTO(sensor_data,time_t1);

18flag_t1 =TTI(all_sensor_data,time_t1);

19 }

20if(flag_t2) {

21load_context();

22t2();

23store_context();

24time_t2 += 6;

25TTO(mode_data,time_t2);

26flag_t2 =TTI(keyboard_data,time_t2);

27 }

28if(flag_t3) {

29load_context();

30t31();

31t32();

32t33();

33store_context();

34time_t3 += 2;

35TTO(loop_data1,loop_data2,loop_data3,time_t3);

36flag_t3 =TTI(sensor_data,mode_data,time_t3);

37 }

38if(flag_t4) {

39load_context();

40t4();

41store_context();

42time_t4 += 6;

43TTO(control_data,time_t4);

44flag_t4 =TTI(loop_data1,loop_data2,loop_data3,time_t4);

45 }

46 }

基于LET编程模型的飞控系统各任务的时序行为如图6所示。其中，t1为传感器任务，t2为模式任务，t31,t32,t33为内循环任务，t4为控制器任务。

Figure 6 Timing for the LET program of the helicopter flight control program图6 直升机飞控LET程序的时序

每个任务的LET实现包含3个部分：基于TTI()的定时输入、计算和基于TTO()的定时输出。其中，TTI()和TTO()分别是对ttiat和ttoat指令的封装。TTI()在指定时刻完成指定数据的输入，TTO()在指定时刻完成指定数据的输出。若指定的时刻未到，则等待，等待过程中TTI()的返回值始终为FALSE，指定时刻到来时，TTI()完成指定数据的输入，此后返回值为TRUE。TTO()类似，但没有返回值。每个任务通过TTI()显式地请求在指定时刻执行指定数据的输入。系统实现代码中第3～6行分别是t1,t2,t3和t4的首次定时输入请求，对应图6中的“↑”标记。计算部分的代码是位于load_contex()和store_context()中间的代码，第14,22,30～32,40行所示。计算执行完毕，每个任务通过TTO()显式地请求在指定时刻输出指定数据，同时通过TTI()发出下一轮的定时输入请求。系统实现代码中第17,25,35,43行分别是这4个任务的定时输出请求，第18,26,36,44行分别是它们的下一轮定时输入请求，并且这4个任务都将本次输出和下一轮的输入放在同一时刻，对应图6中的“?”标记。可以看出，任务的LET实现中，输入输出时间完全由TTI()和TTO()指定的时刻决定，而不受任务计算部分程序执行时间抖动的影响。

飞控系统中设置一个周期性时钟中断，如系统实现代码中第7行将中断频率设置为每秒180次。该中断只用于中断代码中while循环中的4个任务。每次中断处理，系统跳到INT_LABEL处开始处理。系统按照代码顺序依次查看是否需要执行这4个任务的计算部分，如第12,20,28,38行的if语句。当某任务设置的TTI()返回值为TRUE就执行，如图6中t1每次都执行。当某任务设置的TTI()返回值为FALSE，就跳过该任务不执行，如图6中点C处就跳过t2执行t3。若没有任务需要执行，系统idle，如图6中阴影右下角的idle部分，此时可以执行其他软实时或非实时任务。中断发生时，若有当前任务正在执行，则该任务被中断，保存该任务上下文，然后开始新一轮中断处理，如图6中点A处，中断在t2执行过程中发生，此时保存t2上下文，转到INT_LABEL处从t1重新开始依次执行。被中断的任务在后续执行中轮到该任务执行时将继续执行，如图6中点B处，t1执行完后顺次执行t2时，加载t2之前被中断的上下文继续执行。

由于输入输出定时由ttiat/ttoat指令控制，与任务计算逻辑的执行时间无关，保证了控制系统的鲁棒性。

5 结束语

针对未来复杂的混合关键系统需要研究新的紧致时间控制设计方法，采用构件化软件体系结构，基于时间触发执行机制和LET编程模型构建时间关键系统是实现可预测性、时序隔离、可组合和可扩展的有效方案，但性能低效和分析验证复杂是这一方案的瓶颈，需要实时计算机体系结构创新。

本文以冯·诺伊曼模型为基础，定义新的支持时间语义的实时计算机体系结构模型，并以此为基础实现紧致时间方法。文中提出了支持实时计算的RTM计算机模型和TTI指令集。RTM突破了冯·诺伊曼机模型在实时计算应用中的理论局限，分离时域控制和值域控制的时序约束，明确了时间行为控制的基本抽象。

目前本文正在对RISC-V指令集进行TTI扩展，实现一个实时处理器原型RPU(Realtime Processing Unit)，以验证RTM的时序行为控制能力。RPU将采用硬件多线程技术，以满足安全关键应用的高性能和时空隔离需求。支持时间行为约束表达的实时控制设施(原语与结构)、编程语言、中间语言以及时间安全性分析与验证理论和技术都是重要的课题。