软件学报  2018, Vol. 29 Issue (6): 1681-1698   PDF    
考虑中断和上下文切换开销的响应时间分析
于广良1, 杨孟飞2     
1. 北京控制工程研究所, 北京 100190;
2. 中国空间技术研究院, 北京 100094
摘要: 实时嵌入式系统多采用中断和上下文切换实现多任务间调度,在对此类系统进行可调度性分析时,在任务的最差响应时间计算中必须包含中断和上下文切换开销.现有包含这些开销的方法是将中断作为高优先级任务,同时将上下文切换开销加入到任务最差执行时间中进行分析,然而这些方法过于粗略,缺乏对实际系统细节的考虑,计算得到的最差响应时间并不精确.首先,对中断和上下文切换的机制和时间流程进行详细的阐述,进而分析中断和上下文切换对任务关键性时刻的影响;接着,给出包含上述开销的更加精确的响应时间计算方法;最后进行仿真验证.扩展了包含系统调度开销的响应时间计算方法,可用于资源受限的硬实时系统中需要精确计算响应时间的场合.
关键词: 实时系统     嵌入式系统     可调度性     最差响应时间     中断     上下文切换    
Response Time Analysis of Embedded Systems by Taking Interrupt and Context Switch Overheads into Account
YU Guang-Liang1, YANG Meng-Fei2     
1. Beijing Institute of Control Engineering, Beijing 100190, China;
2. China Academy of Space Technology, Beijing 100094, China
Foundation item: National Natural Science Foundation of China (91118007, 61502031, 61632005)
Abstract: Interrupt and context switch are basic mechanisms for multi-task scheduling in real-time and embedded systems. During schedulability analysis, the overheads of the interrupt and context switch should be considered in the calculation of tasks' worst-case response time. The current calculation methods of response time add interrupt as task with high priority, and simply add the overheads of context switch in the meantime. However, these methods neglect the details of practical systems and roughly give an inaccurate worst-case response time. In this paper, the mechanisms and time flow of interrupt and context switch are thoroughly described. In addition, their influence on tasks' critical instant is discussed. More importantly, a much more accurate calculation method for response time is presented. At last, simulations is conducted to validate the improvement in accuracy of this new method. The response time analysis accounting for scheduling overheads is extended in this paper for the resource-constrained hard real-time systems which need to accurately calculate the response time.
Key words: real-time systems     embedded systems     schedulability     worst-case response time     interrupt     context switch    

硬实时系统(hard real-time systems)是对时间要求最苛刻的实时系统, 任务一次错过截止时间便会导致整个系统的错误, 甚至发生灾难性的事情[1].这种系统一般使用嵌入式硬件系统实现, 其上运行嵌入式实时操作系统(real-time operating system, 简称RTOS)对任务进行调度.在系统设计时, 为保证可信性[2], 通常要对系统中的任务进行可调度性分析, 以确保所有任务都能够在截止时间之前完成.判断系统的可调度性通常使用可调度性测试(schedulability test).

响应时间分析(response time analysis, 简称RTA)是最常用的可调度性测试之一, 它通过计算任务最差响应时间(worst-case response time, 简称WCRT), 与任务截止时间相比较, 判断系统任务的可调度性.响应时间分析由Joseph和Pandya[3]在1986年及Audsley等人[4]在1993年给出, 得到了学术界广泛的研究和工业界的应用.利用这种方法对实际嵌入式系统进行分析时, 还应考虑系统的中断和任务间调度引起的上下文切换开销.虽然这些开销与任务最差执行时间(worst-case execution time, 简称WCET)相比要小得多, 然而对其研究仍有理论和现实意义, 如:

1)   在任务最差响应时间的计算公式中, 抢占次数的计算采用向上取整运算, 这意味着低优先级任务的执行被很小时间的延迟就足以导致高优先级任务更多的抢占, 从而引起WCRT的大幅增长;

2)   在其他方面, 如WCET的估计精度难以进一步提升时, 对这些开销的估计显得同样重要;

3)   对系统细节的分析, 可以增强响应时间分析在实际系统中应用的信心.

目前已有一些尝试在响应时间分析中包含上述开销的研究, 综述如下.

●  中断的研究

Regehr[5]详细讨论了实时嵌入式软件里的中断, 并指出需要验证系统内中断过载问题.Brylow和Palsberg[6]分析了使用汇编语言编写的中断驱动程序, 提出了检查每个中断是否都能在截止时间前处理完成的方法. Jonathan等人[7]利用上下文切换次数界限和基本路径来减小需搜索的路径空间, 将中断驱动程序转化为顺序程序进行分析, 以得出主程序在多个中断服务程序影响下的最差执行时间.他们的转化过程需考虑较多路径, 故分析的复杂性较高.Leyva-del-Foyo等人[8]提出了将任务与中断管理进行集成, 定义统一的优先级空间进行调度. Jeffay等人[9]设计了解决动态优先级系统里包含中断处理开销的可调度性分析问题的方法, 并且简单讨论了静态优先级系统的情况.Sandstr m等人[10]讨论了用于汽车系统运动控制的实时系统开发时遇到的静态调度与中断集成的问题, 提出可以将中断当作高优先级的任务对待.Brandenburg等人[11]综述了多处理器实时系统的中断开销计算方法, 包含了对单处理器系统的讨论.他们总结了3种包含中断服务程序的方法:以时间片为中心的包含方法、以任务为中心的包含方法和以处理器为中心的包含方法.另外, 有相关的工作研究了具体的RTOS中的开销, 如文献[12, 13].在上述研究中, 中断服务程序多基于简单模型, 对实际系统中中断与任务的关系缺乏讨论.

●  上下文切换开销的研究

Katcher等人[14]扩展了固定优先级调度下的内核开销计算方法.随后, Burns等人[15]针对时钟调度(tick scheduling), 分析了调度器的开销和任务从延时队列移动到运行队列花费的时间开销, 建立了实时系统调度器更为精确的模型.Gabriëls等人[16]综述了包含时钟中断和上下文切换开销的相关技术.另一方面, Echagüe等人[17]提出了用于离线计算周期性任务在采用最优静态和动态优先级分配策略的调度器下准确抢占次数的模型.Yomsi等人[18]通过在分析中考虑每个抢占自身的开销, 改进了Echagüe等人的模型.他们指出:如果考虑抢占开销, 关键性时刻(critical instant)[19]并不出现在所有任务一齐释放时.然而, 他们在其后计算中仍采用了任务一齐释放的假设, 在本文第3.3节将证明这是不安全的.上述研究中, 文献[14-16]主要讨论的是抢占造成的开销、基于上下文切换与时钟中断的简单模型, 文献[17, 18]讨论的是抢占次数的计算问题.在计算中, 都采用任务同时释放的假设, 没有考虑任务间的释放偏移.

综上所述, 对于响应时间分析中包含中断和上下文切换等时间开销的研究, 存在两方面不足.一是对中断与任务的关联(如任务由中断释放)情况缺乏讨论; 二是在计算中多采用任务同时释放的假设, 没有考虑任务间释放偏移.针对这些不足, 本文的主要工作如下:提出任务由中断释放时, 如何在其响应时间计算里包含系统中的中断开销; 指出了包含上下文切换开销时, 任务间释放偏移对任务的关键性时刻的影响; 给出了一种比现有方法更加精确的包含上下文切换开销的响应时间计算方法; 仿真了真实的软硬件环境下包含中断开销的任务最差响应时间, 并对遇到的实际问题提出解决办法.

