用于多级实时调度分析的系统及方法

摘要

本发明提供了一种针对实时操作系统的通用处理模块的多级调度分析的系统及方法。该方法包括：识别通用处理模块的相应的分区内的任何过程；针对各个所识别到的过程，确定过程是局部时间中心，还是全局时间中心。该方法将全局时间中心过程转化成局部时间中心过程，将单级调度分析技术应用于相应的分区的过程，并且，将基于局部时间的响应时间变换成基于全局时间的响应时间。该方法对相应的分区的所识别到的过程中的一个或更多个执行调度和响应时间分析。能够在同步和/或异步系统上且在层次调度系统上执行该方法，该层次调度系统包括具有静态循环调度和/或通用静态调度的顶级调度器。还公开了系统和非暂时性计算机可读介质。

权利要求

1.一种针对实时操作系统的通用处理模块的多级调度分析的方法，所述方法包含：识别所述通用处理模块的相应的分区内的任何过程；

针对各个所识别到的过程，确定所述过程是局部时间中心过程，还是全局时间中心过程；

将全局时间中心过程转化成局部时间中心过程；

将单级调度分析技术应用于相应的分区的所述局部时间中心过程；以及将基于局部时间的响应时间变换成基于全局时间的响应时间。

2.根据权利要求1所述的方法，其特征在于，应用所述单级调度分析技术确定所述过程的参数。

3.根据权利要求2所述的方法，其特征在于，所述参数包括持续时间、响应时间、优先顺序、利用率以及中断状态中的至少一个。

4.根据权利要求1所述的方法，其特征在于，包括对分区执行可行性测试，以确定所述分区的总体可调度性。

5.根据权利要求1所述的方法，其特征在于，包括对相应的分区的所识别到的过程中的一个或更多个执行响应时间分析。

6.根据权利要求1所述的方法，其特征在于，在同步系统和异步系统中的一个系统上执行所述方法。

7.根据权利要求1所述的方法，其特征在于，在层次调度系统上执行所述方法。

8.根据权利要求7所述的方法，其特征在于，所述层次调度系统包括具有任何类型的静态调度的顶级。

9.根据权利要求7所述的方法，其特征在于，所述层次调度系统包括具有静态循环调度的顶级。

10.根据权利要求1所述的方法，其特征在于，利用使用静态循环调度的顶级调度器来将全局时间中心过程变换成局部时间中心过程包括将全局时间中心过程周期以分区持续时间与分区周期的比来缩放。

11.根据权利要求1所述的方法，其特征在于，利用使用通用静态调度的顶级调度器来将全局时间中心过程转化成局部时间中心过程包括将全局时间中心过程周期以主帧中的所述分区的总持续时间与所述主帧的持续时间的比来缩放。

12.根据权利要求1所述的方法，其特征在于，包括将经过的时间加到分区局部时间，以将所述基于局部时间的响应时间变换成所述基于全局时间的响应时间。

13.根据权利要求1所述的方法，其特征在于，所述分区中的至少一个被细分成第一级的子分区。

14.根据权利要求13所述的方法，其特征在于，所述第一级子分区中的至少一个被进一步细分成任意深度的一个或更多个更低级的子分区。

15.一种针对实时操作系统的通用处理模块的多级调度分析的系统，所述通用处理模块包括分区，所述系统包含：

调度单元，其包括中央控制器处理器；

可调度性单元，其配置成对各分区中的过程执行调度分析；

时间变换单元，其配置成通过应用变换方法来将过程参数和时间在局部时间与全局时间之间变换；以及

所述中央控制器处理器，其配置成运行指令，所述指令促使所述中央控制器处理器执行以下的步骤：

识别所述通用处理模块的相应的分区内的任何过程；

针对各个所识别到的过程，确定所述过程是局部时间中心过程，还是全局时间中心过程；

将全局时间中心过程转化成局部时间中心过程；

将单级调度分析技术应用于相应的分区的所述局部时间中心过程；以及将基于局部时间的响应时间变换成基于全局时间的响应时间。

16.根据权利要求15所述的系统，其特征在于，所述可调度性单元配置成对一个或更多个分区执行可行性测试、响应时间分析和利用率分析中的一个，以确定调度是否为可行的。

17.根据权利要求15所述的系统，其特征在于，将全局时间中心过程转化成局部时间中心过程包括将全局时间中心过程周期以主帧中的所述分区的总持续时间与所述主帧的持续时间的比来缩放。

