高速缓存影响的航天器控制软件调度设计方法*

于广良，杨孟飞，姜 宏，徐 建

(1.北京控制工程研究所，北京100190;2.中国空间技术研究院，北京100094)

高速缓存影响的航天器控制软件调度设计方法*

于广良1，杨孟飞2，姜 宏1，徐 建1

(1.北京控制工程研究所，北京100190;2.中国空间技术研究院，北京100094)

针对高速缓存引起的程序执行时间抖动对航天器控制软件任务调度造成的困难，提出一种基于循环调度的调度设计方法，该方法利用任务程序执行时间的概率分布设计具有不同可靠性的系统模式，通过模式切换，使处理器得到充分利用，同时能够提供一定的可靠性保障，为航天器控制软件的任务调度提供参考.

高速缓存;时间分析;调度设计;航天器控制软件

0 引言

目前随着航天器控制系统集成程度的提高和功能性能要求的不断增加，对计算资源的需求也越来越高，控制计算机作为控制系统的核心部件，也向着更为复杂的方向发展.为解决主存储器与处理器(CPU)的速度匹配问题，根据局部性原理，通过速度更快的高速缓存(cache)来提高存储器的访问速度越来越重要.但是对航天器控制系统这种对实时性要求特别高的系统而言，cache的使用增加速度的同时也带来了很高的时间不确定性，造成设计与验证的困难［1］.

Cache对执行时间的影响概括为两方面:一是增大了程序执行时间的抖动;二是增加了抢占导致的时间延迟.文献［2］综述了程序的最差执行时间(worst-case execution time，WCET)分析的方法与工具，其中包含了cache分析的相关内容，吕鸣松等［3］详细综述了WCET分析中的cache分析的方法与进展.关于cache相关的抢占延迟(cache related preemption delay，CRPD)也有着广泛的研究［4-5］.

Cache对姿态和轨道控制系统软件执行时间的影响，在文献［6］中进行了分析，其中指出由于影响cache命中率的因素非常之多，对星载软件实时性能的验证是一个难题.文献［7］设计了一种用于航天器使用的LEON3处理器的性能检测单元，可以用来实时统计cache的命中情况，用于cache的设计与决策.本文结合cache的时间特性对调度设计方法进行研究，提出应对策略，为工程应用提供参考.

1 问题分析

在开源的LEON3处理器平台下分别采用以下几种cache配置，对某航天器控制软件的任务和中断的执行时间进行仿真.

Cache的使能:1)禁止cache;2)在第一次控制周期中断后，将cache中内容锁定，不再更新;3)在每次进入中断时冻结cache，在中断退出后重新使能cache;4)完全使能cache.

Cache的大小:A)指令cache为2组，8kbytes大小，每行32bytes，数据cache为4组，4kbytes大小，每行16bytes;B)指令cache为2组，4kbytes大小，每行32bytes，数据cache为2组，4kbytes大小，每行32bytes.

Cache的替换策略:a)采用伪随机策略;b)采用最近最少使用策略(least-recently-used，LRU).

用Task1表示姿态控制任务，Task2表示遥测遥控任务，Timer表示系统定时器中断，UART表示串口中断.它们的程序规模(指令数)大约为Task1是4 000，Task2是20 000，Timer和UART是300.执行时间仿真结果见表1～2所示.

表1 执行时间的抖动大小比率Tab.1 Ratios of execution time jitters

表2 最差执行时间的相对大小比率Tab.2 Relative ratios of WCETs

表1表示的是执行时间的抖动(任务的执行时间中包含了定时器中断的执行时间)的仿真结果，抖动大小比率的计算公式采用(Ci-Cbi)/Cbi× 100%，其中Cbi为最优执行时间，Ci为最差执行时间.表2表示的是各情况下的最差执行时间与不使能cache的最差执行时间的相对比值.两表中表头的“禁止”、“锁定”、“冻结”、“使能”分别对应情况4+情况A+情况a;“LRU”表示的是情况4+情况A+情况b;“大小”表示的是情况4+情况B+情况b.仿真结果分析如下:

