学位论文 > 优秀研究生学位论文题录展示

页面分配器的研究与实现

作　者: 陈燕晖
导　师: 罗宇
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 存储器管理页面分配器页面放置策略高速缓存页面着色算法箱跳算法
分类号: TP316
类　型: 硕士论文
年　份: 2006年
下　载: 42次
引　用: 3次
阅　读: 论文下载

内容摘要

大部分现代操作系统实现了基于分页的虚拟存储器系统。物理内存被划分成大小相同的页帧,页面分配器管理所有的页帧,负责分配和释放物理页面。页面级操作是内核代码的关键路径,页面分配器的评价标准首先是必须快,其次是外部碎片和内部碎片必须少。本文研究和改进了Linux的页面分配器。利用内核探测器Kprobe,提出了一种大量采集内核态数据的方法,随后对Linux内核进行数据采集分析,发现页面分配器超过99%的操作是用于单个页面,而且绝大部分被使用页帧是用于单个页面的分配。Linux 2.4采用伙伴系统作为页面分配器以解决外部碎片问题,但主要缺点是反复的合并和剖分操作导致性能较差,2.6内核使用热/冷页层解决该问题。本文提出一种新的页面分配算法,该算法特别优化单个页面的处理,也能满足连续页帧的请求,算法的时间复杂度近似O(1)。新算法在Linux 2.6.9下实现,生成的新内核进行了内核编译时间和lmbench两个基准测试,测试表明内核编译时间在单处理器情况下有一定提高,双处理器情况下性能相当。在双处理器情况下lmbench测试新内核的大部分测试数据优于原有内核。页面分配器实现包含了页面放置策略的选择,合适的页面放置算法可以减少高速缓存冲突,从而提高高速缓存性能。本文具体分析了页面分配器对高速缓存性能的影响,然后研究了几种页面放置算法,继而进行实例分析,包括页面着色算法在FreeBSD 5.4中的实现以及全局箱跳算法在NetBSD 2.0中的实现。本文解决了实现页面放置算法所面临的技术问题,包括高速缓冲级别的选择、高速缓冲大小的获取、对称多处理和超线程体系结构对页面放置算法的影响。Linux操作系统目前的放置策略为随机策略,本文研究了Linux下实现页面放置算法的可能性,分析并解决了相关的技术问题。本文在Linux 2.6.9下实现了全局箱跳算法,性能测试表明该算法并没有明显改善性能,随着高速缓存组关联度的增大,页面放置算法对系统性能的影响正在减弱。

全文目录

摘要  10-11
ABSTRACT  11-12
第一章绪论  12-19
  1.1 背景  12-13
  1.2 页面分配器  13-14
    1.2.1 内核中的页面分配器  13-14
    1.2.2 实现页面分配器需要考虑的因素  14
  1.3 相关的工作  14-17
    1.3.1 存储分配器介绍  14-15
    1.3.2 超页技术  15-16
    1.3.3 页面放置算法  16-17
    1.3.4 页聚技术  17
  1.4 论文的主要工作及组织结构  17-19
第二章 Linux存储器管理系统  19-36
  2.1 物理内存的组织与管理  19-21
    2.1.1 页帧描述符  19
    2.1.2 非一致存储访问结构  19-21
  2.2 Bootmem分配器  21-22
  2.3 页面分配器  22-26
    2.3.1 伙伴分配器  23
    2.3.2 页面操作API  23-24
    2.3.3 热/冷页分配器  24-26
  2.4 Slab分配器  26-31
    2.4.1 基本设计思想  26-28
    2.4.2 Slab分配器在Linux中的实现  28-31
  2.5 进程地址空间  31-35
    2.5.1 Linux的分页模型  31-32
    2.5.2 进程地址空间的组织  32-34
    2.5.3 缺页异常处理  34-35
  2.6 本章小结  35-36
第三章一种新的页面分配算法  36-50
  3.1 内核数据采集的方法  36-39
    3.1.1 内核探测器Kprobe  36-37
    3.1.2 一种大规模采集数据的方法  37-39
  3.2 Linux操作系统页面分配情况的量化分析  39-42
    3.2.1 伙伴系统分配规律的动态统计  39-40
    3.2.2 伙伴系统的客户分析  40-42
    3.2.3 伙伴算法的缺陷分析  42
  3.3 一种新的页面分配算法的设计与实现  42-47
    3.3.1 一种新的页面分配算法  42-44
    3.3.2 新算法在Linux 2.6.9平台下的实现  44-47
  3.4 新内核性能测试  47-49
    3.4.1 编译内核时间测试  47-48
    3.4.2 Lmbench测试  48-49
  3.5 本章小结  49-50
第四章优化高速缓存性能的页面放置算法研究与实现  50-67
  4.1 高速缓存性能与页面分配器  50-52
    4.1.1 高速缓存与虚存的关系  50-52
    4.1.2 页面的颜色  52
  4.2 几种页面放置算法  52-54
    4.2.1 页面着色  52-53
    4.2.2 箱跳算法  53
    4.2.3 最佳箱算法  53
    4.2.4 层次式算法  53-54
  4.3 页面放置算法的实例分析  54-61
    4.3.1 FreeBSD的页面着色算法  54-58
    4.3.2 NetBSD的箱跳算法  58-60
    4.3.3 Solaris的页面放置算法  60-61
  4.4 页面放置算法在Linux 2.6.9下的实现  61-66
    4.4.1 设计的一些技术考虑  61-64
    4.4.2 全局箱跳算法在Linux 2.6.9下的实现  64-66
  4.5 本章小结  66-67
第五章总结与展望  67-69
  5.1 全文工作总结  67-68
  5.2 对下一步研究工作的展望  68-69
致谢  69-70
附录A: 内核开发与proc文件系统编程简介  70-73
附录B: 攻读硕士期间发表的论文  73-74
附录C: 攻读硕士期间参加的科研项目  74-75
参考文献  75-78

页面分配器的研究与实现

内容摘要

全文目录

相似论文