18.根据权利要求15所述的系统，其特征在于，将基于局部时间的响应时间变换成基于全局时间的响应时间包括将经过的时间加到分区局部时间，以将所述基于局部时间的响应时间变换成所述基于全局时间的响应时间。

19.一种非暂时性计算机可读介质，在其上存储有指令，当由中央控制器处理器运行时，所述指令促使所述处理器执行针对实时操作系统的通用处理模块的多级调度分析的方法，所述方法包含：

识别所述通用处理模块的相应的分区内的任何过程；

针对各个所识别到的过程，确定所述过程是局部时间中心过程，还是全局时间中心过程；

将全局时间中心过程转化成局部时间中心过程；

将单级调度分析技术应用于相应的分区的所述局部时间中心过程；以及将基于局部时间的响应时间变换成基于全局时间的响应时间。

20.根据权利要求19所述的非暂时性计算机可读介质，其特征在于，所述指令进一步配置成促使所述中央控制器处理器执行以下的步骤：将全局时间中心过程转化成局部时间中心过程包括将全局时间中心过程周期以主帧中的所述分区的总持续时间与所述主帧的持续时间的比来缩放。

21.根据权利要求19所述的非暂时性计算机可读介质，其特征在于，所述指令进一步配置成促使所述中央控制器处理器执行以下的步骤：将基于局部时间的响应时间变换成基于全局时间的响应时间，通过将经过的时间加到分区局部时间，以将所述基于局部时间的响应时间变换成所述基于全局时间的响应时间。

说明书

用于多级实时调度分析的系统及方法

背景技术

[0001] 实时操作系统(RTOS)软件能够在同一硬件上托管(host)不同等级和复杂度的多个软件应用。RTOS软件使用同一系统资源来在同一处理器上调度且/或实现这些多个软件
应用的运行。RTOS本身的运作取决于按时运行的具体算法。各软件应用能够被称为具有其
自身的处理器和存储器要求的分区。在RTOS环境下，可能需要不同的分区来以不同的速率
且以不同的优先顺序执行其相应的任务。

[0002] RTOS系统能够包括调度器系统，调度器系统能够对各种应用的参数(持续时间、优先顺序、中断状态等)进行分析，以确定对应用的运行调度。实时调度系统能够包括调度器、
时钟和处理硬件元件。能够基于调度器系统对RTOS系统满足应用软件的过程截止期限的能
力的评价，对RTOS系统进行建模和评价。

[0003] 常规的调度系统执行单级调度的方面的调度分析，这些调度分析要求专用分析，以用于多级调度分析。

附图说明

[0004] 图1描绘常规的二级调度方案；

[0005] 图2描绘按照一些实施例的多级调度方案；

[0006] 图3描绘按照一些实施例的调度分析系统；

[0007] 图4描绘按照一些实施例的多级层次调度方案；

[0008] 图5描绘按照一些实施例的另一个多级层次调度方案；以及

[0009] 图6描绘按照一些实施例的多级调度过程。

具体实施方式

[0010] 按照实施例，系统及方法通过将变换和单级调度分析方法应用于多级调度问题，从而使多级实时调度分析问题简化成单级调度分析问题。实施系统及方法能够通过允许更
高级下的任意的静态调度可应用于超过两个的多级调度，从而将使用静态循环调度的二级
调度应用于更高级的调度问题。

[0011] 出于讨论目的，在要求多级调度的标准的背景下，提出了用于多级实时调度分析的实施系统及方法。然而，实施例和实现方案不限于此，而能够应用于其他多级实时调度情
形。

[0012] 一个这样的多级实时调度标准是ARINC 653标准，该标准指定两级调度。在高级下，非抢占式静态调度的使用用于对分区进行调度。在低级下，抢占式调度用于对分区内的
过程进行调度。这允许组成开发，因为，在设计的期间，积分器能够提前将时间分配给不同
的供应商分区。这允许应用供应商使用针对其自身的分区而选择的无论哪一种内部分区调
度方法，都彼此独立地开发其分区。可信操作系统能够强制执行由积分器提供的高级分区
调度，从而提供多个分区之间的有保证的分离。

[0013] 实施系统及方法使多级实时调度分析问题简化成包括可调度性和响应时间分析的单级调度分析问题。术语“可调度性”用于意指如下的一类分析：确定是否有可能在给定
的分区上对一批过程进行调度，使得没有过程的实例化能够错过其截止期限。响应时间分
析能够确定以某些事件所耗费的时间长短(例如，完成过程所耗费的时间长短)为特性的边
界。

