[[420325]]

本文基于 Linux-2.4.16 內核版本

由于計算機的物理內存是有限的, 而進程對內存的使用是不確定的, 所以物理內存總有用完的可能性. 那么當系統的物理內存不足時, Linux內核使用什么方案來避免申請不到物理內存這個問題呢?

相對于內存來說, 磁盤的容量是非常大的, 所以Linux內核實現了一個叫 內存交換 的功能 -- 把某些進程的一些暫時用不到的內存頁保存到磁盤中, 然后把物理內存頁分配給更緊急的用戶使用, 當進程用到時再從磁盤讀回到內存中即可. 有了 內存交換 功能, 系統可使用的內存就可以遠遠大于物理內存的容量。

LRU算法

內存交換 過程首先是找到一個合適的用戶進程內存管理結構，然后把進程占用的內存頁交換到磁盤中，并斷開虛擬內存與物理內存的映射，最后釋放進程占用的內存頁。由于涉及到IO操作，所以這是一個比較耗時的過程。如果被交換出去的內存頁剛好又被訪問了，這時又需要從磁盤中把內存頁的數據交換到內存中。所以，在這種情況下不單不能解決內存緊缺的問題，而且增加了系統的負荷。

為了解決這個問題，Linux內核使用了一種稱為 LRU (Least Recently Used) 的算法, 下面介紹一下 LRU算法 的大體過程。

LRU 的中文翻譯是 最近最少使用, 顧名思義就是一段時間內沒有被使用, 那么Linux內核怎么知道哪些內存頁面最近沒有被使用呢? 最簡單的方法就是把內存頁放進一個隊列里, 如果內存頁被訪問了, 就把內存頁移動到鏈表的頭部, 這樣沒被訪問的內存頁在一段時間后便會移動到隊列的尾部, 而釋放內存頁時從鏈表的尾部開始. 著名的緩存服務器 memcached 就是使用這種 LRU算法。

Linux內核也使用了類似的算法, 但相對要復雜一些. Linux內核維護著三個隊列: 活躍隊列, 非活躍臟隊列和非活躍干凈隊列. 為什么Linux需要維護三個隊列, 而不是使用一個隊列呢? 這是因為Linux希望內存頁交換過程慢慢進行, Linux內核有個內核線程 kswapd 會定時檢查系統的空閑內存頁是否緊缺, 如果系統的空閑內存頁緊缺時時, 就會選擇一些用戶進程把其占用的內存頁添加到活躍鏈表中并斷開進程與此內存頁的映射關系. 隨著時間的推移, 如果內存頁沒有被訪問, 那么就會被移動到非活躍臟鏈表. 非活躍臟鏈表中的內存頁是需要被交換到磁盤的, 當系統中空閑內存頁緊缺時就會從非活躍臟鏈表的尾部開始把內存頁刷新到磁盤中, 然后移動到非活躍干凈鏈表中, 非活躍干凈鏈表中的內存頁是可以立刻分配給進程使用的. 各個鏈表之間的移動如下圖:

lru links

如果在這個過程中, 內存頁又被訪問了, 那么Linux內核會把內存頁移動到活躍鏈表中, 并且建立內存映射關系, 這樣就不需要從磁盤中讀取內存頁的內容。

注意: 內核只維護著一個活躍鏈表和一個非活躍臟鏈表, 但是非活躍干凈鏈表是每個內存管理區都有一個的。

這是因為分配內存是在內存管理區的基礎上進行的, 所以一個內存頁必須屬于某一個內存管理區。

kswapd內核線程

在Linux系統啟動時會調用 kswapd_init() 函數, 代碼如下:

static int __init kswapd_init(void) 
{ 
    printk("Starting kswapd v1.8\n"); 
    swap_setup(); 
    kernel_thread(kswapd, NULL, CLONE_FS | CLONE_FILES | CLONE_SIGNAL); 
    kernel_thread(kreclaimd, NULL, CLONE_FS | CLONE_FILES | CLONE_SIGNAL); 
    return 0; 
} 

可以看到, kswapd_init() 函數會創建 kswapd 和 kreclaimd 兩個內核線程, 這兩個內核線程負責在系統物理內存緊缺時釋放一些物理內存頁, 從而使系統的可用內存達到一個平衡. 下面我們重點來分析 kswapd 這個內核線程, kswapd() 的源碼如下:

