0 引言

实时系统广泛应用于航空航天、武器装备、汽车电子、医疗电子、信息通信等安全关键系统^[1]。随着片上多核以及多处理器系统的大量产业应用，多核/多处理器实时系统成为计算机系统研究领域的重要课题之一，其中，实时调度 (Scheduling) 与资源同步 (Synchronization) 是确保系统实时性的核心与关键技术。围绕多核/多处理器系统的实时调度算法与实时锁协议 (Locking Protocol) 成为实时系统领域的研究热点。近年来，学术界提出了大量实时调度算法、实时任务同步协议以及相应的可调度性分析方法。如何将新算法与已有算法的可调度性能进行快速而客观的分析比较成为亟待解决的问题。

在实时系统研究领域，一些理论指标如利用率界限 (Utilization Bound)^[2]和加速因子 (Speedup Factor)^[3]等常用于基于独立任务模型 (例如周期任务模型^[2]和偶发任务模型^[4]) 的调度算法性能评价，然而，在基于非独立任务模型的研究中，例如实时锁协议^[5-7]等领域，直接使用这些理论指标进行性能评价尚有一定困难。此外，这些理论指标可能受限于实际系统中几乎不会发生的极端情况，因而并不能全面反映具体算法在某些应用场景中的性能。为了快速比较多个算法的相对性能，分析特定因素对算法性能的影响，算法研究中往往通过设计随机实验观测算法性能的变化趋势。近年来，随机实验方法已广泛用于验证实时调度算法以及实时锁协议的可调度性能。

随机实验通常包括随机参数产生、算法逻辑实现、重复实验、数据结果统计以及图表绘制等。由于目前尚没有完整的模块化和标准化实验工具，当研究者提出新的算法时通常需要耗费大量时间重复以上过程。为了进行充分的横向比较，实验中还需要实现已有的相关算法，从而进一步增加了实验用时。此外，大量文献中所发表的实验结果均来自于作者个人或其研究小组的独立实验，实验源码通常不能公开获取，因此难以对实验结果进行验证。另一方面，现有的部分实验源码^[8-10]往往仅包含针对特定系统模型的随机数产生方法，以及针对具体算法的逻辑实现。由于系统模型的兼容性以及调用不同算法的差异性等问题，具体实验中往往难以直接重用或扩展现有代码。

