操作系統(tǒng)管理內(nèi)存中的物理頁面，同時也擔(dān)任著內(nèi)存分配的職責(zé)。應(yīng)用程序可以通過內(nèi)存分配函數(shù)向操作系統(tǒng)申請物理頁面;在使用完這些物理頁面之后，應(yīng)用程序可以通過相應(yīng)的內(nèi)存釋放函數(shù)釋放這些物理頁面。但是，對于內(nèi)存中的某些物理頁面來說，頁面的使用者并不會主動釋放它們，如果這些物理頁面一直被占用而得不到釋放，那么無論計算機上可用的物理內(nèi)存有多少，物理內(nèi)存遲早都有被用完的時候。所以，對于無法被主動釋放的物理頁面來說，操作系統(tǒng)就需要提供相應(yīng)的功能去釋放它們，Linux 中提供頁面回收算法這樣一種機制進(jìn)行頁面回收。

一般來說，用于頁緩存的物理頁面無法被頁面的使用者主動釋放，因為它們不知道這些頁面何時應(yīng)該被釋放。Linux 中頁緩存存在的最大好處就是可以讓程序從緩存中快速獲取數(shù)據(jù)，從而提升系統(tǒng)的性能。在系統(tǒng)負(fù)載不重的情況下，Linux 操作系統(tǒng)會分配較多的物理頁面用于頁緩存，從而提高程序的運行效率;但是在系統(tǒng)負(fù)載較重的情況下，Linux 操作系統(tǒng)就可能會適當(dāng)回收用于緩存的頁面，并減少用于緩存的頁面的分配，從而滿足系統(tǒng)中優(yōu)先級更高的內(nèi)存分配請求。對于用戶進(jìn)程來說，Linux 操作系統(tǒng)可以在它需要的時候為它分配物理內(nèi)存，但是當(dāng)用戶進(jìn)程不再需要這些物理頁面的時候，如果用戶進(jìn)程不主動釋放占用的頁面，Linux 操作系統(tǒng)也不會強制用戶進(jìn)程去釋放這些物理頁面?；谏鲜鲞@些情況，當(dāng)內(nèi)存中可用的物理頁面越來越少，并最終導(dǎo)致內(nèi)存的使用捉襟見肘的時候，為了保證系統(tǒng)的順利運行，Linux 操作系統(tǒng)就會根據(jù)一定的算法去回收那些長期被占用并且沒有得到有效使用的物理頁面。

由操作系統(tǒng)內(nèi)核本身使用的物理頁面不在 Linux 操作系統(tǒng)進(jìn)行頁面回收的考慮范圍之內(nèi)，這是因為與用戶進(jìn)程相比，內(nèi)核不需要占用非常多的內(nèi)存，回收內(nèi)核占用的物理頁面會顯著增加內(nèi)核代碼的復(fù)雜性，潛在收益非常低。

如何進(jìn)行頁面回收

哪些頁面可以被回收

內(nèi)存中并非所有物理頁面都是可以進(jìn)行回收的，總的來說，以下這些種物理頁面可以被 Linux 操作系統(tǒng)回收：

●文件讀寫操作過程中用于緩沖數(shù)據(jù)的頁面

●用戶地址空間中用于文件內(nèi)存映射的頁面

●匿名頁面：進(jìn)程用戶模式下的堆棧或者是使用 mmap 匿名映射的內(nèi)存區(qū)

●特殊的用于 slab 分配器的緩存，比如用于緩存文件目錄結(jié)構(gòu) dentry 的 cache，以及用于緩存索引節(jié)點 inode 的 cache

在頁面被操作系統(tǒng)回收之前，所有與之關(guān)聯(lián)的進(jìn)程頁表項必須要斷開與該頁面之間的映射關(guān)系。對于匿名頁面來說，在頁面被回收之前，匿名頁面中的內(nèi)容首先需要先被交換到交換區(qū)中去;如果要回收的頁面是“臟”頁面，那么該頁面在被回收之前需要先將頁面中的數(shù)據(jù)寫回。

除此之外，其他的頁面要么不可以被回收，要么根本不必進(jìn)行回收。比如，內(nèi)核占用的頁面不會被回收;映射到內(nèi)核空間中的頁面也不會被回收;內(nèi)核在執(zhí)行的過程中動態(tài)生成的頁面需要永駐內(nèi)存;被鎖住的頁面不能被回收;而沒有被占用的物理頁面則根本不需要被回收。

