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

这是复旦大学计算机系 2006 届博士生吴刚的学位论文。 本文的研究内容是“低功耗进程调度算法”。这种算法通过改进进程调度策略，达到降低功耗的目的。此类算法可用于通用系统和嵌入式系统。 低功耗进程调度算法又称 DVS（动态调压）算法。和其他低功耗算法（例如 DPM）相比，优点是效果好、易移植。 从 1994 年 Mar 的论文开始，已经出现了很多算法。可以分成在线和离线两大类。它们都不够实用，具体体现在……（略）。 为了克服现有算法的缺点，本文首先提出并证明了“最优低功耗调度定理”，还证明了任何在线算法都不可能是强实时的：这两点对算法研究有指导意义。 本文提出了两个新的 DVS 算法：自适应 DVS 算法和 DP-DVS 算法。后者同时还具有一定的死锁避免能力，有助于系统健壮性。 本文还研究了进程调度和电池性能的关系。前人在这方面的研究是基于化学、电子线路的，故其通用性有限。本文则基于电池的放电曲线和基本物理定律，通用性好，且研究结论也可以用来改进和遴选 DVS 算法。 需要指出：本文在 2007 年向社会公开。两年后，时为中兴集团员工的欧阳慧琴申请了专利《CPU 的自适应动态调频或调压方法及装置》，其关键字句和本文第 5 章“自适应 DVS 算法”含义相同。经交涉，中兴集团已经承诺撤回专利申请。