[0014] 出于本公开的目的，尺寸n的任务系统由一组周期性实时任务组成，并且，由一组5元组{(Ti，pi，ei，ri，di)| 0 <= i < n}表示，其中：

[0015] Ti是反复地询问运行时间的周期性实时任务的名称。Ti的各实例化是Ti的工作；

[0016] pi是任务的周期‑即，在Ti的相继的工作之间经过的时间长短；

[0017] ei是运行时间‑即，任务Ti的任何工作所要求的最坏情况下的时间量；其中，0 <= ei <= pi；

[0018] ri是初始释放时间‑即，Ti的第一工作可供运行的最早时间；通常，ri < pi；并且，

[0019] di是截止期限：必须在di释放时间内完成工作；其中，ei <= di <= pi。

[0020] 注意到，例如，Ti的第k个工作在时间ri+(k‑l)pi时被释放，并且，必须以时间ri+(k‑l)pi+di完成。工作的响应时间是工作被释放时与工作完成运行时之间的时间。而且，任
务的响应时间是任务的任何工作的最大响应时间。

[0021] 对于涉及一组分区的分析，实施方法访问涉及该组中的分区的高级静态调度的该部分。因此，在组成开发方法论的背景下，这些方法能够为有用的，其中，分区提供商彼此独
立地工作，并且，具有来自过程积分器的如下的保证：分区提供商的工作不受变成不涉及正
运行其软件的分区的高级静态调度的改变影响。

[0022] 图1描绘在ARINC 653标准下使用的常规的二级调度方案。通用处理模块(GPM)100的调度包括四个分区P1、P2、P3以及P4。图1描绘GPM的主帧，其中，分区P1和P2在主帧的期间
具有两个副帧，并且，分区P3和P4各自针对每一主帧而具有一个副帧。主帧结束时的以虚线
描绘的区域与空闲周期相对应。然后，重复GPM主帧。

[0023] 各分区包含一组过程(即，软件应用)，独立于如何对其他分区进行调度，使用分区拥有者都认为适当的无论哪一种调度方案，对该组过程进行调度。可能是如下的情况：抢占
式调度方案用于对分区内的过程进行调度。然而，在GPM等级下，以固定的非抢占式方式，例
如，通过使用静态循环调度，对分区进行调度。

[0024] 按照实施例，高级调度方案基于静态循环调度。然而，实施例不限于此，并且，能够应用于任何静态调度方案。静态循环调度的ARINC 653调度方案能够如下地形式化。

[0025] 定义1：分区是4元组(LT，GT，d，p)，其中：

[0026] LT是可能为空的一组局部时间过程；

[0027] GT是可能为空的一组全局时间过程(在下文中，进一步讨论局部时间和全局时间)；

[0028] d是分区的持续时间，即，分配给副帧中的分区的连续时间量；并且，

[0029] p是分区的周期，即，在分区的相继的副帧之间经过的时间长短。存在d≤p的要求。

[0030] 定义2：GPM是元组(PS，fd)，其中：

[0031] PS是非空的一批分区，P1，……，Pn；并且，

[0032] fd是主帧持续时间，即，GPM的主帧的持续时间。fd值是PS中的分区的周期的最小公倍数的倍数。

[0033] 定义3：GPM的静态循环调度是从分区至表示分区起始时间的有理数的映射。例如，具有持续时间d和周期p的分区P被映射至s，这意味着分区P有权以非抢占式在时间s时开始
使用CPU达d时间(分区的持续时间)。由此断定，分区P同样地有权在时间s+p，s+2p，s+
3p，……时使用CPU，并且，各使用权长达精确地d时间。如果在任何时间点，都没有两个不同
的分区有权使用CPU，则静态循环调度为有效的。

[0034] 定义4：如果对于GPM的分区，存在有效的静态循环调度，则GPM可进行静态循环调度。

[0035] 局部时间过程与全局时间过程之间的区别为，局部时间过程关于分区的(局部)时间而指定过程的周期。当过程的分区不活动时，于是，从过程的角度来看，时间未前进。局部
时间过程的示例是高频计时器，当分区活动时，预期高频计时器以特定的速率运转。与此相
反，从全局时间过程的角度来看，全局时间过程具有全局时间视角‑即使当过程的分区不活
动时，时间也正流逝。预期为，大部分的过程都将是全局时间过程。

