基于SPARC的实时系统寄存器窗口溢出时间分析*

于广良 杨孟飞

1.北京控制工程研究所，北京100191

2.中国空间技术研究院，北京100094

航天器控制系统要求具有很高的实时性和可预测性［1-2］。当处理器采用SPARC体系结构时，由于其采用了寄存器窗口机制，随时出现的窗口上下溢陷阱处理引起的时间开销对任务程序的最差执行时间(WCET，Worst Case Execution Time)［3］有显著影响，这对于验证系统的实时性约束造成困难。WCET主要用来验证硬实时系统中实现任务的软件能否在给定的时间内或给定的时间点之前执行完毕，多数调度算法和可调度性分析算法都需要已知任务的最差执行时间［4］。对于提高嵌入式实时系统软件的可靠性来说，WCET有着非常重要的作用。

文献［5］分析了一个卫星子系统星载软件的静态WCET，其中特别分析了SPARC寄存器窗口机制的时间建模方法，给出了如何在任务的最差执行时间分析中加入窗口上下溢陷阱处理时间。Bound-T［6］是一个静态WCET分析工具，其针对SPARC结构提出了一个建模寄存器窗口的方法，它不仅提供了每个CALL和RESTORE指令可能产生的上溢和下溢，也提供了在每个例程入口点可能用到的寄存器窗口数。但在实际的系统中，寄存器窗口的上下溢次数不仅仅取决于任务程序本身，而且与操作系统和外部中断等因素紧密相关，这些因素的变化增加了最差执行时间分析的复杂性。

本文针对上述问题，通过分析任务的函数调用关系图和系统的中断嵌套关系，有效地找出任务运行期间寄存器窗口上下溢陷阱发生的次数界限，从而为精确地分析任务WCET提供帮助。

1 预备知识

1.1 SPARC的寄存器窗口机制

SPARC体系结构［7］定义了2种类型的寄存器:通用寄存器和控制/状态寄存器。整数单元(IU)的通用寄存器又叫做r寄存器，其个数与具体实现相关，最少为40个(2组)，最多为520个(32组)。这些寄存器进一步分成8个全局寄存器和实现相关的包含16个寄存器的寄存器组，1个寄存器组又分成8个输入寄存器和8个局部寄存器。在某一时刻，用户可以访问8个全局寄存器和1个包含24个寄存器的寄存器窗口，每个寄存器窗口实际包含了8个输入寄存器和8个局部寄存器的寄存器组，以及与相邻窗口的输入寄存器共用的8个输出寄存器。寄存器窗口的结构如图1所示。

SPARC结构的当前寄存器窗口通过当前窗口指针CWP来标识，CWP通过RESTORE或者RETT指令递增，通过SAVE指令或者发生trap递减。窗口的上下溢通过窗口无效标志寄存器WIM来检测。如果嵌套的深度足够，一系列调用后，被调用者可能没有空闲窗口可用，在那种情况下，SAVE指令试图使CWP指向WIM中标记为无效的窗口，寄存器窗口上溢(overflow)陷阱出现，运行的内核trap管理程序负责提供1个新的寄存器窗口给例程。同样，当一系列调用返回时，原来的窗口也可能不可用，RESTORE或RETT指令试图使CWP指向WIM中标记为无效的窗口，这导致了寄存器窗口下溢(underflow)陷阱产生，内核 trap管理程序则进行类似处理。

图1 SPARC寄存器窗口图解［7］

1.2 最差执行时间分析

程序的最差执行时间(WCET)［8］是指在所有可能的情况中，程序在对应的硬件平台上执行时花费的最长时间。相应有程序的最好执行时间(BCET)和平均执行时间(ACET)的概念。WCET给出了某段程序执行的时间上限，评判其分析方法或者工具好坏的2个准则是安全性和精确性:如果分析得到的时间大于程序的实际WCET值，称这种分析结果是“安全(Safe)”的;分析结果越接近实际 WCET 值，称其越“精确(Precision)”［8］，如图2所示。寻找程序的WCET有2种主流的方法:静态分析方法和基于测量的方法，代表性的商业工具有aiT和RapiTime等，在这里不展开阐述。对于任务的最差执行时间可以通过上面任意一种方法或工具获得。

在实际系统中，程序的最坏情况执行时间是很多因素综合作用的结果，影响程序WCET的主要因素有2类:1)是软件特性，包括程序的循环界限、执行路径空间和可行性等;2)是平台特性，流水线、分支预测和寄存器窗口等处理器加速部件及存储器体系结构等［9］。寄存器窗口陷阱属于第2类因素，本文考虑的是其对于任务WCET的影响。

图2 最差执行时间定义

1.3 系统模型

