目前，嵌入式软件在航空航天、列车控制、汽车电子、医疗物联网等领域得到广泛的应用，在嵌入式系统中断处理过程的验证方面，其难度是异常困难和复杂的。因此，中断服务的处理对于嵌入式软件的可靠性和可信性等方面的贡献很重要，在保证嵌入式系统能够可靠、稳定地工作方面具有重要的实际意义和应用价值。

1 相关工作

嵌入式软件运行的外部环境会直接影响其资源是否满足当前工作需要，如果在一个资源受限条件下正常运行，需要系统对计算机的处理能力、存储容量等进行配置与设定等工作^[1]。中断驱动软件存在于许多的嵌入式系统中，来自外部的中断以及系统内部的中断主要是利用系统自身的程序进行接收，中断的处理过程会由不同状态处理过程的状态机进行调度，因此，各种嵌入式操作系统(如VxWorks、Linux)中会嵌入不同的中断处理方式，来扩充和管理嵌入式系统的资源。

中断处理调度过程在嵌入式系统中主要有2个方面需要注意： 1) 根据中断到来数量和中断处理数量这两方面对嵌入式系统的处理能力进行确定。 处理能力太强，消耗资源过多； 处理能力太弱，信息处理不及时。 2) 在大量的中断信息到来后，如果嵌入式系统不能及时响应中断处理，致使一定数量的中断信息丢失，如何保证中断信息数量丢失最少，同时嵌入式系统正常工作，将是嵌入式系统需要重点考虑的问题。

本文对CPU与中断处理能力间的关系进行讨论分析，假设嵌入式系统的中断到来的时间间隔λ服从Poisson分布，中断处理服务时长μ服从负指数分布，本文采用排队方法进行性能评估^[2]，但在嵌入式软件中需要注意以下不同： 1) 传统的任务到来和服务处理是不相关的，而嵌入式系统的处理是相关的，CPU在接收中断时，状态机处理的中断不能运行，这需要设定常数来设置中断对CPU的占用数量和管理占用数量； 2) 不同类型的中断具有不同处理服务的中断强占优先级，高级别中断的执行要优于低级别中断的执行； 3) 中断处理时间会直接影响系统整体的运行效率，而嵌入式系统对系统最长执行时间要求更为苛刻，这要求时间自动机在状态迁移过程中严格按照设定的时间约束进行执行。

张文波等^[3]对基于ARM Linux的EWS的收包处理过程进行了分析，利用二级串连排队网络的理论对基于ARM Linux的EWS的性能进行了实验分析和验证。Sala等^[4]对中断处理中的3个性能指标进行了分析和阐述，而对CPU处理能力和系统损失率等关键性能没有说明。Weidlich等^[5]利用排队论对多线程软件进行性能分析，并计算既定硬件资源下对线程的最优配置策略。牛云等^[6]利用排队论中的M/M/1/K模型，对非周期事务的平均响应时间和异步事务丢失率进行分析。

本文主要建立一种强占优先权的中断排队模型，进而分析嵌入式系统的动态性能，除了对平均服务时长以及平均等待时长分析除外，同时对CPU的中断任务处理量、 系统吞吐量和中断丢失数量三者间关系进行分析，为今后嵌入式系统调度提供参考与设计。

2 模型建立

在嵌入式系统中，现有的中断处理方式分为同步中断处理方式和异步中断处理方式。 本文采用异步处理模式，异步处理时CPU不会立即处理触发时的中断，而是按照中断优先级将该中断信息放入队列中，队列顶部的中断消息被CPU通过状态机取出，开始执行中断对应的处理函数。异步处理模式对中断丢失的概率大大的降低，因此，本文主要建立n中断源的嵌入式系统排队模型，如图 1所示。

输入过程： 中断划分为n等级，随着等级的递增优先级降低，第1等级具有最高优先权，第n等级具有最低优先权。假设每个中断的间隔时间服从Poisson分布或者负指数分布，第i级中断平均时间间隔为λ_i。

