基于对象的反向映射机制的研究

魏绍蓉

(青海大学计算机技术与应用系，青海西宁810016)

0 引言

操作系统中内核管理的一个重要资源就是内存，为了提高效率，一般情况下内存是按照内存页的形式进行管理的，而为了支持多个用户使用，有时可能会出现内存被耗光的情况，所以操作系统管理内存的物理页面，就必须担任内存分配和内存回收的职责。应用程序可以通过内存分配函数向操作系统申请物理页面。在使用完这些物理页面之后，应用程序可以通过相应的内存释放函数释放这些物理页面。但是，对于内存中的某些物理页面来说，页面的使用者并不会主动释放它们，如果这些物理页面一直被占用而得不到释放，那么无论计算机上可用的物理内存有多少，物理内存迟早都有被用完的时候。所以，对于无法被主动释放的物理页面来说，操作系统就需要提供相应的功能去释放它们。所以我们要选择页面回收算法进行页面回收，但是在页面回收之前，操作系统要做的就是对与回收页面相关的进程的页表项进行更新，那么现在的问题是:我们使用什么样的机制找到这些与回收页面相关的进程呢?

1 Linux中的页面回收算法

Linux中的页面回收是基于最近最少使用(Least Recently Used，LRU) 算法［1］。LRU 算法的基本原理是为每个物理页面绑定1个计数器，用以标识该页面的访问频度。操作系统内核进行页面回收的时候就可以根据页面的计数器的值来确定要回收哪些页面。然而，在硬件上提供这种支持的体系结构很少，Linux操作系统没有用页计数器去跟踪每个页面的访问情况，而是在页表项中增加了一个 Accessed位，当页面被访问到的时候，该位就会被硬件自动置位。该位被置位表示该页面还很年轻，不能被换出去。此后，在系统的运行过程中，该页面的年龄会被操作系统更改。所以在Linux中，操作系统对LRU的实现主要是基于1对双向链表［4］:active链表和 inactive链表，这2个链表是Linux操作系统进行页面回收所依赖的关键数据结构，每个内存区域都存在1对这样的链表。那些经常被访问的处于活跃状态的页面会被放在 active链表上，而那些虽然可能关联到1个或者多个进程，但是并不经常使用的页面则会被放到 inactive链表上。页面会在这2个双向链表中移动，操作系统会根据页面的活跃程度来判断应该把页面放到哪个链表上。页面可能会从active链表上被转移到inactive链表上，也可能从inactive链表上被转移到 active链表上，但是，这种转移并不是每次页面访问都会发生，页面的这种转移发生的间隔有可能比较长［9］。那些最近最少使用的页面会被逐个放到inactive链表的尾部。进行页面回收的时候，Linux操作系统会从 inactive链表的尾部开始进行回收。

用于描述内存区域的struct zone()中关于这两个链表以及相关的关键字段的定义如下:

struct zone{

……

struct list_head active_list;管理内存区域中处于活跃状态的页面。

struct list_head inactive_list;管理内存区域中处于不活跃状态

的页面。

unsigned long nr_active;链表上的页面数目。

unsigned long nr_inactive;链表上的页面数目。

……

}

但是，操作系统并不能只考虑回收页面，还要考虑到在把页面回收或者页面被交换出去之前，必须找到映射那个页的每1个进程，这样那些进程中相应页的页表条目才可以被更新，这才是一个关键问题。

有研究显示，慢性持续性低钠血症与步态异常、注意力不集中以及骨质疏松、跌倒和骨折的发生有关[7-9]。人体内约有1/3的钠离子储存在骨骼中，而其中40%是可交换的。当慢性持续性低钠血症发生时，体内的钠离子处于慢性消耗的状态，钠离子逐渐从骨骼中游离交换至血液循环中，骨骼脱矿化，破骨细胞活性逐渐增强，最终导致骨质疏松。而低钠血症同时又影响着中枢神经系统，导致步态异常、注意力减退[10]。此外，低钠血症还与肌肉质量的减少相关，为住院患者跌倒的风险因素之一[11-12]。

2 基于对象的反向映射机制

2.1 反向映射机制

在Linux内存管理器中，页表保持对进程使用的内存物理页的追踪，它们将虚拟页映射到物理页。有些页可能不是长时间使用，它们应该被交换出去。但是在交换出去之前，我们首先要做的就是要更新使用该交换页的每1个进程的页表项。为了更新进程页表项，以往为了确定某个要回收的物理页面都被哪些页表项引用，必须要遍历所有进程，这是1项非常耗资源和时间的工程［5］。所以引入反向映射(RMAP)机制，使得更加有效地回收1个共享页面，反向映射技术的实现主要是基于页表项链表。操作系统为每1个物理页面都维护了1个链表，所有与该物理页面关联的页表项都会被放到这个链表上，建立了物理页面和所有映射了该物理页面的页表项之间的1种关联，从而让操作系统可以快速定位引用了该物理页面的所有页表项，不再是遍历每个进程的页表。该机制中内存管理器为每1个物理页建立了1个链表，包含了指向当前映射那个页的每1个进程的页表条目(Page-Table Entries，PTE)的指针。然而基于页表项链表存在为每个物理页面维护这样1个链表，同样需要占用大量的内存空间造成空间资源的消耗。回收1个物理页面的时候，需要先获取该链表上的锁，然后遍历相应的反向映射链表，链表上的项越多，需要的时间越多，造成时间资源消耗越大。为了解决这一弊端引入基于对象的反向映射机制。