对比表1的“使能”与“禁止”两列，可以看出，使能cache后程序规模较小的中断服务程序的执行时间抖动明显加大，最大抖动已经达两倍以上.究其原因，一方面其程序规模较小，自身执行很难将cache预热;另一方面，其到达的随机性较高，每次到达时处理器状态相差较大，这点从UART中断与Timer中断的对比可以看出，相比于 Timer中断，UART中断到达随机性更高，抖动也更大.使能cache后程序规模较大的任务执行时间抖动很小，是因为循环调度任务间无抢占，而且相对执行顺序固定，减小了对cache的扰动.但不能说明cache对任务程序执行时间影响小，这点从表2的“使能”一列仿真结果可以证明，任务在使能cache后最差执行时间明显减小，已降低到禁止cache时最差执行时间的一半以内.

从两表各自的“锁定”一列结果可以看出，cache内容锁定后，经常不命中会增加惩罚，使执行时间变大.从两表各自的“冻结”一列结果可以看出，采用中断时冻结cache可以减小执行时间的抖动，但是可能增大中断的执行时间.从两表各自的“使能”、“LRU”和“大小”几列的结果对比可得，cache的不同大小和替换策略都会影响执行时间的大小和抖动.

任务执行时间的抖动变大使得最差执行时间与平均执行时间相差变大，由于航天器控制系统多采用最差情况进行调度设计，那么它将导致系统运行时的资源利用率变小.

2 系统模型

2.1 任务模型

采用文献［8］的卫星控制系统时序模型，控制周期T是系统级设计目标，分解为

式中:t1为所有敏感器信息采集和处理时间;t2为控制算法执行时间;t3为所有控制命令发送时间;t4为单个控制周期内所有可能发生的中断时间;t5为空闲时间.为了简化分析过程，忽略了所有的上下文切换和其他非控制任务，但是它们可以用类似的方法加入到分析和设计中.上面各时间还可以进一步分解，将与cache相关的时间提取出来，分别用任务程序模型τ1，τ2和τ3以及中断服务程序模型I1和I2表示.其中τ1代表敏感器信息采集和处理任务程序，τ2代表控制算法实现任务程序，τ3代表控制指令发送任务程序，I1代表偶发性的总线中断服务程序，I2代表周期性的时钟中断服务程序.它们的执行时间是(1)中相对应的时间或者其时间的一部分.

我们定义任务的最差执行时间为所有可能的情况中，任务程序在对应的硬件平台上执行时花费的最长时间.最优情况下的执行时间定义为任务的最优执行时间，平均情况下的执行时间定义为任务的平均执行时间.任务的最差响应时间定义为任务从释放到执行结束的最长时间，其中包含了其他任务或中断的抢占时间.类似的，我们定义中断的最差响应时间为从中断触发到处理结束所需要的最长时间.

特别的，抢占可能会将对任务或中断服务程序有用的高速缓存块驱逐出高速缓存，导致重新运行任务或中断服务程序时这些高速缓存块需要从内存中重新加载，这段重新填充cache中被驱逐的存储块所需的额外时间称为cache相关的抢占延迟［5］.

2.2 调度模型

航天器控制系统的周期性任务调度经常采用循环调度(cyclic executive，CE)［9］.调度决策是静态的，离线计算好之后保存在表格之中.以控制周期为主周期被反复执行.控制周期内再分为许多小时间段，称为帧或次周期.每个帧有一个在其内部执行的任务列表，帧的起始由时钟中断触发，并在中断服务程序中释放帧内各个任务依次执行，下一帧的起始时刻作为本帧的结束时刻，它也是本帧内任务的相对截止时间限.本文任务模型采用循环调度如图1所示.

假定控制计算机使用单处理器，使用下述符号定义:控制周期记为T，也是各控制任务的周期.中断I1的最小到达时间间隔记为TI1，中断I2的周期记为TI2.中断I1的优先级高于中断I2.我们使用下标τ或I来区分任务和中断.定义任务τi的最差执行时间为Cτi，最优执行时间为Cbτi，平均执行时间为Caτi，相对截止时间限为Dτi，最差响应时间为Rτi.定义时钟滴答为tc(两次时钟中断的最小时间间隔)，帧长度是整数倍时钟滴答的时间，各任务的帧长度定义为qi.定义任务τi执行期间任务τj对其抢占造成的CRPD为γτi，τj，中断Ij对其抢占造成的CRPD为 γτi，Ij.

图1 循环调度策略示意图Fig.1 Example of CE

3 时间分析

固定优先级抢占式调度下，任务τi最差响应时间的计算使用如下公式［10］:

其中·为向上取整运算，hp(i)为优先级高于i的任务，上面等式一般通过迭代求解，直到收敛或响应时间超过截止时间限()为止，上标n为迭代次数.