[0036] 作为示例，考虑GPM 100，其中，主帧持续时间fd = 100，分区集PS = {PI，P2，P3，P4}，并且，分区分别具有(10，50)、(20，50)、(20，100)以及(12，100)的持续时间和周期(d，
p)。注意到，GPM为可调度的，且实际上，图1显示有效的调度。

[0037] 出于本示例的目的，分区P1的组成是同步(全都立即被释放)且具有最大截止期限(截止期限等于周期)的过程。因而，不需要指定过程的初始释放时间和截止期限。分区P1具
有一个局部时间过程(Tl，0.25，0.04)，其中，0.25是周期，而0.04是运行时间。分区P1还具
有四个全局时间过程：(T2，50，0.5)、(T3，50，3)、(T4，50，2)以及(T5，100，5)。

[0038] 实施系统及方法不仅确定分区P1是否为可调度的，而且还确定分区P1的利用率。分区P1具有局部时间过程和全局时间过程两者。通过将变换方程‑方程1应用于全局过程的
周期，从而将全局时间过程变换成局部时间过程。

[0039] l(p)= p(Pd/PP)  方程1

[0040] 其中，Pd是分区的持续时间；并且，

[0041] Pp是分区的周期。

[0042] 在Pp的全局时间周期的期间，经过的局部时间为Pd，因此，我们应当将过程周期p以 Pd/PP的因子缩放比例。在应用方程1的变换之后，单级调度分析能够用于确定可调度性、分
区的利用率等。

[0043] 例如，由方程‑方程2提供分区的利用率。例如，关于分区P1的利用率，其中，上文的参数为：

[0044] ∑Ti∈LTei/pi+∑Ti∈GTei/(l(pi))  方程2

[0045] =(0.04/0.25)+(0.5/l(50))+(3/l(50))+(2/l(50))+(5/l(100))