排队规则： 中断到达进入终端服务队列，队列中没有中断执行，系统立即响应此中断，后台执行中断服务； 高优先级中断执行时，先进入等待队列，当处理完所有的高优先级中断之后再执行当前中断； 低优先级的中断在执行时，高优先级中断根据强占优先权优先执行，低优先级中断退回队列队首，再重新排队，同优先级中断按照先来先服务的排队原则执行。

中断服务过程： 利用状态机构建嵌入式系统的中断处理过程模型，每个中断服务时间服从负指数分布，第 i 类中断平均服务率为μ_i。

基于排队方法的中断处理的目标参量^[7]定义如表 1所示。

由表 1中参量W_s、 W_q、 τ的定义得：

${{W}_{s}}={{W}_{q}}+\tau .$

(1)

3 两类中断源的强占优先权排队模型分析

假设中断服务排队系统服从强占优先原则，并且遵循第i类型中断到达状态的参数λ_i服从Poisson分布，中断服务时间的参数μ服从负指数分布(i=1，2，…)，同时在服务系统中有2类中断服务，即1类型中断的优先级高于2类型中断。系统的状态空间E={(i，j)； i≥0，j≥0}，其中i(j)代表第1(2)类型中断。系统的状态空间概率分布为P(i，j)={P_i，j，i≥0，j≥0}，稳态平衡方程如下所示：

$\begin{align} & ({{\lambda }_{1}}+{{\lambda }_{2}}){{P}_{0,0}}={{\mu }_{1}}{{P}_{1,0}}+{{\mu }_{2}}{{P}_{01}}, \\ & ({{\lambda }_{1}}+{{\lambda }_{2}}+{{\mu }_{2}}){{P}_{0,j}}= \\ & {{\lambda }_{2}}{{P}_{0,j-1}}+{{\mu }_{1}}{{P}_{1,j}}+{{\mu }_{2}}{{P}_{0,j+1}},j\ge 1, \\ & ({{\lambda }_{1}}+{{\lambda }_{2}}+{{\mu }_{1}}){{P}_{i,0}}={{\lambda }_{1}}{{P}_{i-1,0}}+{{\mu }_{1}}{{P}_{i+1,0}},i\ge 1, \\ & ({{\lambda }_{1}}+{{\lambda }_{2}}+{{\mu }_{1}}){{P}_{i,j}}= \\ & {{\lambda }_{1}}{{P}_{i-1,j}}+{{\lambda }_{2}}{{P}_{i,j-1}}+{{\mu }_{1}}{{P}_{i+1,j}},i\ge 1,j\ge 1.~ \\ \end{align}$

(2)

按照H_i={(i，j)，j≥0}，i≥0将状态空间E分块，则该马氏过程的无穷小生成元矩阵Q如下：

$Q=\left[ \begin{array}{*{35}{l}} {{B}_{0}} & {{A}_{0}} & 0 & 0 & 0 & 0 & \cdots \\ {{B}_{1}} & {{A}_{1}} & {{A}_{0}} & 0 & 0 & 0 & \cdots \\ 0 & {{A}_{2}} & {{A}_{1}} & {{A}_{0}} & 0 & 0 & \cdots \\ 0 & 0 & {{A}_{2}} & {{A}_{1}} & {{A}_{0}} & 0 & \cdots \\ 0 & 0 & 0 & {{A}_{2}} & {{A}_{1}} & {{A}_{0}} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \end{array} \right].$

(3)

根据马尔可夫生成矩阵Q的特点，此过程可以视为一个以R为率矩阵的拟生灭过程，其中R为二次矩阵方程R²A₂+RA₁+A₀=0的最小非负解。

根据Miller的矩阵几何理论^[8]，对于此排队模型，R具有式(4)所示的特殊结构。