式(2)中，没有考虑高优先级任务嵌套抢占时对低优先级任务造成的间接影响.例如优先级低于τj但高于τi的任务也会被τj抢占，抢占后同样产生CRPD，进而对τi响应时间有间接影响.文献［11］采用了γsum代表由于τj抢占造成的总的抢占延迟.改进的τi最差响应时间计算公式如下:

关于γ的计算可以参考相关文献［4-5，10-11］，本文不展开讨论.利用上述公式，可以推导出本文所述模型的响应时间计算公式.

为了保证中断不丢失数据，一般要求同一中断的处理时间要小于其最小到达时间间隔，即RIi＜TIi.对中断进行时间分析时，重点需要考虑的是中断嵌套情况［12］.在本文中，由于中断I1的优先级大于中断I2，故中断I2在执行过程中可能被I1抢占，系统禁止 cache时，两个中断的最差响应时间分别为:

系统使能 cache时，如果选择在中断时冻结cache，有利于减小中断的执行时间抖动同时避免CRPD，但中断的最差执行时间可能比禁止cache时更长，两个中断的最差响应时间分别为

系统在任何时候cache都使能，则中断1抢占中断2后，将伴随有CRPD产生，在时间分析时需要考虑在内，两个中断的最差响应时间分别为

任务程序最差响应时间的计算应该考虑中断的抢占，禁止cache时，任务的最差响应时间为

使能cache，但是在中断时冻结cache，任务的最差响应时间为

始终使能cache，需要考虑中断抢占任务程序后带来的CRPD，任务的最差响应时间为

任务必须满足可调度性要求，即它每次释放的实例都能在截止时间限之前完成，有Rτi≤Dτi.在设计循环调度的调度表时，分配给各个任务的帧长度应该大于等于任务的最差响应时间.由于任务由时钟中断释放，故帧的长度与时钟滴答是整数倍关系，则任务τi的帧长度应设计为.这样由(1)可得，控制周期为

4 调度设计

任务对资源的需求体现为对CPU时间的竞争.本文模型在一个控制周期T内有3个控制任务，用ci表示任务τi的实际执行时间，则系统运行时，任务τi的资源需求可用其实际的利用率Ui=ci/T来度量.令则所有任务总的利用率为U= c/T.

任务的执行时间满足 Cbi≤ci≤Ci，令 cLB=可得任务总的执行时间满足关系cLB≤c≤cUB.任务必须满足可调度的要求，这便要求最差情况下，任务总的利用率必须小于某一上限，即cUB/T≤UUB≤1，则有:

可见，任务的实际执行时间与最差执行时间差距越大，系统的利用率越低.如第1节所述，使能cache后，最差情况与平均情况相差较大.如果按照最差情况设计任务调度，那么系统在大部分时间资源利用率很低.如果以平均情况设计任务调度，可以提高资源利用率，但是可能有任务超时.综合这两种情况，我们利用任务执行时间的概率分布(可以通过统计或分析的方法得到)，设计具有不同资源利用率和可靠性的系统模式，用于调度选择.

由于系统没有按照最差情况进行设计，那么必须应对可能发生的任务超时，通过设计系统的模式切换来实现.例如设计两种模式，第一种模式下，采用最差情况(Cτi)进行设计，有概率δτi=1;第二种模式下，采用平均情况(Caτi)进行设计，有概率δτi＜1.首先令系统运行在第二种模式下，如果有任务超时，则进行模式切换，切换到第一种模式.若任务一直运行在平均情况以内，将持续处于第二种模式，从而提高了资源利用率.

举例说明所述方法，假设系统中cache始终使能，任务和中断的时间参数如表3所示，单位为处理器的指令周期数×104，tc=TI2.

表3 系统的任务和中断参数Tab.3 Task and interrupt parameters of the system

利用式(6)和式(9)计算得到任务和中断的最差响应时间，然后利用式(10)计算得到帧大小和控制周期大小.注意对于CRPD的计算，我们忽略了间接的抢占延迟，采用了式(2).

表4 时间计算结果Tab.4 Time calculation results

利用表4中的q1和q0.95可以计算得到第一种模式下，控制周期，任务不发生超时的概率P1=100%;第二种模式下，控制周期，任务不发生超时的概率为P2≥0.953×100%≥85.74%.假设满足控制精度要求的控制周期范围是 T=0.1 s～0.15 s，那么令T2=Tmin=0.1 s，可以求得所需CPU的主频为f=8 MHz，在此主频下，第一种模式下的控制周期 T1=(1.05×106)/(8×106)s= 0.131 25 s＜0.15 s，满足设计要求.第二种模式和第一种模式相比，CPU利用率提高了(U2-U1)/U1=(T1-T2)/T2=31.25%.

