对低功耗进程调度算法的研究

论文摘要

本文的研究内容是“低功耗进程调度算法”。这种算法通过改进进程调度策略，达到降低功耗的目的。此类算法的作用是：1．在通用系统方面，由于功耗降低而使芯片热量下降，可以取消散热装置，以使计算机能够更小、更安静、更可靠；2．在嵌入式系统方面，用来延长电池供电系统的工作时间，此类系统包括手机、笔记本电脑、GPS（全球定位仪）等。低功耗进程调度算法又称为“DVS（动态调压）算法”。和其他低功耗算法（例如DPM算法）相比，DVS算法的优点是降耗效果好、便于移植。DVS算法的核心问题是功耗和实时性的矛盾：为了降低功耗，就要降低频率，而这可能破坏实时性。如何把握功耗和实时性的平衡，是最主要的问题。以文献[Mar94]为标志，从那以来，已经有许多论文提出了各自的DVS算法。这些算法可以分成在线和离线两大类。这些算法都不够实用，具体表现在：1．在线算法通过“窗口”统计CPU利用率，这导致功耗浪费，并且也无法确定合适的窗口尺寸；2．无论在线还是离线算法，均假设进程是自由运行的，这显然和实际不符。为了克服现有算法的缺点，本文首先提出并证明了最优低功耗调度定理，还证明了任何在线算法都不可能是强实时的：这两点对算法研究具有指导意义。本文提出了两个新的DVS算法。一个是自适应DVS算法。这是一种在线算法，它统计的不是CPU利用率，而是“频率利用率”，并且也不是通过窗口统计的。这就使它摆脱了现有在线算法的缺点。实验数据表明：它的降耗效果不但优于主要的在线算法，甚至还优于离线算法。它的实时性也可以接受：在合适的硬件平台上，平均每运行1000次，破坏实时性不会超过2次。第二个是DP-DVS算法，这是一个离线算法。它的特点是：注意到了进程并不是“自由”运行的，彼此间存在制约、依赖的关系。该算法利用依赖关系树确定进程的合理执行次序，再利用最优低功耗调度定理确定合理执行频率。该算法还具有一定的死锁避免能力，有助于增强系统健壮性。上述两个算法的开销都很小。因此，都具有较高的工程应用价值。本文还研究了进程调度和电池性能之间的关系。以前也有一些文献研究这个问题，但是它们的方法是基于化学、电子线路的，因此其结论的通用性、权威性较差。本文采用了新的研究方法，基于电池的放电曲线和基本物理知识，其结论具有很好的通用性和权威性。主要结论是：应该优先运行频率较高的进程，简称“高频率优先”原则。本文通过实际放电实验，验证了该结论。这个结论可以用来遴选、改进低功耗算法。作为示范，本文利用该结论改进了一个现有DVS算法。围绕上述的定理、两个算法和电池问题，本文还论述了其他相关方面，比如功耗的产生机制、计算机系统中的功耗分布情况、现有操作系统的进程调度算法、CPU性能对DVS算法性能的影响、现有各种DVS算法的特点和优缺点、模拟和评估手段等。本文的工作也表明：只有当CPU的主频能连续调节的时候，DVS算法的效果才能充分发挥。目前还没有这样的CPU，因此是值得开发的。

论文目录

