复杂实时系统可调度性判定工具的研究与实现

张永悦，孙 瑜，李 允，徐建华

(1.云南师范大学信息学院，昆明 650500；2.西南交通大学信息科学与技术学院，成都 610031；3.电子科技大学计算机科学与工程学院，成都 610054)

1 概述

随着计算机技术的飞速发展，嵌入式系统已广泛应用于各科技领域及日常生活的每个角落。为了满足航空航天等关键领域的嵌入式系统强实时性的要求、精确管理系统时间资源，在系统设计阶段采取相应的方法，对系统任务集进行可调度性判定相当必要。因而，自动化、精准化、高效化判定工具的开发颇具意义。为此，本文提出一种基于仿真方法的任务集可调度性判定工具，用来判定任务集是否具备可调度性。

2 调度理论的相关研究

2.1 调度模型

在任务集可调度性判定的相关研究中，通常所提及的调度模型是一种理想的调度模型，其必备的要素有：调度策略，任务属性参数(执行时间、截止时间限、周期/非周期触发方式)等[1-2]。

随着航空电子应用软件标准接口的制定[3]，分区调度模型的相关研究逐渐成为调度理论研究的热点。相比普通调度模型，分区调度模型增加了分区时间片的约束。分区系统中系统时间资源被划分成多个分区，特定的分区下运行指定的任务集，任务集只有在所在分区获取时间片后才能调度执行，时间片用完后等待下一次时间片的获得。

2.2 可调度性判定方法

在当前的阶段，可调度性判定工具主要采用形式化(时间自动机)方法和仿真方法实现。前者依据穷尽搜索的方法实现，存在状态空间爆炸问题，调度能力有限；后者则采用仿真执行过程的方法实现，判定效率较高，但只能分析拥有确定调度抢占过程任务集的可调度性，适用于纯周期任务集可调度性判定工具的实现。

2.3 复杂实时系统的可调度性判定

2.3.1 复杂实时系统调度模型

基于上述研究，结合现阶段复杂嵌入式系统的特性，提出一种复杂实时系统混合调度模型的可调度性判定工具。该混合调度模型是一种多处理器的系统构架，系统中可以含有多个处理器，各个处理器可挂载不同的任务结构，如分区任务集合、普通任务集合。混合调度模型如图1所示。

图1 复杂调度模型图示

2.3.2 可调度性判定依据

上述混合调度模型包含普通调度模型和分区调度模型，且约定每种调度模型下的任务都是周期任务。文献[4]给出了纯周期任务集的特性及相关证明：纯周期任务集合中所有任务都是周期任务，每个任务的到达都成周期性，所有任务的到达在整体上也呈现周期性，周期值为所有任务周期值的最小公倍数。

现阶段可调度性判定过程中，主要针对2类调度策略进行研究：静态优先级调度策略和动态优先级调度策略。并约定当采用这2种调度策略计算任务优先级过程中遇到多个任务优先级相同时，设计者自定义二级调度策略区分任务的优先级。本文约定当出现优先级相同时，任务列表中编号小的任务优先级高，这样便唯一确定了任务的抢占方式及抢占顺序。

由上述结论可知，普通调度模型下任务集中所有任务在调度过程中的到达、抢占、执行、完成是一个确定的路径且整体上呈周期性，周期值为所有任务周期值的最小公倍数(mul)。同理，分区调度模型的周期值为所有任务周期值与任务集所属分区获取时间片的周期值的最小公倍数(mulpart)。此时，只需分析一个周期值时钟区域内任务集的调度情况，即可等价判定任务集整个调度过程的可调度性。因此，采用仿真方法判定含有纯周期任务集的混合调度模型的可调度性是可行的、确定的。

2.3.3 仿真实现过程

定义变量X为系统时钟，设置一个周期的仿真区域。当待分析的处理器下挂载普通调度模型时，默认任务集中所有任务都在0时刻到达，系统时钟从0时刻开始计时，并以步长为一个时间单位增加系统时钟值，模拟任务集的调度过程，系统时钟的仿真区间为[0,mul]。当待分析的处理器下挂载分区调度模型时，默认当前处理器中所有分区下的所有任务都在所属分区第一次获得系统时间片的时刻到达，系统时钟区域长度为 mulpart。针对上述 2种调度模型，在模拟过程中系统时钟每增加一个时间单位，根据任务到达、抢占的情况更新所有任务的执行时钟、响应时钟、状态，依据任务超时条件判定任务的可调度性，从而判定任务集的可调度性。

3 核心实现及性能分析

3.1 工具整体框架

本文研究的复杂调度模型的可调度性判定工具包含3个主要功能模块：调度模型编辑模块，调度结果判定显示模块，调度过程的甘特图显示模块。调度模型编辑模块提供用户自定义调度模型的建立。调度结果判定显示模块能自动提取用户输入的调度模型参数及调度策略，调用相应的判定算法，自动、准确、快速地给出任务的可调度性判定结果及所有任务的最坏响应时间。调度过程显示模块实现了以甘特图的方式单步或连续地模拟显示任务集的调度过程，便于验证工具判定结果的正确性。