$R=\left[ \begin{array}{*{35}{l}} {{r}_{0}} & {{r}_{1}} & {{r}_{2}} & {{r}_{3}} & \cdots \\ 0 & {{r}_{0}} & {{r}_{1}} & {{r}_{2}} & \cdots \\ 0 & 0 & {{r}_{0}} & {{r}_{0}} & {{r}_{1}} \\ 0 & 0 & 0 & {{r}_{0}} & {{r}_{0}} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \end{array} \right].$

(4)

矩阵Q满足πQ=0，其中向量π=(π₀，π₁，π₂，…)，π_i=(π_i，0，π_i，1，π_i，2，…)，若令λ=λ₁+λ₂，I为单位矩阵，则可得如下结果：

$\begin{align} & {{A}_{0}}={{\lambda }_{1}}I, \\ & {{A}_{1}}=\left[ \begin{matrix} -\lambda -{{\mu }_{1}} & {{\lambda }_{2}} & 0 & 0 & \cdots \\ 0 & -\lambda -{{\mu }_{1}} & {{\lambda }_{2}} & 0 & \cdots \\ 0 & 0 & -\lambda -{{\mu }_{1}} & {{\lambda }_{2}} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \end{matrix} \right], \\ & {{B}_{0}}=\left[ \begin{matrix} -\lambda & {{\lambda }_{2}} & 0 & 0 & \cdots \\ {{\mu }_{2}} & -\lambda -{{\mu }_{2}} & {{\lambda }_{2}} & 0 & \cdots \\ 0 & {{\mu }_{2}} & -\lambda -{{\mu }_{2}} & {{\lambda }_{2}} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \end{matrix} \right]. \\ \end{align}$

根据式(2)和Q矩阵向量所示结果，可以得到：

${{\mu }_{1}}r_{0}^{2}-\text{ }(\lambda +{{\mu }_{1}}){{r}_{0}}+{{\lambda }_{1}}=0$

(5)

${{\lambda }_{2}}{{r}_{i}}-(\lambda +{{\mu }_{1}}){{r}_{i+1}}+{{\mu }_{1}}\sum\limits_{j=0}^{i+1}{{{r}_{j}}{{r}_{i+1-j}}=0},i\ge 0.$

(6)

因为R是R²A₂+RA₁+A₀=0的最小非负解，得式(5)的递归解为

${{r}_{0}}=\frac{\left( \lambda +{{\mu }_{1}}-\sqrt{{{(\lambda +{{\mu }_{1}})}^{2}}-4{{\lambda }_{1}}{{\mu }_{1}}} \right)}{2{{\mu }_{1}}},$

(7)

${{r}_{i+1}}=\frac{{{\lambda }_{2}}{{r}_{i}}+{{\mu }_{1}}\sum\limits_{j=1}^{i+1}{{{r}_{j}}{{r}_{i+1-j}}}}{\sqrt{{{(\lambda +{{\mu }_{1}})}^{2}}-4{{\lambda }_{1}}{{\mu }_{1}}}},i\ge 0.$

(8)

该系统的服务强度ρ=λ₁/μ₁+λ₂/μ₂，当ρ≤1时系统存在稳态分布，π_i，j∈E为系统状态，则由π₀(B₀+RB₁)=0可以得到：

$\begin{align} & {{\pi }_{00}}=1-\rho =1-{{\lambda }_{1}}/{{\mu }_{1}}-{{\lambda }_{2}}/{{\mu }_{2}}, \\ & {{\pi }_{01}}=[(\lambda -{{\mu }_{1}}{{r}_{0}})/{{\mu }_{2}}]{{\pi }_{00}}, \\ & {{\pi }_{0,j+1}}=\text{ }\frac{1}{{{\mu }_{2}}}\left[ ~(\lambda +{{\mu }_{2}}){{\pi }_{0,j}}-{{\lambda }_{2}}{{\pi }_{0,j-1}}-{{\mu }_{1}}\sum\limits_{j=0}^{i}{~{{r}_{j}}{{\pi }_{0,i-j}}} \right],\text{ }i\ge 1. \\ \end{align}$

