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