该工具支持的调度策略有：单调速率调度策略(Rate Monotonic Scheduling, RMS)，短截止时间限优先策略(Deadline Monotonic Scheduling, DMS)，固定优先级调度策略(Fixed Priority Scheduling, FPS)，相对短截止时间限优先策略(Earliest Deadline First,EDF)。其中，前3种为静态优先级抢占策略，最后一种为动态优先级抢占策略。工具的整体结构框图如图2所示。

图2 可调度性判定工具的结构框图

3.2 任务模型

定义 T = {t1, t2,… ,tn}为一个含有n个周期任务的任务集，任务由 ti=(Ci, Ti, Di, Ei, Wi, Li, P)表示。其中，Ci为任务ti的执行时间；Ti为任务的周期；Di为任务的截止时间；Ei为任务ti的执行时钟，只有当任务处于运行状态时，执行时钟才开始计时；Wi为任务ti的响应时钟，当任务请求到达时，响应时钟开始计时，直到任务执行完成；Li为任务ti的当前状态，所有任务在调度过程中都有4个状态：挂起(Suspend)，就绪(Ready)，执行(Running)，超时(Error)。

当任务所在系统为分区系统时，P为任务所在分区。 P =(P t, P c, o ffset )，其中，Pt为分区获取系统时间片的周期；Pc为分区获取时间片的长度；offset为分区第一次获取时间片的系统时钟偏移量。

任务ti在调度时的状态迁移过程(默认任务集中编号小的任务优先级高)如图3所示。

图3 任务状态转换图

图3中任务抢占时的状态迁移描述如下：

(1)Readyi->Runningi描述任务ti由就绪态迁移到运行态。本文研究的复杂调度模型中包含普通调度模型和分区调度模型。针对分区调度模型，当任务所在分区获取系统时间片(即 PartObtainSystem Time为真)，并且所有比此任务优先级高的任务都未到达时，该任务获取 CPU资源，迁移到运行状态开始执行。针对普通调度模型时，默认任务集永远占有 CPU资源，迁移条件与分区调度模型相同，只需设定PartObtainSystemTime始终为真即可。

(2)Runningi->Readyi描述任务ti由运行态迁移到就绪态。分区调度模型下任务ti执行过程中，所在分区未获得系统时间片用完时(即 PartObtain SystemTime为假时)，或者同分区下较高优先级任务到达时，当前任务转向就绪状态，释放 CPU资源。普通调度模型的迁移条件与分区调度模型相同，只需设定PartObtainSystemTime始终为真即可。

3.3 可调度性判定算法

分区任务集可调度性判定算法如下：

输入 任务集合列表 TaskList[n]，任务所在分区获取时间片的相关属性

输出 任务集可调度性isScheduler(true, false)；任务最坏响应时间列表TaskWT[n]

步骤 1 初始化任务集合列表中所有任务的参数(执行时钟、响应时钟、系统时钟、任务状态)，计算分区任务集的仿真区间长度mulpart。

步骤 2 将任务集合列表中的任务按优先级从高到低排序，sort(TaskList[n])。

步骤 3 判定当前系统时钟 X时刻，任务集可调度性：

(1)判定任务列表中当前任务ti的可调度性

1)更新当前任务ti的状态Li、执行时钟Ei、响应时钟Wi：

①如果 Li== "Suspend"&& X %Ti== 0，任务到达，状态迁移时钟计时( Li= "Ready",Wi++)。

②如果ti处于就绪状态( Li= "Ready")，任务获取时间片(PartObtainSystemTime==true)，并且所有较ti优 先 级 高 的 任 务 都 未 到 达 时( ∀j = 1,2 … ,i −1,Lj== "Suspend")，ti开始运行，状态迁移时钟计时( Li= "Running",Ei++,Wi++)。

③如果 Li== "Running"，任意一个较ti优先级高的任务到达时( ∃j = 1,2,… ,i − 1,Lj=="Ready")，或者Part ObtainSystemTime==false时，任务ti由运行态转向就绪态( Li= "Ready",Wi++)。

④如果 Li== "Error"，当前任务不可调度，任务集不可调度(isScheduler=false)，跳转到步骤5。

2)如果ti执行完成( Ei== Ci&&Wi＜= Di)，时钟清零，计算任务响应时间，比较以往所有次响应时间，将最大值存入TaskWT[i]中。

3)如果ti超时( Ei＜ Ci&&Wi== Di)，ti不可调度，任务集合不可调度，设置isScheduler=false，跳转到步骤5，否则跳转到(2)。

(2)i++，如果 i>n，跳转到步骤 4，否则，跳转到(1)。

步骤 4 如果任务集采用动态优先级调度策略(EDF)，重新排序任务集合 sort(TaskList[n])；X++，如果X>mulpart，跳转到步骤5，否则，继续步骤3。

