一文看懂 | 內(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)沒有被使用, 那么Linux內(nèi)核怎么知道哪些內(nèi)存頁(yè)面最近沒有被使用呢? 最簡(jiǎn)單的方法就是把內(nèi)存頁(yè)放進(jìn)一個(gè)隊(duì)列里, 如果內(nèi)存頁(yè)被訪問(wèn)了, 就把內(nèi)存頁(yè)移動(dòng)到鏈表的頭部, 這樣沒被訪問(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è)沒有被訪問(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)如下圖:
如果在這個(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è)面刷新到磁盤后, 并沒有立刻把內(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), 并且沒有進(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)分配使用的.