進(jìn)行頁面回收的時機

Linux 操作系統(tǒng)使用如下這兩種機制檢查系統(tǒng)內(nèi)存的使用情況，從而確定可用的內(nèi)存是否太少從而需要進(jìn)行頁面回收。

○周期性的檢查：這是由后臺運行的守護(hù)進(jìn)程 kswapd 完成的。該進(jìn)程定期檢查當(dāng)前系統(tǒng)的內(nèi)存使用情況，當(dāng)發(fā)現(xiàn)系統(tǒng)內(nèi)空閑的物理頁面數(shù)目少于特定的閾值時，該進(jìn)程就會發(fā)起頁面回收的操作。

○“內(nèi)存嚴(yán)重不足”事件的觸發(fā)：在某些情況下，比如，操作系統(tǒng)忽然需要通過伙伴系統(tǒng)為用戶進(jìn)程分配一大塊內(nèi)存，或者需要創(chuàng)建一個很大的緩沖區(qū)，而當(dāng)時系統(tǒng)中的內(nèi)存沒有辦法提供足夠多的物理內(nèi)存以滿足這種內(nèi)存請求，這時候，操作系統(tǒng)就必須盡快進(jìn)行頁面回收操作，以便釋放出一些內(nèi)存空間從而滿足上述的內(nèi)存請求。這種頁面回收方式也被稱作“直接頁面回收”。

如果操作系統(tǒng)在進(jìn)行了內(nèi)存回收操作之后仍然無法回收到足夠多的頁面以滿足上述內(nèi)存要求，那么操作系統(tǒng)只有最后一個選擇，那就是使用 OOM( out of memory )killer，它從系統(tǒng)中挑選一個最合適的進(jìn)程殺死它，并釋放該進(jìn)程所占用的所有頁面。

上面介紹的內(nèi)存回收機制主要依賴于三個字段：pages_min，pages_low 以及 pages_high。每個內(nèi)存區(qū)域( zone )都在其區(qū)域描述符中定義了這樣三個字段，這三個字段的具體含義如下表 1 所示。

表 1. 字段含義

#p#

頁面回收算法

Linux 中的頁面回收是基于 LRU(least recently used，即最近最少使用 ) 算法的。LRU 算法基于這樣一個事實，過去一段時間內(nèi)頻繁使用的頁面，在不久的將來很可能會被再次訪問到。反過來說，已經(jīng)很久沒有訪問過的頁面在未來較短的時間內(nèi)也不會被頻繁訪問到。因此，在物理內(nèi)存不夠用的情況下，這樣的頁面成為被換出的最佳候選者。

LRU 算法的基本原理很簡單，為每個物理頁面綁定一個計數(shù)器，用以標(biāo)識該頁面的訪問頻度。操作系統(tǒng)內(nèi)核進(jìn)行頁面回收的時候就可以根據(jù)頁面的計數(shù)器的值來確定要回收哪些頁面。然而，在硬件上提供這種支持的體系結(jié)構(gòu)很少，Linux 操作系統(tǒng)沒有辦法依靠這樣一種頁計數(shù)器去跟蹤每個頁面的訪問情況，所以，Linux 在頁表項中增加了一個 Accessed 位，當(dāng)頁面被訪問到的時候，該位就會被硬件自動置位。該位被置位表示該頁面還很年輕，不能被換出去。此后，在系統(tǒng)的運行過程中，該頁面的年齡會被操作系統(tǒng)更改。在 Linux 中，相關(guān)的操作主要是基于兩個 LRU 鏈表以及兩個標(biāo)識頁面狀態(tài)的標(biāo)志符，下文會逐一介紹這些相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以及 Linux 如何使用這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行頁面回收。

LRU 鏈表