2.2 基于对象的反向映射机制

基于对象的反向映射机制也是为物理页面设置1个用于反向映射的链表，但是链表上的节点不再是引用该物理页面的所有页表项，而是相应的虚拟内存区域(vm_area_struct结构)，虚拟内存区域通过内存描述符(mm_struct结构)找到页全局目录，从而找到相应的页表项，在一定程度上也节约了内存空间。用于表示虚拟内存区域的描述符比用于表示页面的描述符要少得多，所以遍历基于对象的反向映射链表所消耗的时间也会少很多。所以在一定程度上减少了空间资源和时间资源的消耗。

基于对象的反向映射的实现，数据结构page结构中与基于对象的反向映射相关的关键字段:_mapcount和mapping。

struct page{

atomic_t_mapcount;

union{

……

struct{

……

struct address_space*mapping;

};

……

};

字段_mapcount表明共享该物理页面的页表项的数目。该计数器可用于快速检查该页面除所有者之外有多少个使用者在使用，初始值是 －1，每增加一个使用者，该计数器加1。字段mapping用于区分匿名页面和基于文件映射的页面，如果该字段的最低位被置位了，那么该字段包含的是指向 anon_vma用于匿名页面结构的指针;否则，该字段包含指向 address_space结构的用于基于文件映射页面指针。

2.3 基于对象的反向映射机制的优势

使用基于对象的反向映射机制改善了查找映射到指定物理页对应的虚拟页的内存管理的瓶颈，并且可以快速定位引用了某个物理页面的所有页表项，这极大地方便了操作系统进行页面回收。相对于之前的遍历方法来说，基于对象的反向映射机制在很大程度上减少了操作系统在页面回收上所占用的 CPU时间。相对于之前的单纯的反向映射机制来说，在一定程度上也解决了要消耗掉一定的内存空间的问题。

3 结语

操作系统中的内存管理负责管理整个系统的物理地址空间和虚地址空间，进行虚实地址之间的转换以及页面的换入换出等操作。它是系统内核中最重要的组成部分之一，是整个系统得以存在和运行的基础。而利用基于对象的反向映射机制和页面回收算法的结合，在最少时间和最少空间消耗的前提下，更有效地进行页面回收是内存管理系统构建一个具有高可靠性、可伸缩性系统的必要前提。

［1］ 赵丽坤.Linux内核内存管理机制和改进［J］.电脑知识与技术，2009(10):112-115.

［2］ 文东戈，王 旭.Linux操作系统原理实验教学平台的设计与应用［J］.实验室研究与探索，2008(5):68-70.

［3］ 王东滨.面向网络数据实时检测的多线程内存管理技术［J］.高技术通讯，2008(12):213-215.

［4］ 韩耀堂.C#编程中的内存管理不该忽略的问题［J］.计算机光盘软件与应用，2011(13):73-76.

［5］ 左利云.基于内存管理的多重查询调度算法［J］.计算机技术与发展，2010(7):121-125.

［6］ 敖青云.存储技术原理分析［M］.北京:电子工业出版社.2011:103-189.

［7］ 莫尔勒著，郭旭译.深入Linux内核架构［M］.北京:人民邮电出版社.2010:135-246.

［8］ 雷铭哲Linux线程机制研究.火力与指挥控制［J］.2010(2):112-118.

［9］ 梁 琛.Linux内核链表及其在虚拟文件系统中的应用［J］.西安邮电学院学报.2011(2):29-33.

［10］ 刘宾礼，孙俊忠，周智勇，等.链表浅析［J］.电脑学习，2010(1):141-142.

［11］ ［美］博韦，西斯特著陈莉君译.深入理解Linux内核［M］.北京:中国电力出版社，2008:178-283.

［12］ 胡章平.虚拟存储管理中缺页中断次数的计算方法［J］.电脑知识与技术.2009(2):272-274.

［13］ 李亚琼.一种面向虚拟化云计算平台的内存优化技术［J］.计算机学报，2011(4):684-690.

［14］ 陈志文，李 亮.基于Linux的安全存储系统设计［J］.计算机工程与设计，2009(15):91-93.

［15］ 张玉洁.文件系统安全存储算法研究与系统设计［J］.华北科技学院学报，2011，30(2):66-69.

［16］ 郑 巍，许 鸿.开源软件Linux内核的进化分析［J］.华南理工大学学报，2007，35(9):74-77.