• 目录
• 摘要
• ABSTRACT
• 第1章 引言
• 1.1 研究动机
• 1.2 本文的研究内容和创新
• 1.3 论文结构
• 第2章 硬软件基础知识
• 2.1 集成电路原理
• 2.2 集成电路的动态功耗
• 2.2.1 频率、电压和功耗的关系
• 2.2.2 频率和电压的关系
• 2.2.3 频率和功耗的关系
• 2.3 集成电路的静态功耗
• 2.4 非集成电路部件的功耗机理
• 2.5 计算机系统中的功耗分布
• 2.6 操作系统简史
• 2.7 实时系统和实时性
• 2.7.1 实时系统、实时性和截止期
• 2.7.2 强实时和弱实时
• 2.8 进程调度
• 2.8.1 进程调度算法
• 2.8.2 优先级反转
• 2.8.3 IDLE进程
• 2.9 常见操作系统的进程调度算法
• 2.9.1 Windows的调度算法
• 2.9.2 Linux的调度算法
• 2.9.3 uC/OS-Ⅱ的调度算法
• 2.10 本章小结
• 第3章 低功耗算法的基本问题
• 3.1 三类不同原理的低功耗算法
• 3.1.1 基于操作的低功耗算法
• 3.1.2 基于状态的低功耗算法
• 3.1.3 基于性能的低功耗算法
• 3.1.4 动态调压算法的优势
• 3.2 低功耗算法的层次性
• 3.3 问题的难度以及硬件性能的制约
• 3.3.1 是NP难度的问题
• 3.3.2 硬件平台制约算法效果
• 3.4 最优低功耗调度定理
• 3.4.1 定理及其证明
• 3.4.2 举例验证
• 3.4.3 DVS优于DPM
• 3.5 评估手段
• 3.5.1 硬件测量手段
• 3.5.2 软件模拟手段
• 3.5.3 理论计算手段
• 3.6 小结
• 第4章 低功耗进程调度算法的研究现状
• 4.1 离线DVS算法
• 4.1.1 LEDF算法
• 4.1.2 PACE算法
• 4.1.3 EADP算法
• 4.1.4 Frances算法
• 4.1.5 离线DVS算法的缺点
• 4.2 在线DVS算法
• 4.2.1 Weiser算法
• 4.2.2 对在线DVS算法的总结和分类
• 4.2.3 在线DVS算法的缺点
• 4.3 在线DVS算法的实时性
• 4.4 最低恒速算法
• 4.5 其他低功耗算法
• 4.5.1 其他CPU低功耗算法
• 4.5.2 内存低功耗算法
• 4.5.3 硬盘低功耗算法
• 4.5.4 显示器低功耗算法
• 4.5.5 无线通讯设备的低功耗算法
• 4.5.6 基于状态的低功耗算法的核心问题
• 4.6 小结
• 第5章 自适应DVS算法
• 5.1 自适应算法的基本思想
• 5.2 自适应算法的实现
• 5.2.1 算法的实现方式
• 5.2.2 当进程的周期超长时,算法的工作过程
• 5.2.3 不能运行IDLE时,算法的工作过程
• 5.2.4 算法的的开销
• 5.2.5 其他要补充的问题
• 5.3 实验结果和分析
• 5.3.1 实验环境
• 5.3.2 对照算法的实现方式
• 5.3.3 实验结果和讨论
• 实验一
• 实验二
• 实验三
• 实验四
• 5.4 本章小结
• 第6章 针对依赖进程的强实时DVS算法
• 6.1 研究动机
• 6.1.1 进程间的依赖关系
• 6.1.2 依赖关系使DVS算法失效
• 6.1.3 不能用优先级继承解决依赖关系问题
• 6.2 DP-DVS算法
• 6.2.1 确定进程执行次序
• 6.2.2 确定进程执行频率
• 6.2.3 完整的DP-DVS算法
• 6.2.4 DP-DVS算法工作过程举例
• 6.3 讨论
• 6.4 DP算法和死锁
• 6.4.1 使DP算法具有死锁避免功能
• 6.4.2 死锁问题的难度和现有死锁避免算法
• 6.4.3 工程实践中的死锁避免方法
• 6.4.4 DP算法的死锁避免能力和运用方式
• 6.5 本章小结
• 第7章 电池特性及其在DVS算法中的应用
• 7.1 电池的基本知识
• 7.1.1 电池分类
• 7.1.2 放电曲线
• 7.1.3 循环性能
• 7.2 电池特性
• 7.2.1 现有分析方法
• 7.2.2 第一个分析结论
• 7.2.3 第二个分析结论
• 7.3 实验和讨论
• 7.3.1 实验环境
• 7.3.2 实验结果
• 7.3.3 讨论
• 7.4 在DVS算法中的应用
• 7.5 本章小结
• 第8章 总结和展望
• 8.1 全文总结
• 8.2 展望
• 参考文献
• 致谢
• 攻读博士期间所发表的论文