在 Linux 中，操作系統(tǒng)對 LRU 的實現(xiàn)主要是基于一對雙向鏈表：active 鏈表和 inactive 鏈表，這兩個鏈表是 Linux 操作系統(tǒng)進(jìn)行頁面回收所依賴的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，每個內(nèi)存區(qū)域都存在一對這樣的鏈表。顧名思義，那些經(jīng)常被訪問的處于活躍狀態(tài)的頁面會被放在 active 鏈表上，而那些雖然可能關(guān)聯(lián)到一個或者多個進(jìn)程，但是并不經(jīng)常使用的頁面則會被放到 inactive 鏈表上。頁面會在這兩個雙向鏈表中移動，操作系統(tǒng)會根據(jù)頁面的活躍程度來判斷應(yīng)該把頁面放到哪個鏈表上。頁面可能會從 active 鏈表上被轉(zhuǎn)移到 inactive 鏈表上，也可能從 inactive 鏈表上被轉(zhuǎn)移到 active 鏈表上，但是，這種轉(zhuǎn)移并不是每次頁面訪問都會發(fā)生，頁面的這種轉(zhuǎn)移發(fā)生的間隔有可能比較長。那些最近最少使用的頁面會被逐個放到 inactive 鏈表的尾部。進(jìn)行頁面回收的時候，Linux 操作系統(tǒng)會從 inactive 鏈表的尾部開始進(jìn)行回收。

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

struct zone {
……
spinlock_t lru_lock;
struct list_head active_list;
struct list_head inactive_list;
unsigned long nr_active;
unsigned long nr_inactive;
……
}

各字段含義如下所示：

lru_lock：active_list 和 inactive_list 使用的自旋鎖。

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

inactive_list：管理內(nèi)存區(qū)域中處于不活躍狀態(tài)的頁面。

nr_active：active_list 鏈表上的頁面數(shù)目。

nr_inactive：inactive_list 鏈表上的頁面數(shù)目。

如何在兩個 LRU 鏈表之間移動頁面

Linux 引入了兩個頁面標(biāo)志符 PG_active 和 PG_referenced 用于標(biāo)識頁面的活躍程度，從而決定如何在兩個鏈表之間移動頁面。PG_active 用于表示頁面當(dāng)前是否是活躍的，如果該位被置位，則表示該頁面是活躍的。PG_referenced 用于表示頁面最近是否被訪問過，每次頁面被訪問，該位都會被置位。Linux 必須同時使用這兩個標(biāo)志符來判斷頁面的活躍程度，假如只是用一個標(biāo)志符，在頁面被訪問時，置位該標(biāo)志符，之后該頁面一直處于活躍狀態(tài)，如果操作系統(tǒng)不清除該標(biāo)志位，那么即使之后很長一段時間內(nèi)該頁面都沒有或很少被訪問過，該頁面也還是處于活躍狀態(tài)。為了能夠有效清除該標(biāo)志位，需要有定時器的支持以便于在超時時間之后該標(biāo)志位可以自動被清除。然而，很多 Linux 支持的體系結(jié)構(gòu)并不能提供這樣的硬件支持，所以 Linux 中使用兩個標(biāo)志符來判斷頁面的活躍程度。

Linux 2.6 中這兩個標(biāo)志符密切合作，其核心思想如下所示：

●如果頁面被認(rèn)為是活躍的，則將該頁的 PG_active 置位;否則，不置位。

●當(dāng)頁面被訪問時，檢查該頁的 PG_referenced 位，若未被置位，則置位之;若發(fā)現(xiàn)該頁的 PG_referenced 已經(jīng)被置位了，則意味著該頁經(jīng)常被訪問，這時，若該頁在 inactive 鏈表上，則置位其 PG_active 位，將其移動到 active 鏈表上去，并清除其 PG_referenced 位的設(shè)置;如果頁面的 PG_referenced 位被置位了一段時間后，該頁面沒有被再次訪問，那么 Linux 操作系統(tǒng)會清除該頁面的 PG_referenced 位，因為這意味著這個頁面最近這段時間都沒有被訪問。

●PG_referenced 位同樣也可以用于頁面從 active 鏈表移動到 inactive 鏈表。對于某個在 active 鏈表上的頁面來說，其 PG_active 位被置位，如果 PG_referenced 位未被置位，給定一段時間之后，該頁面如果還是沒有被訪問，那么該頁面會被清除其 PG_active 位，挪到 inactive 鏈表上去。

Linux 中實現(xiàn)在 LRU 鏈表之間移動頁面的關(guān)鍵函數(shù)如下所示(本文涉及的源代碼均是基于 Linux 2.6.18.1 版本的)：

●mark_page_accessed()：當(dāng)一個頁面被訪問時，則調(diào)用該函數(shù)相應(yīng)地修改 PG_active 和 PG_referenced。