(9)

选择M、N定义所需的概率子集E_M，N={(i，j)，0≤i≤M，0≤j≤ N}，用式(7)和(8)计算{r_j，0≤j≤N}，然后用式(9)计算{π_0，j，0≤j≤N}，最后，对于1≤i≤M用式(10)递归计算{π_i，j，0≤j≤N}。

${{\pi }_{i+1,j}}=\sum\limits_{k=0}^{j}{{{\pi }_{i,k}}{{r}_{j-k}}},i\ge 0,0\le j\le N.$

(10)

因此，在E稳态概率分布的计算算法由式(7)、 (8)、 (9)和(10)组成。

4 系统性能指标

每个中断处理的具体过程描述如下： 1类型中断和2类型中断分别按照参数λ₁和λ₂进行触发，CPU对1类型和2类型的中断服务时间分别为μ₁和μ₂，中断处理的优先级依次降低，并且2类中断在同一等待队列中。输出参数为稳态概率矩阵P={p_i，j，0≤i≤M，0≤j≤N}，由于递归计算{p_i，j，0≤j≤N}的计算量较大，因此，本实验利用Matlab进行仿真完成。实验采用带有强占优先权M/M/1/n排队模型，排队参数描述为： 中断到达过程中，第 i (i=1，2)类型的中断到达，参数λ_i服从Poisson分布； 中断服务时，参数μ_i服从负指数分布，其中，1类型中断的优先级高于2类型中断。

λ₁=100、 λ₂=300、 μ₁=500、 μ₂=500时，本实验的稳态概率矩阵(10×16，部分矩阵)如图 2所示。

1) 稳态队长

在稳态概率矩阵中，令P=0，可得系统稳态产生的最大队长，即保证中断不丢失所需的最小缓冲区长度，本例中系统最大队长L_s=40。 因为P=0时，可以看作中断到来的概率为0，可以认为队长不再增加。所以，可以将P=0时的系统队长看作系统的最大队长。

2) CPU占用率^[9-10]

因为P_0，0是CPU空闲的概率(系统中2类中断个数都为0的概率)，所以ρ=1-P_0，0恰好是CPU被中断占用的概率^[11-12]。 ρ越大，CPU被占用的概率越大，因此，ρ为系统的中断服务强度或者中断负荷水平。

3) 平均逗留时间

约定每一级别的中断到达均服从Poisson分布，λ_i为第i级中断的平均达到率，且为每一级中断服务的时间均服从负指数分布，平均服务时间为1/μ。 所以，平均逗留时间W_s1、 W_s2为

${{W}_{s1}}=\frac{1}{\mu -{{\lambda }_{1}}},$

(11)

${{W}_{s2}}=\left( 1+\frac{{{\lambda }_{1}}}{{{\lambda }_{2}}} \right)\times \frac{1}{\mu -{{\lambda }_{1}}-{{\lambda }_{2}}}-\frac{{{\lambda }_{1}}}{{{\lambda }_{2}}}\times \frac{1}{\mu -{{\lambda }_{1}}}.$

(12)

4) 平均排队等待时间^[13]

同理，平均排队等待时间W_q1、 W_q2为

${{W}_{q1}}={{W}_{s1}}-\frac{1}{\mu }\text{ }=\frac{{{\lambda }_{1}}}{\mu (\mu -{{\lambda }_{1}})},$

(13)

${{W}_{q2}}={{W}_{s2}}-\frac{1}{\mu }.$

(14)

考虑到模型更为贴近于实际应用环境，队列长度不能无限制增长，所以确定性能指标之后采用M/M/1/n排队模型，同时，设置系统缓冲区长度为m。

5) 系统吞吐率

