共享资源约束下的多核实时调度算法研究

摘要

随着计算机系统结构的发展，多核并行已成为当今计算机系统发展的主流。与此同时，随着众多嵌入式系统实时性需求的日益增长，越来越多的实时系统将建立在多核/多处理器平台之上。 在多核实时系统中，任务调度与同步是保障系统实时性的关键。其中，实时调度算法，实时锁协议（ Real-Time Locking Protocols）以及可调度性分析（Schedulability Analysis）是确保系统实时性的基础与核心技术。为了在满足实时性约束的前提下充分发挥多核平台的计算能力，需要采用准确而高效的可调度性分析方法，同时需要对任务调度与资源共享进行协同优化。然而，已有研究中实时调度算法研究往往假设任务相互独立，因而没有充分明确考虑共享资源约束。相反，实时锁协议研究往往专注于锁协议规则设计与任务阻塞时间分析，而缺乏对整体系统的可调度性研究。如何改进共享资源约束下的可调度性分析，以及如何优化共享资源约束下的任务调度是当前多核实时系统研究领域的重点和难点问题。 基于以上背景，本文围绕共享资源约束下的多核实时调度问题，对多核实时调度算法，实时锁协议，以及可调度性分析技术进行系统性研究。本文研究旨在突破共享资源约束下多核实时调度的基础理论难题，为构建高效的多核实时系统提供理论支撑。本文主要研究内容及贡献如下。 （1）指出了经典多处理器实时锁协议分析中存在的两个基础性错误，并给出了更正方法。针对经典多处理器实时锁协议DPCP（ Distributed Priority Ceiling Protocol）和MPCP（Multiprocessor Priority Ceiling Protocol），指出了原始文献中的任务最坏阻塞时间分析错误。同时，指出了近年来在多处理器分组固定优先级（Partitioned Fixed-Priority）调度与信号量实时锁协议分析中存在的最坏响应时间（Worst-Case Response Time）分析错误。随后，分别分析了产生错误的原因，错误所造成的影响以及更正这些错误的方法。 （2）针对全局固定优先级（Global Fixed-Priority）调度与信号量实时锁协议，提出了一种新的任务最坏响应时间分析方法，并对该调度机制下的主流实时锁协议进行了详细分析与总结。根据全局固定优先级调度下任务执行的一般性特征，准确定义了6类任务延迟，并提出了任务最坏响应时间分析的一般性框架。基于该分析框架，提出了通过线性规划分析任务最坏响应时间的一般性方法。该方法可用于全局固定优先级调度下所有主流信号量实时锁协议的可调度性分析。实验结果显示，新分析方法的可调度性明显高于已有分析方法。此外，进行了大规模可调度性实验，首次对全局固定优先级调度下的主流信号量实时锁协议进行统一的比较分析。分析结果显示，全局固定优先级调度中传统的优先级继承协议（ Priority Inheritance Protocol， PIP）和最简单的FMLP（ Flexible Multiprocessor Locking Protocol）协议的可调度率最高。 （3）针对分组固定优先级调度与信号量实时锁协议，提出了一种新的任务最坏阻塞时间分析方法。基于任务结构模型，提出了一种任务临界区执行时间分析方法。该方法能够准确计算任务在任意时间内使用共享资源的最大时间，提高了任务最坏阻塞时间分析的准确性。同时，结合MPCP协议提出了一种新的任务最坏响应时间分析方法。实验分析显示，新分析方法的可调度性高于已有分析方法。 （4）针对自旋锁协议，提出了一种共享资源敏感的分组固定优先级调度算法。针对非抢占FIFO自旋锁机制，提出了一种衡量任务相关性的评价方法，并提出了一种衡量系统利用率损失的评价方法。基于这两种评价方法，提出了一种新的多核任务分配算法。实验分析显示，新算法调度给定任务系统所需的处理器数少于已有的同类调度算法。此外，分析证明了负载非均衡“装箱”（Bin-Packing）启发式任务分配算法存在远程冲突问题，揭示了采用这类算法进行任务分配存在的潜在问题。 （5）针对多核固定优先级调度，提出了一种资源优先分组调度算法。该算法使用共享资源代理实现资源共享，将共享资源调度与任务调度进行分布式管理。理论分析证明，在任务最多包含一个临界区的情况下算法具有加速因子（Speedup Factor）11－6/(m+1)，其中m为处理器核数。该算法是共享资源约束下目前加速因子最小且唯一确保常数加速因子的多核实时调度算法。实验分析显示，在任务具有多个临界区的情况下该算法的可调度率仍高于同类算法。所提出的算法解决了实时调度领域长期未解的一个基础理论难题，为多核/众核环境下的实时调度算法研究提供了新的研究思路。

目录

声明

第一章 绪 论

1.1 研究工作的背景与意义

1.2 实时调度研究概述

1.3 本文的主要贡献与创新

1.4 本文的结构安排

第二章 系统模型及研究背景

2.1 系统模型

2.2 多核实时调度研究现状

2.3 本章小结

第三章 多处理器实时锁协议分析中的基础性错误

3.1 任务最坏阻塞时间分析错误

3.2 任务最坏响应时间分析错误

3.3 本章小结

第四章 全局固定优先级调度下信号量锁协议分析

4.1 全局信号量实时锁协议

4.2 任务延迟的定义及分析

4.3 最坏响应时间分析

4.4 实验分析

4.5 本章小结

第五章 分组固定优先级调度下信号量锁协议分析

5.1 任务阻塞的概念及定义

5.2 任务执行时间分析

5.3 基于MPCP的最坏响应时间分析

5.4 实验分析

5.5 本章小结

第六章 共享资源敏感的多核任务分配算法

6.1 MSRP协议及分析

6.2 远程冲突问题

6.3 共享资源敏感的多核任务分配算法

6.4 实验分析

6.5 本章小结

第七章 基于共享资源约束的多处理器实时调度算法

7.1 资源优先分组调度算法

7.2 可调度性分析

7.3 加速因子分析

7.4 实验分析

7.5 本章小结

第八章 全文总结与展望

8.1 全文总结

8.2 后续工作展望

致谢

参考文献

攻读博士学位期间取得的成果

后记