非对称多核处理器的若干调度问题研究

论文摘要

随着芯片集成规模极限的逼近以及能耗和成本等因素，多核处理器逐渐占据了市场。相对于对称多核处理器，非对称多核处理器在效能、芯片面积、适用范围等方面有着巨大的优势，将成为未来的主流体系结构。现有调度算法从单核处理器发展而来，并为对称多处理器做了相应扩展，不能利用非对称多核处理器的特性和优势。本文致力于研究非对称多核处理器的调度问题，以提高系统的效能、性能和公平性。具体来说，本文从以下4个方面进行了深入研究：(1)针对非对称多核处理器上操作系统的单线程任务调度问题，本文建模分析各种因素，提出了一种综合性调度算法。该算法采用行为匹配、减少迁移和负载均衡的调度策略，包括两个部分：1)集成负载表征，提出集成行为的概念，全面衡量任务的整体性和阶段性行为；2)基于集成行为的调度算法，有效开发非对称多核处理器的特性，能够保证各核心负载均衡，同时可以避免不必要的任务迁移。另外，该算法通过参数调整机制实现了算法的通用性。该算法是一种综合处理任务的整体性和阶段性行为，并具备通用性的调度算法。实验结果表明：该算法可通用于多种环境，且性能比其他同类算法提高6%~22%。(2)针对非对称多核处理器上操作系统的多线程任务调度问题，本文建模分析各种因素，提出了一个集成调度算法。该算法具有以下特性：1)全面考虑多线程任务同步特性、核心非对称性以及核心负载；2)通过集成线程调度和动态电压频率调整来提高效能；3)通过参数调整机制实现了算法的通用性。该算法是第一个在非对称多核处理器上结合线程调度和动态电压频率调整的调度算法。实验结果表明：该算法可适用于多种环境，且效能比其他同类算法高24%~50%。(3)针对非对称多核处理器上的虚拟处理器公平调度问题，本文建模分析各种因素，提出了一个组合调度算法。该算法具有以下特性：1)全面考虑虚拟处理器同步特性、核心非对称性以及核心负载；2)定义了效用因子、比例系数、比例资源的概念，结合虚拟处理器的同步特性和核心的非对称性对资源和负载进行全面度量；3)通过运行队列分解降低调度开销。实验结果表明：该算法实现了公平调度，并且性能比其他同类算法提高19%~48%。(4)针对非对称多核处理器上的虚拟处理器高效能调度问题，本文提出一个并行度感知调度器，该调度器综合利用了虚拟处理器调度和动态电压频率调整。并行度感知调度器用一种非入侵的方法动态监测虚拟机的并行度，然后选择并调度相关的虚拟处理器同时执行。提出的推迟协同调度算法使多个并行的虚拟机可以同时进行协同调度，而不会导致冲突。实际平台上的实验表明，并行度感知调度器的性能和效能优势明显，分别达到26%和65%。此外，并行度感知调度器的开销接近默认调度器，低于其他非对称多核处理器上的虚拟机调度器。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 本文的主要工作
• 1.3 本文组织结构
• 第二章 非对称多核处理器上操作系统的单线程任务调度研究
• 2.1 引言
• 2.2 建模分析
• 2.3 综合性调度算法
• 2.3.1 集成负载表征
• 2.3.2 基于集成行为的调度算法
• 2.3.3 参数调整机制
• 2.4 实验与分析
• 2.4.1 实验平台与方法
• 2.4.2 实验结果与分析
• 2.4.3 实验小结
• 2.5 相关研究
• 2.6 本章小结
• 第三章 非对称多核处理器上操作系统的多线程任务调度研究
• 3.1 引言
• 3.2 问题描述与建模
• 3.2.1 问题描述
• 3.2.2 建模分析
• 3.3 集成调度算法
• 3.3.1 状态监控机制
• 3.3.2 负载均衡
• 3.3.3 重调度
• 3.3.4 任务执行
• 3.3.5 参数调整机制
• 3.3.6 算法运行开销
• 3.4 实验与分析
• 3.4.1 实验平台与方法
• 3.4.2 实验结果与分析
• 3.4.3 实验小结
• 3.5 相关研究
• 3.6 本章小结
• 第四章 非对称多核处理器上的虚拟处理器公平调度研究
• 4.1 引言
• 4.2 问题描述与建模
• 4.2.1 问题描述
• 4.2.2 建模分析
• 4.3 组合调度算法
• 4.3.1 初始映射
• 4.3.2 资源分配
• 4.3.3 资源消耗
• 4.3.4 虚拟处理器选择
• 4.3.5 算法运行开销
• 4.4 实验与分析
• 4.4.1 实验平台与方法
• 4.4.2 实验结果与分析
• 4.4.3 实验小结
• 4.5 相关研究
• 4.6 本章小结
• 第五章 非对称多核处理器上的虚拟处理器高效能调度研究
• 5.1 引言
• 5.2 研究动机与问题描述
• 5.3 并行度感知调度器
• 5.3.1 建模分析
• 5.3.2 虚拟处理器映射和负载均衡
• 5.3.3 动态并行度检测和调度
• 5.3.4 频率调整
• 5.3.5 调度器运行开销
• 5.4 实验与分析
• 5.4.1 实验平台与方法
• 5.4.2 实验结果与分析
• 5.5 相关研究
• 5.6 本章小结
• 结论与展望
• 参考文献
• 附录
• 1 基于 Linux 的实验方案
• 1.1 Linux 调度流程
• 1.2 CFS 调度类
• 1.3 实验方案
• 2 基于 Xen 的实验方案
• 2.1 Xen 调度流程
• 2.2 Credit 调度算法
• 2.3 实验方案
• 攻读博士学位期间取得的研究成果
• 致谢
• 答辩委员会对论文的评定意见