英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
种基于限制带入任务对于全局最早截止日期优先调度的响应时间分析
摘要：
本文解决了在多处理器平台上的最早截止日期优先（G-EDF）策略下的偶发性任务的可调度性分析问题。目前研究水平下，多处理器全局调度策略的可调度性分析测试通常是不可比较的。即，被一个可调度性测试判断为无法调度的任务集可以被另一个测试确认为可以调度的，反之同理。
在本文中，我们首先提出了一种新的对于全局EDF算法的可调度性测试，该测试方法综合限制带入任务（limited carry-in）技术和响应时间分析（RTA）过程。然后，我们提出了此测试具有更好的运行时效率的变形方法。之后，将这两个测试扩展到的自挂起式任务。本文提出的所有可调度性测试都比目前相对应最新技术具有可证明的优势。
最后，本文在不同的可调度性测试之间进行了广泛的比较。结果显示本文提出的测试方法对全局EDF算法的可调度性分析的有显着改进。
- 引言及现有技术
全局调度策略是多处理实时调度系统中重要的一类调度策略。全局调度策略中，所有的就绪任务都在一个队列中等待，具有最高优先级的m个任务在m个处理器上执行。在可抢占式的全局调度中，一个任务可以被比它具有较高优先级的任务打断，并且之后可以在不同的处理器上恢复执行：所以也称这一类的调度策略允许任务的迁移。在Linux操作系统中的对比试验表明全局配置是对多处理器平台的一个可行方案[18]。
最常见的两个全局调度算法是全局固定优先级（Global Fixed Priority ,G-FP) 及全局最早截止时间优先（Global Fixed Priority (G-FP) and Global Earliest DeadlineFirst (G-EDF)。在G-EDF调度中，任务的优先级是与它的截止时间成反比，较小的绝对截至时间对应更高的优先级。
对于在多处理器平台上的一组利用全局调度策略的偶发实时任务的可调度性测试是一个具有挑战性的问题。 与单处理器情况不同，在多处理器全局调度中，任务的最坏情况的释放模式是未知的。因此，任何对于全局调度的一组偶发性任务的可调度性精确测试都需要大量任务释放模式。
Baker和Cirinei[3]提出了第一个精确的可调度性分析方法，他们构建了一个有限状态机，表示到达时间和执行时间间隔的所有可能组合。Bonifaci等人[10]将偶发任务简化为安全博弈，研究了偶发任务在多处理器中的可行性问题。Geeraerts[13]等人使用反链(anti-chain) 技术改进了Baker和Cirinei的方法。更具体地说，他们建立了有限自动机状态之间的仿真关系。Sun和Lipari[21]最近利用连续时间和线性混合自动机提出了一种类似的方法。然而，由于任务释放模式的数量呈指数增长，所有这些解决方案都存在可扩展性差的问题。
由于这个原因，大多数研究人员关注于导出近似分析，即可调度性的充分条件。如果任何一个被可调度性判定条件A接受的任务集(即认定为可调度的任务集)都能被判定条件B接受，并且存在某些任务集可以被判定条件B接受而不能被A接受，那么称判定条件B优于性判定条件A，记为
Baker[1]基于问题窗口概念的提出了一种复杂的分析技术。该技术一次检查一个任务的可调度性:首先，选择问题窗口等于被分析任务的一个实例的到达时间和截止时间之间的间隔。然后，计算高优先级作业的干扰，并在可调度性分析中加以考虑。干扰分为带入(carry-in) 任务实例(即在问题窗口之前就开始执行的作业，其计算时间只对干扰起部分作用)和非带入 (non-carry-in ) 任务实例(即作业的到达时间和执行时间包含在问题窗口中)。
此后，Baker的技术得到了许多研究人员的改进，他们试图改进对干扰作业量的估计。Bertogna等人[9]发现对于问题窗口中作业负载非常高的每个竞争任务的一部分必须与被分析任务并行，因而不应该被算入实际的干扰。后来，Bertogna和Cirinei[8]将此技术应用于迭代响应全局调度的时间分析(RTA)。
Baruah[4]还提出了另一个突破性的结论。尽管这种技术最初是为G-EDF设想的，但Guan等人将其与RTA技术相结合，获得了更精确的G-FP调度算法的可调度性测试。最近Sun等人[22]通过显式地枚举所有可能的带入任务，以更高的复杂度为代价，对文献[14]的结论进行了改进。他们还将分析方法限制在任务释放模式的子集中，这可能导致任务的最坏情况响应时间。对于G-FP可调度性分析，优劣关系如下所示:. 在文献[19]中，提出了另一个一个基于限制性地带入（limiting carry-in）作业负载的G-FP测试，但是它与刚才提到的测试无法进行比较。Lee和Shin[16]把限制性地带入思想推广到所有作业保持（work-conserving）算法上。
对于G-EDF算法，除了文献[1][9][8] [4]的提出的可调度性测试方法，许多其他的测试方法已经被提出，如文献[2]和[5]，但这些测试方法中没有一种优于其它的测试方法。不过，根据经验评估[7]，在文献[4]和[8]中提出的测试方法表现出更好的平均性能。下文我们将Baruah在文献[4]中提出的测试方法称为Bar, Bertogna和Cirinei在文献[8]中提出的测试称为BC。
在[17]中，提出了一种改进整体可调度性结果的组合理论，该理论探讨了在处理器子集上对总任务子集应用现有过近似(over-approximate)检验的充分条件。虽然底层可调度性测试之间的优势关系也可能对组合结果保持不变，但进一步的研究超出了本文的范围。最近，文献[15]中提出了一种“分治”方法并应用于BC测试，它还发现BC测试中未能检测到的某些可调度任务集。
某些应用程序中允许任务暂停执行一段时间(例如等待来自外部设备的数据时)。将暂停时间视为执行时间是一种简化的方法，但它可能会造成悲观的结果。Liu和Anderson[19]为G-FP和G-EDF调度提供了第一个基于暂停感知（suspension-aware）的可调度性测试。在文献[19]中，任务可以在其执行的任何阶段进行自挂起。之后，Tong和Liu[23]研究了具有特定挂起模式的自挂起（self-suspending）任务的可调度性。
- 本文的创新点
本文的作业的目标是进一步提高多处理器平台上G-EDF调度的可调度性测试的性能。我们为G-EDF算法设计了一种新的优于Bar测试和BC测试的可调度性测试。同时，我们在保持测试方式优于Bar测试和BC测试的基础上，提出了一个运行时复杂度较低的测试的过近似版本，然后将新的测试扩展到自挂起任务的情景中。本文广泛地比较了各种综合生成的任务集上的最新测试方法。结果表明，新的测试方法极大地改善了现有的G-EDF调度算法的作业性能。
论文组织如下。第II部分介绍了系统模型。在第III节中，我们回顾了之前关于G-EDF可调度性分析的知识，主要集中在Bar测试和BC测试。在第IV部分，我们提出了G-EDF可调度性分析的新测试方法。在第V部分中，这些新的测试将适用于具有自挂起任务的系统。在第VI部分，我们提供了大量的仿真来评估我们的测试相对于现有测试的性能。最后，在第VII节总结全文。
II. SYSTEM MODEL
离散任务模型由表示，为最坏情况执行时间(Worst-Case Execution Time ,WCET)，为相对截止时间，表示最小释放间隔（也称之为周期）。其中，任务的利用率定义为：. 每个任务可以释放一个无限序列的作业(也称为实例); 两次作业的成功释放之间需要至少时间间隔。每一个作业包含一个释放时间()，一个绝对截止日期，一个已发释放的作业必须在截至时间内完成执行，将作业的结束时间表示为.。如果一个作业已经被释放，但还没有完成执行，那么将这种状态称之为活跃的。因为已经假设，所以在某一时刻一个任务最多有一个作业处于活跃状态。一个任务的最坏情况执行时间(WCRT)定义为。如果某一任务所有作业都在不晚于相应的绝对截止日期前完成，则称任务是可调度的，即。本文考虑的离散的时间域，为正整数。
定义为容量为n的偶发任务集，。任务集总利用率为。我们假设在m (lt; n)个相同的处理器上执行。为了避免极端情况，必须严格小于m。在第V部分，我们讨论了自挂起任务的可调度性分析, 也就是说，任务可以在执行期间挂起自己。一个自挂起任务由四元组组成，表示任务最多能挂起S个时间单位。注意，一个作业只要累计挂起时间不超过，它就可以挂起多次，，并且它可以以一个挂起状态开始或结束。令。
为了与自挂起任务区别开，一个从来不挂起的任务称之为计算任务（computational task）。一个计算任务可以看作是的特殊自挂起任务。当任务集中既包含自挂起任务也包含计算任务时，用表示自挂起任务的子集，用表示计算任务的子集。即 。中的任务应该根据全局最早截止时间优先(G-EDF)抢占式调度策略进行调度。作业可以在任何处理器上执行，一个被抢占或自挂起的作业可能会在以后在相同或不同的处理器上重新开始执行。
III全局EDF可调度性:先验结果
在本节中，我们将简要总结Bar[4]和BC[8]。为了简化表达式，我们定义了以下符号:
A. 干扰
在分析任务的在G-EDF算法下调度性问题时,通常会假定一个问题窗口。一个问题窗口(problem window)是一段时间间隔[a,b)，且存在时刻b与任务的某些作业的截止时间重合，将这些作业称为目标(target)作业
需求上界函数（Demand bound function）：需求上界函数在EDF算法中有十分重要的地位。对于任意t，任务需求约束函数表示释放时间和截止时间都在长度为t的任意时间间隔内的作业的最大的累积执行时间
公式定义如下：
干扰(Interference)：为了检查任务的目标作业是否会错过最后期限，需要估计的干扰。 干扰表示间隔[a，b）的所有长度为t的子间隔的累积长度,在t时间内目标作业活跃但不能被执行完成。 由于计算确切的干扰非常困难，我们将计算上限。 根据[9]中的结论，一个上限是：
为了便于表述，本文用“干扰”一词来表示干扰的任何上界。任务的干扰可以分成两类:带入(carry-in,CI)任务和非带入(non-carry-in ,NC)的任务。给定一个问题窗口[a, b),,，如果任务在问题窗口开始之前已经释放了作业，并且在时间a仍然处于活动状态，则该任务称为CI任务，否则，它就是一个NC任务。CI任务会在问题窗口中产生更多的干扰。
NC任务在问题窗口的干涉上界直接可以通过使用DBF函数得出：
如果是CI的任务, 估计其可能的干扰为:
最坏情况下的CI干扰与图1中描述的场景相对应。注意,当估计任务的干扰时, 用作为的上界比较安全。在任务的可能会对目标作业造成干扰的一序列作业中, ,第一个作业称为带入作业,最后一个称为带出作业。
CI任务在问题窗口的干扰值最大当:1)作业的执行截止时间与b重合的,2)地每一个作业释放时间尽可能地快，并且3)带入作业地在最坏情况下的响应时间时正好结束执行成立。不等式永远成立。
- Bertogna 和 Cirinei 测试
任务在一段时间间隔内的工作负载表示该任务在该时间间隔内需要的计算量。Bertogna和Cirinei[8]在长度为L任意时间间隔内为任务的工作负载规定了一个通用的上界，该上界不依赖于具体的调度算法:
其中
最坏情况工作负载的情况如图2所示:带入作业从窗口的开始处开始执行，并精确地以其最坏情况响应时间结束;以及每一个连续的时间间隔内，任务都尽快到达。
最后，BC依赖于经典的迭代响
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236602]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
