基于對(duì)象的反向映射機(jī)制的研究

魏紹蓉

(青海大學(xué)計(jì)算機(jī)技術(shù)與應(yīng)用系，青海西寧810016)

0 引言

操作系統(tǒng)中內(nèi)核管理的一個(gè)重要資源就是內(nèi)存，為了提高效率，一般情況下內(nèi)存是按照內(nèi)存頁(yè)的形式進(jìn)行管理的，而為了支持多個(gè)用戶使用，有時(shí)可能會(huì)出現(xiàn)內(nèi)存被耗光的情況，所以操作系統(tǒng)管理內(nèi)存的物理頁(yè)面，就必須擔(dān)任內(nèi)存分配和內(nèi)存回收的職責(zé)。應(yīng)用程序可以通過(guò)內(nèi)存分配函數(shù)向操作系統(tǒng)申請(qǐng)物理頁(yè)面。在使用完這些物理頁(yè)面之后，應(yīng)用程序可以通過(guò)相應(yīng)的內(nèi)存釋放函數(shù)釋放這些物理頁(yè)面。但是，對(duì)于內(nèi)存中的某些物理頁(yè)面來(lái)說(shuō)，頁(yè)面的使用者并不會(huì)主動(dòng)釋放它們，如果這些物理頁(yè)面一直被占用而得不到釋放，那么無(wú)論計(jì)算機(jī)上可用的物理內(nèi)存有多少，物理內(nèi)存遲早都有被用完的時(shí)候。所以，對(duì)于無(wú)法被主動(dòng)釋放的物理頁(yè)面來(lái)說(shuō)，操作系統(tǒng)就需要提供相應(yīng)的功能去釋放它們。所以我們要選擇頁(yè)面回收算法進(jìn)行頁(yè)面回收，但是在頁(yè)面回收之前，操作系統(tǒng)要做的就是對(duì)與回收頁(yè)面相關(guān)的進(jìn)程的頁(yè)表項(xiàng)進(jìn)行更新，那么現(xiàn)在的問(wèn)題是:我們使用什么樣的機(jī)制找到這些與回收頁(yè)面相關(guān)的進(jìn)程呢?

1 Linux中的頁(yè)面回收算法

Linux中的頁(yè)面回收是基于最近最少使用(Least Recently Used，LRU) 算法［1］。LRU 算法的基本原理是為每個(gè)物理頁(yè)面綁定1個(gè)計(jì)數(shù)器，用以標(biāo)識(shí)該頁(yè)面的訪問(wèn)頻度。操作系統(tǒng)內(nèi)核進(jìn)行頁(yè)面回收的時(shí)候就可以根據(jù)頁(yè)面的計(jì)數(shù)器的值來(lái)確定要回收哪些頁(yè)面。然而，在硬件上提供這種支持的體系結(jié)構(gòu)很少，Linux操作系統(tǒng)沒(méi)有用頁(yè)計(jì)數(shù)器去跟蹤每個(gè)頁(yè)面的訪問(wèn)情況，而是在頁(yè)表項(xiàng)中增加了一個(gè) Accessed位，當(dāng)頁(yè)面被訪問(wèn)到的時(shí)候，該位就會(huì)被硬件自動(dòng)置位。該位被置位表示該頁(yè)面還很年輕，不能被換出去。此后，在系統(tǒng)的運(yùn)行過(guò)程中，該頁(yè)面的年齡會(huì)被操作系統(tǒng)更改。所以在Linux中，操作系統(tǒng)對(duì)LRU的實(shí)現(xiàn)主要是基于1對(duì)雙向鏈表［4］:active鏈表和 inactive鏈表，這2個(gè)鏈表是Linux操作系統(tǒng)進(jìn)行頁(yè)面回收所依賴的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，每個(gè)內(nèi)存區(qū)域都存在1對(duì)這樣的鏈表。那些經(jīng)常被訪問(wèn)的處于活躍狀態(tài)的頁(yè)面會(huì)被放在 active鏈表上，而那些雖然可能關(guān)聯(lián)到1個(gè)或者多個(gè)進(jìn)程，但是并不經(jīng)常使用的頁(yè)面則會(huì)被放到 inactive鏈表上。頁(yè)面會(huì)在這2個(gè)雙向鏈表中移動(dòng)，操作系統(tǒng)會(huì)根據(jù)頁(yè)面的活躍程度來(lái)判斷應(yīng)該把頁(yè)面放到哪個(gè)鏈表上。頁(yè)面可能會(huì)從active鏈表上被轉(zhuǎn)移到inactive鏈表上，也可能從inactive鏈表上被轉(zhuǎn)移到 active鏈表上，但是，這種轉(zhuǎn)移并不是每次頁(yè)面訪問(wèn)都會(huì)發(fā)生，頁(yè)面的這種轉(zhuǎn)移發(fā)生的間隔有可能比較長(zhǎng)［9］。那些最近最少使用的頁(yè)面會(huì)被逐個(gè)放到inactive鏈表的尾部。進(jìn)行頁(yè)面回收的時(shí)候，Linux操作系統(tǒng)會(huì)從 inactive鏈表的尾部開(kāi)始進(jìn)行回收。

