請求調(diào)頁機制，只要用戶態(tài)進程繼續(xù)執(zhí)行，他們就能獲得頁框，然而，請求調(diào)頁沒有辦法強制進程釋放不再使用的頁框。因此，遲早所有空閑內(nèi)存將被分配給進程和高速緩存，Linux內(nèi)核的頁面回收算法（PFRA）采取從用戶進程和內(nèi)核高速緩存“竊取”頁框的辦法不從伙伴系統(tǒng)的空閑塊列表。

實際上，在用完所有空閑內(nèi)存之前，就必須執(zhí)行頁框回收算法。否則，內(nèi)核很可能陷入一種內(nèi)存請求的僵局中，并導致系統(tǒng)崩潰。也就是說，要釋放一個頁框，內(nèi)核就必須把頁框的數(shù)據(jù)寫入磁盤；但是，為了完成這一操作，內(nèi)核卻要請求另一個頁框（例如，為I/O數(shù)據(jù)傳送分配緩沖區(qū)首部）。因為不存在空閑頁框，因此，不可能釋放頁框。

頁框算法的目標之一就是保存最少的空閑頁框并使內(nèi)核可以安全地從“內(nèi)存緊缺”的情形中恢復過來。

選擇目標頁

PFRA的目標就是獲得頁框并使之空閑。PFRA按照頁框所含內(nèi)容，以不同的方式處理頁框。我們將他們區(qū)分成：不可回收頁、可交換頁、可同步頁和可丟棄頁：

進行頁面回收的時機

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

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

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

睡眠回收，在進入suspend-to-disk狀態(tài)時，內(nèi)核必須釋放內(nèi)存。

?

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

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

字段含義

PFRA設計

設計總則

首先釋放“無害”頁，即必須線回收沒有被任何進程使用的磁盤與內(nèi)存高速緩存中的頁；

將用戶態(tài)進程和所有頁定為可回首頁，F(xiàn)PRA必須能夠竊得人任何用戶態(tài)進程頁，包括匿名頁。這樣，睡眠較長時間的進程將逐漸失去所有頁；

同時取消引用一個共享頁的所有頁表項的映射，就可以回收該共享頁；

只回收“未用”頁，使用LRU算法。Linux使用每個頁表項中的訪問標志位，在頁被訪問時，該標志位由銀獎自動置位；而且，頁年齡由頁描述符在鏈表（兩個不同的鏈表之一）中的位置來表示。

因此，頁框回收算法是集中啟發(fā)式方法的混合：

謹慎選擇檢查高速緩存的順序；

基于頁年齡的變化排序；

區(qū)別對待不同狀態(tài)的頁；

反向映射

PFRA的目標之一是能釋放共享頁框。為達到這個目地。Linux內(nèi)核能夠快速定為指向同一頁框的所有頁表項。這個過程就叫做反向映射。Linux 操作系統(tǒng)為物理頁面建立一個鏈表，用于指向引用了該物理頁面的所有頁表項。

基本思想如下圖：

?
?

Linux采用“面向?qū)ο蟮姆聪蛴成洹奔夹g。實際上，對任何可回收的用戶態(tài)頁，內(nèi)核保留系統(tǒng)中該頁所在所有現(xiàn)行區(qū)（“對象”）的反向鏈接，每個線性區(qū)描述符（ vm_area_struct 結構）存放一個指針指向一個內(nèi)存描述符（ mm_struct 結構），而該內(nèi)存描述符又包含一個指針指向一個頁全局目錄（PGD）。因此，這些反向鏈接使得PFRA能夠檢索引用某頁的所有頁表項。因為線性區(qū)描述符比頁描述符少，所以更新共享頁的反向鏈接就比較省時間。下面是具體的實現(xiàn)：

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

數(shù)據(jù)結構

首先，PFRA必須要確定待回收頁是共享的還是非共享的，以及是映射頁或是匿名頁。為做到這一點，內(nèi)核要查看頁描述符的兩個字段：_mapcount和mapping。_mapcount字段存放引用頁框的頁表項數(shù)目，確定其是否共享；mapping字段用于確定頁是映射的或是匿名的：為空表示該頁屬于交換高速緩存；非空，且最低位是1，表示該頁為匿名頁，同時mapping字段中存放的是指向anon_vma描述符的指針；如果mapping字段非空，且最低位是0，表示該頁為映射頁；同時mapping字段指向?qū)募?a target="_blank">address_space對象。

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

Linux的address_space對象在RAMA中是對其的，所以其起始地址是4的倍數(shù)。因此其mapping字段的最低位可以用作一個標志位來表示該字段的指針是指向address_space對象還是anon_vma描述符。PageAnon檢查mapping最低位。

/*檢查頁是否為匿名頁，低位為1時為匿名頁*/  
static inline int PageAnon(struct page *page)  
{  
    return ((unsigned long)page->mapping & PAGE_MAPPING_ANON) != 0;  
}  

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

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

