第17章 回收頁(yè)框
頁(yè)框回收算法
內(nèi)存及磁盤(pán)高速緩存抓取了那么多的頁(yè)框但從未釋放任何頁(yè)框。因此，遲早所有的空閑內(nèi)存將被分配給進(jìn)程和高速緩存。Linux內(nèi)核的頁(yè)框回收算法（page frame reclaiming algorithm，PFRA）采取從用戶進(jìn)程和內(nèi)核高速緩存“竊取”頁(yè)框的辦法補(bǔ)充伙伴系統(tǒng)的空閑塊列表。
頁(yè)框回收算法的目標(biāo)之一就是保存最少的空閑頁(yè)框池以便內(nèi)核可以安全地從“內(nèi)存緊缺”的情形中恢復(fù)過(guò)來(lái)。
PFRA按照頁(yè)框所含內(nèi)容，以不同的方式處理頁(yè)框：
映射頁(yè)：所謂“映射頁(yè)”就是指該頁(yè)映射了一個(gè)文件的某個(gè)部分。映射頁(yè)差不多都是可同步的，為了回收頁(yè)框，內(nèi)核必須檢查頁(yè)是否為臟，而且必要時(shí)將頁(yè)的內(nèi)容寫(xiě)道相應(yīng)的磁盤(pán)文件。
匿名頁(yè)：所謂“匿名頁(yè)”就是指它屬于一個(gè)進(jìn)程的某個(gè)線性區(qū)（例如，進(jìn)程的用戶態(tài)堆和堆棧中的所有頁(yè)稱(chēng)為匿名頁(yè)）。為了回收頁(yè)框，內(nèi)核必須將頁(yè)中內(nèi)容保存到一個(gè)專(zhuān)門(mén)的磁盤(pán)分區(qū)或磁盤(pán)文件，叫做“交換區(qū)”。所以匿名頁(yè)都是可交換的。
PFRA設(shè)計(jì)
PFRA算法的候選頁(yè)：磁盤(pán)高速緩存 頁(yè)高速緩存以及屬于進(jìn)程用戶態(tài)地址空間的頁(yè)。
PFRA算法的原則：
1.首先釋放無(wú)害頁(yè)：在進(jìn)程用戶態(tài)地址空間的頁(yè)回收之前，必須縣回收沒(méi)有被任何進(jìn)程使用的磁盤(pán)和內(nèi)存高速緩存的頁(yè)
2.將用戶進(jìn)程的所有頁(yè)定為可回收頁(yè)：除了鎖定頁(yè)，PFRA必須能夠竊得任何用戶進(jìn)程頁(yè)。這樣，睡眠較長(zhǎng)時(shí)間的進(jìn)程將會(huì)失去所有頁(yè)框
3.同時(shí)取消引用一個(gè)共享頁(yè)框的所有頁(yè)表項(xiàng)的映射，就可以回收該共享頁(yè)框
4.只回收未用頁(yè)：使用簡(jiǎn)化的LRU算法，PFRA算法將頁(yè)框分為在用（in_use）和未用（unused）
反向映射
PFRA的目標(biāo)之一是回收共享頁(yè)框。Linux 2.6內(nèi)核能夠快速定位指向同一頁(yè)框的所有頁(yè)表項(xiàng)。這個(gè)過(guò)程稱(chēng)為反向映射（reverse mapping）。
反向映射方法的簡(jiǎn)單解決之道，就是在頁(yè)描述符中引入附加字段，從而將某頁(yè)描述符所確定的頁(yè)框中對(duì)應(yīng)的所有頁(yè)表項(xiàng)聯(lián)接起來(lái)。但是，保持更新這樣的鏈表將會(huì)大大增加系統(tǒng)開(kāi)銷(xiāo)。Linux 2.6采用”面向?qū)ο蟮姆聪蛴成洹钡募夹g(shù)。實(shí)際上，對(duì)任何可回收的用戶態(tài)頁(yè)，內(nèi)核保留系統(tǒng)中該頁(yè)所在所有線性區(qū)（“對(duì)象”）的反向鏈接，每個(gè)線性區(qū)描述符存放一個(gè)指針指向一個(gè)內(nèi)存區(qū)描述符，而該內(nèi)存描述符又包含一個(gè)指針 指向一個(gè)頁(yè)全局目錄（Page Global Directory）。因此，這些反向鏈接使得PFRA能夠檢索引用某頁(yè)的所有頁(yè)表項(xiàng)。
為確定頁(yè)框是共享還是非共享的，匿名還是非匿名，內(nèi)核要查看頁(yè)描述符的兩個(gè)字段：_mapcount和mapping。
_mapcount：引用頁(yè)框的頁(yè)表項(xiàng)數(shù)目。
? ? ? ? ? ? ? ? ? 為-1，表示沒(méi)有頁(yè)表項(xiàng)引用該頁(yè)框
? ? ? ? ? ? ? ? ? 為0，表示是非共享頁(yè)框，即只有一個(gè)頁(yè)表項(xiàng)引用該頁(yè)框大于0，表示頁(yè)框是共享的
? ? ? ? ? ? ? ? ? page_mapcount函數(shù)接受一個(gè)頁(yè)描述符地址，返回值為map_count + 1
mapping：用于確定頁(yè)框是映射頁(yè)還是匿名頁(yè)如果mapping
? ? ? ? ? ? ? ? ?字段為空，則該頁(yè)屬于交換頁(yè)如果mapping
? ? ? ? ? ? ? ? ?字段非空，且最低位為1，則為匿名頁(yè)，同時(shí)mapping字段中存放的是指向anon_vma描述符的指針
? ? ? ? ? ? ? ? ? 如果mapping字段非空，且最低位為0，則為映射頁(yè)，同時(shí)mapping字段中存放的是指向?qū)?yīng)文件的address_space對(duì)象。
PageAnon函數(shù)接受頁(yè)描述符地址作為參數(shù)，如果mapping字段最低位置位（最低位為1）,則返回1，否則返回0。
匿名頁(yè)的反向映射
線性區(qū)：進(jìn)程使用的線性地址區(qū)間
將引用同一頁(yè)框的所有匿名頁(yè)鏈接起來(lái)的策略非常簡(jiǎn)單，即將該頁(yè)框所在的匿名線性區(qū)放在一個(gè)雙向循環(huán)鏈表中。注意：即使一個(gè)匿名線性區(qū)存有不同的頁(yè)，頁(yè)始終只有一個(gè)反向映射鏈表用于該區(qū)域中的所有頁(yè)框。
當(dāng)為一個(gè)匿名區(qū)分配第一頁(yè)時(shí)，內(nèi)核創(chuàng)建一個(gè)新的anon_vma數(shù)據(jù)結(jié)構(gòu)，它只包含兩個(gè)字段：lock和head。lock字段時(shí)競(jìng)爭(zhēng)條件下保護(hù)鏈表的自旋鎖，head字段時(shí)指向線性區(qū)描述符雙向循環(huán)鏈表的頭部。然后，內(nèi)核將匿名線性區(qū)的vm_area_struct描述符插入到雙向循環(huán)鏈表中。vm_area_struct包含兩個(gè)字段：anon_vma_node和anon_vma。其中anon_vma_node字段存放指向鏈表中前一個(gè)和后一個(gè)元素的指針，而anon_vma字段指向anon_vma數(shù)據(jù)結(jié)構(gòu)。最后，把指向anon_vma數(shù)據(jù)結(jié)構(gòu)的指針指向頁(yè)框描述符的mapping字段。如下圖：
映射區(qū)頁(yè)的反向映射與匿名頁(yè)相反，映射頁(yè)經(jīng)常時(shí)共享的，這是因?yàn)椴煌倪M(jìn)程經(jīng)常會(huì)共享同一程序代碼。Linux 2.6依靠叫做“優(yōu)先搜索樹(shù)（priority search tree）”的結(jié)構(gòu)來(lái)快速定位引用同一頁(yè)框的所有線性區(qū)。如下圖：
PFRA實(shí)現(xiàn)
頁(yè)框回收算法必須處理多種屬于用戶態(tài)進(jìn)程 磁盤(pán)高速緩存和頁(yè)高速緩存的頁(yè)
頁(yè)框回收算法執(zhí)行的三個(gè)路口：
1.內(nèi)存緊缺回收：內(nèi)核發(fā)現(xiàn)內(nèi)存緊缺
2.睡眠回收：在進(jìn)入suspend-to-disk狀態(tài)時(shí)，內(nèi)核必須釋放內(nèi)存
3.周期回收：必要時(shí)，周期性激活內(nèi)核線程執(zhí)行內(nèi)存回收算法
最近最少使用（LRU）鏈表
屬于進(jìn)程用戶態(tài)的地址空間或者頁(yè)高速緩存中的所有頁(yè)被分成兩組：活動(dòng)鏈表和非活動(dòng)鏈表。它們統(tǒng)稱(chēng)為L(zhǎng)RU鏈表。前面一個(gè)鏈表用于存放最近被訪問(wèn)過(guò)的頁(yè)；后面的則是存放由一段時(shí)間沒(méi)有被訪問(wèn)過(guò)的頁(yè)。顯然，頁(yè)必須從非活動(dòng)鏈表中取。
這兩個(gè)雙向鏈表的頭分別存放在每個(gè)zone描述符的active_list和inactive_list字段，而nr_active和nr_inactive字段表示存放在兩個(gè)鏈表中的頁(yè)數(shù)。最后，lru_lock字段是一個(gè)自旋鎖，保護(hù)兩個(gè)鏈表免受SMP系統(tǒng)上的并發(fā)訪問(wèn)。
如果屬于LRU鏈表，則設(shè)置頁(yè)描述符中的PG_lru標(biāo)志。此外，如果頁(yè)表屬于活動(dòng)鏈表，則設(shè)置PG_active標(biāo)志，如果屬于非活動(dòng)鏈表，則清PG_active標(biāo)志。頁(yè)描述符的lru字段存放指向lru鏈表中下一個(gè)元素和前一個(gè)元素。
在LRU鏈表之間移動(dòng)頁(yè)
在頁(yè)描述符中的PG_referenced標(biāo)志用來(lái)把一個(gè)頁(yè)從非活動(dòng)鏈表移動(dòng)到活動(dòng)鏈表所需的訪問(wèn)次數(shù)加倍。例如，假如在非活動(dòng)鏈表中一個(gè)頁(yè)其PG_referenced標(biāo)志置為0。第一次訪問(wèn)把這個(gè)標(biāo)志置為1，但是這一頁(yè)仍然留在非活動(dòng)鏈表中。第二次堆該頁(yè)訪問(wèn)時(shí)發(fā)現(xiàn)這一標(biāo)志被設(shè)置。因此，把頁(yè)移動(dòng)到活動(dòng)鏈表。但是，如果第一次訪問(wèn)之后在給定的時(shí)間間隔內(nèi)第二次訪問(wèn)沒(méi)有發(fā)生，那么頁(yè)框回收算法就可能重置PG_referencd標(biāo)志。
PFRA使用mark_page_accessed() ?page_referenced() refill_inactive_zone()函數(shù)在LRU鏈表之間移動(dòng)頁(yè)。
mark_page_accessed()函數(shù)
當(dāng)內(nèi)核必須把一個(gè)頁(yè)標(biāo)記為訪問(wèn)過(guò)時(shí)，就調(diào)用mark_page_accessed()函數(shù)。
page_referenced()函數(shù)
PFRA掃描一頁(yè)調(diào)用一次page_referenced()函數(shù)，如果PG_referenced標(biāo)志或頁(yè)表項(xiàng)中的某些Accessed標(biāo)志位置位，則函數(shù)返回1；否則返回0。該函數(shù)首先檢查頁(yè)描述符的PG_referencd標(biāo)志。如果標(biāo)志置為則清0.然后使用面向?qū)ο蟮姆聪蛴成浞椒?，?duì)引用該頁(yè)的所有用戶態(tài)頁(yè)表項(xiàng)中的Accessed標(biāo)志位進(jìn)行檢查并清0.
refill_inactive_zone()函數(shù)
refill_inactive_zone()函數(shù)由shrink_zone()函數(shù)調(diào)用，而shrink_zone()函數(shù)對(duì)頁(yè)高速緩存和用戶態(tài)地址空間地址進(jìn)行頁(yè)回收。此函數(shù)有兩個(gè)參數(shù)：zone 和 sc。
zone：指針zone指向一個(gè)內(nèi)存管理區(qū)的描述符
sc：指針sc指向一個(gè)scan_control結(jié)構(gòu)
scan_control結(jié)構(gòu)字段如下圖：
? ? ?PFRA傾向于壓縮頁(yè)高速緩存，而將用戶態(tài)進(jìn)程的頁(yè)留在RAM中。該函數(shù)按下列公式計(jì)算交換傾向值：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 交換傾向值=映射比率/2 + 負(fù)荷值 + 交換值
映射比率：用戶態(tài)地址空間引用的頁(yè)數(shù)占所有可分配頁(yè)框的百分比
負(fù)荷值：依據(jù)是前一次PFRA運(yùn)行時(shí)管理區(qū)的掃描優(yōu)先級(jí)，這個(gè)優(yōu)先級(jí)存放在管理區(qū)描述符的prev_priority字段。
負(fù)荷值與管理區(qū)前一次優(yōu)先級(jí)的對(duì)應(yīng)關(guān)系： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 管理區(qū)前一次優(yōu)先級(jí) ? ? ? ? ?12...7 ? ? ? ? 6 ? ? ? ? 5 ? ? ? ?4 ? ? ? ?3 ? ? ? ? 2 ? ? ? ? 1 ? ? ? 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?負(fù)荷值 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?0 ? ? ? ? ? ?1 ? ? ? ? 3 ? ? ? ?6 ? ? ? ?12 ? ? ? ?25 ? ? ? 50 ? ? 100
交換值：是一個(gè)自定義的常數(shù)，通常為60。系統(tǒng)管理員可以在/proc/sys/vm/swappiness文件內(nèi)修改這個(gè)值，或用相應(yīng)的sysctl()函數(shù)調(diào)用調(diào)整這個(gè)值。
2015.10.25:23:03
內(nèi)存緊缺回收
當(dāng)內(nèi)存分配失敗時(shí)激活內(nèi)存精確回收。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 在分配VFS緩沖區(qū)或者緩沖區(qū)首部時(shí)，內(nèi)核調(diào)用free_more_memory() ?函數(shù) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 而當(dāng)從伙伴系統(tǒng)分配一個(gè)或多個(gè)頁(yè)框時(shí)，調(diào)用try_to_free_pages()函數(shù)?
free_more_memory()函數(shù)
free_more_memory()函數(shù)執(zhí)行如下操作：
1.調(diào)用wakeup_bdflush()喚醒一個(gè)pdflush內(nèi)核線程，并觸發(fā)頁(yè)高速緩存中1024個(gè)臟頁(yè)的寫(xiě)操作。寫(xiě)臟頁(yè)到磁盤(pán)的操作將最終使包含緩沖區(qū) 緩沖區(qū)首部和其他VFS數(shù)據(jù)結(jié)構(gòu)的頁(yè)框稱(chēng)為可釋放的。
2.調(diào)用sched_yield()系統(tǒng)調(diào)用的服務(wù)例程，為pdflush內(nèi)核線程提供指向機(jī)會(huì)。
3.對(duì)系統(tǒng)的所有內(nèi)存節(jié)點(diǎn)，啟動(dòng)一個(gè)循環(huán)。對(duì)每一個(gè)節(jié)點(diǎn)，調(diào)用try_to_free_pages()函數(shù)，傳給它的參數(shù)時(shí)一個(gè)“緊缺”內(nèi)存管理區(qū)鏈表（在80x86結(jié)構(gòu)中是ZONE_DMA和ZONE_NORMAL）
try_to_free_pages()函數(shù)
try_to_free_pages()函數(shù)接受如下三個(gè)參數(shù)：
zones：要回收的頁(yè)所在的內(nèi)存管理區(qū)鏈表
gfp_mask：用于失敗的內(nèi)存分配的一組分配標(biāo)志
order：沒(méi)有使用
該函數(shù)的目標(biāo)就是通過(guò)重復(fù)調(diào)用shrink_caches()和shrink_slab()函數(shù)時(shí)方至少32個(gè)頁(yè)框，每次調(diào)用后優(yōu)先級(jí)會(huì)比前一次提高。有關(guān)的輔助函數(shù)可以獲得scan_control類(lèi)型描述符中的優(yōu)先級(jí)，以及正在進(jìn)行的掃描操作的其他參數(shù)。最低的 也是初始的優(yōu)先級(jí)是12，而最高的 也是最終的優(yōu)先級(jí)是0。如果try_to_free_pages()每能在某次（共13次）調(diào)用shrink_caches()和shrink_slab()函數(shù)時(shí)成功回收32個(gè)頁(yè)框，PFRA就要黔驢技窮了。最后一招：刪除一個(gè)進(jìn)程，釋放它的所有頁(yè)框。這一操作由out_of_memory()函數(shù)執(zhí)行。
shrink_caches()函數(shù)
shrink_caches()函數(shù)由try_to_free_pages()函數(shù)調(diào)用，它有兩個(gè)參數(shù)：內(nèi)存管理區(qū)鏈表zones和scan_control描述符地址sc。
該函數(shù)的目的值時(shí)對(duì)zones鏈表中的每個(gè)管理區(qū)調(diào)用shrink_zone函數(shù)。但對(duì)給定管理區(qū)調(diào)用shrink_zone()之前，shrink_caches()函數(shù)用sc->priority字段的值更新管理區(qū)描述符的temp_priority字段，這就是掃描操作的當(dāng)前優(yōu)先級(jí)。而且如果PFAR的上一次調(diào)用優(yōu)先級(jí)高于當(dāng)前優(yōu)先級(jí)，即這個(gè)管理區(qū)進(jìn)行頁(yè)框回收變得很難了，那么shrink_caches()函數(shù)把當(dāng)前優(yōu)先級(jí)拷貝到管理區(qū)描述符的pre_priority。最后，如果管理區(qū)描述符中的all_unreclaimable標(biāo)志置位，且當(dāng)前優(yōu)先級(jí)小于12，則shrink_caches()不掉用shrink_zone()，也就是說(shuō)，在try_to_free_pages()的第一次迭代中不調(diào)用shrink_caches()。當(dāng)PFRA確定一個(gè)管理區(qū)都是不可回收頁(yè)，掃描該管理區(qū)的頁(yè)純粹時(shí)浪費(fèi)時(shí)間，則將all_unreclaimable標(biāo)志置位。
shrink_zone()函數(shù)
shrink_zone()函數(shù)有兩個(gè)參數(shù)：zone和sc。zone是指向struct_zone描述符的指針；sc是指向scan_control描述符的指針。該函數(shù)的目標(biāo)是從管理區(qū)非活動(dòng)鏈表回收32頁(yè)。它每次在更大的一段管理區(qū)非活動(dòng)鏈表上重復(fù)調(diào)用輔助函數(shù)shrink_cache()，以期達(dá)到目標(biāo)。而且shrink_zone()重復(fù)調(diào)用refill_inactive_zone()函數(shù)來(lái)補(bǔ)充管理區(qū)非活動(dòng)鏈表。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
管理區(qū)描述符的nr_scan_active和nr_scan_inactive字段在這里起到很重要的作用。為了提高效率，函數(shù)每批處理32頁(yè)。因此如果函數(shù)在低優(yōu)先級(jí)運(yùn)行（對(duì)應(yīng)sc->priority的高值），且某個(gè)lru鏈表中沒(méi)有足夠的頁(yè)，函數(shù)就跳過(guò)對(duì)這個(gè)鏈表的掃描。但因此跳過(guò)的活動(dòng)或不活動(dòng)頁(yè)數(shù)就分別存放在nr_scan_active和nr_scan_inactive字段中，這樣函數(shù)下次執(zhí)行時(shí)再處理這些跳過(guò)的頁(yè)。 ? ? ? ? ? ? ? ? ? ? ??
shrink_cache()函數(shù)
shrink_cache()函數(shù)又是一個(gè)輔助函數(shù)，它的主要目的就是從管理區(qū)非活動(dòng)鏈表取出一組頁(yè)把它們放入一個(gè)臨時(shí)鏈表，然后調(diào)用shrink_list()函數(shù)對(duì)這個(gè)鏈表中的每一個(gè)頁(yè)進(jìn)行有效的頁(yè)框回收操作。shrink_cache()函數(shù)的參數(shù)與shrink_zones()一樣，都是zone和s c。