●page_referenced()：當(dāng)操作系統(tǒng)進(jìn)行頁面回收時，每掃描到一個頁面，就會調(diào)用該函數(shù)設(shè)置頁面的 PG_referenced 位。如果一個頁面的 PG_referenced 位被置位，但是在一定時間內(nèi)該頁面沒有被再次訪問，那么該頁面的 PG_referenced 位會被清除。

●activate_page()：該函數(shù)將頁面放到 active 鏈表上去。

●shrink_active_list()：該函數(shù)將頁面移動到 inactive 鏈表上去。

LRU 緩存

前邊提到，頁面根據(jù)其活躍程度會在 active 鏈表和 inactive 鏈表之間來回移動，如果要將某個頁面插入到這兩個鏈表中去，必須要通過自旋鎖以保證對鏈表的并發(fā)訪問操作不會出錯。為了降低鎖的競爭，Linux 提供了一種特殊的緩存：LRU 緩存，用以批量地向 LRU 鏈表中快速地添加頁面。有了 LRU 緩存之后，新頁不會被馬上添加到相應(yīng)的鏈表上去，而是先被放到一個緩沖區(qū)中去，當(dāng)該緩沖區(qū)緩存了足夠多的頁面之后，緩沖區(qū)中的頁面才會被一次性地全部添加到相應(yīng)的 LRU 鏈表中去。Linux 采用這種方法降低了鎖的競爭，極大地提升了系統(tǒng)的性能。

LRU 緩存用到了 pagevec 結(jié)構(gòu)，如下所示 :

struct pagevec {
unsigned long nr;
unsigned long cold;
struct page *pages[PAGEVEC_SIZE];
};

pagevec 這個結(jié)構(gòu)就是用來管理 LRU 緩存中的這些頁面的。該結(jié)構(gòu)定義了一個數(shù)組，這個數(shù)組中的項是指向 page 結(jié)構(gòu)的指針。一個 pagevec 結(jié)構(gòu)最多可以存在 14 個這樣的項(PAGEVEC_SIZE 的默認(rèn)值是 14)。當(dāng)一個 pagevec 的結(jié)構(gòu)滿了，那么該 pagevec 中的所有頁面會一次性地被移動到相應(yīng)的 LRU 鏈表上去。

用來實現(xiàn) LRU 緩存的兩個關(guān)鍵函數(shù)是 lru_cache_add() 和 lru_cache_add_active()。前者用于延遲將頁面添加到 inactive 鏈表上去，后者用于延遲將頁面添加到 active 鏈表上去。這兩個函數(shù)都會將要移動的頁面先放到頁向量 pagevec 中，當(dāng) pagevec 滿了(已經(jīng)裝了 14 個頁面的描述符指針)，pagevec 結(jié)構(gòu)中的所有頁面才會被一次性地移動到相應(yīng)的鏈表上去。

下圖概括總結(jié)了上文介紹的如何在兩個鏈表之間移動頁面，以及 LRU 緩存在其中起到的作用：

 圖 1. 頁面在 LRU 鏈表之間移動示意圖 

其中，1 表示函數(shù) mark_page_accessed()，2 表示函數(shù) page_referenced()，3 表示函數(shù) activate_page()，4 表示函數(shù) shrink_active_list()。#p#

頁面回收的實現(xiàn)

Linux 操作系統(tǒng)進(jìn)行頁面回收需要考慮的方面很多，下圖列出了 Linux 操作系統(tǒng)進(jìn)行頁面回收的關(guān)鍵代碼流程圖，該圖給出了實現(xiàn)頁面回收的關(guān)鍵代碼函數(shù)名，并說明它們之間是如何彼此鏈接的。

圖 2. 頁面回收關(guān)鍵代碼流程圖

上文提到 Linux 中頁面回收主要是通過兩種方式觸發(fā)的，一種是由“內(nèi)存嚴(yán)重不足”事件觸發(fā)的;一種是由后臺進(jìn)程 kswapd 觸發(fā)的，該進(jìn)程周期性地運行，一旦檢測到內(nèi)存不足，就會觸發(fā)頁面回收操作。對于第一種情況，系統(tǒng)會調(diào)用函數(shù) try_to_free_pages() 去檢查當(dāng)前內(nèi)存區(qū)域中的頁面，回收那些最不常用的頁面。對于第二種情況，函數(shù) balance_pgdat() 是入口函數(shù)。