int kswapd(void *unused) 
{ 
    struct task_struct *tsk = current; 
 
    tsk->session = 1; 
    tsk->pgrp = 1; 
    strcpy(tsk->comm, "kswapd"); 
    sigfillset(&tsk->blocked); 
    kswapd_task = tsk; 
 
    tsk->flags |= PF_MEMALLOC; 
 
    for (;;) { 
        static int recalc = 0; 
 
        if (inactive_shortage() || free_shortage()) { 
            int wait = 0; 
            /* Do we need to do some synchronous flushing? */ 
            if (waitqueue_active(&kswapd_done)) 
                wait = 1; 
            do_try_to_free_pages(GFP_KSWAPD, wait); 
        } 
 
        refill_inactive_scan(6, 0); 
 
        if (time_after(jiffies, recalc + HZ)) { 
            recalc = jiffies; 
            recalculate_vm_stats(); 
        } 
 
        wake_up_all(&kswapd_done); 
        run_task_queue(&tq_disk); 
 
        if (!free_shortage() || !inactive_shortage()) { 
            interruptible_sleep_on_timeout(&kswapd_wait, HZ); 
        } else if (out_of_memory()) { 
            oom_kill(); 
        } 
    } 
} 

kswapd 內核線程由一個無限循環組成, 首先通過 inactive_shortage() 和 free_shortage() 函數判斷系統的非活躍頁面和空閑物理內存頁是否短缺, 如果短缺的話, 那么就調用 do_try_to_free_pages() 函數試圖釋放一些物理內存頁. 然后通過調用 refill_inactive_scan() 函數把一些活躍鏈表中的內存頁移動到非活躍臟鏈表中. 最后, 如果空閑物理內存頁或者非活躍內存頁不短缺, 那么就讓 kswapd 內核線程休眠一秒。

接下來我們分析一下 do_try_to_free_pages() 函數做了一些什么工作, 代碼如下:

static int do_try_to_free_pages(unsigned int gfp_mask, int user) 
{ 
    int ret = 0; 
 
    if (free_shortage() || nr_inactive_dirty_pages > nr_free_pages() + nr_inactive_clean_pages()) 
        ret += page_launder(gfp_mask, user); 
 
    if (free_shortage() || inactive_shortage()) { 
        shrink_dcache_memory(6, gfp_mask); 
        shrink_icache_memory(6, gfp_mask); 
        ret += refill_inactive(gfp_mask, user); 
    } else { 
        kmem_cache_reap(gfp_mask); 
        ret = 1; 
    } 
 
    return ret; 
} 

do_try_to_free_pages() 函數第一步先判斷系統中的空閑物理內存頁是否短缺, 或者非活躍臟頁面的數量大于空閑物理內存頁和非活躍干凈頁面的總和, 其中一個條件滿足了, 就調用 page_launder() 函數把非活躍臟鏈表中的頁面刷到磁盤中, 然后移動到非活躍干凈鏈表中. 接下來如果內存還是緊缺的話, 那么就調用 shrink_dcache_memory(), shrink_icache_memory() 和 refill_inactive() 函數繼續釋放內存。

下面我們先來分析一下 page_launder() 這個函數, 由于這個函數很長, 所以我們分段來解釋:

int page_launder(int gfp_mask, int sync) 
{ 
    int launder_loop, maxscan, cleaned_pages, maxlaunder; 
    int can_get_io_locks; 
    struct list_head * page_lru; 
    struct page * page; 
 
    can_get_io_locks = gfp_mask & __GFP_IO; // 是否需要進行寫盤操作 
 
    launder_loop = 0; 
    maxlaunder = 0; 
    cleaned_pages = 0; 
 
dirty_page_rescan: 
    spin_lock(&pagemap_lru_lock); 
    maxscan = nr_inactive_dirty_pages; 
    // 從非活躍臟鏈表的后面開始掃描 
    while ((page_lru = inactive_dirty_list.prev) != &inactive_dirty_list && 
                maxscan-- > 0) { 
        page = list_entry(page_lru, struct page, lru); 
    ... 

上面的代碼首先把 pagemap_lru_lock 上鎖, 然后從尾部開始遍歷非活躍臟鏈表。

// 如果滿足以下的任意一個條件, 都表示內存頁在使用中, 把他移動到活躍鏈表 
if (PageTestandClearReferenced(page) ||             // 如果設置了 PG_referenced 標志 
        page->age > 0 ||                            // 如果age大于0, 表示頁面被訪問過 
        (!page->buffers && page_count(page) > 1) || // 如果頁面被其他進程映射 
        page_ramdisk(page)) {                       // 如果用于內存磁盤的頁面 
    del_page_from_inactive_dirty_list(page); 
    add_page_to_active_list(page); 
    continue; 
} 

上面代碼判斷內存頁是否能需要重新移動到活躍鏈表中, 依據有:

• 內存頁是否設置了 PG_referenced 標志;
• 內存頁的age字段是否大于0 (age字段是內存頁的生命周期);
• 內存頁是否還有映射關系;
• 內存頁是否用于內存磁盤.

如果滿足上面其中一個條件, 都需要重新把內存頁移動到活躍頁面中。

if (PageDirty(page)) { // 如果頁面是臟的, 那么應該把頁面寫到磁盤中 
      int (*writepage)(struct page *) = page->mapping->a_ops->writepage; 
      int result; 
 
      if (!writepage) 
          goto page_active; 
 
      /* First time through? Move it to the back of the list */ 
      if (!launder_loop) { // 第一次只把頁面移動到鏈表的頭部, 這是為了先處理已經干凈的頁面 
          list_del(page_lru); 
          list_add(page_lru, &inactive_dirty_list); 
          UnlockPage(page); 
          continue; 
      } 
 
      /* OK, do a physical asynchronous write to swap.  */ 
      ClearPageDirty(page); 
      page_cache_get(page); 
      spin_unlock(&pagemap_lru_lock); 
 
      result = writepage(page); 
      page_cache_release(page); 
 
      /* And re-start the thing.. */ 
      spin_lock(&pagemap_lru_lock); 
      if (result != 1) 
          continue; 
      /* writepage refused to do anything */ 
      set_page_dirty(page); 
      goto page_active; 
  } 

上面的代碼首先判斷內存頁是否臟的(是否設置了 PG_dirty 標志), 如果是, 那么就需要把內存頁刷新到磁盤中. 這里有個要主要的地方是, 當 launder_loop 變量為0時只是把內存頁移動到非活躍臟鏈表的頭部. 當 launder_loop 變量為1時才會把內存頁刷新到磁盤中. 為什么要這樣做呢? 這是因為Linux內核希望第一次掃描先把非活躍臟鏈表中的干凈內存頁移動到非活躍干凈鏈表中, 第二次掃描才把臟的內存頁刷新到磁盤中. 后面的代碼會對 launder_loop 變量進行修改. 而且我們發現, 把臟頁面刷新到磁盤后, 并沒有立刻把內存頁移動到非活躍干凈鏈表中, 而是簡單的清除了 PG_dirty 標志。

        if (page->buffers) { // 涉及文件系統部分, 先略過 
            ... 
        } else if (page->mapping && !PageDirty(page)) { // 內存頁是干凈的, 移動到非活躍干凈鏈表 
            del_page_from_inactive_dirty_list(page); 
            add_page_to_inactive_clean_list(page); 
            UnlockPage(page); 
            cleaned_pages++; 
        } else { 
page_active: 
            del_page_from_inactive_dirty_list(page); 
            add_page_to_active_list(page); 
            UnlockPage(page); 
        } 

上面的代碼比較簡單, 如果內存頁已經是干凈的, 那么久移動到非活躍干凈鏈表中.

if (can_get_io_locks && !launder_loop && free_shortage()) { 
    launder_loop = 1; 
    /* If we cleaned pages, never do synchronous IO. */ 
    if (cleaned_pages) 
        sync = 0; 
    /* We only do a few "out of order" flushes. */ 
    maxlaunder = MAX_LAUNDER; 
    /* Kflushd takes care of the rest. */ 
    wakeup_bdflush(0); 
    goto dirty_page_rescan; 
} 
 
/* Return the number of pages moved to the inactive_clean list. */ 
return cleaned_pages; 

從上面的代碼可以看到, 當 can_get_io_locks 等于1(gfp_mask 設置了 __GFP_IO 標志), launder_loop 等于0, 并且空閑內存頁還是短缺(free_shortage() 為真)的情況下, 把 launder_loop 變量被設置為1, 并且跳轉到 dirty_page_rescan 處重新掃描, 這是第二次掃描非活躍臟鏈表, 會把臟的內存頁刷新到磁盤中。

接下來我們繼續分析 refill_inactive() 這個函數:

static int refill_inactive(unsigned int gfp_mask, int user) 
{ 
    int priority, count, start_count, made_progress; 
 
    count = inactive_shortage() + free_shortage(); 
    if (user) 
        count = (1 << page_cluster); 
    start_count = count; 
 
    ... 
 
    priority = 6; 
    do { 
        made_progress = 0; 
 
        if (current->need_resched) { 
            __set_current_state(TASK_RUNNING); 
            schedule(); 
        } 
 
        while (refill_inactive_scan(priority, 1)) { // 把活躍頁面鏈表中的頁面移動到非活躍臟頁面鏈表中 
            made_progress = 1; 
            if (--count <= 0) 
                goto done; 
        } 
 
        ... 
 
        while (swap_out(priority, gfp_mask)) { // 把一些用戶進程映射的內存頁放置到活躍頁面鏈表中 
            made_progress = 1; 
            if (--count <= 0) 
                goto done; 
        } 
 
        if (!inactive_shortage() || !free_shortage()) 
            goto done; 
 
        if (!made_progress) 
            priority--; 
    } while (priority >= 0); 
 
    while (refill_inactive_scan(0, 1)) { 
        if (--count <= 0) 
            goto done; 
    } 
 
done: 
    return (count < start_count); 
} 

在這個函數中, 我們主要關注兩個地方:

• 調用 refill_inactive_scan() 函數, refill_inactive_scan() 函數的作用是把活躍鏈表中的內存頁移動到非活躍臟鏈表中。
• 調用 swap_out() 函數, swap_out() 函數的作用是選擇一個用戶進程, 并且把其映射的內存頁添加到活躍鏈表中。

先來看看 refill_inactive_scan() 函數:

int refill_inactive_scan(unsigned int priority, int oneshot) 
{ 
    struct list_head * page_lru; 
    struct page * page; 
    int maxscan, page_active = 0; 
    int ret = 0; 
 
    spin_lock(&pagemap_lru_lock); 
    maxscan = nr_active_pages >> priority; 
    while (maxscan-- > 0 && (page_lru = active_list.prev) != &active_list) { 
        page = list_entry(page_lru, struct page, lru); 
 
        ... 
 
        /* Do aging on the pages. */ 
        if (PageTestandClearReferenced(page)) { 
            age_page_up_nolock(page); 
            page_active = 1; 
        } else { 
            age_page_down_ageonly(page); // page->age = page->age / 2 
 
            if (page->age == 0 && page_count(page) <= (page->buffers ? 2 : 1)) { 
                deactivate_page_nolock(page); // 把頁面放置到非活躍臟頁面鏈表 
                page_active = 0; 
            } else { 
                page_active = 1; 
            } 
        } 
 
        if (page_active || PageActive(page)) { 
            list_del(page_lru); 
            list_add(page_lru, &active_list); 
        } else { 
            ret = 1; 
            if (oneshot) 
                break; 
        } 
    } 
    spin_unlock(&pagemap_lru_lock); 
 
    return ret; 
} 

refill_inactive_scan() 函數比較簡單, 首先從活躍鏈表的尾部開始遍歷, 然后判斷內存頁的生命是否已經用完(age是否等于0), 并且沒有進程與其有映射關系(count是否等于1). 如果是, 那么就調用 deactivate_page_nolock() 函數把內存頁移動到非活躍臟鏈表中。

接著來看看 swap_out() 函數, swap_out() 函數比較復雜, 但最終會調用 try_to_swap_out() 函數, 所以我們只分析 try_to_swap_out() 函數:

static int try_to_swap_out(struct mm_struct * mm, struct vm_area_struct* vma, unsigned long address, pte_t * page_table, int gfp_mask) 
{ 
    ... 
    page = pte_page(pte); 
 
    if (!mm->swap_cnt) 
        return 1; 
 
    mm->swap_cnt--; 
 
    ... 
 
    if (PageSwapCache(page)) { // 內存頁之前已經發生過交換操作 
        entry.val = page->index; 
        if (pte_dirty(pte)) 
            set_page_dirty(page); 
set_swap_pte: 
        swap_duplicate(entry); 
        // 把頁目錄項設置為磁盤交換區的信息(注意:此時是否在內存中標志位為0, 所以訪問這個內存地址會觸發內存訪問異常) 
        set_pte(page_table, swp_entry_to_pte(entry)); 
drop_pte: 
        UnlockPage(page); 
        mm->rss--; 
        deactivate_page(page); 
        page_cache_release(page); 
out_failed: 
        return 0; 
    } 
 
    ... 
 
    entry = get_swap_page(); 
    if (!entry.val) 
        goto out_unlock_restore; /* No swap space left */ 
 
    add_to_swap_cache(page, entry); 
    set_page_dirty(page); 
    goto set_swap_pte; 
 
out_unlock_restore: 
    set_pte(page_table, pte); 
    UnlockPage(page); 
    return 0; 
} 

上面的代碼中, 首先調用 get_swap_page() 函數獲取交換文件的一個槽(用于保存內存頁的內容), 然后調用 add_to_swap_cache() 函數把內存頁添加到活躍鏈表中, add_to_swap_cache() 函數源碼如下:

void add_to_swap_cache(struct page *page, swp_entry_t entry) 
{ 
    ... 
    add_to_page_cache_locked(page, &swapper_space, entry.val); 
} 
 
void add_to_page_cache_locked(struct page * page, struct address_space *mapping, unsigned long index) 
{ 
    if (!PageLocked(page)) 
        BUG(); 
 
    page_cache_get(page); 
    spin_lock(&pagecache_lock); 
    page->index = index; 
    add_page_to_inode_queue(mapping, page); 
    add_page_to_hash_queue(page, page_hash(mapping, index)); 
    lru_cache_add(page); 
    spin_unlock(&pagecache_lock); 
} 

add_to_swap_cache() 函數會調用 add_to_page_cache_locked() 函數, 而add_to_page_cache_locked() 函數會調用 lru_cache_add() 函數來把內存頁添加到活躍鏈表中, lru_cache_add() 函數代碼如下:

#define add_page_to_active_list(page) {     \ 
    DEBUG_ADD_PAGE                          \ 
    ZERO_PAGE_BUG                           \ 
    SetPageActive(page);                    \ 
    list_add(&(page)->lru, &active_list);   \ 
    nr_active_pages++;                      \ 
} 
 
void lru_cache_add(struct page * page) 
{ 
    spin_lock(&pagemap_lru_lock); 
    if (!PageLocked(page)) 
        BUG(); 
    DEBUG_ADD_PAGE 
    add_page_to_active_list(page); 
    /* This should be relatively rare */ 
    if (!page->age) 
        deactivate_page_nolock(page); 
    spin_unlock(&pagemap_lru_lock); 
} 

從上面的代碼可以看到, lru_cache_add() 函數最終會調用 list_add(&(page)->lru, &active_list) 這行代碼來把內存頁添加到活躍鏈表(active_list)中, 并設置內存頁的 PG_active 標志.

最后我們通過一幅圖來總結一下 kswapd 內核線程的流程:

kswap() 
└→ do_try_free_pages() 
   └→ page_launder() 
   └→ refill_inactive() 
      └→ refill_inactive_scan() 
      └→ swap_out() 

swap_out() 函數會把進程占用的內存頁添加到活躍鏈表中, 而 refill_inactive_scan() 函數會把活躍鏈表的內存頁移動到非活躍臟鏈表中, 最后 page_launder() 會把非活躍臟鏈表的內存頁刷新到磁盤并且移動到非活躍干凈鏈表中, 非活躍干凈鏈表中的內存頁是直接可以用來分配使用的。