匿名頁的面向?qū)ο蠓聪蛴成淙缦聢D：

?
?

可以通過頁面的mapping找到anon_vma然后找到映射該頁面的所有線性區(qū)域（vm_area_struct結構）。

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

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

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

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

vm_set.list 和 vm_set.head

?

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

反向映射實現(xiàn)

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

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

?

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

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

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

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

代碼如下，對關鍵部分做了注釋：

static int try_to_unmap_anon(struct page *page, enum ttu_flags flags)  
{  
    struct anon_vma *anon_vma;  
    struct vm_area_struct *vma;  
    unsigned int mlocked = 0;  
    int ret = SWAP_AGAIN;  
    int unlock = TTU_ACTION(flags) == TTU_MUNLOCK;  
  
    if (MLOCK_PAGES && unlikely(unlock))  
        ret = SWAP_SUCCESS; /* default for try_to_munlock() */  
    /*如果該頁面為匿名映射，返回該頁面對應的匿名結構*/  
    anon_vma = page_lock_anon_vma(page);  
    if (!anon_vma)  
        return ret;  
    /*這里可以看出，vma的anon_vma_node字段鏈接到 
    anon_vma的head字段*/  
    /*掃描線性區(qū)描述符的anon_vma鏈表*/  
    list_for_each_entry(vma, &anon_vma->head, anon_vma_node) {  
        if (MLOCK_PAGES && unlikely(unlock)) {  
            if (!((vma->vm_flags & VM_LOCKED) &&  
                  page_mapped_in_vma(page, vma)))  
                continue;  /* must visit all unlocked vmas */  
            ret = SWAP_MLOCK;  /* saw at least one mlocked vma */  
        } else {  
            /*對anon_vma鏈表中的每一個vma線性區(qū)描述符 
            調(diào)用該函數(shù)*/  
            ret = try_to_unmap_one(page, vma, flags);  
            if (ret == SWAP_FAIL || !page_mapped(page))  
                break;  
        }  
        if (ret == SWAP_MLOCK) {  
            mlocked = try_to_mlock_page(page, vma);  
            if (mlocked)  
                break;  /* stop if actually mlocked page */  
        }  
    }  
  
    page_unlock_anon_vma(anon_vma);  
  
    if (mlocked)  
        ret = SWAP_MLOCK;   /* actually mlocked the page */  
    else if (ret == SWAP_MLOCK)  
        ret = SWAP_AGAIN;   /* saw VM_LOCKED vma */  
  
    return ret;  
｝  
/* 
 * Subfunctions of try_to_unmap: try_to_unmap_one called 
 * repeatedly from either try_to_unmap_anon or try_to_unmap_file. 
 */  
 /** 
    *page是一個指向目標頁描述符的指針； 
    *vma是指向線性區(qū)描述符的指針 
    */  
static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma,  
                enum ttu_flags flags)  
{  
    struct mm_struct *mm = vma->vm_mm;  
    unsigned long address;  
    pte_t *pte;  
    pte_t pteval;  
    spinlock_t *ptl;  
    int ret = SWAP_AGAIN;  
    /*計算出待回收頁的線性地址*/  
    address = vma_address(page, vma);  
    if (address == -EFAULT)  
        goto out;  
    /*獲取線性地址對應的頁表項地址*/  
    pte = page_check_address(page, mm, address, &ptl, 0);  
    if (!pte)  
        goto out;  
  
    /* 
     * If the page is mlock()d, we cannot swap it out. 
     * If it's recently referenced (perhaps page_referenced 
     * skipped over this mm) then we should reactivate it. 
     */  
     /*下面為判斷是否可以被回收*/  
    if (!(flags & TTU_IGNORE_MLOCK)) {  
        if (vma->vm_flags & VM_LOCKED) {  
            ret = SWAP_MLOCK;  
            goto out_unmap;  
        }  
    }  
    if (!(flags & TTU_IGNORE_ACCESS)) {  
        if (ptep_clear_flush_young_notify(vma, address, pte)) {  
            ret = SWAP_FAIL;  
            goto out_unmap;  
        }  
    }  
  
    /* Nuke the page table entry. */  
    flush_cache_page(vma, address, page_to_pfn(page));  
    /*更新頁表項并沖刷相應的TLB*/  
    pteval = ptep_clear_flush_notify(vma, address, pte);  
  
    /* Move the dirty bit to the physical page now the pte is gone. */  
    if (pte_dirty(pteval))/*如果是臟頁面，置位PG_dirty*/  
        set_page_dirty(page);  
  
    /* Update high watermark before we lower rss */  
    /*更新mm的hiwater_rss*/  
    update_hiwater_rss(mm);  
  