當(dāng) NUMA 上的某個節(jié)點的低內(nèi)存區(qū)域調(diào)用函數(shù) try_to_free_pages() 的時候，該函數(shù)會反復(fù)調(diào)用 shrink_zones() 以及 shrink_slab() 釋放一定數(shù)目的頁面，默認(rèn)值是 32 個頁面。如果在特定的循環(huán)次數(shù)內(nèi)沒有能夠成功釋放 32 個頁面，那么頁面回收會調(diào)用 OOM killer 選擇并殺死一個進(jìn)程，然后釋放它占用的所有頁面。函數(shù) shrink_zones() 會對內(nèi)存區(qū)域列表中的所有區(qū)域分別調(diào)用 shrink_zone() 函數(shù)，后者是從內(nèi)存回收最近最少使用頁面的入口函數(shù)。

對于定期頁面檢查并進(jìn)行回收的入口函數(shù) balance_pgdat() 來說，它主要調(diào)用的函數(shù)是 shrink_zone() 和 shrink_slab()。從上圖中我們也可以看出，進(jìn)行頁面回收的兩條代碼路徑最終匯合到函數(shù) shrink_zone() 和函數(shù) shrink_slab() 上。

函數(shù) shrink_zone()

其中，shrink_zone() 函數(shù)是 Linux 操作系統(tǒng)實現(xiàn)頁面回收的最核心的函數(shù)之一，它實現(xiàn)了對一個內(nèi)存區(qū)域的頁面進(jìn)行回收的功能，該函數(shù)主要做了兩件事情：

●將某些頁面從 active 鏈表移到 inactive 鏈表，這是由函數(shù) shrink_active_list() 實現(xiàn)的。

●從 inactive 鏈表中選定一定數(shù)目的頁面，將其放到一個臨時鏈表中，這由函數(shù) shrink_inactive_list() 完成。該函數(shù)最終會調(diào)用 shrink_page_list() 去回收這些頁面。

函數(shù) shrink_page_list() 返回的是回收成功的頁面數(shù)目。概括來說，對于可進(jìn)行回收的頁面，該函數(shù)主要做了這樣幾件事情，其代碼流程圖如下所示：

圖 3. 函數(shù) shrink_page_list() 實現(xiàn)的關(guān)鍵功能

●對于匿名頁面來說，在回收此類頁面時，需要將其數(shù)據(jù)寫入到交換區(qū)。如果尚未為該頁面分配交換區(qū)槽位，則先分配一個槽位，并將該頁面添加到交換緩存。同時，將相關(guān)的 page 實例加入到交換區(qū)，這樣，對該頁面的處理就可以跟其他已經(jīng)建立映射的頁面一樣;

●如果該頁面已經(jīng)被映射到一個或者多個進(jìn)程的頁表項中，那么必須找到所有引用該頁面的進(jìn)程，并更新頁表中與這些進(jìn)程相關(guān)的所有頁表項。在這里，Linux 2.6 操作系統(tǒng)會利用反向映射機制去檢查哪些頁表項引用了該頁面，關(guān)于反向映射的內(nèi)容在后邊會有介紹;

●如果該頁面中的數(shù)據(jù)是臟的，那么數(shù)據(jù)必須要被回寫;

●釋放頁緩存中的干凈頁面。

函數(shù) shrink_slab()

函數(shù) shrink_slab() 是用來回收磁盤緩存所占用的頁面的。Linux 操作系統(tǒng)并不清楚這類頁面是如何使用的，所以如果希望操作系統(tǒng)回收磁盤緩存所占用的頁面，那么必須要向操作系統(tǒng)內(nèi)核注冊 shrinker 函數(shù)，shrinker 函數(shù)會在內(nèi)存較少的時候主動釋放一些該磁盤緩存占用的空間。函數(shù) shrink_slab() 會遍歷 shrinker 鏈表，從而對所有注冊了 shrinker 函數(shù)的磁盤緩存進(jìn)行處理。

從實現(xiàn)上來看，shrinker 函數(shù)和 slab 分配器并沒有固定的聯(lián)系，只是當(dāng)前主要是 slab 緩存使用 shrinker 函數(shù)最多。

注冊 shrinker 是通過函數(shù) set_shrinker() 實現(xiàn)的，解除 shrinker 注冊是通過函數(shù) remove_shrinker() 實現(xiàn)的。當(dāng)前，Linux 操作系統(tǒng)中主要的 shrinker 函數(shù)有如下幾種：