系统中CPU总的占用时间T_CPU由3个部分组成： 中断处理时间T_i、 状态机处理时间T_s与CPU空闲时间T_r。 在不考虑CPU空闲时间T_r(处理机除了进行中断处理以外，剩余时间运行状态机)情况下，可得到T_i+T_s≈T_CPU。 由于系统中断处理的优先级高于状态机处理的优先级，设ρ_i为中断服务强度，则中断处理时间为T_i=ρ_iT，状态机处理时间为T_s=(1-ρ_i)T_CPU。

系统运行状态机的过程是单服务台混合制的排队过程，即M/M/1/n排队模型^[7]。其中输入过程为λ_s，服务时间为μ_s服从负指数分布，n是系统缓冲区的长度。由于中断处理的速度远大于状态机处理的速度，而且硬件中断丢失的概率比较小，可以认为系统状态机的输入λ_s约等于中断处理的输入λ_i^[14]。由于中断处理优先级高于状态机处理，所以状态机的实际处理能力为μ_sr=(1-ρ_i)μ_s，则在缓冲区长度为m的情况下，系统的丢失率为

${{P}_{lost}}=\text{ }\frac{1-{{\rho }_{sr}}}{1-1-\rho _{sr}^{m+1}}\rho _{sr}^{m}.$

(15)

其中，ρ_sr=λ_s/ μ_sr。

根据式(13)，得到嵌入式系统状态机实际吞吐率：

${{\lambda }_{o}}={{\lambda }_{s}}~\left( 1-\frac{\text{ }1-{{\rho }_{sr}}}{1-\rho _{sr}^{m+1}}\rho _{sr}^{m} \right).$

(16)

当系统负载过大时，即λ_s$\gg $μ_sr，因此，ρ_sr$\gg $1，根据式(14)可得：

${{\lambda }_{o}}\approx {{\mu }_{sr}}=(1-{{\rho }_{i}}){{\mu }_{r}}=\left( \text{ }1-\frac{{{\lambda }_{i}}}{{{\mu }_{i}}} \right){{\mu }_{r}}.~$

(17)

根据式(17)，在负载过大情况下，系统中断速率λ_i对系统性能影响很大，λ_i 值越大，其性能越低。

6) CPU处理能力

假定嵌入式系统的CPU处理能力为N mips，C₁ 和C₂分别为中断处理所需的执行操作数和状态机处理所需的执行操作数，则CPU处理能力满足：

$\begin{align} & {{\rho }_{sr}}=\text{ }\frac{{{\lambda }_{s}}}{{{\mu }_{sr}}}=\text{ }\frac{{{\lambda }_{i}}}{(1-{{\rho }_{i}}){{\mu }_{s}}}= \\ & \frac{{{\lambda }_{i}}}{\left( \text{ }1-\frac{{{\lambda }_{i}}}{{{\mu }_{i}}} \right){{\mu }_{s}}}=\text{ }\frac{{{\lambda }_{i}}}{\left( 1-\frac{{{\lambda }_{i}}}{N/{{C}_{1}}} \right)\frac{N}{{{C}_{2}}}}~=\text{ }\frac{{{\lambda }_{i}}{{C}_{2}}}{(N-{{\lambda }_{1}}{{C}_{1}})}. \\ \end{align}$

(18)

将式(18)代入式(15)，进行推导得出中断损失率q，推导过程如下：

$\begin{align} & q={{P}_{\text{lost}}}=\frac{1-\frac{{{\lambda }_{i}}{{C}_{2}}}{N-{{\lambda }_{i}}{{C}_{1}}}}{1-{{\left( \frac{{{\lambda }_{i}}{{C}_{2}}}{N-{{\lambda }_{i}}{{C}_{1}}} \right)}^{m+1}}}\times {{\left[ \frac{{{\lambda }_{i}}{{C}_{2}}}{N-{{\lambda }_{i}}{{C}_{1}}} \right]}^{m}}= \\ & \frac{{{\left( {{\lambda }_{i}}{{C}_{2}} \right)}^{m}}}{\sum\limits_{n=0}^{m}{{{\left[ \left( N-{{\lambda }_{i}}{{C}_{1}} \right) \right]}^{n}}}{{\left( {{\lambda }_{i}}{{C}_{2}} \right)}^{m-n}}}. \\ \end{align}$