步骤5 如果isScheduler==true，输出任务集可调度、输出任务集最坏响应时间列表TaskWT[n]；否则，输出任务集不可调度，判定过程结束。

上述判定算法的时间复杂度为 O(taskNum×mulpart)，将上述算法中系统时钟仿真上限更改为mul，设定PartObtainSystemTime参数始终为真值时，即变更为普通模型可调度性判定算法。

3.4 工具性能分析

该工具的判定效率数据在简单调度模型判定工具文献中详细列举。文献[5-8]也分别对RMS及EDF调度策略下任务集可调度性判定算法进行研究，但均未涉及分区约束。文献[9-10]对分区调度算法进行了相关研究，提出了合理利用空闲时间片的方法，但并未过多涉及分区调度模型的可调度性判定问题。

相比上述文献的相关研究，本文的可调度性判定工具提供更友好的用户操作界面；更强的复杂模型判定仿真能力，能判定单处理器、多处理器、多分区之间任意组合的调度模型，适用于复杂嵌入式系统的需要。

4 实例分析

假定待判定系统含有2个处理器CPU1和CPU2。CPU1下挂载分区调度模型，模型中包含3个分区，每个分区下挂载各自的任务集合；CPU2下挂载普通调度模型。

CPU1下3个分区获取时间片情况如表1所示。各分区下挂载的任务集合、调度策略、任务属性参数如表2所示。CPU2下挂载普通调度模型，调度模型中任务的属性参数、调度策略如表3所示。

表1 CPU1下分区时间片分派情况

表2 CPU1下各分区挂载任务的属性参数

表3 CPU2下任务集中任务属性参数

图4描述了上述系统中2个处理器下所有调度单元的调度结果及甘特图仿真结果。结果显示，CPU1中分区 PART1下的任务集可调度，各任务的最坏响应时间分别为6、7、6；分区PART2下任务集可调度，各任务的最坏响应时间分别为 3、34；分区 PART3下的任务集合不可调度，任务执行过程超时。CPU2下任务集可调度，任务集中3个任务的最坏响应时间分别是 3、4、8。

图4 复杂调度模型的可调度性判定及甘特图仿真结果

对比各调度模块下的甘特图仿真结果可知，可调度性判定工具的分析结果准确无误。该甘特图仿真结果验证了纯周期任务集的特性、动态优先级抢占策略EDF的特性、分区调度模型的特性。如：CPU2下任务集调度的甘特图仿真结果显示，在区间[0,60]与区间[60,120]中任务集的调度过程完全一致，满足纯周期任务集的特性；CPU1中分区 PART1下任务集及CPU2下任务集调度的甘特图仿真结果，准确无误地显示了不同时刻下各个任务的优先级动态变化情况；CPU1中分区PART1、PART2、PART3中任务集调度的甘特图仿真结果同样显示了分区调度模型的特性，分区下的任务只有在所属分区获取时间片的时钟区域内调度执行，在调度过程中当所在分区时间片用完时，只有等待分区下一次获取时间片时才能继续任务执行过程。

5 结束语

本文基于仿真方法实现了含有多处理器、多分区复杂实时系统的可调度性判定工具，阐述了工具核心模块构成及核心算法的实现过程，并通过实例验证了工具的可调度性判定结果和仿真过程的正确性。涉及分区间任务抢占、多处理器之间存在触发关系的模型调度问题是下一步的工作重点。

[1]Liu C L, Layland J W.Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment[J].Journal of the ACM, 1973, 20(1): 46-61.

[2]王永吉, 陈秋萍.单调速率及其扩展算法的可调度性判定[J].软件学报, 2004, 15(6): 799-814.

[3]Airlines Electronic Engineering Committee.ARINC 653P1-3-2010 Avionics Application Software Standard Interface Part1——Required Services[S].2006.

[4]Leung J Y T, Merrill M L.A Note on Preemptive Scheduling of Periodic, Real-time Tasks[J].Information Processing Letters, 1980, 11(3): 115-118.

[5]刘军祥, 王永吉, Cartmell M.一种改进的RM可调度性判断算法[J].软件学报, 2005, 16(1): 89-100.

[6]刁 承, 虞慧群.改进的单调速率调度算法[J].计算机科学与探索, 2011, 5(6): 562-568.

[7]李 琦, 巴 巍.两种改进的 EDF软实时动态调度算法[J].计算机学报, 2011, 34(5): 943-950.

[8]张 杰, 阳富民, 卢炎生, 等.EDF统一调度硬实时周期任务和偶发任务的可调度性判定算法[J].小型微型计算机系统, 2009, 30(12): 2383-2388.

[9]何 峰, 宋丽茹, 熊华钢.航空电子双层任务分区调度设计[J].北京航空航天大学学报, 2008, 34(11): 1364-1368.

[10]李昕颖, 顾 健, 何 峰, 等.硬实时系统在强分区约束下的双层分区调度[J].计算机学报, 2010, 33(6):1032-1039.