（计算机软件与理论专业论文）linux26内存管理反向映射分析与改进.pdf

重庆大学硕士学位论文中文摘要 摘要 在l i n u x 操作系统中，内存管理单元负责管理整个系统的物理地址空间和虚地址 空间，进行虚实地址之间的转换以及页面的换入换出等操作。它是系统内核中最重要 的组成部分之一，是整个系统得以存在和运行的基础。拥有一个强大和完备的内存管 理子系统是构建一个具有高可靠性以及可伸缩性系统的必备条件。随着l i n u x 内核的 发展和成熟，更多的用户期待着l i n u x 可以运行非常大的系统来处理科学分析应用程 序或者甚至海量数据库。l i n u x 2 6 内核于2 0 0 4 年发布，l i n u x 2 6 内核使用了许多技 术来改进对内存的使用，提高内存管理子系统的工作效率。 本论文针对l i n u x 内存管理部分开展研究，主要分析了l i n u x 操作系统的请求式 分页虚拟存储管理方法以及内存映射和管理机制，重点研究了l i n u x 2 6 内核正式加入 的反向映射技术，从最初提出的基于页的反向映射到各种改进方式的可行性。 第二章主要探讨研究l i n u x 内存管理减少外部分片和内部分片所采取的b u d d y 算 法、分配器的技术以及在伙伴算法中增加的v m a l l o e 函数。l i n u x 在这块管理方面的性 能在经过用户的测试具有比较高的效率，目前很多嵌入式操作系统没有统一的内存分 配管理标准，很多时候都是在参考l i n u x 内存分配管理方式。 第三章主要研究虚拟地址到物理地址的转化以及保证各个进程公平有效的分享 物理内存的虚拟内存管理方式。同时介绍l i n u x 2 6 内核加入的新技术：使用更大的内 存页、页表条目存储在高端内存中以及基于页的反向映射技术。 第四章重点分析研究l i n u x 2 6 内核加入的反向映射技术，也是本论文介绍的重点。 反向映射技术改善了查找映射到指定物理页对应的虚拟页的内存管理的瓶颈。本章主 要研究最初的基于页的反向映射技术及p 直接法的改进方式，从而为加入基于对象的 反向映射的方法及可行性增加理论依据。 第五章正是根据对前面l i n u x 虚拟内存的管理管理方式以及映射关系进行分析后 得出的基于对象反向映射的可行性。以及针对缺页调用时提出加入基于对象反向映射 的实现方式。 关键词：换页，基于页反向映射，基于对象反向映射 重庆大学硕士学位论文英文摘要 a b s t r a c t i nt h el i n u xo p e r a t i n gs y s t e m s y s t e mm e m o r ym a n a g e m e n tu n i tr e s p o n s i b l ef o r t h e o v e r a l lm a n a g e m e n to f t h ep h y s i c a la d d r e s ss p a c ea n dv i r t u a la d d r e s ss p a c e t r a n s l a t eu s e r v i r t u a la d d r e s s e st op h y s i c a la d d r e s s e sa n dt h ep a g e so u ts u c ho p e r a t i o n s i ti st h em o s t i m p o r t a n ts y s t e mk e r n e li n t e g r a lp a r to f , t h ee x i s t e n c ea n do p e r a t i o no ft h ee n t i r es y s t e mi s b a s e d h a v eas f f o n ga n ds o p h i s t i c a t e dm e m o r ym a n a g e m e n ts u b s y s t e mi sb u i l d i n gah i 曲 r e l i a b i l i t ya n ds c a l a b i l i t yo ft h es y s t e ma sah e d g ep i e c e s w i t ht h ed e v e l o p m e n ta n d m a t u r i t yo f t h el i n u xk e r n e l l i n u xu s e r sc a l ll o o kf o r w a r dt om o r eo f t h eo p e r a t i n gs y s t e m t oh a n d l ev e r yl a r g es c i e n t i f i ca n a l y s i so ft h ea p p l i c a t i o np r o c e d u r e o re v e nm a s s i v e d a t a b a s e l i n u xk e r n e l2 6r e l e a s ei n2 0 0 4 m a n yo ft h e2 6l i n u xk e r n e lu s i n gt e c h n o l o g y t oi m p r o v et h eu s eo f m e m o r y , i m p r o v em e m o r ym a n a g e m e n ts u b s y s t e me f f i c i e n c y i nt h ep a p e rt h el i n u xm e m o r ym a n a g e m e n tp a r to ft h e i rr e s e a r c h ，a n a l y s i so ft h e m a i nc e r e m o n ya tt h er e q u e s to ft h el i n u xo p e r a t i n gs y s t e mv i r t u a lm e m o r ym a n a g e m e n t a n dp a g i n gm e m o r ym a p p i n ga n dm a n a g e m e n tm e c h a n i s m s ，l i n u x 2 6f o c u so nt h ec o r e f o r m a l l yj o i n e dt h er e v e r s em a p p i n gt e c h n o l o g yb a s e do nt h er e v e r s eo fp a g e sf r o mt h e o r i g i n a lm a p p i n go f t h ef e a s i b i l i t yo f v a r i o u sm e t h o d so f i m p r o v e m e n t c h a p t e r2a n a l y z e sl i n u xm e m o r ym a n a g e m e n tp r o g r a m sa n dar e d u c t i o ni ns o m e p a r t so f t h ef i l mh a v et a k e nb u d d ya l g o r i t h mm o t s a d i s t r i b u t o rp a r t n e r si nt h et e c h n o l o g y a n da l g o r i t h m st oi n c r e a s et h ev m a l l o cf u n c t i o n i nap i e c eo f t h ep e r f o r m a n c em a n a g e m e n t o f l i n u xr i s e r sa f t e rt h et e s ti sah i g he f f i c i e n c y , m a n yo f t h ee m b e d d e do p e r a t i n gs y s t e mn o u n i f o r mm e m o r ya l l o c a t i o nm a n a g e m e n ts t a n d a r d sv e r yo f t e n , i nr e f e r e n c el i n u xm e m o r y a l l o c a t i o nm a n a g e m e n t c h a p t e r3a n a l y z e st h ev i r t u a la d d r e s s e si n t op h y s i c a la d d r e s s e s ，a n dt oe n s u r et h ef a i r a n de f f i c i e n ts h a r i n go ft h ep h y s i c a lp r o c e s s e si nt h ev i r t u a lm e m o r yt ob em e m o r y m a n a g e m e n t i n t r o d u c e dn e wt e c h n o l o g y ：t h eu s eo ft h el i n u xk e r n e lb ya d d i n gm o r e m e m o r yp a g e s p a g et a b l ee n t r i e sa r es t o r e di nm e m o r ya n dp a g e b a s e dr e v e r s em a p p i n g t e c h n o l o g y c h a p t e r4c o n t i n u et oj o i nt h ek e r n e la n a l y s i sl i n u x 2 6r e v g t s em a p p i n gt e c h n i q u e , b u t a l s ot h ef o c u so ft h ep r e s e n t a t i o n s r e v e r s em a p p i n gt e c h n o l o g yt oi m p r o v et h et r a c k i n go f t h ep h y s i c a lm a p p a g ec o r r e s p o n d i n gt ot h ed e s i g n a t e dp a g ev i r t u a lm e m o r ym a n a g e m e n ti n t h er e g i o n p a g e - b a s e dr e v e r s em a p p i n ga n dp a g e d i r e c ta p p r o a c ha n do b j e e t - b a s e dr e v e r s e 重庆大学硕士学位论文英文摘要 m a p p i n ga n df e a s i b i l i t yo f t h em e t h o da r et h i sc h a p t e rm a j o rc o n t e n t c h a p t e r5i sb a s e do nt h er i g h tf r o n to f t h el i n u xv i r t u a lm e m o r ym a n a g e m e n ta n d m a n a g e m e n tr e l a t i o n s h i pm a p p i n go f t h ea n a l y s i so b j e c t - b a s e dr e v e r s em a p p i n gf e a s i b i l i t y a n d a g a i n s tt h ep a g e j o i n e dt h ec a l lm a d eb a s e do no b j e c tm a p p i n gt h er e v e r s ew a y s k e y w o r d s ：p a g eo u t ，p a g e - b a s e dr e v e r s em a p p i n g ，o b j e c t - b a s e dr e v e r s em a p p i n g i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重鏖太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 王州) 签字日期： 2 l 。7 年月re t 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庞太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( v 7 ) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：王帅导师签 签字e t 期：踟印年月je t签字日 日 重庆大学硕士学位论文1 绪论 1 绪论 1 1 课题学术和实用意义 l i n u x 内核始于1 9 9 1 年由l i n u st o r v a l d s 为他的3 8 6 开发的一个类m i n i x 的操作 系统。随后l i n u x1 0 的官方版发行于1 9 9 4 年3 月，包含了3 8 6 的官方支持，仅支 持单c p u 系统。l i n u x l 2 发行于1 9 9 5 年3 月，它是第一个包含多平台支持的官方 版本。l i n u x2 0 发行于1 9 9 6 年6 月，它是第一个支持s m p 体系的内核版本。l i n u x 2 2 在1 9 9 9 年1 月到来，它带来了s m p 系统上性能的极大提升，同时支持更多的硬 件。l i n u x2 4 于2 0 0 1 年1 月发布，它进一步地提升了s m p 系统的扩展性，同时它 也集成了很多用于支持桌面系统的特性。l i n u x2 6 于2 0 0 3 年年底发布，无论是对于 企业服务器还是对于嵌入式系统，l i n u x2 6 都是一个巨大的进步。对高端的机器来 说，新特性针对的是性能改进、可扩展性、吞吐率，以及对s m p 机器n 1 7 _ - m a 的支 持。在进程调度、内存管理、文件系统、网络、系统安全、设备驱动等方面也都有很 大的改进。 从产品角度来说，计算机操作系统分为三类：服务器操作系统、桌面操作系统和 嵌入式操作系统。微软仅仅是在桌面部分占有垄断地位。在服务器部分，l i n u x 与u n i x 和w i n d o w s n t 三分天下的局面已经开始形成。l i n u x 服务器操作系统已经非常成熟， 完全可以替代u n i x 和n t 。随着l i n u x 内核的发展和成熟，为了增进l i n u x 做为服务 器操作系统的性能，l i n u x 内核在后期版本中使用了许多技术来改进系统内核，使得 l i n u x 更适合企业服务器的角色，也巩固其在服务器方面的位置。 在所有改进中对操作系统中的内存管理单元的改进相对最大，操作系统中的内存 管理单元负责管理整个系统的物理地址空间和虚地址空间，进行虚实地址之间的转换 以及页面的换人换出等操作。它是系统内核中最重要的组成部分之，是整个系统得以 存在和运行的基础。拥有一个强大和完备的内存管理子系统是构建一个具有高可靠性 以及可伸缩性系统的必备条件。l i n u x 内核的发展和成熟，更多的用户期待着l i n u x 可以运行非常大的系统来处理科学分析应用程序或者甚至海量数据库。2 6l i n u x 内核 使用了许多技术来改进对内存的使用，使得l i n u x 比以往任何时候都更适用于企业。 这些更重要的改变包括反向映射( r e v e r s e m a p p i n g ) 、使用更大的内存页、页表条目存 储在高端内存中，以及更稳定的内存管理器【l j 。 l i n u x 2 6 进行这些改善一方面是满足当前不断改进的硬件设备，包括多c p u 的兴 起，6 4 位芯片的成熟等。另一方面是改善l i n u x 操作系统的一些瓶颈，这些瓶颈已经 限制了l i n u x 内存管理效率的进一步提高。其中反向映射( r e v e r s em a p p i n g ) 技术的 重庆人学硕士学位论文1 绪论 加入就是为了改善l i n u x 内存管理中查找映射到指定物理页对应的虚拟页的内存管理 的瓶颈，提高页换出的效率【2 1 。不过最初的基于页的反向映射技术还颇有争议，有待 迸一步完善，本文就是重点讨论此技术改进问题。 1 2 国内外研究现状 l i n u x 2 6 内核增加了反向映射，大内存页，在高端内存中存储页表条目，其中反 向映射是目前国内外研究的重点方向，也是确实需要进步改进的方面。l i n u x 2 6 内核 想要释放映射到特定物理页的虚拟页采用的是基于页面的反向映射，这种方法对于页 面换出可以获得很高的效率。但此技术加入以后带来了最重要、明显的代价是内存开 销。不得不用一些内存来保持对所有那些反向映射的追踪，而且这些内存必须是低端 内存。所以随后就提出一种改进方式p 页直接方法( p a g e - d i r e c ta p p r o a c h ) 。这种方式 是对大多数页可以优化到只使用一个条目而不使用链表。即如果只有一个到这个页的 映射，那么可以用一个叫做“d i r e c t ”的指针来代替链表。只有在某个页只是由一个惟 一的进程映射时才可以进行这种优化。一个标记设置用来告诉内存管理器什么时候这 种优化对一个给定的页有效。此外，增加反向映射指针同时会对一些过程产生影响， 如页面错异常，进程复制退出，内存映射等，对于大于一个页面的对象( 如v m a ) 在这些过程中会降低性能，这是如果采用基于对象的反向映射，会获得比较好的性能。 不过基于对象的反向映射同时存在缺点，因为并不是所有的页面都具有对象属性，所 以针对不具有对象属性的的页面，必须采取特殊处理方式，这对设计要求要更高些【3 】。 目前关于反向映射技术的研究还有分歧，但是支持去掉l i n u x 内核中反向映射技术 的呼吁还是越来越少了。改进方式方法逐渐成熟，其中以采用基于对象反向映射技术 为主。通过分析l i n u x 页的基本分类，采用分类处理的方式，使反向映射技术更加成熟， 对系统资源消耗逐渐降低。 1 3 本文的研究目的和研究内容 本文打算设计出一种更合理的更高效的关于内存管理的方式，使l i n u x 更适合现 代大内存机器，多进程系统的应用。首先分析l i n u x 内存管理方式，学习l i n u x 进程 虚拟内存的管理基础知识，理解l i n u x 如何管理物理内存以及多进程。深入了解进程用 户空间，进程内核空间以及进程虚存区域。了解物理内存页式管理方式的优缺点，从 而进一步理解如何内存映射和管理机制。可以说虚拟存储技术是l i n u x 多进程稳定运 行的基础。 根据虚拟内存抽象模型，每个进程都可以互不干扰的使用所有虚拟地址。每一个 进程都维护一个自己的页表。l i n u x 为了统一不同的处理器分页级别，采用了三级分 页管理方式。虚存管理器不断的调整页目录和页表项，以反映物理内存和页表的映射 2 重庆大学硕士学位论文1 绪论 关系。 可以说页表保持对进程使用的内存物理页的追踪，它们将虚拟页映射到物理页， 不过这种映射是单方向映射。如果系统准备释放某个指定的物理页，必须找到映射那 个页的每一个进程，这样那些进程中相应页的页表条目才可以被更新。在l i n u x2 4 内 核中，这是一项任务执行效率比较低，因为为了确定某个页是否被某个进程映射，必 须遍历每个进程的页表，无法通过该物理页面找到对应的虚拟页以及对应的页表条 目。随着在系统中运行的进程数量的增加，将这些页交换出去的工作量也会增加。尤 其在面对要交换共享内存页时的情况会更复杂。 所以在l i n u x 2 6 内核中加入了反向映射技术，本文就是重点研究反向映射技术。 2 6 版内核最初加入的是基于页面反向映射( p a g e - b a s e d r e v e r s e m a p p i n g ) 技术， 虽然对单独指定物理页的释放具有很高的效率，不过对低端内存的占用以及在进程创 建，撤消时带给系统的较复杂操作，也使这项技术的加入受到很大质疑。 本文首先研究反向映射的基本原理，以及加入基于页反向映射技术后体现出的优 缺点。然后分析p 页直接方法( p a g e d i r e c ta p p r o a c h ) 在减少内存占用方面的可行性。 最后研究基于对象反相映射( o b j e c t - b a s e dr e v e r s em a p p i n g ) 的可行性以及必要性。最终 通过对页的属性进行基本分类，分为a n o n y m o u sp a g e s 和f i l e - b a c k e dp a g e s 。针对不同 种类的页采用不同处理方式，将页面与对象属性相结合，对特殊内存页采用特殊处理 方式，从而最终实现基于对象反向映射技术。 1 4 论文的内容安排 论文的内容的具体安排如下： 第一章：研究了l l i n u x 内存管理技术的研究现状。对论文的内容以及组织安排进 行概要地介绍。 第二章：主要分析l i n u x 内存管理减少外部分片和内部分片所采取的b u d d y 算法、 s l a b 分配器的技术以及在伙伴算法中增加的v m a l l o e 函数。 第三章：主要分析虚拟地址到物理地址的转化以及保证各个进程公平有效的分享 物理内存的虚拟内存管理方式。同时分析了l i n u x 2 6 内核加入的新技术。 第四章：重点研究l i n u x 2 6 内核加入的反向映射技术，从基于页的反向映射技术 及p 直接法的改进方式到基于对象的反向映射技术。 第五章：总结了论文的工作，并指出了进一步研究工作的方向。 重庆大学硕士学位论文l i n u x 内存管理综述 2l i n u x 内存管理综述 2 1l i n u x 存储管理方式简介 l i n u x 操作系统采用了请求式分页虚拟存储管理方法。虚拟存储器的基本思想是： 程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留 在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。当进 程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在 内存时，由系统自动完成将它们从外存调入内存工作在进程开始运行之前，不是装入 全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面； 当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装 入新的页面。当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某 些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态 调度。 2 2 进程虚拟内存的管理 进程运行时能访问的存储空间只是它的虚拟内存空间。对当前该进程而言只有属 于它的虚拟内存是可见的。每个任务拥有不同的虚拟地址到物理地址的映射，内核空 间地址有自己对应的页表，用户进程各自有不同的页表，进程彼此之问虚拟内存空间 是独立的 4 1 。在进程的虚拟内存包含着进程本身的程序代码和数据。进程在运行中还 必须得到操作系统的支持。进程的虚拟内存中还包含着操作系统内核。所以l i n u x 把 进程的虚拟内存分成两部分，内核区和用户区。操作系统内核的代码和数据等被映射 到内核区，进程的可执行映像( 代码和数据) 映射到虚拟内存的用户区。进程虚拟内 存的内核区的访问权限设置为0 级，用户区为3 级。内核访问虚存的权限为0 级，而 进程的访问权限为3 级。l i n u x 运行在x 8 6 时，进程的虚拟内存为4 g b 。4 g 的进程地 址空间被人为的分为两个部分一一用户空间与内核空间。用户空间从0 到3 g ( 0 x c 0 0 0 0 0 0 0 ) ，内核空间占据3 g 到4 g 。用户进程通常情况下只能访问用户空间的 虚拟地址，不能访问内核空间虚拟地址。例外情况只有用户进程进行系统调用等时刻 可以访问到内核空间。用户空间对应进程，所以每当进程切换，用户空间就会跟着变 化；而内核空间是由内核负责映射，它并不会跟着进程改变，是固定的。进程的虚拟 空间如图2 1 ： 4 重庆大学硕士学位论文l i n u x 内存管理综述 0 x c 0 x 0 图2 1 进程的虚拟空间 f i 9 2 1v i r t u a l m e m o r y o f p e r p r o c e s s 2 2 1 进程用户空间 进程虚拟内存的用户区分成代码段、数据段、堆栈以及进程运行的环境变量、参 数传递区域等a 每一个进程，用一个m m s t r u c t 结构体来定义它的虚存用户区。 n z r ns t r u c t 结构体首地址在任务结构体t a s ks t r u c t 成员项m l n 中： s t r u c ti t l t ns t r u c t n 1 1 t i ； m ms t r u c t 结构如下： s t r u c tm m s t r u c t i n tc o u n t ； p g d _ t + p g d ； u n s i g n e dl o n gc o n t e x t ； u n s i g n e dl o n gs t a r t _ c o d e ，e n d _ c o d e ，s t a r t _ d a t a , e n dd a t a ； u n s i g n e dl o n gs t a r t _ b r k ，b r k ，s t a r t _ s t a c k , s t a r t _ m m a p ； u n s i g n e dl o n ga r g _ s t a r t ，a r g _ c n d ，e n v _ s t a r t ，e n v _ e n d ； u n s i g n e dl o n gr s s , t o t a l _ v m ，l o c k e d _ v m ； u n s i g n e dl o n gd e f _ _ f l a g s ； s t r u c tv m a r e a s t r u c t + m m a p ； s t r u c tv m a r e a s t r u c t + m m a p a v l ； s t r u c ts e m a p h o r em m a p _ s e r n ； 重庆大学硕士学位论文l i n u x 内存管理综述 ) ； p g d 为指向进程页目录表的指针；c o n t e x t 是进程上下文的地址；s t a r tc o d e , e n dc o d e ，s t a r td a t a ，e n dd a t a 分别为代码段、数据段的首地址和终止地址；s t a l ts t a c k 是进程堆栈的首地址；a r g _ _ s t a r la r g _ e n d ，e n v s t a r t ，e n v _ e n d 分别为参数区、环境变量 区的首地址和终止地址。 2 。2 2 进程内核空间 进程虚拟内存的内核区主要包括操作系统内核的代码和数据等。所有进程内核空 间均相同，具有相同页目录和页表。内核虚拟空间3 g b 到3 g b + 8 m b 映射到物理内存 0 到8 m b ，对应内核启动和设备内存映射等，虚拟内存的组织如图2 2 所示： 图2 2 虚存空间示意图 f i g 2 2v i r t u a lm e m o r yo f k e r n e l 2 2 3 进程虚存区域 在l i n u x 内核中对应进程内存区域的数据结构是：v ma r e as t r u c t ，内核将每个内 存区域作为一个单独的内存对象管理，相应的操作也都一致。采用面向对象方法使 v m a 结构体可以代表多种类型的内存区域一一比如内存映射文件或进程的用户空间 栈等，对这些区域的操作也都不尽相同。v ma r e as t r u c t 首地址在m i l ls t r u c t 结构体中。 v ma r e as t r u c t 是描述进程地址空间的基本管理单元，一个进程一般需要多个内 存区域来描述它的虚拟空间，v l na r e as t r u c t 结构以链表形式链接。为了提高查找效率， 内核又以红黑树的形式组织内存区域，以便降低搜索耗时。并存两种组织形式，并非 冗余：链表用于需要遍历全部节点的时候用，而红黑树适用于在地址空间中定位特定 内存区域的时候巧】。内核为了内存区域上的各种不同操作都能获得高性能，所以同时 使用了这两种数据结构。进程地址空间的管理模型如图2 3 ： 6 重庆大学硕士学位论文l i n u x 内存管理综述 t a s k s tr u c t a m _ s t r u c t v ma r e a _ z t r u c t 进程虚存空间 蕴裤嗟域i r u c t 瞳存区城 v mo p e r a t i s t r u c t 图2 3 进程地址空间示意图 f i g2 3t h ea d d r e s so f p r o c e s s 进程的地址空间对应的描述结构是“内存描述符结构”，它表示进程的全部地址空 间，包含了进程的内存区域和进程地址空间其它有关的全部信息。v m a r e a s t r e u t 结构 如下： s t r u c tv m a r e a s t r u c t s t r u c tm m _ s t r u c t + v m _ m m ； u n s i g n e dl o n gv ms t a r t ； u n s i g n e dl o n gv m _ c n d ； p g p r o t _ tv m _ p a g e j r o t ； u n s i g n e ds h o r tv mf l a g s ； s h o r tv m a v lh e i g h t ； s t r u c tv m a r e a s t r u c t v m a v l 一1 e f t ； s t r u c tv m a r e a s t r u c t + v m _ a v l _ r i g h t ； s t r u c tv m a r e a s t r u e t v m _ n e x t ； s t r u e tv m a r e a s t r u c t + v m n e x t s h a r e ； s t r u c tv m a r e a s t r u c t v m - p r e v _ s h a r e ； 7 妻磊一 重庆大学硕士学位论文l i n u x 内存管理综述 s t r u c tv m _ o p e r a t i o n s _ s t r u c t v m _ o p s ； u n s i g n e dl o n gv mo f f s e t ； s t r u c ti n o d e v mi n o d e ； u n s i g n e dl o n gv mp t e ； ) ； v l n m l n 指针指向进程的m ms t r u c t 结构体。v m _ s t a r t 和v m e n d 虚拟区域的开始 和终止地址。v m _ f l a g s 指出了虚存区域的操作特性。v mp a g e _ p r o t 虚存区域的页面的 保护特性。若虚存区域映射的是磁盘文件或设备文件的的内容，则啪i n o d e 指向这 个文件的i n o d e 结构体，否则v mi n o d e 为n u l l 。v i i lo f f s e t 是该区域的内容相对于文 件起始位置的偏移量，或相对于共享内存首址的偏移量。所有v ma r e as t m c t 结构体 链接成一个单向链表，v i i in e x t 指向下一个v t nr r e as t r u c t 结构体。链表的首地址由 m ms t r u c t 中成员项m m a p 指出。v i i i 是指向结构体的指针，_ o p s v i i io p e r a t i o n s _ s t r u c t 该结构体中包含着指向各种操作的函数的指针。所有v ma r e as t r u c t 结构体组成一个 a v l 树，a v l 树是一种具有平衡结构的二叉树，v ma v ll e f t 左指针指向相邻的低地 址虚存区域，v ma v lr i g h t 右指针指向相邻的高地址虚存区域，m m a p 表示进程_avl a v l 树的根，v i i ia v l表示树的高度。 和，把highta v lv mn e x ts h a r ev mp r e x ts h a r e 有关的v i i ia r e as l n j c t 结合成一个共享内存时使用的双向链表。 2 3 物理内存页式管理方式 进程所能直接操作的地址都为虚拟地址。当进程需要内存时，从内核获得的仅仅 时虚拟的内存区域，而不是实际的物理地址，进程并没有获得物理内存，获得的仅仅 是对一个新的线性地址区间的使用权。实际的物理内存只有当进程真的去访问新获取 的虚拟地址时，才会由“请页机制”产生“缺页”异常，从而进入分配实际页框的例 程。该异常是虚拟内存机制赖以存在的基本保证它会告诉内核去真正为进程分配 物理页，并建立对应的页表，即建立虚拟地址到物理地址的映射，之后虚拟地址才实 实在在映射到了系统物理内存上。 逻辑地址：出现在机器指令中，用来制定操作数的地址。线性地址：逻辑地址经 过分段单元处理后( 如将段地址左移四位与偏移量) 得到线性地址，这是一个3 2 位的 无符号整数，可用于定位4 g 个存储单元。物理地址：线性地址经过页表查找后得出 物理地址，这个地址将被送到地址总线上指示所要访问的物理内存单元。 l i n u x 对物理内存空间按照分页方式进行管理，把物理内存划分成大小相同的物 理页面。在x 8 6 机器中一个页面的大小为4 k b ，在a l p h a 、s p a r e 中一个页面大小8 k b 。 l i n u x 设置了一个m e r em a p 数组管理内存页面。m e m _ m a p 在系统初始化时由 f r e ea r e ai n i t o 函数创建，它存放在物理内存的底部。m e n lm a p 数组的元素是个个 重庆大学硕士学位论文l i n u x 内存管理综述 的p a g e 结构体，每一个p a g e 结构体它对应一个物理页面。p a g e 结构如下： t y p e d e fs t r u e tp a g e s t r u e tp a g e n e x t ； s t r u c tp a g e p r e y ； s t r u c ti n o d e + i n o d e ； u n s i g n e dl o n go f f s e t ； s t r u e tp a g e + n e x t _ h a s h ； a t o m i e _ tc o u n t ； u n s i g n e df l a g s ； u n s i g n e dd i r t y ：1 6 ，a g e ：8 ； s t r u c tw a i t _ q u e u e + w a i t ； s t r u e tb u f f e r _ h e a d + b u f f e r s ； u n s i g n e dl o n gs w a p _ u n l o c k _ e n t r y ； u n s i g n e dl o n gm a p _ m ； ) m e m _ m a p _ t ； c o u n t 是共享该页面的进程计数。a g e 是标志页面的“年龄”。d i r t y 是表示该页面 是否被修改过。p r e v 和n e x 是把p a g e 结构体链接成一个双向循环链表。p r e yh a s h 和 n e x t _ h a s h 是有关p a g e 结构体连成一个哈希表。i n o d e 和o f f s e t 是有关文件的i n o d e 和 它们在文件中的偏移量。w a i t 是等待该页资源的进程等待队列的指针。f l a g 是页面标 志。m a pn r 是该页面p a g e 结构体在m e m _ m a p 数组中的下标值，也就是物理页面的 页号。 分配和回收内存的基本单位是内存页。利用分页管理有助于灵活分配内存地址。 系统使用内存虽然可以使用非连续内存块，不过考虑到效率，系统分配内存更倾向于 分配连续的内存块，因为分配连续内存时，页表不需要更改，因此能降低t l b 的刷新 率。 鉴于上述需求，内核分配物理页为了尽量减少不连续情况，采用了“伙伴”关系， 即b u d d y 算法来管理空闲页框。分配器维护空闲页面所组成的块，这里每一块都是2 的方幂个页面。方幂的指数被称为阶。内核用构数组f r e ea r e at 对每一个阶进行维护， f r e ea r e at 一个数组元素用于指向一个空闲页面块的链表。数组的第0 个元素将会指 向具有1 个页面大小的块的链表，第一个元素将会是一个具有2 个页面大小的块的 链表，直到2 的o r d e rm a x 次幂个页面大小的块，m a x _ o r d e r 的值一般为1 0 。 这消除了一个大页面被分开来满足一个小页面块即能满足的要求的可能性。 在请求内存分配时，系统按照b u d d y 算法，根据请求的页面数在f r e e _ a r e a 对应 的空闲页块组中搜索，若请求的页面数不是2 的整数次幂，则按照稍大于请求数的2 9 重庆大学硕士学位论文 l i n u x 内存管理综述 的整数次幂的值搜索相应的页面块组。当相应的页块组中没有可使用的空闲页面块时 就查询更大一些的页块组，在找到可利用的空闲页面块后，分配所需的页面。当某一 空闲页面块被分配后，若仍有剩余的空闲页面，则根据剩余页面的大小把它们加入到 相应的页块组中。在内存页面释放时，系统将做为空闲页面看待。然后检查是否存在 与这些页面相邻的其它空闲页块，若存在，则合为一个连续的空闲区按b u d d y 算法重 新分组【6 】。 内存管理理论角度而言目的基本是一致的，都是为了防止“分片”，分片又分为 外部分片和内部分片，内部分片是说系统为了满足一小段连续内存区的需要，不得不 分配了一大区域连续内存给它，从而造成了空间浪费；外部分片是指系统虽有足够的 内存，但却是分散的碎片，无法满足对大块“连续内存”的需求。无论何种分片都是 系统有效利用内存的障碍。 以页为最小单位分配内存对于内核管理系统物理内存来说的确比较方便，但内核 自身最常使用的内存却往往是很小( 远远小于一页) 的内存块一比如存放文件描述 符、进程描述符、虚拟内存区域描述符等行为所需的内存都不足一页。这些用来存放 描述符的内存相比页面而言，只是页面空间的百分之一甚至更小。一个整页中可以聚 集多个这种这些小块内存；而且这些小块内存块频繁地生成销毁。 为了满足内核对这种小内存块的需要，l i n u x 系统采用了一种被称为s i a b 分配器 的技术。s l a b 分配器的实现比较复杂，其核心思想是“存储池”的运用。内存片段( 小 块内存) 被看作对象，当被使用完后，并不直接释放而是被缓存到“存储池”里，留 做下次使用，这避免了频繁创建与销毁对象所带来的额外负载。 s l a b 技术不但避免了内存内部分片带来的不便，而且可以很好利用硬件缓存提高 访问速度。s l a b 分配器不仅仅只用来存放内核专用的结构体，还被用来处理内核对小 块内存的请求。鉴于s l a b 分配器的特点，内核程序中对小于一页的小块内存的请求才 通过s l a b 分配器提供的接口k m a l l o e 来完成。 在l i n u x 中，外部碎片不是一个非常严重的问题，不过为了满足对大块连续页面 的请求的目的，在伙伴算法中增加了v m a l l o c 函数。内核内存管理借用了用户空间分 配虚拟内存，即内存逻辑上连续，其实影射到并不一定连续的物理内存上。所以v m a l l o e 函数实现原理：允许内核程序在内核地址空间中分配虚拟地址，同样也利用页表( 内 核页表) 将虚拟地址影射到分散的内存页上。与进程虚拟地址的特性一样，这些虚拟 地址可与物理内存没有简单的位移关系，必须通过内核页表才可转换为物理地址或物 理页。它们有可能尚未被映射，在发生缺页时才真正分配物理页框。结构v 1 t is t r u c t 描述由v m a l l o e ( ) 分配的虚存块，