本文第1节对实时嵌入式系统中的中断和上下文切换机制进行详细的讨论.第2节给出系统软件模型并对已有的响应时间计算方法进行简单回顾.第3节详细讨论中断和上下文切换开销对于关键性时刻的影响.第4节提出一种包含上下文切换开销的任务最差响应时间计算方法.第5节进行仿真分析.最后, 第6节总结全文, 并指出后续研究方向.

1 概述 1.1 中断

一般来说, 处理器的异常包含了中断、陷阱、故障和终止.陷阱、故障和终止通常是同步发生的, 是执行当前指令的结果; 中断通常是异步发生的, 是来自处理器外部的I/O设备的信号的结果[20].一个典型的中断处理时间流程如图 1所示.

Fig. 1 Timeline of interrupt handling 图 1 中断处理时间流程

任务程序在t0时刻开始执行, t1时刻中断信号产生, t2时刻处理器开始响应中断, 此时, 处理器将继续完成正在执行的指令(有些处理器可能允许中断长指令), 完成断点保存并跳转到中断向量表处, 以上部分由处理器自动完成.从t3时刻起, 执行中断向量表中指令并分支到相应的中断服务程序, 开始任务上下文的保存等, 从t4时刻到t5时刻为用户编写的中断服务程序的执行时间, 到t6时刻恢复了被中断任务的上下文, 中断服务程序处理完成, 任务程序继续执行到t7时刻结束.

为了使系统快速响应紧急事件, 经常允许中断嵌套, 以减小高优先级中断的响应时间, 中断嵌套的典型处理流程如图 2所示.

Fig. 2 Timeline of interrupt nested 图 2 中断嵌套时间流程

处理器刚进入中断时, 往往会自动关闭中断以保证对断点的处理不被打扰.在进入用户中断服务程序前, 可以打开高优先级中断以加快其响应.此时若有高优先级中断请求, 系统将再次跳转到高优先级中断执行, 执行完毕后返回到低优先级中断, 低优先级中断继续执行, 在返回任务前关中断, 返回后处理器将自动打开中断(不同处理器处理流程或有差异).

中断通常是处理一些关键和紧急的情况, 由于优先级高于任务, 其处理时间应当越短越好, 尽可能把更多的处理向后推迟, 以减少对高优先级任务的干扰.某些时候, 在用户中断服务程序中仅仅发布信号或者缓存数据(上半部), 然后将更多的处理操作放到任务中完成(下半部).这样, 中断可能使得某个比被中断的任务优先级更高的任务进入就绪态, 则在中断服务程序结束后将进行任务切换, 运行更高优先级的任务, 使用符号γi, j来表示这种情况下中断下半部处理的时间开销, 如图 3所示.这种情况下的中断处理时间流程如图 4所示.

Fig. 3 Task released by interrupt and causes preemption 图 3 中断上下部模型

图 4图 1的时间流程有所不同, 在t5~t6时间段里, 服务程序检测到有比当前任务更高优先级的任务就绪, 将进行任务切换, 中断返回后高优先级任务得到执行, 当其执行结束后, 由系统调用切换到内核恢复先前被中断的任务继续执行.

Fig. 4 Timeline of interrupt handler and context switches 图 4 中断上下部时间流程

事实上, 这也是中断释放任务的典型处理过程.系统中的周期性任务通常通过系统的时钟中断来释放, 例如:图 4的中断若为系统的时钟中断, 则其在某设定的时间点被触发(即任务到达), 到达的任务在中断服务程序中被释放, 中断返回后开始执行.其他形式的中断释放任务的情况与此类似.这种情况下, 系统中的其他中断与释放某任务的中断可能形成嵌套, 造成某任务释放延迟, 在任务最差响应时间分析中需要考虑.

1.2 上下文切换

操作系统内核使用一种称为上下文切换(context switch)的较高层形式的控制流来实现多任务, 内核为每个任务维持一个上下文.上下文就是内核重新启动一个被抢占的任务所需的状态, 它由一些对象的值组成, 这些对象包括通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构等[20].上下文切换就是CPU从一个任务切换到另一个任务, 它的产生有很多原因, 可能是任务被抢占或任务用尽了自己的时间片等.上下文切换包括了保存旧的状态和恢复新的状态.通常情况下, CPU拥有的寄存器越多, 切换带来的开销就越大.由于抢占导致的上下文切换的实例如图 5所示.

Fig. 5 Example of context switch between tasks caused by preemption 图 5 抢占导致的上下文切换示意图

τ表示任务, 在任务τi执行过程中, 高优先级的任务tj被释放, 则系统调度器将执行上下文切换, 首先保存任务τi的状态信息, 以便后面恢复; 然后加载任务tj的状态信息, 切换到τj运行, 等其运行完毕后, 调度器将重新恢复任务ti的状态信息, 令其从断点处继续运行, 好像没有被打断一样.

任务的到达和释放一般是通过某些事件来触发的, 对于周期性任务而言, 可能是系统定时器的定时结束, 也可能是某个外部周期性信号的触发, 如果任务τj是通过中断释放的, 那么它的时间处理流程可能如图 4所示.图 5中的时间区间t1~t2相当于图 4中的t2~t6, 其中包含了中断的处理时间和上下文切换的时间; 图 5中的时间区间t3~t4相当于图 4中的t7~t8, 其中包含了上下文切换的时间.

图 5中的t1~t2t3~t4分别代表了从ti切换到τj和从τj切换回τi所用的时间.通常情况下, 这两部分时间是不相同的, 若τj是新释放任务, 则前一部分包含了τj的释放时间(任务创建或任务加入就绪队列的时间).进一步, 如果τj由中断释放, 那么由图 4看出, 前部分时间还同时包含了中断的处理执行时间.为了简化分析, 本文用tsw代表切换开销的最大值, 即图 5中的t1~t2t3~t4两者中切换代码WCET的较大者.如果是中断释放的任务, 如图 4所示情况, 那么将前一段时间分为中断的WCET记为Ctick和切换代码的WCET两部分, 其中, 中断的WCET指的是没有任务切换时中断服务程序执行花费的最长时间, 剩下部分的最大值作为切换时间.

2 软件模型

实时嵌入式系统通常包含多个完成特定工作的任务(task).每个任务包含一系列(无穷多个)的实例(task instance), 任务释放执行的每个实例称为一次作业(job).根据实例的到达时间特性不同, 可以将任务分为周期性任务(periodic task)、偶发性任务(sporadic task)和非周期性任务(aperiodic task)[21]:周期性任务实例的到达有固定的周期; 偶发性任务实例的到达没有固定的周期, 但是有最小到达时间(minimal inter-arrival time)间隔的限制, 在最坏情况下可以作为周期性任务对待; 非周期性任务可能随时到达, 没有最小到达时间间隔的限制.固定优先级抢占式调度是实时系统里经常采用的调度, 无论何时, 系统中只要有更高优先级的任务就绪, 便可以抢占当前运行的任务得到运行.当有多个任务就绪, 调度器会选择最高优先级的任务运行.

假设一个包含n个任务的周期性任务集τ=(τ1, τ2, …, τn), 运行在采用固定优先级抢占式调度的单处理器上, 任务优先级按照下标顺序从高到低排列(i从1到n), n是最低优先级.每个任务τi表示为四元组〈Ci, Di, Ti, Ji〉, 其中, Ci为任务的最差执行时间, Di为任务的相对截止时间, Ti为任务的周期或最小到达时间间隔, Ji为任务的释放抖动.

