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

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

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

如何進行頁面回收

哪些頁面可以被回收

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

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

●用戶地址空間中用于文件內存映射的頁面

●匿名頁面：進程用戶模式下的堆?；蛘呤鞘褂?mmap 匿名映射的內存區(qū)

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

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

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

進行頁面回收的時機

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

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

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

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

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

表 1. 字段含義

#p#

頁面回收算法

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

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

LRU 鏈表

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

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

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：管理內存區(qū)域中處于活躍狀態(tài)的頁面。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

LRU 緩存

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

LRU 緩存用到了 pagevec 結構，如下所示 :

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

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

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

下圖概括總結了上文介紹的如何在兩個鏈表之間移動頁面，以及 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)進行頁面回收需要考慮的方面很多，下圖列出了 Linux 操作系統(tǒng)進行頁面回收的關鍵代碼流程圖，該圖給出了實現(xiàn)頁面回收的關鍵代碼函數(shù)名，并說明它們之間是如何彼此鏈接的。

圖 2. 頁面回收關鍵代碼流程圖

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

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

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

函數(shù) shrink_zone()

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

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

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

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

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

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

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

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

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

函數(shù) shrink_slab()

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

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

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

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

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

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

反向映射(reverse mapping)

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

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

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

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

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

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

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

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

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

數(shù)據結構

page 結構中與基于對象的反向映射相關的關鍵字段有兩個：_mapcount 和 mapping。

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

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

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

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

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

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

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

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

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

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;
};

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

圖 5. vm_set.list 和 vm_set.head

通過結構 vm_area_struct 中的 vm_mm 字段可以找到對應的 mm_struct 結構，在該結構中找到頁全局目錄，從而定位所有相關的頁表項。#p#

使用反向映射

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

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

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

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

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

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

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

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

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

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

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

總結

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

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

【編輯推薦】

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