浅析周期性任务系统调度的MCS任务模型

陈洪琪 涂珍 王志军

摘要：随着技术的发展，嵌入式实时系统处理能力飞速提升，如汽车和飞机的电子系统集合了数百个处理器。受嵌入式系统体积和能耗等方面制约，许多原来不同子系统（组件）中的关键性应用被共享到单个处理器（硬件）平台中，这就导致混合关键系统（简称MCS）的出现。

关键字：MCS；系统模型

一、MCS现状分析

如今，已有的调度策略能一定程度上提升系统的可调度性，但依然存在许多问题：其一，很多策略是基于单核平台，不能直接应用于多处理器之间的任务处理；其二，任务模型大多基于周期性任务或偶发性任务，忽略了兼容周期性与偶发性两种形态的存在；其三，主要目标为关键性任务的成功率，忽略了其他系统指标和有效利用率。

周期性任务系统调度方法研究的MCS系统模型提出了基于多核平台的任务调度策略，使系统不仅获得较高的成功率，还具备较强的综合性能，能有效利用已有的硬件环境。

二、MCS趋势分析

MCS具有不同关键性等级的任务，下面对其系统模型和代表性调度策略进行分析。

Vestal等首先利用形式化提出了MCS系统任务模型，系统由k个组件的有限集合来表示，每个组件拥有一个关键性级别记为L。任务τi是一个四元组组成：τi=（Ti，Di，Ci，Li），其中：Ti、Di、Ci和Li分别为任务τi的周期、截止期、估算执行时间和关键性级别。

由于许多任务参数与关键性级别没有太多联系，如最坏估算执行时间（WCET，Ci）。随着关键性级别越高，Ci的数值越大，但其准确数值难以估算，估算WCET需要花费大量的系统资源，会导致MCS系统中的资源浪费。

Baruah等从任务执行时间和周期与关键性级别关系的角度改进了MCS任务模型，任务τi是一个四元组组成：τi=（Di，Li），其中分别为表示执行时间和周期的向量，对于任意两个关键性级别L1、L2，关键性级别高的任务，具有更高的估算执行时间、周期以及更大数值的截止期。

三、MCS研究意义及目标

由于多核平台的普及，原有的基于單核环境的MCS系统资源共享策略不再适用。为此，需要研究适用于多核环境以及兼容周期性任务和偶发性任务的资源共享策略，在保证高关键性和高优先级任务获得资源的前提下，提高系统资源利用率。具体如下：

首先，防止出现高关键性倒置问题。MCS系统与一般实时应用环境的区别在于：系统中混合着不同关键性级别的任务，如果低关键性任务阻塞了高关键性任务的资源请求，那么可能会影响整个系统的安全性。

其次，防止出现优先级倒置问题。传统实时环境下防止出现优先级倒置可采用优先级继承、优先级思想等方法。同时，为了执行的逻辑正确性及数据的一致性，可引入基于封锁的思想。

最后，注意多核平台下的资源利用和负载均衡。单核实时系统下的资源共享策略的高利用率一般是以保证高优先级（及高关键性）任务执行为前提，如果出现更紧急的任务则在前者的空闲时间内执行，MCS系统也是此思想。另外，多核平台下系统在资源分配时，必须尽量使各个处理器上执行的任务都能获得资源，利用排队论M/M/1模型来分配任务集到处理器上，并允许任务能够在不同处理器上进行迁移，从而充分均衡地利用平台资源。

多核平台下MCS系统任务处理机制需解决的关键问题包括：一种周期性任务系统调度多核平台任务模型、针对周期性任务模型构造任务的优先级分配函数、基于优先级继承的资源共享等。

由于MCS的并发控制和任务调度都是基于优先级驱动的，因此优先级分派极为重要。已有的MCS较少考虑除截止期之外的因素。本项目的优先级分配问题具体考虑如下：

首先，任务关键性与优先级的关系。为了保证高关键性任务的优先执行，在同等时间性特点下，高关键性任务应被赋予更高的优先级。

其次，任务价值密度。为了量化任务完成给系统带来的收益，优先级分派应考虑任务的价值密度因素（即单位时间所具有的价值）。根据已有的实时调度策略，价值密度可根据数值特性分为静态价值密度和动态价值密度两种形式。

最后，综合构造优先级函数。为了体现系统综合性能，在优先级分派时应结合执行时间、空闲时间和关键性级别等因素，动态多维度地构造分派函数，优化函数模型。

四、MCS研究内容

根据已有的MCS调度策略研究结果，对多核环境下的MCS采用划分调度思想，对分配到具体处理器上的任务采用基于抢占阈值的调度方法。主要研究内容如下：

第一，实时任务的排序。在将任务分配到具体处理器之前，需要对任务集进行排序，尽量将特征相近的任务分配到同一个处理器上。考虑关键性级别的因素，MCS在任务排序和处理器选择时可以按关键性排序。

第二，处理器的选择。针对排序之后的任务子集，可以利用启发式策略将其分配到处理器，以达到更好的可划分性能。

第三，单处理机上实时调度策略。由于任务子集是在单处理器上执行的，因此可以采用基于单处理器的调度策略，即基于优先级驱动的策略。

参考文献

[1]黄经州.开放式混合实时系统调度策略研究[D]. 浙江师范大学，2009.

[2]谷传才，关楠，于金铭，等.多处理器混合关键性系统中的划分调度策略[J]. 软件学报，2014（2）：284-297

[3]佟欣. 嵌入式实时系统的混合调度算法研究[D]. 沈阳工业大学，2010.