5 结论

本文给出了一种高速缓存影响的航天器控制软件任务调度设计方法.该方法基于循环调度策略，利用任务程序执行时间的概率分布，设计具有不同可靠性的系统模式，在保证系统较高资源利用率的同时，提供一定的可靠性保障.

［1］杨孟飞，顾斌，郭向英，等.航天嵌入式软件可信保障技术及应用研究［J］.中国科学:技术科学，2015，45 (2):198-203.YANG M F，GU B，GUO X Y，et al.Aerospace embedded software dependability guarantee technology and application［J］.Sci Sin Tech，2015，45(1):198-203.

［2］WILHELM R，ENGBLOM J，ERMEDAHL A，et al.The worst-case execution-time problem-overview of methods and survey of tools［J］.ACM Transactions on Embedded Computing Systems，2008，7(3):1-53.

［3］吕鸣松，关楠，王义.面向WCET估计的Cache分析研究综述［J］.软件学报，2014，25(2):179-199.LYU M S，GUAN N，WANG Y.Survey of cache analysis for worst-case execution time estimation［J］.Journal of Software，2014，25(2):179-199.

［4］LEE C G，HAHN J，SE Y M，et al.Analysis of cacherelated preemption delay in fixed-priority preemptive scheduling［J］.IEEE Transactions on Computers，1998，47(6):700-713.

［5］ALTMEYER S，DAVIS，R I，MAIZA C.Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems［J］.Real-Time System，2012，48:499-526.

［6］BERNAT G，COLIN A，ESTEVES J，et al.Considerations on the LEON cache effects on the timing analysis of on-board applications［C］//Proceedings of the Data Systems in Aerospace Conference，2008.

［7］GUZMÁN D，PRIETO M，SÁNCHEZ S，ALMENA J.Improving the LEON spacecraft computer processor for real-time performance analysis［J］.Journal of Spacecraft and Rockets，2011，48(4):671-678

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

［9］BAKER T P，SHAW A.The cyclic executive model and ada［C］//IEEE Real-Time Systems Symposium.New Yrok:IEEE，1988.

［10］BUSQUETS-MATAIX J V，SERRANO J J，ORS R，et al.Adding instruction cahe effect to schedulability anal-ysis of preemptive real-time systems［C］//Proceedings of the IEEE Real-Time Technology and Applications Symposium.New York:IEEE，1996.

［11］STASCHULAT J，SCHLIECKER S，ERNST R.Scheduling analysis of real-time systems with precise modeling of cache related preemption delay［C］//Proceedings of the 17thEuromicro Conference on Real-Time Systems.Palma de Mallorca，Spain，2005.

［12］于广良，杨孟飞，徐建，姜宏.面向多级中断系统的任务最差响应时间分析［J］.中国空间科学技术，2016，36(2):28-36.YU G L，YANG M F，XU J，et al.Worst case response time analysis of multilevel interrupt systems［J］.Chinese Space Science and Technology，2016，36(2):28-36.

Scheduling Design Method for Spacecraft Control Software with Cache

YU Guangliang1，YANG Mengfei2，JIANG Hong1，XU Jian1
(1.Beijing Institute of Control Engineering，Beijing 100190，China; 2.China Academy of Space Technology，Beijing 100094，China)

The task scheduling of spacecraft control software becomes more difficult due to the execution time jitter caused by cache.To deal with this problem，a scheduling design method is proposed based on cyclic executive.The probability distributions of execution times are used to design different system modes with different reliability.Through the mode changes，the processor can be sufficiently utilized and a certain extent degree of reliability is guaranteed.The proposed method can provide useful reference for the task scheduling of spacecraft control software.

cache;timing analysis;scheduling design;spacecraft control software

TP31

A

1674-1579(2017)01-0055-06

10.3969/j.issn.1674-1579.2017.01.009

于广良(1986—)，男，工程师，研究方向为航天嵌入式系统可信软件;杨孟飞(1962—)，男，研究员，研究方向为空间飞行器总体设计、控制系统和控制计算机;姜 宏(1975—)，男，工程师，研究方向为航天器控制计算机的软硬件协同设计;徐 建(1987—)，男，工程师，研究方向为高可信操作系统.

*国家自然科学基金资助项目(91118007).

2016-04-10