用于描述內(nèi)存區(qū)域的struct zone()中關(guān)于這兩個(gè)鏈表以及相關(guān)的關(guān)鍵字段的定義如下:

struct zone{

……

struct list_head active_list;管理內(nèi)存區(qū)域中處于活躍狀態(tài)的頁(yè)面。

struct list_head inactive_list;管理內(nèi)存區(qū)域中處于不活躍狀態(tài)

的頁(yè)面。

unsigned long nr_active;鏈表上的頁(yè)面數(shù)目。

unsigned long nr_inactive;鏈表上的頁(yè)面數(shù)目。

……

}

但是，操作系統(tǒng)并不能只考慮回收頁(yè)面，還要考慮到在把頁(yè)面回收或者頁(yè)面被交換出去之前，必須找到映射那個(gè)頁(yè)的每1個(gè)進(jìn)程，這樣那些進(jìn)程中相應(yīng)頁(yè)的頁(yè)表?xiàng)l目才可以被更新，這才是一個(gè)關(guān)鍵問(wèn)題。

有研究顯示，慢性持續(xù)性低鈉血癥與步態(tài)異常、注意力不集中以及骨質(zhì)疏松、跌倒和骨折的發(fā)生有關(guān)[7-9]。人體內(nèi)約有1/3的鈉離子儲(chǔ)存在骨骼中，而其中40%是可交換的。當(dāng)慢性持續(xù)性低鈉血癥發(fā)生時(shí)，體內(nèi)的鈉離子處于慢性消耗的狀態(tài)，鈉離子逐漸從骨骼中游離交換至血液循環(huán)中，骨骼脫礦化，破骨細(xì)胞活性逐漸增強(qiáng)，最終導(dǎo)致骨質(zhì)疏松。而低鈉血癥同時(shí)又影響著中樞神經(jīng)系統(tǒng)，導(dǎo)致步態(tài)異常、注意力減退[10]。此外，低鈉血癥還與肌肉質(zhì)量的減少相關(guān)，為住院患者跌倒的風(fēng)險(xiǎn)因素之一[11-12]。

2 基于對(duì)象的反向映射機(jī)制

2.1 反向映射機(jī)制