到达时间$a_{i}^{j} $表示任务τi的第j个实例的到达时刻, 那么任务的下一个实例最早在Ti时刻后到达, 有:

$ a_{i}^{j+1}\ge a_{i}^{j}+{{T}_{i}}. $

由于系统的调度器只在某些特定的时间点才会被调用, 任务实例到达后可能不会立刻被释放到就绪队列,

任务的释放时间$r_{i}^{j} $与到达时间$ a_{i}^{j}$之间的最大时间延迟为Ji, 有:

$ r_{i}^{j}\le a_{i}^{j}+{{J}_{i}}. $

$f_{i}^{j} $表示任务τi的第j个实例完成执行的时刻, 则τi的所有作业从释放到完成执行的最大时间间隔即为任务τi的最差响应时间Ri, 有:

$ {R_i} = \mathop {\max }\limits_j {\mkern 1mu} \{ f_i^j - r_i^j\} . $

任务τi的第j个实例的截止时间$ d_{i}^{j}$是相对于其到达时间的, 有:

$ d_{i}^{j}=a_{i}^{j}+{{D}_{i}}. $

一个任务τi称为可调度的(schedulable), 如果它的每个作业都能在截止时间之前完成, 有:

$ {R_i} \le {D_i} - {J_i} \Leftrightarrow {\tau _i}\;\;\;{\rm{schedulable}}{\rm{.}} $

任务集τ称为可调度的, 如果其中的每个任务τiτ都是可调度的.

若一个任务τi的截止时间满足Di=Ti, 称τi为隐含截止时间的任务; 若DiTi, 称τi为受限截止时间的任务; 若Di > Ti, 称τi为任意截止时间的任务.

本文假设任务含有受限截止时间, 任务之间没有相互依赖关系, 定义任务的上下文切换最大时间开销为tsw.同时假定系统中包含有m个中断I=(I1, I2, …, Im), 中断的优先级高于任务, 中断的参数定义与任务类似, 采用与任务类似的符号[22].周期性中断(如定时器中断)的触发有固定的周期, 而非周期性中断(如总线通信中断)没有固定的周期, 但其到达通常有一个最小的时间间隔[7, 21], 故最坏情况下, 可当作周期性中断处理.

定义1(关键性时刻)[19].任务τi的关键性时刻定义为任务τi与所有高优先级任务一齐释放的时刻.接着任务τi将经历最长的可能延迟, 即它的最差响应时间.

对固定优先级抢占式调度的响应时间分析[3, 4], 使用下面公式:

$ {R_i} = {C_i} + \sum\limits_{\forall j \in hp(i)} {\left( {\left\lceil {\frac{{{R_i} + {J_j}}}{{{T_j}}}} \right\rceil {C_j}} \right)} $ (1)

其中, $\left\lceil \cdot \right\rceil $为向上取整运算, 代表任务τi的响应期间被任务tj抢占的最大次数; Ci为任务τi的最差执行时间; Jj为高优先级任务τj的释放抖动; Cj为其最差执行时间; Tj为其周期, hp(i)代表优先级高于tj的任务.

我们在文献[22]中进行过分析, 考虑系统中断时, 某任务τi的响应时间为

$ {R_i} = {C_i} + \sum\limits_{m < j < i} {\left( {\left\lceil {\frac{{{R_i} + {J_j}}}{{{T_j}}}} \right\rceil {C_j}} \right)} + \sum\limits_{1 \le j \le m} {\left( {\left\lceil {\frac{{{R_i} + {J_j}}}{{{T_j}}}} \right\rceil {C_j}} \right)} $ (2)

由于中断优先级大于任务, 用下标1到m表示中断, m+1到m+n表示任务, 等式右边第2部分为优先级大于i的任务对其抢占所占用的时间, 第3部分为所有中断对其抢占所占用的时间.公式(2)迭代到其响应时间不再变化或者超过截止时间为止, 得到在中断与任务嵌套下的任务的最差响应时间.

3 关键性时刻 3.1 释放抖动

如第2节所述, 目前大部分的文献使用如下公式计算任务的最差响应时间.

$~{{R}_{i}}={{C}_{i}}+\sum\limits_{\forall j\in hp(i)}{\left( \left\lceil \frac{{{R}_{i}}+{{J}_{j}}}{{{T}_{j}}} \right\rceil {{C}_{j}} \right)} $, 判定条件为RiDi-Ji$ \Leftrightarrow $τi schedulable.

上述迭代公式中并没有包含任务τi的释放抖动Ji, 而是将截止时间减去释放抖动作为判定条件.这意味着Ji并没有参与迭代.在实际系统中, 并不一定是这种情况.

嵌入式实时操作系统一般有4种相关操作:开中断、关中断、开调度、关调度.其关系为:

●  开中断时, 允许响应中断请求, 此时若开调度, 则允许任务调度; 若关调度, 则不允许任务调度.

●  关中断时, 不允许响应中断请求和任务调度.

下面分几种情况进行讨论.

●  情况1:在区间Ji内关中断或者关调度, 则没有高优先级任务能够在Ji区间内释放, 如果有高优先级任务τjJi区间到达, 则其释放将延后, 直到开中断且开调度为止, 这段延后时间可以使用任务τj的释放抖动Jj来建模, 公式适用.

●  情况2:在区间Ji内如果开中断且开调度, 则可能有高优先级任务在此期间释放, 此时可以将Ri定义为从任务到达到完成执行的最大时间间隔, 上述公式修改为

$ ~{{R}_{i}}={{C}_{i}}+{{J}_{i}}+\sum\limits_{\forall j\in hp(i)}{\left( \left\lceil \frac{{{R}_{i}}+{{J}_{j}}}{{{T}_{j}}} \right\rceil {{C}_{j}} \right)}$, 判定条件为RiDi$ \Leftrightarrow $τi schedulable.

●  情况3:对于中断而言, 由于中断的优先级高于任务, 且中断到达即被释放, 故在区间Ji内无论开关中断, 计算中断开销时, 都应将Ji进行迭代(注意:关中断不能当作中断Ij的释放抖动Jj来建模, 由于中断已释放, 故应当作其阻塞时间.在文献[22]中有详细说明).将中断作为高优先级任务, 单列出来, 计算公式修改为

$ ~{{R}_{i}}={{C}_{i}}+{{J}_{i}}+\sum\limits_{m <j <i}{\left( \left\lceil \frac{{{R}_{i}}+{{J}_{j}}}{{{T}_{j}}} \right\rceil {{C}_{j}} \right)}+\sum\limits_{1\le j\le m}{\left( \left\lceil \frac{{{R}_{i}}+{{J}_{j}}}{{{T}_{j}}} \right\rceil {{C}_{j}} \right)}, 判定条件为 {{R}_{i}}\le {{D}_{i}}\Leftrightarrow {{\tau }_{i}}\ \ \text{schedulable} $ (3)

情况3将在下节进行详细的讨论, 情况1、情况2类似, 不再赘述.

3.2 中断

本节考虑任务由系统时钟中断释放时的情形, 其时间流程可以参考图 4里的t1~t7区间, 其中:t1时刻任务到达, t6时刻任务释放, t1~t6即为任务的释放抖动.由上节讨论可知:这种情况下, 在任务最差响应时间里包含中断开销时, 需考虑系统中其他中断与时钟中断之间的关系.在文献[11]中, 作者讨论了类似的问题, 但是它们的研究对象是多处理器中不同的用于任务释放的中断服务程序.

