操作系统调度器结构及算法研究

论文摘要

计算机体系结构和应用需求的变化,不断推动着操作系统技术的发展。如何针对新的体系结构和应用需求来设计进程调度算法成为操作系统领域的重要研究方向之一,并得到业界的广泛关注。论文首先分析了处理器体系结构和应用需求的发展给调度算法设计带来的新挑战以及Linux操作系统调度算法为适应这些挑战而作出的主要改变,总结和归纳了业界在调度算法设计、实现及评价方面采用的主要方法及工具,在此基础上针对当前发展较快的桌面应用提出调度算法评测指标体系,作为对现有调度算法性能进行评价的依据。论文通过研究,在理论及测试两个层次上证明了现有算法在桌面应用中仍然存在不足之处,并指出目前算法研究方面存在的主要障碍是缺乏有效的支持手段及工具。虽然通过模拟器模拟的方式可以取得一定的研究结果,但模拟无法做到真实有效,而在真实系统内部开展研究既受到源码的使用限制,也受到代码结构复杂所带来的高昂实现成本的限制。为此,论文提出一种模块化调度器框架,通过将调度器代码封装到十个模块中,来降低各部分代码间的相互关联,提高代码的清晰度。基于Linux操作系统改造实现的模块化调度器提供了一组简单的算法实现接口,用户可以使用该接口方便地实现自定义的调度算法,而无须关心调度器与操作系统其它部分之间存在的错综复杂的关系。通过接口在系统内核实现调度算法可以降低算法实现的难度,准确获得调度算法的真实性能,因而该模块化调度器可以作为算法实现及研究的基础平台。论文在分析O(1)、CFS及BFS算法实现原理及优缺点基础上,针对桌面应用提出一种理想的盲目调度算法模型,该模型可以作为算法设计时的参考。基于模型部分实现的动态优先级调度算法DPS通过跟踪进程的运行状态来动态调整不同种类进程的优先级以及进程单次运行的时间,以提高交互式进程的响应速度。该算法在改造后的Linux模块化调度器中实现,测试表明,该算法在不降低现有算法其它方面性能的前提下提高了系统的交互性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 进（线）程调度概述
• 1.2 课题背景和来源
• 1.2.1 课题背景
• 1.2.2 课题来源
• 1.3 本文的主要工作
• 1.4 本文的组织结构
• 第二章 相关研究与分析
• 2.1 硬件体系结构的发展
• 2.2 用户应用需求分类
• 2.2.1 实时应用
• 2.2.2 交互式应用
• 2.2.3 批处理应用
• 2.3 调度算法发展与分析
• 2.3.1 O（1）算法
• 2.3.2 CFS 算法
• 2.3.3 BFS 算法
• 2.4 调度算法设计与实现方法
• 2.5 调度算法性能评测指标及工具
• 2.5.1 评测指标
• 2.5.2 测试工具
• 2.6 本章小结
• 第三章 调度器模块化设计与实现
• 3.1 调度器功能分析
• 3.2 调度器模块化设计
• 3.3 Linux 调度器模块化及算法接口
• 3.4 算法实现流程及示例
• 3.5 本章小结
• 第四章 调度算法设计及实现
• 4.1 现有调度算法性能分析
• 4.2 理想调度算法模型
• 4.3 DPS 算法设计
• 4.4 DPS 算法参数分析
• 4.5 本章小结
• 第五章 评测与分析
• 5.1 测试环境
• 5.1.1 硬件配置
• 5.1.2 软件环境
• 5.2 测试内容
• 5.2.1 模块化调度器性能测试
• 5.2.2 DPS 性能测试
• 5.3 测试结果及分析
• 5.4 本章小结
• 第六章 结束语
• 6.1 论文的研究成果
• 6.1.1 主要工作
• 6.1.2 创新点
• 6.2 进一步的工作
• 致谢
• 参考文献
• 作者在学期间取得的学术成果