LRU鏈表

本文轉(zhuǎn)自http://liurugongzi.blog.sohu.com/153648100.html

lru鏈表是統(tǒng)稱，細(xì)分為：活動鏈表、非活動鏈表。鏈表中存放的是屬于進(jìn)程用戶態(tài)地址空間或者頁高速緩存的所有頁。前者是最近被訪問過的頁，后者是一段時間內(nèi)未曾訪問過的頁，這樣的好處是提高效率，減少搬運(yùn)次數(shù)。而lru也是頁框回收算法的核心數(shù)據(jù)結(jié)構(gòu)。這兩個雙向鏈表是通過zone描述符結(jié)合入系統(tǒng)中，在zone中，有兩個字段：active_list,inactive_list.一個是活動鏈表的表頭，一個是非活動鏈表的表頭。而同時，處于此兩個鏈表中的頁框標(biāo)志位也需要相應(yīng)設(shè)置：PG_lru,PG_active.前者的標(biāo)志表明頁在活動或非活動頁鏈表中，而后者是頁在活動鏈表中。當(dāng)是屬于非活動鏈表時，標(biāo)志位要清。而頁描述符中的字段lru指向的是鏈表中的下一頁。如此，則形成了從zone管理區(qū)描述符中一個字段為起始點(diǎn)鏈接而成的lru鏈表。而處理鏈表也有幾個相應(yīng)的函數(shù)：

static inline void add_page_to_active_list(struct zone *zone, struct page *page)

static inline void add_page_to_inactive_list(struct zone *zone, struct page *page)

static inline void del_page_from_active_list(struct zone *zone, struct page *page)

static inline void del_page_from_inactive_list(struct zone *zone, struct page *page)

static inline void del_page_from_lru(struct zone *zone, struct page *page)

void fastcall activate_page(struct page *page)

void fastcall lru_cache_add(struct page *page)

void fastcall lru_cache_add_active(struct page *page)

兩個插入和刪除鏈表的函數(shù)是很簡單的，參數(shù)都是zone和page.使用的語句也是鏈表操作語句：list_add，list_del所不同的是，其中的參數(shù)傳遞：

list_add(&page->lru, &zone->active_list);

list_add(&page->lru, &zone->inactive_list);

list_del(&page->lru);

list_del(&page->lru);

而加入完畢后，zone中表示頁數(shù)目的字段也相應(yīng)增加：

zone->nr_active++;

zone->nr_inactive++;

zone->nr_active--;

zone->nr_inactive--;

而del_page_from_lru也與前兩個大同小異其中不同之處在于判斷了頁的PG_active標(biāo)志位。

static inline void del_page_from_lru(struct zone *zone, struct page *page)

{

list_del(&page->lru);

if (PageActive(page)) {

ClearPageActive(page);

zone->nr_active--;

} else {

zone->nr_inactive--;

}

}

而activate_page函數(shù)的目的就是將頁從非活動鏈表中移動到活動鏈表，其中的if塊就是這個作用，首先檢查是不是lru鏈表中的，然后判斷頁是不是在非活動鏈表中。如果在，就刪除。而刪除的目的是為了移動到活動鏈表中，而在活動鏈表中的頁的PG_active標(biāo)志位需要置位，于是SetPageActive(page);

void fastcall activate_page(struct page *page)

{

struct zone *zone = page_zone(page);

spin_lock_irq(&zone->lru_lock);

if (PageLRU(page) && !PageActive(page)) {

del_page_from_inactive_list(zone, page);

SetPageActive(page);

add_page_to_active_list(zone, page);

inc_page_state(pgactivate);

}

spin_unlock_irq(&zone->lru_lock);

}

而之所以設(shè)計這個框架，目的就是為了便于PFRA移動頁。而這中有涉及到一個頁標(biāo)志的使用：PG_referenced(剛被訪問過的頁)。當(dāng)非活動鏈表中的某一個頁被訪問時，那么并不是立刻移入活動鏈表，而是先檢查這個標(biāo)志位，如果這個標(biāo)志置位為0則置位(為1)，此頁依然保留在非活動鏈表中。當(dāng)再次訪問到此頁時，檢查此標(biāo)識符，如果為1，那么移入活動鏈表。如果兩次訪問時間間距超過了給定間隔，那么就要重新設(shè)置此標(biāo)志位。如果移動進(jìn)入了活動鏈表，那么PG_active標(biāo)志位也將被置位。可以說，在移動移出這兩個動作中，PG_referenced和PG_active兩個標(biāo)志位是配合使用的。

而涉及到這兩個動作的關(guān)鍵函數(shù)有三個：

void fastcall mark_page_accessed(struct page *page)

int page_referenced(struct page *page, int is_locked, int ignore_token)

static void refill_inactive_zone(struct zone *zone, struct scan_control *sc)

