页面分配器的研究与实现

《页面分配器的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分类号UDC学号!§!!151111密级公五．同等学力申请工学硕士学位论文页面分配器的研究与实现学科专业让簋扭叠堂皇挞苤国防科学技术大学研究生院二oo六年三月国防科学技术人学研究生院工学硕士学位论文摘要大部分现代操作系统实现了基于分页的虚拟存储器系统。物理内存被划分成大小相同的页帧，页面分配器管理所有的页帧，负责分配和释放物理页面。页面级操作是内核代码的关键路径，页面分配器的评价标准首先是必须快，其次是外部碎片和内部碎片必须少。本文研究和改进了Linux的页面分配器．利用内核探测器Kprobe，提出了一种大量采集内核态数据的方法，随后对Linux内核进行数据采集分析，发现页面分配器超过99

2、％的操作是用于单个页面，而且绝大部分被使用页帧是用于单个页面的分配。Linux2．4采用伙伴系统作为页面分配器以解决外部碎片问题，但主要缺点是反复的合并和剖分操作导致性能较差，2．6内核使用热，冷页层解决该问题。本文提出一种新的页面分配算法，该算法特别优化单个页面的处理，也能满足连续页帧的请求，算法的时间复杂度近似O(1)。新算法在Linux2．6．9下实现，生成的新内核进行了内核编译时间和lmbench两个基准测试，测试表明内核编译时间在单处理器情况下有一定提高，双处理器情况下性能相当。在双处理器情况下lmbench测试新内核的大部分测试数据优于原有内核。页面分配器实现包含了页面放置策略

3、的选择，合适的页面放置算法可以减少高速缓存冲突，从而提高高速缓存性能。本文具体分析了页面分配器对高速缓存性能的影响，然后研究了几种页面放置算法，继而进行实例分析，包括页面着色算法在FreeBSD5．4中的实现以及全局箱跳算法在NetBSD2．0中的实现。本文解决了实现页面放置算法所面临的技术问题，包括高速缓冲级别的选择、高速缓冲大小的获取、对称多处理和超线程体系结构对页面放置算法的影响。Linux操作系统目前的放置策略为随机策略，本文研究了Linux下实现页面放置算法的可能性，分析并解决了相关的技术问题。本文在Linux2．6．9下实现了全局箱跳算法，性能测试表明该算法并没有明显改善性能，

4、随着高速缓存组关联度的增大，页面放置算法对系统性能的影响正在减弱。关键词：存储器管理，页面分配器，页面放置策略，高速缓存，页面着色算法，箱跳算法蔫l兜国防科学技术人学研究生院I：学硕士学位论文ABSTRACTMostofmodemoperatingsyStemsimplementpaging-basedvirtualmemorysystem．Physicalmemoryisdividedintofixed-sizepageframes．Thepageallocator,whichisthemanagerofallthepages，allocatesandfreesphysicalpages

5、．Pageleveloperationisacriticalpathofkernelcode．Themostimportantcriterionforapageallocatoristhatitmustbefast．Thesecondimportantcriterionisitsintemalandexternalfragmentationmustbelow．InthisdissertationwestudyandimprovetheLinuxpageallocator．BasedonkernelprobeKprobe，amethodofcollectingalargeamountofda

6、tafromkerneldynamicallyisproposed．Usingthemethodthepageallocator'sbehaviourisanalyzed，theratioofpagealloeator'soperationforsinglepageexceeds99％，andmostofusedmemoryisallocatedforsinglepagerequest．Toavoidexternalfragmentation,Linux2．4usesbuddyallocatorasitspageallocator,butthemaindisadvantageofthisa

7、lgorithmisthepoorperformanceduetorepetitivecoalescingandsplitting．Linux2．6addshot／coldpageintopageallocatortosolvethisproblem．Thisdissertationproposesanewpageallocatorwhichoptimizessinglepageoperationandalsosatis