    if (PageHWPoison(page) && !(flags & TTU_IGNORE_HWPOISON)) {  
        if (PageAnon(page))  
            dec_mm_counter(mm, anon_rss);  
        else  
            dec_mm_counter(mm, file_rss);  
        set_pte_at(mm, address, pte,  
                swp_entry_to_pte(make_hwpoison_entry(page)));  
    } else if (PageAnon(page)) {/*如果是匿名頁*/  
        swp_entry_t entry = { .val = page_private(page) };  
  
        if (PageSwapCache(page)) {  
            /* 
             * Store the swap location in the pte. 
             * See handle_pte_fault() ... 
             */  
             /*保存換出位置*/  
            swap_duplicate(entry);  
            if (list_empty(&mm->mmlist)) {  
                spin_lock(&mmlist_lock);  
                if (list_empty(&mm->mmlist))  
                    /*添加到init_mm的相應鏈表，從這里可以 
                    看出mm->mmlist為交換用的鏈表*/  
                    list_add(&mm->mmlist, &init_mm.mmlist);  
                spin_unlock(&mmlist_lock);  
            }  
            dec_mm_counter(mm, anon_rss);  
        } else if (PAGE_MIGRATION) {  
            /* 
             * Store the pfn of the page in a special migration 
             * pte. do_swap_page() will wait until the migration 
             * pte is removed and then restart fault handling. 
             */  
            BUG_ON(TTU_ACTION(flags) != TTU_MIGRATION);  
            entry = make_migration_entry(page, pte_write(pteval));  
        }  
        set_pte_at(mm, address, pte, swp_entry_to_pte(entry));  
        BUG_ON(pte_file(*pte));  
    } else if (PAGE_MIGRATION && (TTU_ACTION(flags) == TTU_MIGRATION)) {  
        /* Establish migration entry for a file page */  
        swp_entry_t entry;  
        entry = make_migration_entry(page, pte_write(pteval));  
        set_pte_at(mm, address, pte, swp_entry_to_pte(entry));  
    } else  
        dec_mm_counter(mm, file_rss);  
  
    /*斷開頁表項和物理頁面的關系*/  
    page_remove_rmap(page);  
    /*釋放所分配的緩存*/  
    page_cache_release(page);  
  
out_unmap:  
    pte_unmap_unlock(pte, ptl);  
out:  
    return ret;  
}  

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

PFRA具體實現(xiàn)

LRU 鏈表

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

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

inactive_list：管理內(nèi)存區(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)不清除該標志位，那么即使之后很長一段時間內(nèi)該頁面都沒有或很少被訪問過，該頁面也還是處于活躍狀態(tài)。為了能夠有效清除該標志位，需要有定時器的支持以便于在超時時間之后該標志位可以自動被清除。然而，很多 Linux 支持的體系結構并不能提供這樣的硬件支持，所以 Linux 中使用兩個標志符來判斷頁面的活躍程度。

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

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

當頁面被訪問時，檢查該頁的 PG_referenced 位，若未被置位，則置位之；若發(fā)現(xiàn)該頁的 PG_referenced 已經(jīng)被置位了，則意味著該頁經(jīng)常被訪問，這時，若該頁在 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()：當一個頁面被訪問時，則調(diào)用該函數(shù)相應地修改 PG_active 和 PG_referenced。

page_referenced()：當操作系統(tǒng)進行頁面回收時，每掃描到一個頁面，就會調(diào)用該函數(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 緩存之后，新頁不會被馬上添加到相應的鏈表上去，而是先被放到一個緩沖區(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 滿了（已經(jīng)裝了 14 個頁面的描述符指針），pagevec 結構中的所有頁面才會被一次性地移動到相應的鏈表上去。

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

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

?

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

PFRA具體實現(xiàn)

PFRA必須處理多種屬于用戶態(tài)進程、磁盤高速緩存和內(nèi)存高速緩存的頁，而且必須遵照幾條試探法準則。PFRA的大部分函數(shù)如下：

?

如上圖在分配VFS緩沖區(qū)或緩沖區(qū)首部時，內(nèi)核調(diào)用free_more_memory();而當從伙伴系統(tǒng)分配一個或多個頁框時，調(diào)用try_to_free_pages()。

頁面回收關鍵代碼流程圖

?

?

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

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

對于定期頁面檢查并進行回收的入口函數(shù) balance_pgdat() 來說，它主要調(diào)用的函數(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)了對一個內(nèi)存區(qū)域的頁面進行回收的功能，該函數(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ù)目。概括來說，對于可進行回收的頁面，該函數(shù)主要做了這樣幾件事情，其代碼流程圖如下所示：

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

?

?

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

如果該頁面已經(jīng)被映射到一個或者多個進程的頁表項中，那么必須找到所有引用該頁面的進程，并更新頁表中與這些進程相關的所有頁表項。在這里，Linux 2.6 操作系統(tǒng)會利用反向映射機制去檢查哪些頁表項引用了該頁面，關于反向映射的內(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ù)的磁盤緩存進行處理。

從實現(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ù)據(jù)的緩存。

具體的源代碼實現(xiàn)細節(jié)有時間再做分析。后面將談論交換。

　　審核編輯：湯梓紅