●shrink_dcache_memory()：該 shrinker 函數(shù)負(fù)責(zé) dentry 緩存。

●shrink_icache_memory()：該 shrinker 函數(shù)負(fù)責(zé) inode 緩存。

●mb_cache_shrink_fn()：該 shrinker 函數(shù)負(fù)責(zé)用于文件系統(tǒng)元數(shù)據(jù)的緩存。#p#

反向映射(reverse mapping)

前文介紹過，在回收一個物理頁面之前，需要查找到所有關(guān)聯(lián)了該物理頁面的頁表項，并逐一更新這些頁表項。Linux 2.6 使用了反向映射這種機制用于快速定位那些引用了某個物理頁面的所有頁表項。Linux 操作系統(tǒng)為物理頁面建立一個鏈表，用于指向引用了該物理頁面的所有頁表項。其基本思想如下圖所述：

圖 4. 反向映射的基本思想

反向映射技術(shù)的發(fā)展歷史

在 Linux 2.4 中，為了確定某個要回收的物理頁面都被哪些頁表項引用，必須要遍歷所有進(jìn)程，這是一項非常耗資源和時間的工程。為了更加有效地回收一個共享頁面，Linux 在 2.5 版本的開發(fā)期間引入了反向映射這樣一種機制。這種機制建立了物理頁面和所有映射了該物理頁面的頁表項之間的一種關(guān)聯(lián)，從而讓操作系統(tǒng)可以快速定位引用了該物理頁面的所有頁表項。在 Linux 2.6 版本中，反向映射算法又經(jīng)歷了大量改進(jìn)。

在 Linux 2.5 版本中，反向映射技術(shù)的實現(xiàn)主要是基于頁表項鏈表。操作系統(tǒng)為每一個物理頁面都維護(hù)了一個鏈表，所有與該物理頁面關(guān)聯(lián)的頁表項都會被放到這個鏈表上。這種方法會存在一些問題：

●空間資源的消耗：為每個物理頁面維護(hù)這樣一個鏈表，需要占用大量的內(nèi)存空間。

●時間資源的消耗：回收一個物理頁面的時候，需要先獲取該鏈表上的鎖，然后遍歷相應(yīng)的反向映射鏈表，鏈表上的項越多，需要的時間就越多。

后來，Linux 2.6 引入了基于對象的反向映射機制。這種方法也是為物理頁面設(shè)置一個用于反向映射的鏈表，但是鏈表上的節(jié)點并不是引用了該物理頁面的所有頁表項，而是相應(yīng)的虛擬內(nèi)存區(qū)域( vm_area_struct 結(jié)構(gòu))，虛擬內(nèi)存區(qū)域通過內(nèi)存描述符( mm_struct 結(jié)構(gòu))找到頁全局目錄，從而找到相應(yīng)的頁表項。相對于前一種方法來說，用于表示虛擬內(nèi)存區(qū)域的描述符比用于表示頁面的描述符要少得多，所以遍歷后邊這種反向映射鏈表所消耗的時間也會少很多。

基于對象的反向映射的實現(xiàn)

數(shù)據(jù)結(jié)構(gòu)

page 結(jié)構(gòu)中與基于對象的反向映射相關(guān)的關(guān)鍵字段有兩個：_mapcount 和 mapping。