(19)

根据式(19)可以得到中断损失率Q与CPU处理能力N之间的关系。这样可以在设定中断损失率的前提下决定多大处理能力的CPU可以满足特定的性能需求，对嵌入式系统CPU类型选择具有重要意义。

5 实验验证与分析

本实验采用自主研发的基于SPARC V8架构处理器的软件仿真平台Virtual_SPARC 3.0，本平台实现了SPARC V8处理器对汇编指令的处理机制，同时对SPARC V8架构中的流水线、寄存器滑动窗口、协处理器、Cache、外设端口、中断控制器等硬件进行仿真实现，并在此基础上进行嵌入式Linux的移植和Leon核的SOC验证平台的实现^[15]。利用软件平台和SOC验证平台进行动态协同评估，在软件平台中构建过载检测功能，同时集成中断测试用例生成等功能模块。

采用仿真平台的中断测试用例生成模块，主程序开启多个定时器中断、键盘中断、I²C中断，定制定时器中断为低中断优先级，键盘中断和I²C中断为高中断优先级。配置中断处理函数，分别设置C₁和C₂为400和4 000，根据不同的实验参数λ、m触发中断，测试中断触发对CPU性能的影响。在集成动态性能评估模块后，对计算系统产生的各项性能指标进行统计，同时对实验仿真结果与排队计算结果进行对比，其数据统计和对比如图 3和4所示。

通过对图 3和4的分析可知： 1) 通过动态测试所得的结果与排队论方法计算结果基本相近，因此，基于排队模型的性能评估方法可以有效地评估嵌入式系统动态性能，指导软硬件设计。 2) 利用排队论计算的各项指标和仿真模拟结果仍有一定的差距，其原因主要有2个方面。 首先，尽管选择了多组数据进行实验，概率性计算结果与偶然性统计结果仍会有不可避免的差距； 其次，本文所提出的排队论模型是基于若干假设的，与实际嵌入式系统稍有不同，这些是今后改进的方向。

图 5和6是验证系统吞吐量与丢失率随中断到来速率的变化趋势。 假定实验条件μ_i=700、 μ_r=700、m=100。

通过实验，在保持一定条件不变下，中断到达速率会影响中断丢失率，前者越大后者也同时变大，反之亦然。系统吞吐率在达到一定峰值后会迅速下降。当中断过载时，中断处理会占用CPU很长时间，CPU不能响应系统内状态机的处理服务，而μ_s远大于实际处理速度μ_sr。 根据式(21)可得到中断丢失率和CPU处理能力间的关系，可进行相应的设置，也可按照不同中断丢失的数量选择相应的处理系统，进而对相应的处理能力进行改进。

本方法与文^[16]中的蚁群优化算法的调度方法的负载均衡具有明显的区别，实验初始中断服务处理的数量较少时，蚁群方法的处理效率相对较快，但是差距不是很大，随着队列的长度增加，排队等待的中断服务将会等待执行，服务的时间较长，但是，在中断服务的丢失率上排队方法比较可靠。因此，在进行可靠性和高效性方面比较时，需要考虑2个方面的均衡点，进而为实现嵌入式系统的负载均衡提供参考依据。

6 结 论

本文提出两级中断源的强占排队模型的评估方法，对嵌入式系统的中断服务可靠性及其性能进行评价，根据中断排队处理中的等待时长、 响应时长、 丢失率、 中断处理的吞吐量与系统中断处理能力等条件，进而用来确定CPU的工作参数。实验和分析结果表明： 对嵌入式系统的中断服务，基本与模型设计的处理方式相近，其可靠度基本满足目前的需求，方便今后类似问题的解决。