如果关中断或者其他中断的优先级低于时钟中断的优先级, 那么其他中断在时钟中断运行期间到达, 则会被延迟到时钟中断返回, 开中断后它们会立刻抢占新释放的任务得到执行; 如果开中断且其他中断的优先级高于时钟中断, 那么它们到达后会立刻抢占时钟中断得到运行, 此时相当于增加了任务的释放抖动.无论哪种情况, 都会对任务造成延迟.可见:任务与中断同时释放并不一定是其关键性时刻, 需要将释放任务的时钟中断考虑在内.需要说明的是:由于中断的到达和释放之间的间隔非常短暂, 所以在分析中忽略了这个时间, 认为中断到达即释放.

图 6所示, 假定时钟中断的释放时刻和任务的到达时刻为同一时刻, 任务的截止时间为下一个时钟中断的起始时刻, 则相对截止时间等于相邻两时钟中断起始时刻之间的时间间隔.要验证任务能否在截止时间之前完成, 需要计算出从任务到达到任务完成所需要的最长时间与相对截止时间比较得出.由此, 在分析时, 认为任务的响应时间Ri为从任务τi到达到完成之间的时间, 即包括了任务的释放抖动Ji.

Fig. 6 Critical instant including the interrupt overhead 图 6 包含中断开销时任务的关键性时刻

定理1(任务在中断抢占下的关键性时刻).任务在中断抢占下的关键性时刻出现在用于释放此任务的中断与其他中断一齐释放的时刻, 在此之后, 其他中断以其周期或最小到达时间间隔到来, 任务τi将经历最长的可能延迟.

证明:假定任务τi由系统的时钟中断释放, 如图 6所示, 由公式(2)易得, 其他中断的周期越小, 对τi可能造成的抢占次数越多, 故其他中断应以其周期或最小到达时间间隔到来.假定中断Ij的释放时刻与时钟中断的释放时刻间有Oj大小的偏移, 则:

●  单个中断:若Oj≥0, 如图中情况(a), 易得Oj越小, Ij可能的抢占次数越多.故Oj=0时, Ij的干扰最大.若Oj≤0, 如图中情况(b)所示, 随着Oj的减小, Ri随之减小, Ij的左移并不能导致更多的抢占.故Oj=0时, Ij的干扰最大.可得, Oj=0为关键性时刻;

●  两个中断:考虑IkIj, 假定二者并无依赖关系, 若Oj≥0且Ok≥0, 如图中情况(a), 可固定Ik分析Ij或者固定Ij分析Ik, 与单个中断分析情况相同, 易得Ok=Oj=0时, 中断IkIj的干扰最大; 若Oj≥0且Ok < 0, 则Ij为情况(a), Ik为情况(b), , 亦可固定其一分析其二, 结论不变, Ok≥0且Oj < 0情况类似; 若Ok < 0且Oj < 0, 二者如图中情况(b), 固定Ij分析Ik, 此时, 假设将τi的到达时刻移动到Oj处, 可得Ok=Oj时, 等价的响应时间$ {{{R}'}_{i}}$获得最大, 而实际响应时间$ {{R}_{i}} <{{{R}'}_{i}}$, 故Ok=Oj=0干扰最大, 可得, Ok=Oj=0为关键性时刻.

综上可得, 对于任意数量的中断, 有类似结论成立, 定理得证.

在计算任务τi在中断抢占下的最差响应时间时, 可以使用公式(3), 其中Ji=Ctick+tsw.

3.3 上下文切换

固定优先级抢占式调度下切换开销的简单考虑方法是在每个任务最差执行时间里加入两次上下文切换开销, 即Cj+2tsw.若在高优先级任务抢占低优先级任务得到运行的过程中, 有中间优先级的任务释放, 则在高优先级任务运行完毕, 并不会恢复低优先级任务, 而是切换到中间优先级任务运行, 切换开销将减少1次, 如图 7所示.

Fig. 7 Preemption with scheduling overheads 图 7 包含任务调度开销的抢占

将中断处理的开销Ctick剔除, 并将图 5中的t1~t2中包含的切换开销最大值定义为$ t_{sw}^{1}$, t3~t4中包含的切换开销最大值定义为$t_{sw}^{2} $.根据文献[15]中的定义, Cql是调度器将第1个任务从延时队列放到运行队列的开销, Cqs是将多于一个任务时的其他任务从延时队列放入到运行队列的开销, 则有Cqs < Cql.如果任务1和任务2都在点B释放, 则任务3运行期间总的抢占开销是$ 8{{C}_{tick}}+t_{sw}^{1}+2t_{sw}^{2}+{{C}_{ql}}+{{C}_{qs}}$.如果任务2在C点释放, 则总的抢占开销为$8{{C}_{tick}}+t_{sw}^{1}+2t_{sw}^{2}+2{{C}_{ql}} $.如果任务2在D点释放, 则总的抢占开销为$8{{C}_{tick}}+2t_{sw}^{1}+2t_{sw}^{2}+2{{C}_{ql}} $.由此说明, 不但切换开销少了1次, 而且释放开销减小.同时可以看出:如果高优先级任务之间减少重叠, 容易导致更多的切换开销.

固定优先级抢占式调度的最差响应时间认为出现在理论的关键性时刻(见定义1), 即所有任务一齐释放的时刻(这里认为“t=0”时刻).然而, 在考虑上下文切换开销时, 这并不一定是任务的关键性时刻.观察图 8:在情况(b)中, 任务1和任务2同时释放; 而在情况(a)中, 任务2和任务1之间有一个偏移O2, 它大于任务1的WCET.依据前述讨论, 情况(a)下任务的切换次数要比情况(b)多1次.由于两种情况下, 任务1和任务2对于任务3的抢占是相同的, 故对于任务3而言, 最差情况是情况(a), 并非任务同时释放的情况(b).并且从图 8可以看出:在情况(b)中, 如果任务1运行并非其WCET的时间, 即运行时间比WCET小△c1, 那么这同样将导致多一次切换, 如果这个多的切换时间比Dc1大, 那么将导致任务3的响应时间更长, 本文中不讨论这种情况.

Fig. 8 Task release with offset 图 8 任务释放带有偏移

在文献[18]中, 他们得出了关于关键性时刻同样的结论, 但是在计算准确的抢占次数时, 他们使用了任务同时释放这一关键性时刻, 与不考虑切换开销情况不同的是他们在第1个超周期(hyperperiod, 所有任务周期的最小公倍数)里进行可调度分析来找到最差情况.然而, 这样做在考虑任务间释放偏移时是不安全的.很容易从图 8中观察到这一点:如果任务2的周期是任务1周期的整数倍, 那么在同时释放的假设下, 任务2将永远与任务1一同释放, 故切换次数难以最大化.

很明显, 与一个任务相关的最大上下文切换次数小于等于2, 如果把每个高优先级任务的WCET加入两个上下文切换开销, 即Ci+2tsw, 以“t=0”时刻为关键性时刻可以计算出任务τi最差响应时间的一个上界$R_{i}^{UB} $.类似地, 如果不考虑切换开销, 可以计算出任务ti最差响应时间的一个下界$ R_{i}^{LB}$, 那么准确地考虑开销的任务最差响应时间则位于$ (R_{i}^{LB}, R_{i}^{UB}]$中, 可以通过给每个任务分配相对于“t=0”时刻的不同的偏移来找到.

4 响应时间分析