/*

* Mark a page as having seen activity.

*

* inactive,unreferenced??????? ->????? inactive,referenced

* inactive,referenced????????? ->????? active,unreferenced

* active,unreferenced????????? ->????? active,referenced

*/

void fastcall mark_page_accessed(struct page *page)

{

if (!PageActive(page) && PageReferenced(page) && PageLRU(page)) {

activate_page(page);

ClearPageReferenced(page);

} else if (!PageReferenced(page)) {

SetPageReferenced(page);

}

}

這個函數(shù)的作用就是必須把頁標(biāo)記為訪問過時調(diào)用。看函數(shù)的注釋，三種狀態(tài)之間的轉(zhuǎn)化：當(dāng)非活動鏈表和未使用過時調(diào)用函數(shù)，變?yōu)榉腔顒渔湵砗褪褂眠^；當(dāng)非活動鏈表和使用過時調(diào)用函數(shù)，變?yōu)榛顒渔湵砗臀词褂眠^；當(dāng)活動鏈表未使用過時調(diào)用函數(shù)，變?yōu)榛顒渔湵聿⑹褂眠^。完成以上功能的就是函數(shù)的目的。在函數(shù)體的if第一個判斷中，首先是判斷頁是否在lru鏈表中，還要判斷頁的標(biāo)志PG_referenced是否置位，還要判斷頁的PG_active標(biāo)志是否置位。如果此時頁標(biāo)志的組合是：在lru鏈表中，并且在單位時間內(nèi)使用過，并且未在活動鏈表中，則將此頁調(diào)入活動鏈表，并且清除PG_referenced標(biāo)志。然后在下一個判斷語句中，條件是頁沒有被剛剛使用過。也就是PG_referenced標(biāo)志位并沒有置位為1.那么此時就要置未。

而函數(shù)page_referenced的作用就是掃描時，對部分標(biāo)志位進(jìn)行清零工作，比如PG_referenced.

回收函數(shù)的重點(diǎn)是refill_inactive_zone函數(shù)。而函數(shù)中用到一個重要結(jié)構(gòu)：scan_control，這個結(jié)構(gòu)也是被PFRA廣泛使用，其中的各個字段存放著回首操作執(zhí)行的各種信息，直接影響到系統(tǒng)的策略取舍。

struct scan_control {

unsigned long nr_to_scan;活動鏈表中待掃描的目標(biāo)頁數(shù)

unsigned long nr_scanned;當(dāng)前迭代中掃描過的非活動頁數(shù)

unsigned long nr_reclaimed;當(dāng)前迭代中回收的頁數(shù)

unsigned long nr_mapped;用戶態(tài)地址空間引用的頁數(shù)

int nr_to_reclaim;待回收的目標(biāo)頁數(shù)

unsigned int priority;掃描優(yōu)先級范圍從12到0，低優(yōu)先級表示掃描更多的頁

unsigned int gfp_mask;調(diào)用進(jìn)程傳來的GFP掩碼

int may_writepage;如果置位，則允許將臟頁寫到磁盤(只針對便攜情形)

};

這個函數(shù)所從事的基本工作始終是循環(huán)判斷標(biāo)志，然后將頁插入不同的鏈表。前后需要四次循環(huán)。在移動過程中的判斷，需要一個臨時的輔助鏈表LIST_HEAD(l_hold);

第一次循環(huán)：在這個循環(huán)判斷語句中，int pgscanned = 0;int nr_pages = sc->nr_to_scan(活動鏈表中待掃描的目標(biāo)頁數(shù));可見循環(huán)的第一個條件就是活動鏈表中的目標(biāo)頁的個數(shù)，下一個條件就是list_empty(&zone->active_list)或者鏈表為空時結(jié)束。將掃描頁加入到臨時鏈表中 list_add(&page->lru, &l_hold);而如果標(biāo)志為0，則一定是伙伴系統(tǒng)中的，所以要放回到活動鏈表中。因為伙伴系統(tǒng)是準(zhǔn)備分配大塊內(nèi)存區(qū)時使用，而并不是“零星”使用的。

while (pgscanned < nr_pages && !list_empty(&zone->active_list)) {

page = lru_to_page(&zone->active_list);

prefetchw_prev_lru_page(page, &zone->active_list, flags);

list_del(&page->lru);

if (get_page_testone(page)) {

__put_page(page);

SetPageLRU(page);

list_add(&page->lru, &zone->active_list);

} else {

list_add(&page->lru, &l_hold);

pgmoved++;

}

pgscanned++;

}

在完成第一個循環(huán)體后，臨時鏈表中已經(jīng)有了頁，而在活動鏈表中也已經(jīng)摘除了部分頁，這些是準(zhǔn)備回收的頁。然后就是準(zhǔn)備工作以及“計算交換值”。

