一文看懂內(nèi)存交換機(jī)制
本文基于 Linux-2.4.16 內(nèi)核版本
由于計(jì)算機(jī)的物理內(nèi)存是有限的, 而進(jìn)程對(duì)內(nèi)存的使用是不確定的, 所以物理內(nèi)存總有用完的可能性. 那么當(dāng)系統(tǒng)的物理內(nèi)存不足時(shí), Linux內(nèi)核使用什么方案來(lái)避免申請(qǐng)不到物理內(nèi)存這個(gè)問(wèn)題呢?
相對(duì)于內(nèi)存來(lái)說(shuō), 磁盤的容量是非常大的, 所以Linux內(nèi)核實(shí)現(xiàn)了一個(gè)叫 內(nèi)存交換 的功能 -- 把某些進(jìn)程的一些暫時(shí)用不到的內(nèi)存頁(yè)保存到磁盤中, 然后把物理內(nèi)存頁(yè)分配給更緊急的用戶使用, 當(dāng)進(jìn)程用到時(shí)再?gòu)拇疟P讀回到內(nèi)存中即可. 有了 內(nèi)存交換 功能, 系統(tǒng)可使用的內(nèi)存就可以遠(yuǎn)遠(yuǎn)大于物理內(nèi)存的容量。
LRU算法
內(nèi)存交換 過(guò)程首先是找到一個(gè)合適的用戶進(jìn)程內(nèi)存管理結(jié)構(gòu)，然后把進(jìn)程占用的內(nèi)存頁(yè)交換到磁盤中，并斷開虛擬內(nèi)存與物理內(nèi)存的映射，最后釋放進(jìn)程占用的內(nèi)存頁(yè)。由于涉及到IO操作，所以這是一個(gè)比較耗時(shí)的過(guò)程。如果被交換出去的內(nèi)存頁(yè)剛好又被訪問(wèn)了，這時(shí)又需要從磁盤中把內(nèi)存頁(yè)的數(shù)據(jù)交換到內(nèi)存中。所以，在這種情況下不單不能解決內(nèi)存緊缺的問(wèn)題，而且增加了系統(tǒng)的負(fù)荷。
為了解決這個(gè)問(wèn)題，Linux內(nèi)核使用了一種稱為 LRU (Least Recently Used) 的算法, 下面介紹一下 LRU算法 的大體過(guò)程。
LRU 的中文翻譯是 最近最少使用, 顧名思義就是一段時(shí)間內(nèi)沒(méi)有被使用, 那么Linux內(nèi)核怎么知道哪些內(nèi)存頁(yè)面最近沒(méi)有被使用呢? 最簡(jiǎn)單的方法就是把內(nèi)存頁(yè)放進(jìn)一個(gè)隊(duì)列里, 如果內(nèi)存頁(yè)被訪問(wèn)了, 就把內(nèi)存頁(yè)移動(dòng)到鏈表的頭部, 這樣沒(méi)被訪問(wèn)的內(nèi)存頁(yè)在一段時(shí)間后便會(huì)移動(dòng)到隊(duì)列的尾部, 而釋放內(nèi)存頁(yè)時(shí)從鏈表的尾部開始. 著名的緩存服務(wù)器 memcached 就是使用這種 LRU算法。
Linux內(nèi)核也使用了類似的算法, 但相對(duì)要復(fù)雜一些. Linux內(nèi)核維護(hù)著三個(gè)隊(duì)列: 活躍隊(duì)列, 非活躍臟隊(duì)列和非活躍干凈隊(duì)列. 為什么Linux需要維護(hù)三個(gè)隊(duì)列, 而不是使用一個(gè)隊(duì)列呢? 這是因?yàn)長(zhǎng)inux希望內(nèi)存頁(yè)交換過(guò)程慢慢進(jìn)行, Linux內(nèi)核有個(gè)內(nèi)核線程 kswapd 會(huì)定時(shí)檢查系統(tǒng)的空閑內(nèi)存頁(yè)是否緊缺, 如果系統(tǒng)的空閑內(nèi)存頁(yè)緊缺時(shí)時(shí), 就會(huì)選擇一些用戶進(jìn)程把其占用的內(nèi)存頁(yè)添加到活躍鏈表中并斷開進(jìn)程與此內(nèi)存頁(yè)的映射關(guān)系. 隨著時(shí)間的推移, 如果內(nèi)存頁(yè)沒(méi)有被訪問(wèn), 那么就會(huì)被移動(dòng)到非活躍臟鏈表. 非活躍臟鏈表中的內(nèi)存頁(yè)是需要被交換到磁盤的, 當(dāng)系統(tǒng)中空閑內(nèi)存頁(yè)緊缺時(shí)就會(huì)從非活躍臟鏈表的尾部開始把內(nèi)存頁(yè)刷新到磁盤中, 然后移動(dòng)到非活躍干凈鏈表中, 非活躍干凈鏈表中的內(nèi)存頁(yè)是可以立刻分配給進(jìn)程使用的. 各個(gè)鏈表之間的移動(dòng)如下圖:
lru links
如果在這個(gè)過(guò)程中, 內(nèi)存頁(yè)又被訪問(wèn)了, 那么Linux內(nèi)核會(huì)把內(nèi)存頁(yè)移動(dòng)到活躍鏈表中, 并且建立內(nèi)存映射關(guān)系, 這樣就不需要從磁盤中讀取內(nèi)存頁(yè)的內(nèi)容。
注意: 內(nèi)核只維護(hù)著一個(gè)活躍鏈表和一個(gè)非活躍臟鏈表, 但是非活躍干凈鏈表是每個(gè)內(nèi)存管理區(qū)都有一個(gè)的。
這是因?yàn)榉峙鋬?nèi)存是在內(nèi)存管理區(qū)的基礎(chǔ)上進(jìn)行的, 所以一個(gè)內(nèi)存頁(yè)必須屬于某一個(gè)內(nèi)存管理區(qū)。
kswapd內(nèi)核線程
在Linux系統(tǒng)啟動(dòng)時(shí)會(huì)調(diào)用 kswapd_init() 函數(shù), 代碼如下:
- 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() 函數(shù)會(huì)創(chuàng)建 kswapd 和 kreclaimd 兩個(gè)內(nèi)核線程, 這兩個(gè)內(nèi)核線程負(fù)責(zé)在系統(tǒng)物理內(nèi)存緊缺時(shí)釋放一些物理內(nèi)存頁(yè), 從而使系統(tǒng)的可用內(nèi)存達(dá)到一個(gè)平衡. 下面我們重點(diǎn)來(lái)分析 kswapd 這個(gè)內(nèi)核線程, 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 內(nèi)核線程由一個(gè)無(wú)限循環(huán)組成, 首先通過(guò) inactive_shortage() 和 free_shortage() 函數(shù)判斷系統(tǒng)的非活躍頁(yè)面和空閑物理內(nèi)存頁(yè)是否短缺, 如果短缺的話, 那么就調(diào)用 do_try_to_free_pages() 函數(shù)試圖釋放一些物理內(nèi)存頁(yè). 然后通過(guò)調(diào)用 refill_inactive_scan() 函數(shù)把一些活躍鏈表中的內(nèi)存頁(yè)移動(dòng)到非活躍臟鏈表中. 最后, 如果空閑物理內(nèi)存頁(yè)或者非活躍內(nèi)存頁(yè)不短缺, 那么就讓 kswapd 內(nèi)核線程休眠一秒。
接下來(lái)我們分析一下 do_try_to_free_pages() 函數(shù)做了一些什么工作, 代碼如下:
- 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() 函數(shù)第一步先判斷系統(tǒng)中的空閑物理內(nèi)存頁(yè)是否短缺, 或者非活躍臟頁(yè)面的數(shù)量大于空閑物理內(nèi)存頁(yè)和非活躍干凈頁(yè)面的總和, 其中一個(gè)條件滿足了, 就調(diào)用 page_launder() 函數(shù)把非活躍臟鏈表中的頁(yè)面刷到磁盤中, 然后移動(dòng)到非活躍干凈鏈表中. 接下來(lái)如果內(nèi)存還是緊缺的話, 那么就調(diào)用 shrink_dcache_memory(), shrink_icache_memory() 和 refill_inactive() 函數(shù)繼續(xù)釋放內(nèi)存。
下面我們先來(lái)分析一下 page_launder() 這個(gè)函數(shù), 由于這個(gè)函數(shù)很長(zhǎng), 所以我們分段來(lái)解釋:
- 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; // 是否需要進(jìn)行寫盤操作
- 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 上鎖, 然后從尾部開始遍歷非活躍臟鏈表。
- // 如果滿足以下的任意一個(gè)條件, 都表示內(nèi)存頁(yè)在使用中, 把他移動(dòng)到活躍鏈表
- if (PageTestandClearReferenced(page) || // 如果設(shè)置了 PG_referenced 標(biāo)志
- page->age > 0 || // 如果age大于0, 表示頁(yè)面被訪問(wèn)過(guò)
- (!page->buffers && page_count(page) > 1) || // 如果頁(yè)面被其他進(jìn)程映射
- page_ramdisk(page)) { // 如果用于內(nèi)存磁盤的頁(yè)面
- del_page_from_inactive_dirty_list(page);
- add_page_to_active_list(page);
- continue;
- }
上面代碼判斷內(nèi)存頁(yè)是否能需要重新移動(dòng)到活躍鏈表中, 依據(jù)有:
- 內(nèi)存頁(yè)是否設(shè)置了 PG_referenced 標(biāo)志;
- 內(nèi)存頁(yè)的age字段是否大于0 (age字段是內(nèi)存頁(yè)的生命周期);
- 內(nèi)存頁(yè)是否還有映射關(guān)系;
- 內(nèi)存頁(yè)是否用于內(nèi)存磁盤.
如果滿足上面其中一個(gè)條件, 都需要重新把內(nèi)存頁(yè)移動(dòng)到活躍頁(yè)面中。
- if (PageDirty(page)) { // 如果頁(yè)面是臟的, 那么應(yīng)該把頁(yè)面寫到磁盤中
- 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) { // 第一次只把頁(yè)面移動(dòng)到鏈表的頭部, 這是為了先處理已經(jīng)干凈的頁(yè)面
- 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;
- }
上面的代碼首先判斷內(nèi)存頁(yè)是否臟的(是否設(shè)置了 PG_dirty 標(biāo)志), 如果是, 那么就需要把內(nèi)存頁(yè)刷新到磁盤中. 這里有個(gè)要主要的地方是, 當(dāng) launder_loop 變量為0時(shí)只是把內(nèi)存頁(yè)移動(dòng)到非活躍臟鏈表的頭部. 當(dāng) launder_loop 變量為1時(shí)才會(huì)把內(nèi)存頁(yè)刷新到磁盤中. 為什么要這樣做呢? 這是因?yàn)長(zhǎng)inux內(nèi)核希望第一次掃描先把非活躍臟鏈表中的干凈內(nèi)存頁(yè)移動(dòng)到非活躍干凈鏈表中, 第二次掃描才把臟的內(nèi)存頁(yè)刷新到磁盤中. 后面的代碼會(huì)對(duì) launder_loop 變量進(jìn)行修改. 而且我們發(fā)現(xiàn), 把臟頁(yè)面刷新到磁盤后, 并沒(méi)有立刻把內(nèi)存頁(yè)移動(dòng)到非活躍干凈鏈表中, 而是簡(jiǎn)單的清除了 PG_dirty 標(biāo)志。
- if (page->buffers) { // 涉及文件系統(tǒng)部分, 先略過(guò)
- ...
- } else if (page->mapping && !PageDirty(page)) { // 內(nèi)存頁(yè)是干凈的, 移動(dòng)到非活躍干凈鏈表
- 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);
- }
上面的代碼比較簡(jiǎn)單, 如果內(nèi)存頁(yè)已經(jīng)是干凈的, 那么久移動(dòng)到非活躍干凈鏈表中.
- 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;
從上面的代碼可以看到, 當(dāng) can_get_io_locks 等于1(gfp_mask 設(shè)置了 __GFP_IO 標(biāo)志), launder_loop 等于0, 并且空閑內(nèi)存頁(yè)還是短缺(free_shortage() 為真)的情況下, 把 launder_loop 變量被設(shè)置為1, 并且跳轉(zhuǎn)到 dirty_page_rescan 處重新掃描, 這是第二次掃描非活躍臟鏈表, 會(huì)把臟的內(nèi)存頁(yè)刷新到磁盤中。
接下來(lái)我們繼續(xù)分析 refill_inactive() 這個(gè)函數(shù):
- 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)) { // 把活躍頁(yè)面鏈表中的頁(yè)面移動(dòng)到非活躍臟頁(yè)面鏈表中
- made_progress = 1;
- if (--count <= 0)
- goto done;
- }
- ...
- while (swap_out(priority, gfp_mask)) { // 把一些用戶進(jìn)程映射的內(nèi)存頁(yè)放置到活躍頁(yè)面鏈表中
- 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);
- }
在這個(gè)函數(shù)中, 我們主要關(guān)注兩個(gè)地方:
- 調(diào)用 refill_inactive_scan() 函數(shù), refill_inactive_scan() 函數(shù)的作用是把活躍鏈表中的內(nèi)存頁(yè)移動(dòng)到非活躍臟鏈表中。
- 調(diào)用 swap_out() 函數(shù), swap_out() 函數(shù)的作用是選擇一個(gè)用戶進(jìn)程, 并且把其映射的內(nèi)存頁(yè)添加到活躍鏈表中。
先來(lái)看看 refill_inactive_scan() 函數(shù):
- 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); // 把頁(yè)面放置到非活躍臟頁(yè)面鏈表
- 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() 函數(shù)比較簡(jiǎn)單, 首先從活躍鏈表的尾部開始遍歷, 然后判斷內(nèi)存頁(yè)的生命是否已經(jīng)用完(age是否等于0), 并且沒(méi)有進(jìn)程與其有映射關(guān)系(count是否等于1). 如果是, 那么就調(diào)用 deactivate_page_nolock() 函數(shù)把內(nèi)存頁(yè)移動(dòng)到非活躍臟鏈表中。
接著來(lái)看看 swap_out() 函數(shù), swap_out() 函數(shù)比較復(fù)雜, 但最終會(huì)調(diào)用 try_to_swap_out() 函數(shù), 所以我們只分析 try_to_swap_out() 函數(shù):
- 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)) { // 內(nèi)存頁(yè)之前已經(jīng)發(fā)生過(guò)交換操作
- entry.val = page->index;
- if (pte_dirty(pte))
- set_page_dirty(page);
- set_swap_pte:
- swap_duplicate(entry);
- // 把頁(yè)目錄項(xiàng)設(shè)置為磁盤交換區(qū)的信息(注意:此時(shí)是否在內(nèi)存中標(biāo)志位為0, 所以訪問(wèn)這個(gè)內(nèi)存地址會(huì)觸發(fā)內(nèi)存訪問(wèn)異常)
- 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;
- }
上面的代碼中, 首先調(diào)用 get_swap_page() 函數(shù)獲取交換文件的一個(gè)槽(用于保存內(nèi)存頁(yè)的內(nèi)容), 然后調(diào)用 add_to_swap_cache() 函數(shù)把內(nèi)存頁(yè)添加到活躍鏈表中, add_to_swap_cache() 函數(shù)源碼如下:
- 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() 函數(shù)會(huì)調(diào)用 add_to_page_cache_locked() 函數(shù), 而add_to_page_cache_locked() 函數(shù)會(huì)調(diào)用 lru_cache_add() 函數(shù)來(lái)把內(nèi)存頁(yè)添加到活躍鏈表中, lru_cache_add() 函數(shù)代碼如下:
- #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() 函數(shù)最終會(huì)調(diào)用 list_add(&(page)->lru, &active_list) 這行代碼來(lái)把內(nèi)存頁(yè)添加到活躍鏈表(active_list)中, 并設(shè)置內(nèi)存頁(yè)的 PG_active 標(biāo)志.
最后我們通過(guò)一幅圖來(lái)總結(jié)一下 kswapd 內(nèi)核線程的流程:
- kswap()
- └→ do_try_free_pages()
- └→ page_launder()
- └→ refill_inactive()
- └→ refill_inactive_scan()
- └→ swap_out()
swap_out() 函數(shù)會(huì)把進(jìn)程占用的內(nèi)存頁(yè)添加到活躍鏈表中, 而 refill_inactive_scan() 函數(shù)會(huì)把活躍鏈表的內(nèi)存頁(yè)移動(dòng)到非活躍臟鏈表中, 最后 page_launder() 會(huì)把非活躍臟鏈表的內(nèi)存頁(yè)刷新到磁盤并且移動(dòng)到非活躍干凈鏈表中, 非活躍干凈鏈表中的內(nèi)存頁(yè)是直接可以用來(lái)分配使用的。