通过前述讨论观察到, 可以通过给高优先级任务分配不同的偏移来找到最差情况.为了简化分析, 不考虑时钟中断和上下文切换开销.保持任务τi的响应时间$R_i^{LB} $不变, 高优先级任务tj的偏移Oj应满足某个范围$[0, O_{j}^{\max }) $.下面用3个任务的例子进行说明.如图 9所示, 情况(a)中3个任务在0时刻一齐释放, 任务1的最后一次释放在t1时刻, 任务2的最后一次释放在t2时刻, 由图可知任务3在t3时刻执行完毕, 其最差响应时间为$R_{3}^{LB} $.在情况(b)中, 任务1有了一个偏移, 它的最后一次释放将延后, 结果是延迟了任务2的执行, 却使得任务3后续部分可以提前执行, 当偏移刚好为$O_{1}^{\max } $时, 任务3提前执行完毕, 其响应时间小于$ R_{3}^{LB}.$

Fig. 9 Example of effect of offset on response time calculation 图 9 偏移对响应时间的影响举例

为了计算$ O_{j}^{\max }$, 使用文献[17]中的方法来建立处理器的空闲时间.令i代表在Ri+1期间调度任务t1到任务τi后处理器空闲时间的行向量, 即${{\Delta }^{i}}=\{\Delta _{{{t}_{1}}}^{i}, \Delta _{{{t}_{2}}}^{i}, ..., \Delta _{{{t}_{p}}}^{i}\} $, 其中, $ \Delta _{t}^{i}$是在t时刻结束的处理器空闲时间的长度, 并有$\Delta _{t}^{i}>0, t\in N $.0定义为${{\Delta }^{0}}=\{\Delta _{0}^{0}, \Delta _{{{R}_{i+1}}}^{0}\} $, 有$\Delta _{0}^{0}=0 $$\Delta _{{{R}_{i+1}}}^{0}={{R}_{i+1}} $.i是通过考虑在[0, Ri+1)期间任务τi的所有请求后, 更新i-1来构造的.令i, j-表示在Ri+1期间调度{τk}, (k=1, …, j-1, j+1, …, i)后处理器空闲时间的行向量, 即除去任务tj.事实上, $ \Delta _{t}^{i}$实际是高优先级任务调度后, 留给任务τi+1运行的时间, 如图 10所示.

Fig. 10 Illustration of $ \Delta _{t}^{i}$ 图 10 $ \Delta _{t}^{i}$的示意图

$ t_{j}^{last}$表示在$ R_{i}^{LB}$期间, 偏移Oj=0的情况下, 任务τj最后一次释放的时刻, 则有$ t_{j}^{last}=\left\lfloor R_{i}^{LB}/{{T}_{j}} \right\rfloor {{T}_{j}}$; 令$t_{j}^{lastO} $表示在$ R_{i}^{LB}$期间, 偏移${{O}_{j}}=O_{j}^{\max } $的情况下, 任务τj最后一次释放的时刻, 则有$ t_{j}^{lastO}=t_{j}^{last}+O_{j}^{\max }$.通过对任务τi响应时间$ R_{i}^{LB}$的研究, 可以得出以下结论:

引理1.在$[R_{i}^{LB}-{{\delta }_{inst}}, R_{i}^{LB}] $时间段, 任务τi的最后一条指令执行完毕, 其中, δinst为任务τi最后一条指令的执行时间.

证明:由$ R_{i}^{LB}$定义可得.

引理2.若任务τj$t_{j}^{lastO} $处开始执行, 用$\Delta _{{{t}_{k}}}^{i-1, j-} $代表除了任务ti和任务τj外, 其他任务调度后的空闲时间, 则这些空闲时间在区间$ [t_{j}^{lastO}, R_{i}^{LB}-{{\delta }_{inst}}]$内, 刚好被任务τj填满.

证明:在任务τi响应期间, 任务τ1τi累积的对处理器的需求一直不被满足, 直到$ R_{i}^{LB}$.由$\Delta _{{{t}_{k}}}^{i-1, j-} $的定义知, 其一定被任务τi和任务τj填满.在区间$[t_{j}^{lastO}, R_{i}^{LB}-{{\delta }_{inst}}] $内, 如果任务τj未执行完, 那么$ [R_{i}^{LB}-{{\delta }_{inst}}, R_{i}^{LB}]$区间内其必然在执行, 与引理1矛盾; 如果任务τj$ R_{i}^{LB}-{{\delta }_{inst}}$前执行完, 则$ {{O}_{j}}$可以继续增大, 直到其刚好在$ R_{i}^{LB}-{{\delta }_{inst}}$时刻执行完, 而不影响任务${{\tau }_{i}} $的响应时间.可得在区间$[t_{j}^{lastO}, R_{i}^{LB}-{{\delta }_{inst}}] $内, 空闲时间刚好被任务$ {{\tau }_{j}}$填满, 引理得证.

一般δinst时间非常短, 简单起见, 后续不再单独考虑其影响, 令δinst=0.利用引理1和引理2, 可得定理2.

定理2(任务的最大偏移).不考虑上下文切换开销时, 保持任务τi的最差响应时间不变, 若高优先级任务tj获得最大偏移, 则其他任务应以“t=0”的关键性时刻到来, 且满足下述关系:

$ \left\{ {\begin{array}{*{20}{l}} {t_j^{lastO} = t + \sum\limits_{{t_k} \in (t, R_i^{LB}]} {\Delta _{{t_k}}^{i - 1, j - }} - {C_j}}\\ {{C_j} - \Delta _t^{i - 1, j - } \le \sum\limits_{{t_k} \in (t, R_i^{LB}]} {\Delta _{{t_k}}^{i - 1, j - }} < {C_j}} \end{array}} \right.(t_j^{last} < t \le R_i^{LB}, \Delta _t^{i - 1, j - } \in {\Delta ^{i - 1, j - }}) $ (4)

证明:如图 11所示, 由引理2可知, 若高优先级任务tj获得最大偏移, 区间$[t_{j}^{lastO}, R_{i}^{LB}] $的空闲时间$ \Delta _{{{t}_{k}}}^{i-1, j-}$刚好被任务τj填满, 则以时间t$ R_{i}^{LB}$向前搜索, 累加的空闲时间等于任务τj的最差执行时间Cj的时刻即为$ t_{j}^{lastO}$, 故第1项成立; 由于$t_{j}^{lastO} $时刻, 任务τj开始执行, 则$t_{j}^{lastO} $必然位于某个区间$\Delta _{t}^{i-1, j-} $内, 可得第2项成立, 故公式(4)成立.

Fig. 11 Maximum offset diagram 图 11 最大偏移示意图

反之, 若有公式(4)成立, 将第1项带入到第2项中, 有$t-t_{j}^{lastO}\le \Delta _{t}^{i-1, j-} $, 故$ t_{j}^{lastO}$位于$ \Delta _{t}^{i-1, j-}$内; 由第1项知, $t_{j}^{lastO} $之后累积的空闲时间刚好等于Cj.故$ t_{j}^{lastO}$为任务τj最大偏移时, 最后一次释放后开始执行的时刻.

其次, 若其他任务相对于t=0的关键性时刻有偏移, 则空闲时间$ \Delta _{{{t}_{k}}}^{i-1, j-}$将前移, 由公式(4)知, t将减小, 从而导致$ t_{j}^{lastO}$减小, 故在其他任务的偏移都为0时, 任务τj将得到最大的偏移.定理得证.

由于加入上下文切换开销后任务响应时间会增加, 故计算时假设偏移$ {{O}_{j}}\le O_{j}^{\max }$, 由此, 可以使用文献[17]或

文献[18]中的方法测试每个可能的偏移组合下各个任务的最差响应时间, 也可以使用仿真的方法找到最大值.

事实上, 时间是一个连续变量, 其偏移的组合是无限的, 所以难以做到遍历各个偏移的组合.在RTOS里, 执行上下文切换通常是离散的时间点, 称为调度点.在分析中, 可以假设任务都是通过时钟中断释放的, 这符合实际情况, 因为这是RTOS用于释放周期性任务常用的方式.在这个假设下, 任务仅仅在离散的时间点被释放, 即周期性时钟中断执行的时间点, 所以在任务τi的响应期间, 高优先级任务可能的偏移组合是有限的, 问题是可处理的.

将时钟滴答的大小记tc, 任务τj相对于“t=0”的关键性时刻所有可能的释放偏移为

$ {O_j} = k{t_c}, (0 \le k \le \left\lfloor {O_j^{\max }/{t_c}} \right\rfloor , k \in N) $ (5)

此处假定任务的偏移为时钟嘀嗒的整数倍, 由于任务释放时间连续时允许的最大偏移$ O_{j}^{\max }$并不一定与时钟滴答对齐, 故采用了向下取整运算$ \left\lfloor O_{j}^{\max }/{{t}_{c}} \right\rfloor $表示释放时间离散后最大偏移处的k值.同时, 由于任务都在时钟

滴答的整数倍处释放, 故任务的周期均为时钟嘀嗒的整数倍.此种情况下, 有:

$ t_j^{last} = \left\lfloor {R_i^{LB}/{T_j}} \right\rfloor {T_j}, t_j^{lastO} = t_j^{last} + \left\lfloor {O_j^{\max }/{t_c}} \right\rfloor {t_c} $
5 案例与仿真 5.1 中断

本节通过真实的软硬件仿真来检验文中中断开销的分析方法和结论.仿真环境和配置与文献[22]类似, 对相关细节进行了补充说明, 概述如下.

系统的软硬件分别采用开源的LEON3处理器和SpaceOS操作系统, 仿真环境采用Modelsim软件. LEON3[23]是欧洲航天局下的Gaisler研究所开发的使用SPARC V8指令集的32位RISC处理器, 它的源代码由可综合的VHDL代码构成.基于GPL许可证协议, LEON3非容错版本软核IP提供VHDL源代码.空间嵌入式操作系统SpaceOS是由北京控制工程研究所研制的星载计算机嵌入式操作系统, 已经在多个航天型号任务上得到了应用.

整个仿真验证方案如图 12所示:首先, 通过配置config.vhd和leon3mp.vhd文件来选择LEON3处理器的功能特性; 接着, 通过配置OSSet.h和OSMacro.h来选择SpaceOS操作系统相应的功能特性; 配置完系统运行所需的软硬件环境后, 通过编写testbench.vhd来仿真外围的SRAM存储器、UART串口和其他信号; 通过编写应用程序文件app.c来定义系统中运行的任务程序和用户中断服务程序; 最后将软硬件文件分别编译生成Modelsim仿真文件和用于加载到SRAM的可执行二进制文件.在Modelsim里运行仿真, 得到相应的波形和程序运行时的反汇编代码, 进而分析得到各个任务与中断的相应时间特性.

Fig. 12 Simulation framework 图 12 仿真验证框架

本仿真中硬件具体配置为时钟频率为100MHz, 处理器核心数为1, 寄存器窗口数目设置为8个, 整数单元不使用分支预测, 不使用指令与数据Cache, 不开启存储器管理单元(MMU).片外连接8M×32bit的SRAM存储器, 带有5个片内定时器和两个通用串口等.软件环境配置为使用循环调度, 主周期由外部中断0产生, 时间片中断由定时器1产生, 任务的读写等待周期全部设置为1(指CPU的指令周期数).系统另外设计为包含4个任务和4个中断, 相应参数见表 1表 2.表中的WCET值是通过大量仿真后选取的最大值, 表 1中TIMR1括号内的值是带有任务释放时的最差执行时间.

Table 1 Interrupts of the system 表 1 系统的中断

Table 2 Tasks of the system 表 2 系统的任务

系统的软件调度策略选择循环调度(cyclic executive)[25].循环调度是硬实时系统广泛采用的一种周期性任务调度策略, 它的调度决策是静态的, 离线计算好之后保存在表格中, 然后在系统里以一个确定的速率被反复地执行, 这个反复执行的周期称为主周期(major cycle).主周期又被分为许多小时间段, 称为帧(frame)或次周期(minor cycle).每个帧都附带一个需要在帧内部执行的任务列表, 通常列表里分配的任务在帧的起始时刻由系统的硬件时钟中断服务程序释放, 在帧的结束时刻前必须完成.

任务1除了在分配的帧内执行外, 每次UART1中断执行完毕后, 还会释放任务1执行, 由于任务1为最高优先级任务, 故其会立刻抢占其他任务得到运行.由此造成的额外切换开销tγo=35.87μs.最长关中断时间$ b_{i}^{\max }=$ 50.71μs.在具体分析的过程中, 遇到以下两个需要解决的问题.

1) 某些延时操作(例如void Delay_us())采用硬件定时器实现, 这种情况下, 即使被中断抢占, 延时阶段的时间也不一定会被延长, 故不能直接按抢占次数乘以最差执行时间计算干扰;

2) LEON3采用SPARC体系结构, 采用寄存器窗口机制、上溢和下溢陷阱将带入开销, 需要额外分析.

5.1.1 任务延时

仿真中, 任务的延时函数使用硬件定时器, 在一个循环语句中反复读取定时器的值, 做差与设定值进行比较来实现特定时间延时.如图 13(a)所示, 函数代码在B点读取定时器时间初值, 在D点读取时间终值, 通过计算B, D两点的时间差来确定延时的时间.

Fig. 13 Analysis of delay interval 图 13 延时区间分析

一方面, 由于定时器有一定的精度, 其值只在离散的时间点进行更新(本仿真采用的定时器精度为10μs), 并且函数代码在连续读取时间值之间需要执行条件判断语句, 故延时时间并不精确等于设定值.假设定时器的值在A点和C点发生跳变, 可以看出:要想使得实际的延时时间最长, 那么B点应当尽量靠近A点, D点应当尽量远离C点.设期望延时时间为tdk, 则最坏情况下的延时时间为tdk+δd.容易得到本仿真中δd=1.5μs, 分析细节便不再赘述.

另一方面, 抢占发生时, 真正造成延时区间增长的是那些在延时结束前到达释放并且没有返回的中断.如图 13(a)所示:B点之前释放的中断会增加任务的响应时间; 在B点之后到C点之前释放并在C点之前执行完毕的中断不会影响任务的响应时间; 在C点之前释放并且到C点仍未执行完的中断会部分增加任务的响应时间; 在C点之后D点之前释放的中断会将D点读取时间操作延后, 也会增加任务响应时间.

综上分析, 可以以C点为界, 将任务分为延时区间和非延时区间, 将非延时区间单独进行分析, 假设任务执行过程中中断一直打开, 有如下定理:

定理3(非延时区间的关键性时刻).对于延时结束后的非延时区间而言, 其关键时刻出现在延时结束定时器时间值跳变时刻, 所有中断一齐释放并被响应, 此后所有中断各自以周期或者最小时间间隔到达.