本文研究的系统为实时系统，假定系统采用固定优先级抢占式调度，任务和中断都具有唯一优先级。系统包含多个任务和多级中断时，高优先级任务可以通过抢占低优先级任务优先运行。同时系统允许中断嵌套，即在低优先级中断响应期间，如有高优先级的中断到来，如果此时中断被允许，则系统会响应高优先级的中断，等待高优先级中断处理完毕再返回到低优先级中断处理。所有中断都优先于任务，即任务运行期间，如果有中断到来，则系统会首先响应中断，进行中断处理，完毕后再返回到任务执行。中断可能会唤醒处于睡眠或挂起状态的任务，使其加入到就绪队列，这种情况下，当中断处理结束后，系统将会根据优先级进行重调度。如果中断响应前运行的任务的优先级低于被唤醒的任务的优先级，操作系统将进行任务上下文切换，高优先级任务得到优先运行，其运行完毕后再回到被中断的任务继续运行。

2 上下溢陷阱时间分析

在计算上下溢陷阱数目时有2个问题必须考虑:1)对于上下溢陷阱的处理;2)对于任务上下文切换的处理。SPARC体系结构允许2到32个寄存器窗口，当上下溢陷阱出现时可以选择保存或恢复1个到所有的窗口，当任务上下文切换时也是如此。这样对所有情况的详细讨论将非常复杂，故本文假定的处理策略是:

1)每次上下溢陷阱出现时只保存或恢复1个窗口。

2)每次任务上下文切换时保存所有旧任务的寄存器窗口，而只恢复1个新任务的寄存器窗口，其他窗口通过下溢陷阱恢复。

2.1 问题阐述

通过分析每个任务可能使用的最大寄存器窗口深度和系统中断的嵌套深度来计算最大的上下溢陷阱数目和切换时需要保存的最多寄存器窗口数目。需要说明:

1)优化的叶子函数:分析要先抽取任务函数调用图，其形式可参考图3。图中的子函数4即为优化的叶子函数。叶子函数是程序调用图中的叶结点，即其不再调用任何其他函数。而优化的叶子函数不包含SAVE和RESTORE指令，即其没有独立的寄存器窗口，而是使用其调用者的堆栈结构和寄存器。在计算任务的最大可能调用深度时，需要剔除优化的叶子函数，故计算可得图3中的函数调用深度应为4层(包含任务2自身)，而不应计算为5层。

图3 任务2的函数调用图示例

2)最差路径:任务程序可能沿着不同的路径执行，而最大上下溢陷阱出现的路径并不一定是任务的最差执行时间出现的路径。为了简化分析同时保证分析结果的安全性，假设最大上下溢陷阱出现的路径和任务WCET发生的路径为同一条路径。由于本文的分析与任务的WCET分析是独立进行的，故分析有效，但分析结果会略显悲观，一体化的分析将留做后续工作。

3)任务可用的寄存器窗口数:通常情况下寄存器窗口中有1个窗口是供操作系统使用，同时由于寄存器窗口是环形结构，最后1个窗口与第1个有交叠，所以任务程序实际可用而不发生上溢的寄存器窗口个数比系统的寄存器窗口总数少2个。例如处理器有8个寄存器窗口，则任务程序可以使用的窗口数为6个。不同的操作系统可能会有不同，需要根据具体情况确定，本文设定为上述情况。

4)中断服务程序:发生中断时，将使用1个寄存器窗口，对于单纯中断没有任务切换发生时，假设中断服务程序不再调用子程序而只用1个寄存器窗口。而用户的中断服务程序使用的窗口个数则是与具体应用相关的，发生中断嵌套时亦是如此。

2.2 无任务上下文切换时的界限分析

设上溢陷阱的处理时间为to，下溢陷阱的处理时间为tu，则可得任务的上下溢处理的时间开销为woh=noto+nutu。

2.3 包含任务上下文切换时的界限分析

当有任务切换发生时，切换到新任务将保存被中断任务的所有寄存器窗口，保存的寄存器个数越多，所花费时间越长，最长切换时间出现在任务调用深度最大时。精确地分析需要计算每层调用可能出现的任务切换数，进而确定任务切换时间，一个简单的处理办法是任务切换时间全部取任务调用深度最大时的值。新任务运行完毕后，再次切换回被打断任务将只恢复1个寄存器窗口，其他寄存器窗口的恢复利用下溢陷阱来完成。故被中断的任务恢复运行后每次执行RESTORE指令返回都会发生1次下溢，最差的情况下，下溢处理程序执行完成后再次执行任务切换，则下溢陷阱刚刚恢复的窗口将被保存，再次切换回来后执行RESTORE指令将再次产生下溢。依然采用任务2为例进行说明，如图4所示。

图4 窗口下溢图示