在Linux內(nèi)存管理器中，頁(yè)表保持對(duì)進(jìn)程使用的內(nèi)存物理頁(yè)的追蹤，它們將虛擬頁(yè)映射到物理頁(yè)。有些頁(yè)可能不是長(zhǎng)時(shí)間使用，它們應(yīng)該被交換出去。但是在交換出去之前，我們首先要做的就是要更新使用該交換頁(yè)的每1個(gè)進(jìn)程的頁(yè)表項(xiàng)。為了更新進(jìn)程頁(yè)表項(xiàng)，以往為了確定某個(gè)要回收的物理頁(yè)面都被哪些頁(yè)表項(xiàng)引用，必須要遍歷所有進(jìn)程，這是1項(xiàng)非常耗資源和時(shí)間的工程［5］。所以引入反向映射(RMAP)機(jī)制，使得更加有效地回收1個(gè)共享頁(yè)面，反向映射技術(shù)的實(shí)現(xiàn)主要是基于頁(yè)表項(xiàng)鏈表。操作系統(tǒng)為每1個(gè)物理頁(yè)面都維護(hù)了1個(gè)鏈表，所有與該物理頁(yè)面關(guān)聯(lián)的頁(yè)表項(xiàng)都會(huì)被放到這個(gè)鏈表上，建立了物理頁(yè)面和所有映射了該物理頁(yè)面的頁(yè)表項(xiàng)之間的1種關(guān)聯(lián)，從而讓操作系統(tǒng)可以快速定位引用了該物理頁(yè)面的所有頁(yè)表項(xiàng)，不再是遍歷每個(gè)進(jìn)程的頁(yè)表。該機(jī)制中內(nèi)存管理器為每1個(gè)物理頁(yè)建立了1個(gè)鏈表，包含了指向當(dāng)前映射那個(gè)頁(yè)的每1個(gè)進(jìn)程的頁(yè)表?xiàng)l目(Page-Table Entries，PTE)的指針。然而基于頁(yè)表項(xiàng)鏈表存在為每個(gè)物理頁(yè)面維護(hù)這樣1個(gè)鏈表，同樣需要占用大量的內(nèi)存空間造成空間資源的消耗。回收1個(gè)物理頁(yè)面的時(shí)候，需要先獲取該鏈表上的鎖，然后遍歷相應(yīng)的反向映射鏈表，鏈表上的項(xiàng)越多，需要的時(shí)間越多，造成時(shí)間資源消耗越大。為了解決這一弊端引入基于對(duì)象的反向映射機(jī)制。

2.2 基于對(duì)象的反向映射機(jī)制

基于對(duì)象的反向映射機(jī)制也是為物理頁(yè)面設(shè)置1個(gè)用于反向映射的鏈表，但是鏈表上的節(jié)點(diǎn)不再是引用該物理頁(yè)面的所有頁(yè)表項(xiàng)，而是相應(yīng)的虛擬內(nèi)存區(qū)域(vm_area_struct結(jié)構(gòu))，虛擬內(nèi)存區(qū)域通過(guò)內(nèi)存描述符(mm_struct結(jié)構(gòu))找到頁(yè)全局目錄，從而找到相應(yīng)的頁(yè)表項(xiàng)，在一定程度上也節(jié)約了內(nèi)存空間。用于表示虛擬內(nèi)存區(qū)域的描述符比用于表示頁(yè)面的描述符要少得多，所以遍歷基于對(duì)象的反向映射鏈表所消耗的時(shí)間也會(huì)少很多。所以在一定程度上減少了空間資源和時(shí)間資源的消耗。

基于對(duì)象的反向映射的實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)page結(jié)構(gòu)中與基于對(duì)象的反向映射相關(guān)的關(guān)鍵字段:_mapcount和mapping。