基于以上背景，本文针对实时系统可调度性实验提出一种随机实验框架，并基于该框架开发了可调度性实验开源平台SET-MRTS (Schedulability Experiment Toolkit for Multiprocessor Real-Time Systems)(https://github.com/ChenZewei/SET-MRTS)。开源平台基于C++语言开发，包含了进行可调度性实验所需的完整工具，包括系统参数产生模块、算法库、实验配置模块、数据统计模块以及图表绘制模块。其中，系统参数模块提供了灵活丰富的系统参数，包括任务参数、处理器参数、共享资源参数等。用户可以基于这些参数实现各种算法并将新算法添加到算法库。算法库中的所有算法均可以重用。随机实验中，用户只需根据实验需求，在配置模块中对实验参数进行简单配置，同时选取所需比较的算法。SET-MRTS将根据配置信息进行重复实验，统计实验结果并自动绘图。SET-MRTS是第一个具备完整可调度性实验工具链的开源平台。

1 实时调度领域相关研究 1.1 相关工作

可调度性实验广泛用于实时调度算法分析与比较。文献[11]针对单处理器系统可调度性实验，提出了UUnifast算法用以随机产生均匀分布的任务资源利用率 (Utilization)。文献[12]针对多处理器系统，研究了任务资源利用率的产生方法，提出了UUnifast-Discard算法。在可调度性实验平台方面，国内尚没有开源实验平台，国际上也仅有少数研究团队发布了可调度性实验所需的部分工具。

马克斯普朗克软件系统研究所 (Max Planck Institute for Software System) 开发的SchedCAT^[8]是目前维护较活跃的多处理器可调度性实验开源工具。SchedCAT最初用于多处理器实时锁协议分析^[5]，是目前最完善的实时锁协议分析工具；然而，SchedCAT仅包含系统参数产生模块和算法库，用户必须独立设计实验流程并完成数据统计和绘图。ReTis实验室的开源工具Algorithms^[9]是针对单处理器实时调度算法的算法库。该工具仅包含UUnifast算法以及实现单处理器可调度性分析的Matlab函数，而缺乏支持完整随机实验所需的其他模块。意大利系统分析与计算机科学研究所 (IASI) 发布的多处理器可调度性判定工具C++ Exact Multiprocessor Feasibility/Schedulability Tools^[10], 但仅用于判断某个给定任务系统的可调度性，尚不支持批量化随机实验。此外，一些研究团队发布了实时调度仿真开源工具，如YAO-SIM^[13]、RTSIM^[14]、PartiCor^[15]、TrueTime^[16]等。然而，调度仿真仅能够作为系统不可调度的充分条件，不能直接用于评价可调度性分析方法的性能。本文推出的开源工具平台SET-MRTS包含了可调度性实验所需的完整模块且易于扩展，可直接用于可调度性实验。

1.2 可调度性判定

常用的可调度性分析方法包括响应时间分析法 (Response-Time Analysis, RTA) 和资源利用率界限判定法。

1.2.1 基于响应时间分析的判定

定义1    任务τ_i的第j个任务实例记为J_{i, j}。令J_{i, j}的释放时间为r_{i, j}，完成时间为f_{i, j}，则响应时间R_{i, j}为：

$ {R_{i,j}} = {f_{i,j}} - {r_{i,j}} $

(1)

任务τ_i的最坏响应时间 (Worst-Case Response Time, WCRT)R_i为τ_i的所有任务实例的响应时间的最大值，即：

$ {R_i} = \mathop {\max }\limits_{\forall j} \max {R_{i,j}} $

(2)

根据经典RTA分析框架^[17]，R_i可进一步表示为：

$ {R_i} = {C_i} + {B_i} + {I_i} $

(3)

其中:C_i为τ_i的最坏执行时间 (Worst-Case Execution Time，WCET)，B_i为τ_i的最坏阻塞时间 (Worst-Case Blocking Time, WCBT)，I_i为τ_i的最大抢占延迟 (Interference)。R_i的具体计算方法由具体调度算法、锁协议以及可调度性分析方法决定。

若计算法所得的R_i不大于τ_i的相对截止时间，则称该任务可调度。若任务系统中所有任务均可调度，则称该任务集合可调度。

1.2.2 资源利用率界限判定法

资源利用率界限判定法常用于隐式截止时间 (Implicit Deadline) 周期任务系统。令τ_i的最坏执行时间为C_i，相对截止时间为D_i，周期为T_i。τ_i的相邻两个任务实例的时间间隔为T_i，且T_i=D_i。任务τ_i以及任务系统的资源利用率定义如下。

定义2    任务τ_i的资源利用率u_i如式 (4) 所示，任务系统Γ的资源利用率U如式 (5) 所示:

$ {u_i}\underline{\underline {{\rm{def}}}} {C_i}/{T_i} $

(4)

$ U\underline{\underline {{\rm{def}}}} \sum\limits_{{\tau _i} \in \mathit{\Gamma }} {{u_i}} $

(5)

一个调度算法A的资源利用率界限为U_A，则可确保任意资源利用率小于等于U_A的任务系统在算法A中可调度。例如，在单处理器系统中最早截止时间优先 (Earliest Deadline First，EDF) 算法的利用率界限为1，则对于任意资源利用率不大于1的隐式截止时间周期任务系统，EDF算法能够确保该任务系统可调度。

2 平台设计与实现 2.1 平台设计需求

SET-MRTS的设计目的是提供一个功能完善、兼容性强、易于扩展的可调度性实验平台，用户无需二次开发便可使用该平台进行可调度性实验。当需要对算法库中尚未建立的算法或分析方法 (如新提出的方法) 进行实验时，开发者仅需实现该方法即可与算法库中所有方法进行比较。

2.2 平台模块设计

为了实现上述设计需求，采取了高内聚、低耦合的模块化设计方法。SET-MRTS主要包括任务模块、处理器模块、共享资源模块、配置解析模块以及输出模块。其中，任务模块、处理器模块与共享资源模块之间具有关联关系。例如，在分组调度 (Partitioned Scheduling) 算法可调度性实验中，处理器模块中需要维护分配到各处理器上的任务信息；而在实时锁协议可调度性实验中，任务模块也需要维护每个任务所访问的共享资源信息。此外，各子模块间还存在聚合或组合的关系。平台的结构图 (类图) 如图 1所示 (空心菱形为聚合关系，实心菱形为组合关系，箭头为关联关系)。

任务模块是SET-MRTS中的重要模块，由任务类、任务集合类以及共享资源请求类所构成。其中，任务类 (Task) 描述了可调度性分析方法中所使用的所有随机任务参数，包括了任务的最坏执行时间 (WCET)、相对截止时间 (Deadline)、周期 (Period) 和共享资源请求 (Request) 等主要属性。新的任务将被加入任务集合中，组成一个任务系统。通过任务集合类 (TaskSet) 可以获得系统资源利用率 (get_utilization_sum)、最大任务资源利用率 (get_utilization_max) 等，并且可以根据某一属性对任务进行排序 (sort_by_xxx)，使任务系统能够灵活地调整，为各种可调度性分析方法的实现提供了方便。此外，每个任务还通过共享资源请求类来表示对共享资源的访问。

处理器模块则包括通过处理器类和处理器集合类。处理器类用于描述实验所使用的处理器模型，包括各处理器的执行速率 (Speedfactor) 以及处理器系统的规模 (核心数量，core_num) 等。处理器集合 (ProcessorSet) 类则用于表示处理器平台的组成。虽然SET-MRTS现在主要用于同构多处理器下可调度性分析方法的测试，但也为异构多核/多处理器平台与可并行任务模型下的实时任务调度分析提供了基础。

共享资源模块主要用于实时调度领域中的实时锁协议分析，如多处理器优先级天花板协议 (Multiprocessor Priority Ceiling Protocol, MPCP)^[18]、分布式优先级天花板协议 (Distributed Priority Ceiling Protocol, DPCP)^[19]和多处理器堆资源协议 (Multiprocessor Stack Resource Protocol, MSRP)^[20]等。该模块由共享资源类与共享资源集合类所组成，其中共享资源类对共享资源进行了抽象描述，包括了共享资源号、共享资源的全局性 (global_resource) 以及访问该共享资源的任务队列 (TaskQueue) 等。共享资源类通过共享资源集合类 (ResourceSet) 进行封装。通过该模块可以描述整个系统的共享资源，并且与各个任务建立访问关系，从而实现共享资源的优先级天花板 (Priority Ceiling) 查询以及任务的阻塞时间分析。

以上3个模块是SET-MRTS的核心组成部分，也是可调度性分析所依赖的基本结构。通过对这些模块进行操作，能够规范实验流程，确保实验平台可调度性分析方法的兼容性与可扩展性。

此外，随机实验参数设置也是实验流程的重要环节。SET-MRTS采用配置文件的方式实现实验参数的输入。参数配置模块通过实现一个解析类对使用XML格式的配置文件进行解析，并存放在指定的参数结构中。如图 1的配置模块中，XML类通过get_integers函数来提取配置文件中指定元素的整型参数集合。用户仅需要对配置文件进行配置即可进行实验。通过参数配置模块能够有效提高参数输入的效率。随着SET-MRTS的不断拓展与更新，会有更多的参数需要输入，配置模块能够保证参数的拓展不影响平台的兼容性。

目前已知的其他开源平台仅提供实验结果的在线输出，或通过文本格式保存实验统计结果，用户需要对该结果进行整理，才能够得到更加直观的实验结果。SET-MRTS的输出模块不仅能够在实验结束后以文本格式保存实验结果 (通过Output类)，还能够根据配置生成对应的折线图 (通过Chart类)，并保存为位图或矢量图，从而为研究者提供更直观的实验统计结果。

2.3 实验流程 2.3.1 实验流程

实验中，SET-MRTS通过参数输入模块建立实验场景，然后根据可调度性分析方法围绕任务模块、处理器模块以及共享资源模块进行相应操作，并输出实验统计结果。实验开始时，通过XML类提取配置文件中的参数并保存于Param类的实例中，并以此参数建立实验场景，例如处理器种类与数量、生成共享资源实例以及产生任务系统等。接着，测试所选可调度性分析方法在以上实验场景中的可调度率，并进行重复实验。最后，统计各算法的性能指标 (如可调度率) 并通过输出模块输出实验结果。整体实验流程如图 2所示。

2.3.2 参数配置

SET-MRTS使用XML结构化语言描述实验参数，并通过配置文件进行参数配置。用户可以配置随机实验参数的产生规则，如任务资源利用率均值、任务系统资源利用率取值范围，以及任务集合资源利用率取值的步长等。配置文件支持整型、浮点型、字符型参数的输入，并支持多组数据的组合输入。实验参数配置示例如下所示：

<?xml version="1.0" encoding="UTF-8"?>

<parameters>

    <schedulability_test>

        <data TEST_TYPE="0">WF-DM</data>

        <data TEST_TYPE="1">WF-DM</data>

    </schedulability_test>

    <step>        //实验中任务系统资源利用率增长的步长

        <data>0.2</data>

    </step>

    <experiment_times>100</experiment_times>

    <init_utilization_range>

        <data>        //任务系统资源利用率范围

            <min>0</min>

            <max>4</max>

        </data>

    </init_utilization_range>

…

</parameters>

2.3.3 任务系统产生

SET-MRTS使用随机分布产生任务的属性。根据配置文件中设置的参数产生范围，使用基于均匀分布和指数分布等随机数产生方法随机产生任务周期、任务最坏执行时间、任务截止时间、任务资源利用率等参数；同时，记录每个任务集合的任务数、任务系统资源利用率等参数。该流程伪代码如下：

uniform_gen (int min, int max)

//产生在min和max之间的均匀分布随机数

exponential _gen (int lambda)

//以lambda为率参数产生指数分布随机数

while (current_utilization < utilization_bound)

{

    period=uniform_gen (u_min, u_max);

    deadline=uniform_gen (d_min, d_max) * period;

    utilization=exponential_gen (lambda);

    if (current_utilization+utilization>utilization_bound);

    {

        utilization=utilization_bound-current_utilization;

    }

    wcet=period * utilization;

    taskset.add_task (wcet, deadline, period);

}

2.3.4 共享资源访问

共享资源是实时锁协议分析中的重要结构。任务所需要访问的共享资源集合、任务访问每个共享资源的最大次数以及最长访问时间是计算任务阻塞时间的主要依据。SET-MRTS采用访问概率来决定任务对共享资源的请求，该流程的伪代码如下：

calculate_total_len ()        //用于计算访问总时长

add_request ()        //用于将共享资源访问申请添加至任务

add_task ()        //用于将该任务添加到共享资源访问队列

probability (double P)        //以概率P为真

foreach (resource in resource_set)

{

    if (probability (request_prob))

    {

    request_num=uniform_gen (1, num_max);

    max_len=uniform_gen (len_min, len_max);

    total_len=calculate_total_len ();

    task.add_request (request_num, max_len, total_len);

    resource_set.add_task ( & task);

    }

}

任务创建时将遍历共享资源集合，根据配置文件中设置的共享资源访问概率随机确定是否访问某个共享资源，并通过随机分布函数产生其他属性。

2.4 平台扩展性

SET-MRTS具有良好的兼容性与可扩展性。实验平台能够方便地实现新的可调度性分析方法并能够与已实现的方法进行比较。分析者只需要按照各模块的格式实现新的算法并添加到算法库中，便能够通过配置文件随意选择算法库中的算法进行实验比较。在实验平台的设计和实现中，采取了模块化的方法来设计和实现平台的任务、处理器和共享资源模块。各模间通过清晰的接口连接，从而方便设计者实现新的算法。随着本平台功能的扩充，将支持更多的可调度性分析方法。

3 实验与分析

以下通过两个简单的实验来验证SET-MRTS的功能。实验一针对独立任务模型，不包含实时锁协议的分析，因此没有配置共享资源参数。实验二则分别对基于自旋锁和信号量机制的实时锁协议进行分析。实验二中测试了共享资源访问概率对可调度率的影响。两个实验均采用了同构多处理器模型，所有处理器的执行速度均相同。

3.1 实验配置

表 1列出了实验一所使用的主要参数。

3.2 实验结果与分析

以经典可调度性分析方法为例进行可调度性实验，由实验平台所导出的折线图结果如图 3所示。

实验一的结果如图 3所示，展示了独立任务模型中多种分析方法的可调度率 (Ratio) 随系统资源利用率 (TaskSet Utilization) 的变化趋势。其中，RTA-GFP表示基于全局固定优先级调度的响应时间分析，其后缀则表示分析方法的不同版本，[native]为文献[21]的响应时间分析方法，[bc]则是Bertogna和Cirinei提出的改进方法^[22]，[gn]则是由Guan等所提出的分析方法^[23]。WF-DM和WF-EDF表示分组调度中采用Worst-Fit (WF) 算法进行任务分配的可调度率。其中，DM和EDF分别表示采用单调截止时间 (Deadline-Monotonic) 算法^[24]以及最早截止时间优先 (Earliest Dealine First, EDF)^[2]算法进行任务调度。图 3所示的各算法可调度率变化趋势与相应理论分析的结论一致。

实验二对多处理器环境下基于自旋锁机制^[20]和信号量机制^[25-26]的实时锁协议作对比实验，图例中为使用自旋锁机制的可调度性测试，则使用了信号量机制，并使用无共享资源的可调度性测试作为最优参照组。实验中所使用的参数配置与表 1保持一致, 而对于产生共享资源的主要参数配置则如表 2所示，实验结果如图 4所示。

4 结语

本文针对实时系统设计中的可调度性分析技术，提出了一种可调度性实验框架，并基于该框架设计实现了一个新的可调度性实验开源平台SET-MRTS。该平台基于模块化设计原则，提供了可调度性实验所需的完整功能模块。SET-MRTS是第一个提供从算法实施、参数配置、随机实验、结果统计到自动绘图全过程支持的可调度性实验开源平台。对图模型分析的支持和异构多处理器平台的可调度性分析是SET-MRTS下一步的工作重点。