证明:如图 13(b)所示, 假定中断Ij的释放时间与延时结束定时器的值跳变时刻之间有Oj的偏移.若Oj≥0, 则Ij会增加任务响应时间, 易得Oj越小, 中断Ij可能的抢占次数越多, 故Oj=0时, 中断Ij的干扰最大.若Oj≤0, 则Ij在定时器跳变时刻之前执行部分不会增加任务响应时间.故随着Oj的减小, 任务响应时间随之减小, 中断Ij的左移并不能导致更多抢占.故Oj=0时, 中断Ij的干扰最大.可得, Oj=0为关键性时刻.对于任意数量的中断, 有类似结论, 定理得证.

设任务3的程序中延时操作个数为nd, 每个延时操作的时间为di, k, 则被延时造作分割成的区间个数为nd+1个, 其最差执行时间分别为Ci, k.分别以Cik+δd为初值, 利用公式(2)计算任务被分割成的非延时区间的最差响应时间Ri, k的值.根据前面分析, 得到任务的最差响应时间为

$ {R_i} = \sum\limits_{k = 1}^{{n_d} + 1} {{R_{i, k}}} + \sum\limits_{k = 1}^{{n_d}} {{d_{i, k}}} $ (6)

这种方法的缺点是:当两个相邻延时区间间隔较短时, 会出现较大的过估.见表 3, 任务3中有3个延时, 其中, 第1个延时只有10ms, 其与第2个延时的间隔最大只有2.97μs, 相对于中断的周期要小得多, 这样如果单独考虑, 定义关键时刻进行计算, 则会产生较大过估.在分析中, 将其当作非延时区间对待.

Table 3 Composition of Task3 表 3 任务3的组成

5.1.2 上下溢陷阱

本仿真验证采用我们在文献[24]中提出的方法对寄存器窗口溢出陷阱的开销进行分析, 方法的内容不再赘述, 只对一些情况进行说明(在本例中, 上下溢陷阱服务程序的最差执行时间分别为上溢陷阱tof=2.67μs, 下溢陷阱tuf=3.47μs).

1) 抢占出现时, 被抢占任务使用过的所有寄存器窗口都要保存, 而且保存的寄存器个数越多, 所花费时间越长, 那么最长切换时间应出现在任务调用深度最大时.这个切换时间对应图 5中的t1~t2.若被抢占任务是由中断释放的, 如此例中的中断UART1每次都会释放任务1, 那么这个切换时间对应图 4中的t5~t6.在计算时, 安全简便的处理方式是这个切换时间全部取成任务调用深度最大时的值;

2) 抢占返回时, 被抢占任务只恢复一个新窗口, 任务恢复运行后每次执行RESTORE指令返回都会发生一次下溢, 同样在任务调用深度最大时, 需要返回的次数最多, 那么发生下溢的次数也越多, 所花费时间越长.而且文献[24]指出, 每次返回潜在的可能发生两次下溢陷阱.下面以任务4为例分析这种情况.

图 14为任务4的函数调用图.先计算出任务4响应期间的最大上下文切换次数为nc=6次.为了得到最差情况, 这些切换应该首先发生在最深层, 即1次在Func4或Func5, 1次在Func7或Func8, 1次在Func11到Func16.这3次切换在Func3, Func6, Func10, Func1和Task4返回时同样可以引起下溢陷阱.剩下的3次切换每个可以引起一次下溢陷阱, 则总的下溢次数为3+3+5=11.对上溢而言, 当切换发生时, 如果下一个运行的任务是新运行任务(未被抢占), 那么将有nr-2=6个寄存器窗口; 如果是恢复运行的任务(前面被抢占), 那么将有nr-1=7个寄存器窗口(没有被RTOS占用的窗口).在两次切换之间, 利用无任务切换时的计算公式计算最大上溢次数.

Fig. 14 Call graph of task4 图 14 任务4的函数调用图

具体到本例中, 任务2、任务3和任务4发生下溢最大次数分别为任务2是4次、任务3是10次、任务4为11次.由于频繁的任务切换, 没有上溢陷阱.

5.1.3 仿真结果

综上所述, 计算得到中断影响下的任务最差响应时间与仿真得到的最差响应时间对比见表 4.仿真使用前述配置并且使用不同的中断偏移重复多次, 仿真值一栏给出的是所测时间的最大值.任务3的过估最小, 原因是其延时区间时间较长, 非延时程序运行时间较短, 所以分析结果比较准确, 同时也说明对延时区间的分析方法比较有效.任务4的过估最大, 主要是因为其执行时间最短, 但是函数调用关系和控制流复杂, 测试很难覆盖到最差情况, 同时分析也有较大过估.可以看出, 最大过估仅为13.25%, 说明本文所述的中断开销的计算方法是非常有效的.

Table 4 Analysis and simulation results 表 4 分析和仿真结果

另外, 通过本例的分析过程可以看出:在对实际系统进行分析时, 会遇到很多实际的困难, 所以在对理论方法进行研究的同时, 也需要进行对方法的应用进行探索.本文提出的仿真架构(如图 12所示), 为应用验证提供一个很好的平台.

5.2 上下文切换

由于任务上下文切换的机理比较明确, 而使用实际系统进行仿真测试过于耗时, 故本节使用仿真工具进行分析.我们用一个例子来阐述第4节提出的响应时间计算方法.假设系统共有4个任务{τ1, τ2, τ3, τ4}, 它们的参数见表 5.假设时钟滴答tc为0.5, 上下文切换的时间上限tsw为0.05.

Table 5 Task parameters 表 5 任务的参数

使用开源的可调度性分析工具集MAST[26]来做分析.JSimMAST是其中的一个事件触发的仿真工具, 用它来仿真每种偏移组合下任务的最差响应时间.以寻找任务τ4的最差响应时间为例, 分析过程如下.

●  首先, 仿真不考虑上下文切换开销时, 在t=0时刻所有任务一齐释放的情形, 得到$ R_{4}^{LB}=20$, 并且可以得到$ {{\Delta }^{3, 1-}}=\{\Delta _{8}^{3, 1-}=3, \Delta _{12}^{3, 1-}=2, \Delta _{16}^{3, 1-}=1, \Delta _{20}^{3, 1-}=2\}$.使用公式(4)计算出$t_{1}^{last}=18, t_{1}^{O}=19 $$O_{1}^{\max }=1 $.接着, 使用公式(5)可以计算出0≤k < 2, 可得O1=0, 0.5, 1.类似的, 可以计算出O2=0, 0.5, 1和O3=0, 0.5, 1, 1.5, 2.当然, 也可以使用仿真的方法来找到最大偏移, 只要令其他任务的偏移都为0, 在${{R}_{i}}-t_{j}^{last}-{{C}_{j}} $范围内测试Oj即可;

●  其次, 使用不同的任务偏移组合来仿真任务集.由于只关注任务t4, 故只给出它的最差响应时间仿真结果为20.9.而所有任务一齐释放时的最差响应时间为20.75.可以观察到, 任务τ4响应时间的增长允许它可以接受高优先级任务更大的偏移;

●  第三, 增大偏移的数值, 令O1=1.5, O2=1.5和O3=2.5, 并再次执行仿真过程.现在观察到某些情况下, R4小于20.例如, O1=0, O2=0和O3=2.5情况下, 有R4=14.5;而O1=0.5, O2=0和O3=2.5情况下, 有R4=20.85.原因是后者带入了更多的上下文切换开销, 从而增大了R4;

●  最后得到任务τ4的最差响应时间的准确值为20.95.这个结果实际上与给每个高优先级任务的WCET增加两次切换开销的分析结果相同, 仅仅是任务τ4结束时, 最后一次切换开销在仿真中没有计算而已.