struct page{

atomic_t_mapcount;

union{

……

struct{

……

struct address_space*mapping;

};

……

};

字段_mapcount表明共享該物理頁(yè)面的頁(yè)表項(xiàng)的數(shù)目。該計(jì)數(shù)器可用于快速檢查該頁(yè)面除所有者之外有多少個(gè)使用者在使用，初始值是 －1，每增加一個(gè)使用者，該計(jì)數(shù)器加1。字段mapping用于區(qū)分匿名頁(yè)面和基于文件映射的頁(yè)面，如果該字段的最低位被置位了，那么該字段包含的是指向 anon_vma用于匿名頁(yè)面結(jié)構(gòu)的指針;否則，該字段包含指向 address_space結(jié)構(gòu)的用于基于文件映射頁(yè)面指針。

2.3 基于對(duì)象的反向映射機(jī)制的優(yōu)勢(shì)

使用基于對(duì)象的反向映射機(jī)制改善了查找映射到指定物理頁(yè)對(duì)應(yīng)的虛擬頁(yè)的內(nèi)存管理的瓶頸，并且可以快速定位引用了某個(gè)物理頁(yè)面的所有頁(yè)表項(xiàng)，這極大地方便了操作系統(tǒng)進(jìn)行頁(yè)面回收。相對(duì)于之前的遍歷方法來(lái)說(shuō)，基于對(duì)象的反向映射機(jī)制在很大程度上減少了操作系統(tǒng)在頁(yè)面回收上所占用的 CPU時(shí)間。相對(duì)于之前的單純的反向映射機(jī)制來(lái)說(shuō)，在一定程度上也解決了要消耗掉一定的內(nèi)存空間的問(wèn)題。

3 結(jié)語(yǔ)

操作系統(tǒng)中的內(nèi)存管理負(fù)責(zé)管理整個(gè)系統(tǒng)的物理地址空間和虛地址空間，進(jìn)行虛實(shí)地址之間的轉(zhuǎn)換以及頁(yè)面的換入換出等操作。它是系統(tǒng)內(nèi)核中最重要的組成部分之一，是整個(gè)系統(tǒng)得以存在和運(yùn)行的基礎(chǔ)。而利用基于對(duì)象的反向映射機(jī)制和頁(yè)面回收算法的結(jié)合，在最少時(shí)間和最少空間消耗的前提下，更有效地進(jìn)行頁(yè)面回收是內(nèi)存管理系統(tǒng)構(gòu)建一個(gè)具有高可靠性、可伸縮性系統(tǒng)的必要前提。

［1］ 趙麗坤.Linux內(nèi)核內(nèi)存管理機(jī)制和改進(jìn)［J］.電腦知識(shí)與技術(shù)，2009(10):112-115.

［2］ 文東戈，王 旭.Linux操作系統(tǒng)原理實(shí)驗(yàn)教學(xué)平臺(tái)的設(shè)計(jì)與應(yīng)用［J］.實(shí)驗(yàn)室研究與探索，2008(5):68-70.

［3］ 王東濱.面向網(wǎng)絡(luò)數(shù)據(jù)實(shí)時(shí)檢測(cè)的多線程內(nèi)存管理技術(shù)［J］.高技術(shù)通訊，2008(12):213-215.

［4］ 韓耀堂.C#編程中的內(nèi)存管理不該忽略的問(wèn)題［J］.計(jì)算機(jī)光盤(pán)軟件與應(yīng)用，2011(13):73-76.

［5］ 左利云.基于內(nèi)存管理的多重查詢調(diào)度算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010(7):121-125.

［6］ 敖青云.存儲(chǔ)技術(shù)原理分析［M］.北京:電子工業(yè)出版社.2011:103-189.

［7］ 莫爾勒著，郭旭譯.深入Linux內(nèi)核架構(gòu)［M］.北京:人民郵電出版社.2010:135-246.

［8］ 雷銘哲Linux線程機(jī)制研究.火力與指揮控制［J］.2010(2):112-118.

［9］ 梁 琛.Linux內(nèi)核鏈表及其在虛擬文件系統(tǒng)中的應(yīng)用［J］.西安郵電學(xué)院學(xué)報(bào).2011(2):29-33.

［10］ 劉賓禮，孫俊忠，周智勇，等.鏈表淺析［J］.電腦學(xué)習(xí)，2010(1):141-142.

［11］ ［美］博韋，西斯特著陳莉君譯.深入理解Linux內(nèi)核［M］.北京:中國(guó)電力出版社，2008:178-283.

［12］ 胡章平.虛擬存儲(chǔ)管理中缺頁(yè)中斷次數(shù)的計(jì)算方法［J］.電腦知識(shí)與技術(shù).2009(2):272-274.

［13］ 李亞瓊.一種面向虛擬化云計(jì)算平臺(tái)的內(nèi)存優(yōu)化技術(shù)［J］.計(jì)算機(jī)學(xué)報(bào)，2011(4):684-690.

［14］ 陳志文，李 亮.基于Linux的安全存儲(chǔ)系統(tǒng)設(shè)計(jì)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009(15):91-93.

［15］ 張玉潔.文件系統(tǒng)安全存儲(chǔ)算法研究與系統(tǒng)設(shè)計(jì)［J］.華北科技學(xué)院學(xué)報(bào)，2011，30(2):66-69.

［16］ 鄭 巍，許 鴻.開(kāi)源軟件Linux內(nèi)核的進(jìn)化分析［J］.華南理工大學(xué)學(xué)報(bào)，2007，35(9):74-77.