摘 要

随着实时应用的使用范围扩大，复杂度提高，具有高性能及高可靠性特征的多处理器系统逐渐成为处理这种复杂应用的有效手段。在过去的四十年中，面向单处理器的实时调度技术已经发展得比较成熟。相比之下，面向多并行体系结构的实时调度在理论方面和系统实现方面依然面临着巨大挑战。

最早截止期优先（Earliest Deadline First ,EDF）己被证明是单处理器系统上的最优调度算法，而在多处理器系统上EDF算法却不存在这种最优性。最早截止时间优先直到零松弛算法(Earliest Deadline First until Zero-laxity ,EDZL)是EDF的简单扩展，同时具有“并行性”和“紧急性”的特点，更适用于多处理器系统。本文基于资源需求的可调度测试方法的原理，提出了一种更高精度的EDZL算法的可调度性测试方法。首先，本文从实时调度模型出发，研究了EDZL算法的性质，比较了EDF调度算法和EDZL调度算法的调度策略，说明了在多处理器系统中DZL算法对EDF算法的支配性。然后，重点研究了一种可调度测试方法—EDZL-O测试。接着，本文基于“紧急任务集”的概念提出了一种新的可调度性测试方法:EDZL-I测试，并从理论上证明EDZL-I测试能够在不增加时间复杂度的前提下，支配EDZL-O测试。最后，仿真实验表明，EDZL-I测试的调度成功率比EDZL-O测试提高了4%--7%，EDZL-I测试更适用于处理器个数为8或者任务集总利用率相对较小的实时系统。

关键词：多处理器系统；实时调度；EDZL算法；可调度性测试

Abstract

With the increasing scope and complexity of real-time applications, multiprocessor systems have gradually become effective means of handling such complex applications due to their high performance and reliability. In the past forty years, the real-time scheduling technology for single processors has developed relatively maturely, However the real-time scheduling for multi-parallel architectures still faces huge challenges both in theory and system implementation.

Earliest Deadline First (EDF) has been proved to be the optimal scheduling algorithm on single-processor systems, but there is no such optimality on multi-processor systems. Earliest Deadline First until Zero-laxity (EDZL) is a simple extension of EDF. It has the characteristics of "parallelism" and "urgency" and is more suitable for multiprocessor systems. Based on the principle of resource-schedulable test, this paper proposes a more accurate test method for EDZL algorithm. First, starting from the real-time scheduling model, this paper studies the properties of the EDZL algorithm, compares the scheduling strategies of the EDF scheduling algorithm and the EDZL scheduling algorithm, and illustrates the dominance of the EDF algorithm over the EDF algorithm in a multiprocessor system. Afterwards, this paper focuses on schedulable testing method—EDZL-O test ,and uses the concept of "urgent task set" to propose a new schedulability test EDZL-I test. We theoretically prove that the EDZL-I test dominates the original EDZL-O test without increasing the time complexity. Finally, simulation experiments show that the EDZL-I test improves the scheduling success rate by 4% -7% and EDZL-I test is more suitable for real-time systems with 8 processors or a relatively low total utilization of the task set.

Keywords:： multiprocessor system; real-time scheduling; EDZL algorithm; schedulability test

目录

第1章 研究背景及意义 1

1.1 研究背景及意义 1

1.2 研究目的 2

第2章 国内外研究现状分析 3

第3章 系统模型 5

第4章 EDZL算法介绍 7

4.1 EDZL算法的调度策略 7

4.2 EDZL算法与EDF算法比较 7

第5章 一种新的EDZL算法的可调度性分析方法 10

5.1 基于资源需求可调度性分析方法的原理 10

5.2 下界 11

5.3 上界 12

5.4 一种新的EDZL可调度性分析方法及对比 15

5.4.1 原有的EDZL可调度性方法--EDZL-O 15

5.4.2 一种新的EDZL迭代式可调度性方法--EDZL-I 16

5.4.2 EDZL-I方法对于EDZL-O方法的支配性 17

第6章 仿真实验 18

6.1 实验设置 18

6.2 实验结果 19

第7章 总结与展望 24

7.1结论 24

7.2未来工作的展望 24

参考文献 25

致谢 27

研究背景及意义

1.1 研究背景及意义

当一个处理系统的正确性不仅取决于逻辑计算的正确性，而且还取决于计算完成的时间时，该系统被称之为实时系统^[1]。随着多处理器的飞速发展，越来越多的嵌入式实时系统设计者选择多处理器作为硬件平台，以满足各类应用不断增长的高性能与低功耗的需求。实时多处理器系统的调度算法则成为一个重要研究课题^[2]。

由于实时系统，尤其是硬实时系统，对系统的时间行为特性有严苛的要求，因此通常需要在系统实际运行之前对系统的时间特性进行验证，以确保系统在运行过程中规定的时间特性要求得到满足^[3]。故在实时系统的设计中，系统设计者需要考虑到两方面问题：其一是如何安排任务集在处理器上的执行顺序，这部分功能通常由调度算法实现；其二是，如何对系统的运行情况进行预测与分析。具体来说，就是在一个给定的调度算法之下，判断每个任务能否在指定的时间点(即截止期)之前完成，通常称这种分析为可调度性分析。一个好的实时调度算法需要有相关的可调度性分析来验证任务是否存在超时现象。

自上世纪六十年代末以来，单处理机系统上的实时调度技术被广泛研究，经过几十年的发展，单处理器上的调度方法日益成熟。但是多处理器上的调度问题与单处理器有本质上的不同，增加处理器的个数为调度问题的复杂程度增加了一个维度，单处理器上的算法无法直接化用到多处理上^[4]。最早截止日期优先（Earliest Deadline First ,EDF）被认为为单处理器上的最优调度算法^[5]。但是，EDF在多处理机模型上非但不是最优，而且会导致极低的资源利用率界限^[6]。对此，大量研究致力于通过改善可调度性分析方法的精度或效率来提高EDF算法在多处理器上的调度性能^[7][8]，另一些研究提出了不同于EDF的调度策略，EDF-US[]算法和EDZL算法是EDF算法的简单扩展。EDF-US[]算法通过将任务利用率大于的任务赋予最高优先级来改进EDF算法，其中已知最优的参数为，在此参数下，任何任务集的总利用率小于的任务集都能够在处理器个数为的任务集上调度成功^[9]。不过尽管。EDF-US[]算法提高了EDF算法的调度能力，也有一些原本能在EDF算法下调度的任务集不能在EDF-US[]算法下调度。最早截止时间直到零松弛优先算法(Earliest Deadline First until Zero-laxity ,EDZL) ^[10]结合了EDF算法和最少松弛时间优先（Least Laxity First, LLF）算法的特点，将松弛度最低的作业赋予最高优先级，能够同时表现任务的“紧急性”和“并行性”^[11]，并且具有较低的运行时开销^[12][13]，展现出更适用于多处理器调度潜能。与EDF-US[]算法不同，所有在EDF算法下能够被调度的任务集都能够在EDZL算法下被调度。