struct page {
atomic_t _mapcount;
union {
……
struct {
……
struct address_space *mapping;
};
……
};

●字段 _mapcount 表明共享該物理頁面的頁表項的數(shù)目。該計數(shù)器可用于快速檢查該頁面除所有者之外有多少個使用者在使用，初始值是 -1，每增加一個使用者，該計數(shù)器加 1。

●字段 mapping 用于區(qū)分匿名頁面和基于文件映射的頁面，如果該字段的最低位被置位了，那么該字段包含的是指向 anon_vma 結(jié)構(gòu)(用于匿名頁面)的指針;否則，該字段包含指向 address_space 結(jié)構(gòu)的指針(用于基于文件映射的頁面)。

匿名頁面和文件映射頁面分別采用了不同的底層數(shù)據(jù)結(jié)構(gòu)去存放與頁面相關(guān)的虛擬內(nèi)存區(qū)域。對于匿名頁面來說，與該頁面相關(guān)的虛擬內(nèi)存區(qū)域存放在結(jié)構(gòu) anon_vma 中定義的雙向鏈表中。結(jié)構(gòu) anon_vma 定義很簡單，如下所示：

struct anon_vma {
spinlock_t lock;
struct list_head head;
};

而對于基于文件映射的頁面來說，與匿名頁面不同的是，與該頁面相關(guān)的虛擬內(nèi)存區(qū)域的存放是利用了優(yōu)先級搜索樹這種數(shù)據(jù)結(jié)構(gòu)的。這是因為對于匿名頁面來說，頁面雖然可以是共享的，但是一般情況下，共享匿名頁面的使用者的數(shù)目不會很多;而對于基于文件映射的頁面來說，共享頁面的使用者的數(shù)目可能會非常多，使用優(yōu)先級搜索樹這種結(jié)構(gòu)可以更加快速地定位那些引用了該頁面的虛擬內(nèi)存區(qū)域。操作系統(tǒng)會為每一個文件都建立一個優(yōu)先級搜索樹，其根節(jié)點可以通過結(jié)構(gòu) address_space 中的 i_mmap 字段獲取。

struct address_space {
……
struct prio_tree_root i_mmap;
……
}

Linux 2.6 中使用 (radix,size,heap) 來表示優(yōu)先級搜索樹中的節(jié)點。其中，radix 表示內(nèi)存區(qū)域的起始位置，heap 表示內(nèi)存區(qū)域的結(jié)束位置，size 與內(nèi)存區(qū)域的大小成正比。在優(yōu)先級搜索樹中，父節(jié)點的 heap 值一定不會小于子節(jié)點的 heap 值。在樹中進(jìn)行查找時，根據(jù)節(jié)點的 radix 值進(jìn)行。程序可以根據(jù) size 值區(qū)分那些具有相同 radix 值的節(jié)點。

在用于表示虛擬內(nèi)存區(qū)域的結(jié)構(gòu) vm_area_struct 中，與上邊介紹的雙向鏈表和優(yōu)先級搜索樹相關(guān)的字段如下所示：

struct vm_area_struct {
struct mm_struct * vm_mm;
……
union {
struct {
struct list_head list;
void *parent;
struct vm_area_struct *head;
} vm_set;
struct raw_prio_tree_node prio_tree_node;
} shared;
struct list_head anon_vma_node;
struct anon_vma *anon_vma;
};

與匿名頁面的雙向鏈表相關(guān)的字段是 anon_vma_node 和 anon_vma。union shared 則與文件映射頁面使用的優(yōu)先級搜索樹相關(guān)。字段 anon_vma 指向 anon_vma 表;字段 anon_vma_node 將映射該頁面的所有虛擬內(nèi)存區(qū)域鏈接起來;union shared 中的 prio_tree_node 結(jié)構(gòu)用于表示優(yōu)先級搜索樹的一個節(jié)點;在某些情況下，比如不同的進(jìn)程的內(nèi)存區(qū)域可能映射到了同一個文件的相同部分，也就是說這些內(nèi)存區(qū)域具有相同的(radix,size,heap)值，這個時候 Linux 就會在樹上相應(yīng)的節(jié)點(樹上原來那個具有相同 (radix,size,heap) 值的內(nèi)存區(qū)域)上接一個雙向鏈表用來存放這些內(nèi)存區(qū)域，這個鏈表用 vm_set.list 來表示;樹上那個節(jié)點指向的鏈表中的第一個節(jié)點是表頭，用 vm_set.head 表示;vm_set.parent 用于表示是否是樹結(jié)點。下邊給出一個小圖示簡單說明一下 vm_set.list 和 vm_set.head。

圖 5. vm_set.list 和 vm_set.head

通過結(jié)構(gòu) vm_area_struct 中的 vm_mm 字段可以找到對應(yīng)的 mm_struct 結(jié)構(gòu)，在該結(jié)構(gòu)中找到頁全局目錄，從而定位所有相關(guān)的頁表項。#p#

使用反向映射

在進(jìn)行頁面回收的時候，Linux 2.6 在前邊介紹的 shrink_page_list() 函數(shù)中調(diào)用 try_to_unmap() 函數(shù)去更新所有引用了回收頁面的頁表項。其代碼流程如下所示：

圖 6. 實現(xiàn)函數(shù) try_to_unmap() 的關(guān)鍵代碼流程圖 

函數(shù) try_to_unmap() 分別調(diào)用了兩個函數(shù) try_to_unmap_anon() 和 try_to_unmap_file()，其目的都是檢查并確定都有哪些頁表項引用了同一個物理頁面，但是，由于匿名頁面和文件映射頁面分別采用了不同的數(shù)據(jù)結(jié)構(gòu)，所以二者采用了不同的方法。

函數(shù) try_to_unmap_anon() 用于匿名頁面，該函數(shù)掃描相應(yīng)的 anon_vma 表中包含的所有內(nèi)存區(qū)域，并對這些內(nèi)存區(qū)域分別調(diào)用 try_to_unmap_one() 函數(shù)。

函數(shù) try_to_unmap_file() 用于文件映射頁面，該函數(shù)會在優(yōu)先級搜索樹中進(jìn)行搜索，并為每一個搜索到的內(nèi)存區(qū)域調(diào)用 try_to_unmap_one() 函數(shù)。

兩條代碼路徑最終匯合到 try_to_unmap_one() 函數(shù)中，更新引用特定物理頁面的所有頁表項的操作都是在這個函數(shù)中實現(xiàn)的。該函數(shù)實現(xiàn)的關(guān)鍵功能如下圖所示：

圖 7. 函數(shù) try_to_unmap_one() 實現(xiàn)的關(guān)鍵功能

對于給定的物理頁面來說，該函數(shù)會根據(jù)計算出來的線性地址找到對應(yīng)的頁表項地址，并更新頁表項。對于匿名頁面來說，換出的位置必須要被保存下來，以便于該頁面下次被訪問的時候可以被換進(jìn)來。并非所有的頁面都是可以被回收的，比如被 mlock() 函數(shù)設(shè)置過的內(nèi)存頁，或者最近剛被訪問過的頁面，等等，都是不可以被回收的。一旦遇上這樣的頁面，該函數(shù)會直接跳出執(zhí)行并返回錯誤代碼。如果涉及到頁緩存中的數(shù)據(jù)，需要設(shè)置頁緩存中的數(shù)據(jù)無效，必要的時候還要置位頁面標(biāo)識符以進(jìn)行數(shù)據(jù)回寫。該函數(shù)還會更新相應(yīng)的一些頁面使用計數(shù)器，比如前邊提到的 _mapcount 字段，還會相應(yīng)地更新進(jìn)程擁有的物理頁面數(shù)目等。

使用反向映射的優(yōu)缺點

使用反向映射機制所帶來的好處是顯而易見的：可以快速定為引用了某個物理頁面的所有頁表項，這極大地方便了操作系統(tǒng)進(jìn)行頁面回收。相對于之前的遍歷方法來說，反向映射機制在很大程度上減少了操作系統(tǒng)在頁面回收上所占用的 CPU 時間。

但是，使用反向映射所面臨的挑戰(zhàn)也是很明顯的，不管采用上述介紹的哪種方法建立反向映射，都不可避免地要消耗掉一定的內(nèi)存空間，區(qū)別就在于用哪種方法占用的空間會更少，整體性能會更好。

總結(jié)

頁面回收是 Linux 內(nèi)存管理中比較復(fù)雜的一個部分，涉及到的相關(guān)內(nèi)容非常多，本文也不是面面俱到。反向映射是 Linux 2.5 開發(fā)過程中一個比較大的亮點，該技術(shù)在后續(xù) Linux 2.6 版本中又得到了更進(jìn)一步的發(fā)展。本文的目的是想幫助讀者理清 Linux 2.6 中的頁面回收和反向映射機制，本文通過相關(guān)的數(shù)據(jù)結(jié)構(gòu)和關(guān)鍵的代碼流程介紹了 Linux 操作系統(tǒng)如何利用反向映射機制有效地進(jìn)行頁面回收。關(guān)于 Linux 操作系統(tǒng)如何建立反向映射的內(nèi)容，本文沒有做詳盡介紹，感興趣的讀者可以自行參考內(nèi)核源代碼。

原文連接：http://www.ibm.com/developerworks/cn/linux/l-cn-pagerecycle/index.html?ca=drs-

【編輯推薦】

1. 通過dsh批量管理Linux服務(wù)器
2. Linux上XFS文件系統(tǒng)的特性介紹
3. 用C語言實現(xiàn)Linux 下幾個文件操作命令