zone->pages_scanned += pgscanned;

zone->nr_active -= pgmoved;

distress = 100 >> zone->prev_priority;

mapped_ratio = (sc->nr_mapped * 100) / total_memory;

swap_tendency = mapped_ratio / 2 + distress + vm_swappiness;

if (swap_tendency >= 100)

reclaim_mapped = 1;

交換傾向值是用來決定系統(tǒng)回收方式的。它的目的是用來判斷不同情況下，回收數(shù)量的多少。也就是說，當(dāng)回收的頁框數(shù)量太多的時候，那么系統(tǒng)的效率就會受到很大的影響，也就是回收了過多的活動鏈表中的頁。而如果回收的數(shù)量太少，那么同樣非活動鏈表中的準(zhǔn)備引用頁數(shù)量不足以彌補(bǔ)系統(tǒng)調(diào)用，那么效率也會受到影響，而如何保持均衡，就是通過這個數(shù)值來判斷的。而在結(jié)構(gòu)sc_contrl中的字段priority，是對應(yīng)zone中的prev_priority;后者是管理區(qū)優(yōu)先級。而另一種方式就是通過計算，也就是交換傾向數(shù)值。

lru鏈表中有兩類頁：屬于用戶態(tài)地址空間的頁、不屬于任何用戶態(tài)進(jìn)程且在頁高速緩存中的頁。而PFRA傾向與把用戶態(tài)進(jìn)程的頁保留在ram中，從而壓縮頁高速緩存。而這個數(shù)值的作用就是決定函數(shù)是移動所有的頁，還是僅僅移動不屬于用戶態(tài)進(jìn)程的頁。

交換傾向值＝映射比率／2+負(fù)荷值＋交換值

其中映射比率由字段：nr_mapped來表示，也就是占有可分配頁框的比率。如果這個數(shù)值大，那么系統(tǒng)中的大部分動態(tài)內(nèi)存大部分用于用戶態(tài)進(jìn)程，反之則用于頁高速緩存。

而負(fù)荷值是表示回收頁框算法在管理區(qū)中回收頁框的效率。也就是字段：prev_priority

交換值則為用戶定義的常數(shù)，通常為60，在/proc/sys/vm/swappiness中可以修改數(shù)值。

當(dāng)交換傾向數(shù)值大于100時，頁將從進(jìn)程地址空間回收。當(dāng)交換值被人為設(shè)置為0時，那么系統(tǒng)不會從用戶態(tài)地址空間回收。如果人為設(shè)置為100時，那么每次調(diào)用此函數(shù)都會從用戶態(tài)地址空間回收。以上就是這段程序的用途。

第二次循環(huán)：則是通過上面的交換數(shù)值以及一些條件來判斷是否加入活動鏈表，其余的一概加入非活動鏈表。也就是從第一次循環(huán)中摘出的那些頁的第二次再分配。

while (!list_empty(&l_hold)) {

cond_resched();

page = lru_to_page(&l_hold);

list_del(&page->lru);

if (page_mapped(page)) {

if (!reclaim_mapped || (total_swap_pages == 0 && PageAnon(page)) || page_referenced(page, 0, sc->priority <= 0)) {

list_add(&page->lru, &l_active);

continue;

}

}

list_add(&page->lru, &l_inactive);

}

第三次循環(huán)：將頁移入到管理區(qū)非活動鏈表中。

while (!list_empty(&l_inactive)) {

page = lru_to_page(&l_inactive);

prefetchw_prev_lru_page(page, &l_inactive, flags);

list_move(&page->lru, &zone->inactive_list);

pgmoved++;

if (!pagevec_add(&pvec, page)) {

zone->nr_inactive += pgmoved;

spin_unlock_irq(&zone->lru_lock);

pgdeactivate += pgmoved;

pgmoved = 0;

if (buffer_heads_over_limit)

pagevec_strip(&pvec);

__pagevec_release(&pvec);

spin_lock_irq(&zone->lru_lock);

}

}

第四次循環(huán)，將頁移入到管理區(qū)的活動鏈表中。

while (!list_empty(&l_active)) {

page = lru_to_page(&l_active);

prefetchw_prev_lru_page(page, &l_active, flags);

if (TestSetPageLRU(page))

BUG();

BUG_ON(!PageActive(page));

list_move(&page->lru, &zone->active_list);

pgmoved++;

if (!pagevec_add(&pvec, page)) {

zone->nr_active += pgmoved;

pgmoved = 0;

spin_unlock_irq(&zone->lru_lock);

__pagevec_release(&pvec);

spin_lock_irq(&zone->lru_lock);

}

}

總結(jié)

以上是生活随笔為你收集整理的linux2.6内核分析,linux2.6内核分析——LRU链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。