更进一步, 如果假设时钟滴答tc为1, 那么有O1=0, 1, O2=0, 1和O3=0, 1, 2, 从而得到R4=20.85.如果假设tc是2, 那么有O1=0, O2=0和O3=0, 2, 从而得到R4=20.8.这些情况下, 利用本文方法计算得到的最差响应时间将更加精确.同时也可以看出:上下文切换次数与时钟滴答的大小是密切相关的, 某些时候, 增大时钟滴答可以减少切换次数, 但可能使系统的响应变迟缓.

6 总结

响应时间分析方法多基于系统任务的抽象模型, 将其应用于实际系统分析时, 还需要考虑很多实际的因素, 如中断、上下文切换、延时区间、寄存器窗口溢出陷阱等.目前对于这些实际因素的研究较少, 这在一定程度上阻碍了其在一些安全关键系统中的实际应用.

本文对响应时间分析方法应用于实际系统进行了有益的探索, 对实时嵌入式系统里的中断和上下文切换时序进行了详细的讨论, 给出了这些开销的估计方法, 并分别通过真实的硬件进行了仿真.同时, 在理论方面, 本文对任务由中断释放、考虑上下文切换开销、程序包含定时器延时等情况下的任务的关键性时刻进行了讨论, 并给出了相关证明.本文仍有一些不足之处, 如对于阻塞和cache相关的抢占延迟等因素以及多处理器系统缺乏讨论, 这将作为未来的工作.

参考文献
[1]
Liu JWS. Real-Time Systems. Prentice Hall, 2000.
[2]
Yang MF, Gu B, Guo XY, Dong XG, Wang Z, Chen R. Aerospace embedded software dependability guarantee technology and application. Scientia Sinica Technologica, 2015, 45(1): 198–203(in Chinese with English abstract). [doi:10.1360/N092014-00485]
[3]
Joseph M, Pandya P. Finding response times in a real-time systems. The Computer Journal, 1986, 29(5): 390–395. [doi:10.1093/comjnl/29.5.390]
[4]
Audsley NC, Burns A, Richardson M, Tindell K, Wellings AJ. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 1993, 8(5): 284–292. http://www.utdallas.edu/~cxl137330/courses/fall13/RTS/papers/21.pdf
[5]
Regehr J. Safe and structured use of interrupts in real-time and embedded software. In: Lee I, Leung JYT, Son SH, eds. Handbook of Real-Time and Embedded Systems. Chapman and Hall/CRC Press, 2007. [doi:10.1201/9781420011746.ch16]
[6]
Brylow D, Palsberg J. Deadline analysis of interrupt-driven software. IEEE Trans. on Software Engineering, 2004, 30(10): 634-655. [doi:10.1109/TSE.2004.64]
[7]
Jonathan K, Dorsa S, Sanjit AS. Timing analysis of interrupt-driven programs under context bounds. In: Proc. of the Formal Methods in Computer-Aided Design (FMCAD). 2011.
[8]
Leyva-del-Foyo LE, Mejia-Alvarez P, Niz D. Integrated task and interrupt management for real-time systems. ACM Trans. on Embedded Computing Systems, 2012, 11(2): 1-31. [doi:10.1145/2220336.2220344]
[9]
Jeffay K, Stone DL. Accounting for interrupt handling costs in dynamic priority task sysetms. In: Proc. of the IEEE Real-Time Systems Symp. 1993. 212-221.
[10]
Sandström K, Eriksson C, Fohler G. Handling interrupts with static scheduling in an automotive vehicle control system. In: Proc. of the IEEE Int'l Conf. on Real-Time Systems and Applications (RTAS). 1998.
[11]
Brandenburg BB, Leontyev H, Anderson JH. An overview of interrupt accounting techniques for multiprocessor real-time systems. Journal of Systems Architecture, 2011, 57: 638–654. [doi:10.1016/j.sysarc.2010.05.011]
[12]
Cofer D, Rangarajan M. Formal verification of overhead accounting in an avionics RTOS. In: Proc. of the IEEE Real-Time Systems Symp. 2002. 181-190. [doi:10.1109/REAL.2002.1181573]
[13]
Bimbard F, George L. FP/FIFO feasibility conditions with kernel overheads for periodic tasks on an event driven OSEK system. In: Proc. of the IEEE Int'l Symp. on Object and Component-Oriented Real-Time Distributed Computing. 2006. [doi:10.1109/ISORC.2006]
[14]
Katcher DI, Arakawa H, Strosnider JK. Engineering and analysis of fixed priority schedulers. IEEE Trans. on Software Engineering, 1993, 19(9): 920-934. [doi:10.1109/32.241774]
[15]
Burns A, Tindell K, Wellings A. Effective analysis for engineering real-time fixed priority schedulers. IEEE Trans. on Software Engineering, 1995, 21(5): 475-480.
[16]
Gabriëls R, Gerrits D. Accounting for overhead in fixed priority pre-emptive scheduling. Department of Mathematics & Computer Science, Technische Universiteit Eindhoven, 2007.
[17]
Echagüe J, Ripoll I, Crespo A. Hard real-time preemptively scheduling with high context switch cost. In: Proc. of the Euromicro Workshop on Real-Time Systems (ECRTS). 1995. [doi:10.1109/EMWRTS.1995.514310]
[18]
Yomsi PM, Sorel Y. Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems. In: Proc. of the Euromicro Conf. on Real-Time Systems (ECRTS). 2007.
[19]
Liu CL, Layland JW. Scheduling algorithms for mul-tiprogramming in a real-time environment. Journal of the ACM, 1973, 20(1): 46–61. [doi:10.1145/321738.321743]
[20]
Bryant RE, O'Hallaron DR. Computer Systems:A Programmer's Perspective. 2nd ed.. , Prentice Hall, 2011.
[21]
Buttazzo GC. Hard Real-Time Computing Systems:Predictable Scheduling Algorithms and Applications. 3rd ed.. Boston: Springer-Verla, 2011. DOI:10.1007/b102312
[22]
Yu GL, Yang MF, Xu J, Jiang H. Worst case response time analysis of multilevel interrupt systems. Chinese Space Science and Technology, 2016, 36(2): 28–36(in Chinese with English abstract). [doi:10.16708/j.cnki.1000-758X.2016.0003]
[23]
[24]
Yu GL, Yang MF. Timing analysis of register windows traps for real time system based on SPARC. Aerospace Control, 2015, 33(6): 70–75(in Chinese with English abstract). http://www.cqvip.com/QK/90122X/201506/667216247.html
[25]
Baker TP, Shaw A. The cyclic executive model and ada. In: Proc. of the IEEE Real-Time Systems Symp. (RTSS'88). 1988.
[26]
[2]
杨孟飞, 顾斌, 郭向英, 董晓刚, 王政, 陈睿. 航天嵌入式软件可信保障技术及应用研究. 中国科学:技术科学, 2015, 45(2): 198–203. [doi:10.1360/N092014-00485]
[22]
于广良, 杨孟飞, 徐建, 姜宏. 面向多级中断系统的任务最差响应时间分析. 中国空间科学技术, 2016, 36(2): 28–36. [doi:10.16708/j.cnki.1000-758X.2016.0003]
[24]
于广良, 杨孟飞. 基于SPARC的实时系统寄存器窗口溢出时间分析. 航天控制, 2015, 33(6): 70–75. http://www.cqvip.com/QK/90122X/201506/667216247.html