图中子函数2运行过程中，有中断产生并唤醒高优先级的任务1，当中断退出后将切换到任务1执行，任务1执行完毕后再切换回到任务2，从断点继续执行。这种情况下，在子函数2的运行过程中发生了任务切换，此时系统将只有1个可用的寄存器窗口，当子函数2运行到返回指令(RESTORE)时，将发生下溢陷阱，运行下溢陷阱处理程序，极端情况下，在下溢陷阱处理过程中，中断再次到来并伴随高优先级任务1的释放，则此时当下溢陷阱处理结束后，系统将首先响应中断而不会执行子函数2的返回指令。当中断和任务1执行完毕，再次切换回子函数2断点运行返回指令时，由于又进行了任务切换，故将再次发生下溢，在该情况下子函数2在返回过程中发生了2次下溢陷阱。

3 仿真验证

利用开源的LEON3处理器和Modelsim仿真软件来仿真验证我们的方法。LEON3处理器采用了SPARC V8的体系结构，设置寄存器窗口数目为8个，另外系统包含有5个中断，优先级由高到低分别为 TIMER1，EXINT2，EXINT1，UART2 和 UART1，在任务运行时全部使能。前4个中断并不唤醒任务。UART1中断设置为2种情形:一种情形下和其他4种中断一样，没有唤醒任务;另一种情形下如前所述将唤醒高优先级任务，则在中断退出后切换到新的高优先级任务运行，高优先级任务运行结束后再切换回原被中断的任务继续运行。中断 EXINT2、EXINT1、UART2的用户中断处理函数全部不占用单独的寄存器窗口，而中断TIMER1用户中断处理函数调用深度为1，即其将占用1个寄存器窗口。UART1的用户中断处理函数在不进行任务切换时不占用单独的寄存器窗口，当其进行任务切换时则包含有2层调用，即占用2个寄存器窗口。

表1 仿真结果

从表1中可以看出，仿真结果均小于分析结果，这说明分析是安全的。同时也可以看出，对于存在任务切换时窗口上溢的数量比分析结果小得多，说明实际系统中任务与中断并不一定会满足最差情况，另一方面也可能是通过仿真测试也难以覆盖到所有情形，还需要依据具体情况进行分析。对于存在任务切换时窗口下溢的仿真结果与分析结果非常接近，说明分析是精确的。当然这只是提供一种分析的方法，具体应用中还需要根据系统的实际情况设定约束条件以便得到更加精确的结果。

4 结论

研究了采用SPARC体系结构的实时系统的WCET分析中寄存器窗口的溢出的时间开销。提出了系统中存在多级中断嵌套，采用某一溢出陷阱处理策略时，寄存器窗口的溢出陷阱次数界限的计算方法。结果表明，本文的方法可以有效地给出寄存器溢出陷阱的次数界限，但是其分析精度还可根据系统的约束条件进一步提高，后续也将针对其他陷阱处理策略进行分析。

［1］ 杨孟飞，顾斌，郭向英，等.航天嵌入式软件可信保障技术及应用研究［J］.中国科学:技术科学，2015，45(2):198-203.(Yang Mengfei，Gu Bin，Guo Xiangying，et al.Aerospace embedded software dependability guarantee technology and application［J］.Science Sin Tech，2015，45(2):198-203.)

［2］ 王磊，袁利，戴居峰.卫星控制系统时序建模分析方法研究［J］.空间控制技术与应用，2014，40(3):31-35.(Wang Lei，Yuan Li，Dai Jufeng.Timing modeling and analysis method for satellite control system［J］.Aerospace Control and Application，2014，40(3):31-35.)

［3］ Wilhelm R，Engblom J，Ermedahl A，et al.The worstcase execution-time problem-overview of methods and survey of tools［J］.ACM Transactions on Embedded Computing Systems，2008，7(3):1-53.

［4］ Layland L J.Seheduling Algorithms for Multi-Programing in a Hard Real-Time Environment［J］.Journal of ACM，1973，20(1):46-61.

［5］ Garrido J，Zamorano J，Juan A de la Puente.Static Analysis of WCET in a Satellite Software Subsystem［C］.The 13th International Workshop on Worst-Case Execution Time Analysis.Paris，France，OASICS，2013:87-96.

［6］ Bound-T time and stack analyzer reference manual Issue 6.4［Z］.Tidorum Ltd.，2013.

［7］ The SPARC ArchitectureManualVersion 8［Z］.SPARC International Inc.，1992.

［8］ Engblom J，Ermedahl A，Sjödin M，Gustafsson J，Hansson H.Worst-case execution-time analysis for embedded real-time systems［J］.Int J Softw Tools Technol Transfer.2003，4:437-455.

［9］ Lee E A，Seshia S A.Introduction to Embedded Systems-A Cyber-Physical Systems Approach［M］.LeeS-eshia.org，2011.