[0046] =0.16+(0.5/(50(10/50))+(3/(50(10/50))+(2/(50(10/50))+(5/(100(10/50))

[0047] =0.16+0.05+0.3+0.2+0.25

[0048] =0.96

[0049] 由于变换后的分区中的过程为谐波的，因而针对谐波过程的可行性测试能够应用于确定分区是否为可调度的。

[0050] 图2描绘按照一些实施例的GPM 200的多级调度方案。当利用实施系统及方法来对响应时间进行分析时，能够在全局时间(而不是局部时间)的方面，呈现结果。对变换后的分
区执行响应时间分析，以获得局部时间的方面的数。

[0051] 图2从系统的全局时间视角开始，然后，描绘系统的变换后的局部时间视角。例如，假定T5的响应时间在局部时间上为19.2。P1的第二副帧的下方的箭头用图表描绘在系统的
局部时间视角上出现的情况。为了将这样的数变换成全局时间数，我们应用如下的方程‑方
程3的变换：

[0052]

[0053] 其中，t是局部时间。

[0054] 实施系统及方法将当分区不活动时经过的时间加到局部时间。以这种方式，局部时间能够变换成全局时间。为了得到对应的全局时间，应用变换方程‑方程3的过程得出：

[0055]

[0056] =19.2+40

[0057] =59.2

[0058] 如果将局部时间数投射回到系统的全局时间视角，则该结果(59.2)与预期的答案一致。

[0059] 用于计算通用设置(其中，释放时间不一定为0)中的全局时间上的响应时间的更普遍的途径是，使用方程‑方程4的公式：

[0060] g(r+l)‑g(l)  方程4

[0061] 其中，l是释放时间(局部时间)；并且，

[0062] r是响应时间(局部时间)。

[0063] 经由示例，方程4的普遍的途径允许实施方法及系统应用于同步系统和异步系统两者。由于l为0，因而应用方程‑方程4，以对过程T5进行分析的运算得出与之前相同的答
案，59.2。然而，如果l改变为5，而r依然不变，那么，局部时间响应时间依然与之前相同，为
19.2。然而，现在，响应跨越P1的三个副帧，而不是两个，因此，全局时间响应时间应当改变。
我们使用上文的公式而得到g(24.2)‑g(5)=99.2的响应时间，该响应时间比先前获得的响
应时间更大40。该增加导致从额外的副帧起的延迟。

[0064] 图3描绘按照一些实施例的调度分析系统300。调度分析系统300包括调度单元310，调度单元310包括中央控制器处理器、控制软件、存储器、时间变换单元、可调度性单元
以及一个或更多个通信端口。(多个)通信端口能够与多个过程(过程1、过程2、……、过程N)
通信，这些过程各自包括一个或更多个待调度的软件应用。过程本身能够通过相关联的数
据传感器而收集数据。

[0065] 在一个示例中，RTOS系统能够是客机上的航空电子设备系统。然而，实施系统及方法不限于此，而在所公开的系统及方法的预期和实现方案内，存在其他RTOS系统。

[0066] 机载航空电子设备系统能够包括多个过程(例如，导航、雷达、液压、座舱显示器、环境等)。这些过程中的每个过程可能具有许多不同的需要调度的正在进行的子过程。这些
子过程可能具有过程本身内的不同的优先级，并且，过程同样地可能具有不同的优先级。例
如，雷达过程的防撞子过程可能具有比天气雷达子过程更高的优先顺序；并且，雷达过程可
能具有比环境过程的客舱温度子过程更高的优先顺序。RTOS依赖于调度分析系统，从而在
同一硬件上组织多个过程及其软件应用的托管。

[0067] 调度单元的时间变换单元通过应用变换方程，从而将过程时间在局部时间与全局时间之间变换。可调度性单元确定各分区中的过程的响应时间，并且，对所有的分区执行可
行性测试，以确定调度是否为可行的‑没有过程的实例化能够错过其截止期限。

[0068] 实施系统及方法能够应用于问题的更普遍的版本，并且，能够应用于其他静态调度方案，而不仅仅应用于静态循环调度(如上文所公开那样)。

[0069] 为了支持该普遍的版本，以稍有不同的方式限定分区和GPM。

[0070] 定义5：分区是元组(LT，GT)，其中：

[0071] LT是可能为空的一组局部时间过程；并且，

[0072] GT是可能为空的一组全局时间过程。

[0073] 定义6：GPM是3元组(PS，S，fd)，其中：

[0074] PS是非空的一批分区，P1、……、Pn；

[0075] S是分区的静态调度，即，从分区至一组区间的映射，使得任何两个区间都不重叠(其中，区间可能来自同一分区，或来自不同的分区)；并且，

[0076] fd是主帧持续时间，即，GPM的主帧的持续时间。该值必须大于静态调度下的任何区间中所包含的任何数。

[0077] 术语SP用于表示与分区P相关联的区间。在区间的上确界(大于或等于区间中所包含的所有的数的最小数)之前，按递增次序对区间进行排序。我们使用基于零的指数化而用
P
表示分区P的第i个区间。因此， 是具有最小的上确界的S中的区间。

[0078] 图1中所描绘的GPM 100由一批分区PS = {P1，P2，P3，P4}组成，其中，fd = 100，并且，将分区映射至多组区间的静态调度如下：

[0079] SP1是{ [0，10)，[50，60)}

[0080] SP2是{ [10，30)，[60，80)}

[0081] SP3是{ [30，50)}

[0082] SP4是{ [80，90)}

[0083] 注意到，六个区间( ， ， ， ， ， )彼此都不重叠。还注意到，这与图1中所显示的调度精确地相对应。

[0084] 正如在此所形式化那样，赋予静态调度，以作为对实施方法的输入。实施方法还能够用作涉及使用一些其他手段来实现的对静态调度的推导的过程的一部分。例如，能够根
据对分区的约束条件而在算法上推导静态调度；在这样的情况下，可应用用于多级实时调
度分析的实施方法。

[0085] 还能够使上文中所公开的从全局时间过程至局部时间过程的变换普遍化，使得该变换能够应用于更普遍的情况。能够通过将变换方程‑方程5应用于全局过程的周期，从而
进行该变换，其中，Pd是主帧中的分区的总持续时间，并且，fd是主帧持续时间。

[0086] l(p)= p(Pd/fd)  方程5

[0087] 其中，Pd =∑i∈p的区间|i|。

[0088] 实施方法能够应用于层次调度系统，其中，顶级具有静态循环调度。方程5和下文的公开解释，还能够使实施方法普遍化，且应用于层次调度系统，其中，顶级具有任何类型
的静态调度(例如，不一定循环的静态调度)。在上文的普遍化的方面，方程5与方程1“平
行”。

[0089] 在fd(主帧持续时间)的全局时间周期的期间，经过的局部时间为Pd，因此，过程周期p以Pd/fd缩放比例。在应用变换方程5之后，能够执行单级调度分析，以确定可调度性、分
区的利用率等。例如，P1的利用率(在上文中定义P1的过程)为：

[0090]

[0091] =(0.04/0.25)+(0.5/l(50))+(3/l(50))+(2/l(50))+(5/l(100))

[0092] =0.16+(0.5/(50(20/100))+(3/(50(20/100))+(2/(50(20/100))+(5/(100(20/100))

[0093] =0.16+0.05+0.3+0.2+0.25

[0094] =0.96

[0095] 该运算与来自详述的上文的利用率运算一致。如所提到的，对于某些分析(诸如，响应时间分析)，在全局时间(而不是局部时间)的方面，更清楚地呈现结果。仍然对变换后
的分区执行响应时间分析，以获得局部时间的方面的数。为了将这些结果变换成全局时间
数，应用变换方程‑方程6：

[0096]

[0097] 其中，sup(X)是X中的区间的上确界；

[0098]

[0099] 其中，inf(X)是X中的区间的下确界‑即，小于或等于X的区间中所包含的所有的数的最大数。注意到，方程6与上文中的方程3平行。

[0100] 如果t是Pd的倍数，且大于0，那么，局部时间上的t与全局时间上的t/Pd主帧(注意到，该分数是正整数)相对应。在该情况下，t/Pd‑1主帧将经过外加分区P完成上一个主帧中
的运行所要求的时间。

[0101] 如果t不是Pd的倍数，那么，考虑t完全地覆盖的主帧的数量，且然后，确定经过的P的副帧的数量。函数F通过副帧而按顺序迭代，且保证以达到与P相关联的静态调度下的区
间的数量的时间i终止。

[0102] 再次查看先前的示例，其中，T5的响应时间在局部时间上确定为19.2。为了得到对应的全局时间，应用变换方程‑方程6的过程得出：

[0103]

[0104] =100∙0+F(19.2‑100∙0,0,0)

[0105] =0+F(19.2,0,0)

[0106] =F(9.2,1,0+50‑0)

[0107] =F(9.2,1,50)

[0108] =9.2+50

[0109] =59.2

[0110] 在释放时间不一定为0的通用设置中，更普遍的用于计算全局时间上的响应时间的方法是使用方程‑方程7的公式：

[0111] g(r+l)‑g(l)  方程7

[0112] 其中，l是释放时间(局部时间)；

[0113] 并且，r是响应时间(局部时间)。由于l=0，且g(0)=F(0,0,0)=0，因而使用公式‑方程7来对过程T5进行分析的运算得出与之前相同的答案，59.2。

[0114] 然而，如果l改变为5，且r依然不变，那么，虽然局部时间响应时间为19.2(与之前相同)，但现在，响应跨越P1的三个副帧，而不是两个。因此，全局时间响应时间应当改变。使
用方程‑方程7的过程得出g(24.2)‑g(5)=99.2的响应时间，该响应时间比先前获得的响应
时间更大40。该增加的响应时间导致从额外的副帧起的延迟。

[0115] 当调度等级的数量超过两个时，实施系统及方法也能够为可应用的。例如，分区能够进一步被细分成子分区，并且，这些子分区能够进一步被细分，导致分区的任意地较深的
层次。该层次能够被组织为树，其中，叶分区是具有与分区相关联的过程的分区。

[0116] 图4描绘按照一些实施例的多级层次调度方案400。例如，各副帧410分区P1包括两1 2 1
个子副帧420分区SP1、SP1 ，其中，SP1包括待调度的四个应用‑应用l、应用2、应用3、应用
4。能够使用任何非抢占式静态调度方案来对分区进行调度，并且，在任何情况下，能够使用
任何种类的调度，对与叶分区相关联的过程进行调度。例如，能够使用抢占式调度。由于其
组成性质‑关于分配给非常需要的分析中所涉及的分区的时间的区间的信息，而导致实施
系统及方法能够用于在此背景下执行分析。

[0117] 图5描绘按照一些实施例的多级层次调度方案500。如图4‑5中所图示的，当调度等级的数量超过两个时，实施方法能够为可应用的。例如，如图4‑5中所描绘的，分区能够进一
步被细分成子分区，并且，这些子分区能够进一步被细分，导致分区的任意地较深的层次。
如图5中所描绘的，副分区P1是由子分区Pl1、Pl2、Pl3组成的一级分区。在该示例中，这些子
分区之一是二级分区Pl3，二级分区Pl3本身同样地由子分区P131、P132、P133组成。不具有其自
身的子分区的分区被称为末端分区。在该示例中，图5中所描绘的末端分区是分区P2、P3、P4
和子分区P11、P12、P131、P132以及P133。非末端分区是层次分区，例如，分区P1和P13。然而，实
施系统及方法不限于此。在本公开的预期内，存在多级层次调度方案的其他示例。

[0118] 各末端分区可能具有其自身的调度方案，例如，分区P2能够使用速率单调(RM)调度，而分区Pl2使用截止期限单调(DM)调度，并且，分区Pl32使用最早截止期限优先(EDF)调
度。

[0119] 各层次分区可能具有其自身的静态调度方案，例如，P1能够使用定制的静态调度方案，而P13使用静态循环调度。

[0120] 定义7：末端分区是元组(LT，GT)，其中：

[0121] LT是可能为空的一组局部时间过程；并且，

[0122] GT是可能为空的一组全局时间过程。

[0123] 注意到，与上文中在定义1中定义分区的方式类似地定义末端分区。接着，能够使用定义2的扩展来定义GPM：

[0124] 定义8：GPM是3元组(PS,S,fd)，其中：

[0125] PS是非空的一批末端或层次分区P1……Pn；

[0126] S是分区的静态调度‑即，从分区至一组区间的映射，使得任何两个区间都不重叠(其中，区间可能来自同一分区，或来自不同的分区)；并且，

[0127] fd是主帧持续时间‑即，GPM的主帧的持续时间。该值必须大于静态调度下的任何区间中所包含的任何数。

[0128] 最后，定义层次分区。层次分区能够包含多个层次分区，因此，定义为自引用的，但仍然定义明确(如在归纳类型中很常见)。由于层次分区具有父代(GPM或另一层次分区)，因
而层次分区从其父代的静态调度继承能够有权使用的一组区间。

[0129] 定义9：层次分区是3元组(I,PS,S)，其中：

[0130] I是分区能够有权使用的一组区间。I必须等于从分区的父代的静态调度继承的一组区间；

[0131] PS是非空的一批(末端或层次)分区，P1，……，Pn；并且，

[0132] S是分区的静态调度，即，从分区至一组区间的映射，其受制于下文的两个约束条件：

[0133] 1.来自层次分区的分区的任何两个区间(即，P1，……，Pn)都不重叠。

[0134] 2. P1，……，Pn 的区间被包含在I的区间中。

[0135] 与层次分区的定义中的静态调度相关联的第二约束条件保证分区能够仅在分区所拥有的时间的区间的期间活动(如其父代的静态调度所定义那样)。例如，关于图5，如果
层次分区P1的区间为J={[0，10)，[50，60)}，那么，P13的区间必须被包含于J中，且不能与P11
或P12的区间(其同样地必须被包含于J中)重叠。

[0136] 按照实施例，多级调度方案能够允许分区内的组成设计。例如，在图5中，分区Pl3被分解成三个分区P131、P132、P133；其中，(例如)P131能够包含安全临界周期性过程，且使用
RM调度，而P132能够包含剩余的周期性过程，且使用DM调度。分区Pl33能够包含散发性过程，
且使用EDF调度。分区Pl31、P132和P133可能具有与拥有者不同的组而独立地工作。

[0137] 实施系统及方法使开发分区所要求的全局交互的量最小化。例如，能够独立于与分区P1相关联的其他四个末端分区Pl1、P12、P131以及P133的开发而进行分区Pl32的开发。在
标准ARINC 653的背景下，所有的这些分区都将是P1的一部分，并且，将不存在使其开发隔
离的内置式机构。

[0138] 实施系统及方法说明成本和项目管理。由于使各末端分区与其他分区隔离，因而更容易确定项目成本且追踪并管理分配给项目的人员、时间及其他资源。而且，实施系统及
方法能够使用RTOS等级保护机构来使过程之间的干扰隔离。例如，RTOS能够用于保证使不
同的末端分区中的 P13的过程隔离。

[0139] 实施系统及方法能够针对不同类别的过程而使用不同的调度方案。例如，如上所述，分区Pl3包含三个子分区，子分区各自具有不同的调度方案。

[0140] 实施系统及方法包括隐藏信息且/或制约从在分区上工作的不同的组实行的对分区的访问的能力。这样做有很多原因。例如，如果利用分包商来开发分区，那么，对分包商隐
瞒企业数据的方案可以为理想的。另一示例为在一个分区上工作的工程师不具有需要查看
与另一分区相关联的数据的空隙时。

[0141] 实施系统及方法使认证论证简化。例如，人们能够基于临界等级而将过程分组成分区。如在上文中关于图5而描述的，子分区P131是包含安全临界周期性过程且使用非常清
楚地理解的调度方案RM的分区P13的子分区。这在允许在P13的另一子分区(即，P133)中使用
动态调度(EDF)的同时，使认证论证更简单。

[0142] 实施系统及方法能够执行仅使用局部信息的多级调度的背景下的分析。由于实施方法的组成性质而导致，常见的分析仅要求关于分配给分析中所涉及的分区的时间的区间
的信息。另外，能够针对不同的分区而执行不同类型的分析。例如，使用非常严格的方法的
WCET(最坏情况下的运行时间选择)能够用于安全临界分区，并且，基于测量的方法能够用
于以温和的(而非安全临界的)性能要求分区。使用上文中所公开的公式来执行全局和局部
时间变换。

[0143] 图6描绘按照一些实施例的多级调度过程600。过程600识别各分区内的过程(步骤605)。在识别过程之后，关于各过程是局部时间中心过程，还是全局时间中心过程而作出确
定(步骤610)。对于全局时间中心的过程，执行变换(步骤615)，从而将过程转化成局部时间
过程。能够通过应用上文中所讨论的变换方程而进行该变换。

[0144] 在变换成局部时间中心之后，能够应用单级调度分析技术(步骤620)，以确定过程的参数(例如，持续时间、响应时间、优先顺序、利用率、中断状态等)。能够对分区执行可行
性测试(步骤625)，以确定分区的总体可调度性(例如，是否有可能在给定的分区上调度一
批过程，使得没有过程的实例化能够错过其截止期限)。对于分区中的过程，能够实施响应
时间分析和利用率分析(步骤630)。能够将基于局部时间的响应时间变换(步骤635)成基于
全局时间的响应时间。

[0145] 局部至全局的变换和全局至局部的变换能够用作从ARINC 653设置移动至一级调度设置的桥。这允许实施系统及方法将对于大部分而基于更简单的一级调度设置的现有的
分析转移到更复杂的二级ARINC 653设置。

[0146] 该桥接允许实施系统及方法在一级调度设置下执行可调度性分析，且将这些分析转移到ARINC 653设置。在此提出的方法能够用于任何二级或多级调度方案，并且，当使用
静态循环调度或任何其他非抢占式静态调度方案来对分区进行调度时，能够使用该方法。

[0147] 在局部时间过程与全局时间过程之间存在区别。全局时间过程具有全局时间视角，即，从过程的角度来看，时间一直流逝。与此相反，局部时间过程具有局部时间视角，即，
从过程的角度来看，仅当其分区活动时，时间流逝。该区别导致便于使用诸如高频计时器来
对过程进行建模，其中，预期当特定的分区活动时，高频计时器以特定的速率运转。实施系
统及方法支持包括局部时间过程和全局时间过程两者的分区。

[0148] 按照一些实施例，存储于非易失性存储器或计算机可读介质(例如，寄存器式存储器、处理器式高速缓存器、RAM、ROM、硬盘驱动器、闪速存储器、CD ROM、磁介质等)中的计算
机程序应用可以包括代码或可运行指令，当运行时，该代码或可运行指令可以指导且/或促
使控制器或处理器执行本文中所讨论的方法，诸如，如上所述的用于对实时操作系统的通
用处理模块的多级调度分析的方法。

[0149] 计算机可读介质可以是非暂时性计算机可读介质，其包括除了暂时传播信号以外的所有的形式和类型的存储器以及所有的计算机可读介质。在一个实现方案中，非易失性
存储器或计算机可读介质可以是外部存储器。

[0150] 虽然在本文中描述了具体的硬件和方法，但注意到，可以按照本发明的实施例而提供任何数量的其他配置。因而，虽然已显示、描述且指出本发明的基本新型特征，但将理
解到，在不背离本发明的实质和范围的情况下，可以由本领域技术人员作出所图示的实施
例及其运行中的形式和细节的各种省略、置换以及改变。也完全地预期且预计到元件从一
个实施例至另一个实施例的置换。本发明仅仅关于所附权利要求及其中的详述的等效物而
限定。