一文看懂 | 內(nèi)存交換機(jī)制
掃描二維碼
隨時(shí)隨地手機(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ō), 磁盤(pán)的容量是非常大的, 所以L(fǎng)inux內(nèi)核實(shí)現(xiàn)了一個(gè)叫內(nèi)存交換的功能 -- 把某些進(jìn)程的一些暫時(shí)用不到的內(nèi)存頁(yè)保存到磁盤(pán)中, 然后把物理內(nèi)存頁(yè)分配給更緊急的用戶(hù)使用, 當(dāng)進(jìn)程用到時(shí)再?gòu)拇疟P(pán)讀回到內(nèi)存中即可. 有了內(nèi)存交換功能, 系統(tǒng)可使用的內(nèi)存就可以遠(yuǎn)遠(yuǎn)大于物理內(nèi)存的容量.
LRU算法
內(nèi)存交換過(guò)程首先是找到一個(gè)合適的用戶(hù)進(jìn)程內(nèi)存管理結(jié)構(gòu)，然后把進(jìn)程占用的內(nèi)存頁(yè)交換到磁盤(pán)中，并斷開(kāi)虛擬內(nèi)存與物理內(nèi)存的映射，最后釋放進(jìn)程占用的內(nèi)存頁(yè)。由于涉及到IO操作，所以這是一個(gè)比較耗時(shí)的過(guò)程。如果被交換出去的內(nèi)存頁(yè)剛好又被訪(fǎng)問(wèn)了，這時(shí)又需要從磁盤(pán)中把內(nèi)存頁(yè)的數(shù)據(jù)交換到內(nèi)存中。所以，在這種情況下不單不能解決內(nèi)存緊缺的問(wèn)題，而且增加了系統(tǒng)的負(fù)荷。
為了解決這個(gè)問(wèn)題，Linux內(nèi)核使用了一種稱(chēng)為L(zhǎng)RU (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è)被訪(fǎng)問(wèn)了, 就把內(nèi)存頁(yè)移動(dòng)到鏈表的頭部, 這樣沒(méi)被訪(fǎng)問(wèn)的內(nèi)存頁(yè)在一段時(shí)間后便會(huì)移動(dòng)到隊(duì)列的尾部, 而釋放內(nèi)存頁(yè)時(shí)從鏈表的尾部開(kāi)始. 著名的緩存服務(wù)器memcached就是使用這種LRU算法.
Linux內(nèi)核也使用了類(lè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)核線(xiàn)程kswapd會(huì)定時(shí)檢查系統(tǒng)的空閑內(nèi)存頁(yè)是否緊缺, 如果系統(tǒng)的空閑內(nèi)存頁(yè)緊缺時(shí)時(shí), 就會(huì)選擇一些用戶(hù)進(jìn)程把其占用的內(nèi)存頁(yè)添加到活躍鏈表中并斷開(kāi)進(jìn)程與此內(nèi)存頁(yè)的映射關(guān)系. 隨著時(shí)間的推移, 如果內(nèi)存頁(yè)沒(méi)有被訪(fǎng)問(wèn), 那么就會(huì)被移動(dòng)到非活躍臟鏈表. 非活躍臟鏈表中的內(nèi)存頁(yè)是需要被交換到磁盤(pán)的, 當(dāng)系統(tǒng)中空閑內(nèi)存頁(yè)緊缺時(shí)就會(huì)從非活躍臟鏈表的尾部開(kāi)始把內(nèi)存頁(yè)刷新到磁盤(pán)中, 然后移動(dòng)到非活躍干凈鏈表中, 非活躍干凈鏈表中的內(nèi)存頁(yè)是可以立刻分配給進(jìn)程使用的. 各個(gè)鏈表之間的移動(dòng)如下圖:
lru links
如果在這個(gè)過(guò)程中, 內(nèi)存頁(yè)又被訪(fǎng)問(wèn)了, 那么Linux內(nèi)核會(huì)把內(nèi)存頁(yè)移動(dòng)到活躍鏈表中, 并且建立內(nèi)存映射關(guān)系, 這樣就不需要從磁盤(pá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)核線(xiàn)程
在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)核線(xiàn)程, 這兩個(gè)內(nèi)核線(xiàn)程負(fù)責(zé)在系統(tǒng)物理內(nèi)存緊缺時(shí)釋放一些物理內(nèi)存頁(yè), 從而使系統(tǒng)的可用內(nèi)存達(dá)到一個(gè)平衡. 下面我們重點(diǎn)來(lái)分析kswapd這個(gè)內(nèi)核線(xiàn)程,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)核線(xiàn)程由一個(gè)無(wú)限循環(huán)組成, 首先通過(guò)inactive_shortage()和free_shortage()函數(shù)判斷系統(tǒng)的非活躍頁(yè)面和空閑物理內(nèi)存頁(yè)是否短缺, 如果短缺的話(huà), 那么就調(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)核線(xiàn)程休眠一秒.
接下來(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è)條件滿(mǎn)足了, 就調(diào)用page_launder()函數(shù)把非活躍臟鏈表中的頁(yè)面刷到磁盤(pán)中, 然后移動(dòng)到非活躍干凈鏈表中. 接下來(lái)如果內(nèi)存還是緊缺的話(huà), 那么就調(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)行寫(xiě)盤(pán)操作 launder_loop = 0; maxlaunder = 0; cleaned_pages = 0; dirty_page_rescan: spin_lock(&pagemap_lru_lock); maxscan = nr_inactive_dirty_pages; // 從非活躍臟鏈表的后面開(kāi)始掃描 while ((page_lru = inactive_dirty_list.prev) != &inactive_dirty_list && maxscan-- > 0) { page = list_entry(page_lru, struct page, lru); ...
上面的代碼首先把pagemap_lru_lock上鎖, 然后從尾部開(kāi)始遍歷非活躍臟鏈表.
// 如果滿(mǎn)足以下的任意一個(gè)條件, 都表示內(nèi)存頁(yè)在使用中, 把他移動(dòng)到活躍鏈表 if (PageTestandClearReferenced(page) || // 如果設(shè)置了 PG_referenced 標(biāo)志 page->age > 0 || // 如果age大于0, 表示頁(yè)面被訪(fǎng)問(wèn)過(guò) (!page->buffers && page_count(page) > 1) || // 如果頁(yè)面被其他進(jìn)程映射 page_ramdisk(page)) { // 如果用于內(nèi)存磁盤(pán)的頁(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)存磁盤(pán).
如果滿(mǎn)足上面其中一個(gè)條件, 都需要重新把內(nèi)存頁(yè)移動(dòng)到活躍頁(yè)面中.
if (PageDirty(page)) { // 如果頁(yè)面是臟的, 那么應(yīng)該把頁(yè)面寫(xiě)到磁盤(pán)中 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è)刷新到磁盤(pán)中. 這里有個(gè)要主要的地方是, 當(dāng)launder_loop變量為0時(shí)只是把內(nèi)存頁(yè)移動(dòng)到非活躍臟鏈表的頭部. 當(dāng)launder_loop變量為1時(shí)才會(huì)把內(nèi)存頁(yè)刷新到磁盤(pán)中. 為什么要這樣做呢? 這是因?yàn)長(zhǎng)inux內(nèi)核希望第一次掃描先把非活躍臟鏈表中的干凈內(nèi)存頁(yè)移動(dòng)到非活躍干凈鏈表中, 第二次掃描才把臟的內(nèi)存頁(yè)刷新到磁盤(pán)中. 后面的代碼會(huì)對(duì)launder_loop變量進(jìn)行修改. 而且我們發(fā)現(xiàn), 把臟頁(yè)面刷新到磁盤(pán)后, 并沒(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è)刷新到磁盤(pán)中.
接下來(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)) { // 把一些用戶(hù)進(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è)用戶(hù)進(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)單, 首先從活躍鏈表的尾部開(kāi)始遍歷, 然后判斷內(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è)置為磁盤(pán)交換區(qū)的信息(注意:此時(shí)是否在內(nèi)存中標(biāo)志位為0, 所以訪(fǎng)問(wèn)這個(gè)內(nèi)存地址會(huì)觸發(fā)內(nèi)存訪(fǎng)問(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)核線(xiàn)程的流程:
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è)刷新到磁盤(pán)并且移動(dòng)到非活躍干凈鏈表中, 非活躍干凈鏈表中的內(nèi)存頁(yè)是直接可以用來(lái)分配使用的.
下載文檔
