1 、前言
自從誕生以來，Linux 就被不斷完善和普及，目前它已經(jīng)成為主流通用操作系統(tǒng)之一，使用得非常廣泛，它與 Windows、UNIX 一起占據(jù)了操作系統(tǒng)領(lǐng)域幾乎所有的市場份額。特別是在高性能計(jì)算領(lǐng)域，Linux 已經(jīng)成為一個(gè)占主導(dǎo)地位的操作系統(tǒng)，在2005年6月全球TOP500 計(jì)算機(jī)中，有 301 臺部署的是 Linux 操作系統(tǒng)。因此，研究和使用 Linux 已經(jīng)成為開發(fā)者的不可回避的問題了。
下面我們介紹一下 Linux 內(nèi)核中文件 Cache 管理的機(jī)制。本文以 2.6 系列內(nèi)核為基準(zhǔn)，主要講述工作原理、數(shù)據(jù)結(jié)構(gòu)和算法，不涉及具體代碼。
2 操作系統(tǒng)和文件 Cache 管理
操作系統(tǒng)是計(jì)算機(jī)上最重要的系統(tǒng)軟件，它負(fù)責(zé)管理各種物理資源，并向應(yīng)用程序提供各種抽象接口以便其使用這些物理資源。從應(yīng)用程序的角度看，操作系統(tǒng)提供了一個(gè)統(tǒng)一的虛擬機(jī)，在該虛擬機(jī)中沒有各種機(jī)器的具體細(xì)節(jié)，只有進(jìn)程、文件、地址空間以及進(jìn)程間通信等邏輯概念。這種抽象虛擬機(jī)使得應(yīng)用程序的開發(fā)變得相對容易：開發(fā)者只需與虛擬機(jī)中的各種邏輯對象交互，而不需要了解各種機(jī)器的具體細(xì)節(jié)。此外，這些抽象的邏輯對象使得操作系統(tǒng)能夠很容易隔離并保護(hù)各個(gè)應(yīng)用程序。
對于存儲設(shè)備上的數(shù)據(jù)，操作系統(tǒng)向應(yīng)用程序提供的邏輯概念就是"文件"。應(yīng)用程序要存儲或訪問數(shù)據(jù)時(shí)，只需讀或者寫"文件"的一維地址空間即可，而這個(gè)地址空間與存儲設(shè)備上存儲塊之間的對應(yīng)關(guān)系則由操作系統(tǒng)維護(hù)。
在 Linux 操作系統(tǒng)中，當(dāng)應(yīng)用程序需要讀取文件中的數(shù)據(jù)時(shí)，操作系統(tǒng)先分配一些內(nèi)存，將數(shù)據(jù)從存儲設(shè)備讀入到這些內(nèi)存中，然后再將數(shù)據(jù)分發(fā)給應(yīng)用程序；當(dāng)需要往文件中寫數(shù)據(jù)時(shí)，操作系統(tǒng)先分配內(nèi)存接收用戶數(shù)據(jù)，然后再將數(shù)據(jù)從內(nèi)存寫到磁盤上。文件 Cache 管理指的就是對這些由操作系統(tǒng)分配，并用來存儲文件數(shù)據(jù)的內(nèi)存的管理。 Cache 管理的優(yōu)劣通過兩個(gè)指標(biāo)衡量：一是 Cache 命中率，Cache 命中時(shí)數(shù)據(jù)可以直接從內(nèi)存中獲取，不再需要訪問低速外設(shè)，因而可以顯著提高性能；二是有效 Cache 的比率，有效 Cache 是指真正會(huì)被訪問到的 Cache 項(xiàng)，如果有效 Cache 的比率偏低，則相當(dāng)部分磁盤帶寬會(huì)被浪費(fèi)到讀取無用 Cache 上，而且無用 Cache 會(huì)間接導(dǎo)致系統(tǒng)內(nèi)存緊張，最后可能會(huì)嚴(yán)重影響性能。
下面分別介紹文件 Cache 管理在 Linux 操作系統(tǒng)中的地位和作用、Linux 中文件 Cache相關(guān)的數(shù)據(jù)結(jié)構(gòu)、Linux 中文件 Cache 的預(yù)讀和替換、Linux 中文件 Cache 相關(guān) API 及其實(shí)現(xiàn)。
2、 文件 Cache 的地位和作用
文件 Cache 是文件數(shù)據(jù)在內(nèi)存中的副本，因此文件 Cache 管理與內(nèi)存管理系統(tǒng)和文件系統(tǒng)都相關(guān)：一方面文件 Cache 作為物理內(nèi)存的一部分，需要參與物理內(nèi)存的分配回收過程，另一方面文件 Cache 中的數(shù)據(jù)來源于存儲設(shè)備上的文件，需要通過文件系統(tǒng)與存儲設(shè)備進(jìn)行讀寫交互。從操作系統(tǒng)的角度考慮，文件 Cache 可以看做是內(nèi)存管理系統(tǒng)與文件系統(tǒng)之間的聯(lián)系紐帶。因此，文件 Cache 管理是操作系統(tǒng)的一個(gè)重要組成部分，它的性能直接影響著文件系統(tǒng)和內(nèi)存管理系統(tǒng)的性能。
圖1描述了 Linux 操作系統(tǒng)中文件 Cache 管理與內(nèi)存管理以及文件系統(tǒng)的關(guān)系示意圖。從圖中可以看到，在 Linux 中，具體文件系統(tǒng)，如 ext2/ext3、jfs、ntfs 等，負(fù)責(zé)在文件 Cache和存儲設(shè)備之間交換數(shù)據(jù)，位于具體文件系統(tǒng)之上的虛擬文件系統(tǒng)VFS負(fù)責(zé)在應(yīng)用程序和文件 Cache 之間通過 read/write 等接口交換數(shù)據(jù)，而內(nèi)存管理系統(tǒng)負(fù)責(zé)文件 Cache 的分配和回收，同時(shí)虛擬內(nèi)存管理系統(tǒng)(VMM)則允許應(yīng)用程序和文件 Cache 之間通過 memory map的方式交換數(shù)據(jù)。可見，在 Linux 系統(tǒng)中，文件 Cache 是內(nèi)存管理系統(tǒng)、文件系統(tǒng)以及應(yīng)用程序之間的一個(gè)聯(lián)系樞紐。
、文件 Cache 相關(guān)數(shù)據(jù)結(jié)構(gòu)
在 Linux 的實(shí)現(xiàn)中，文件 Cache 分為兩個(gè)層面，一是 Page Cache，另一個(gè) Buffer Cache，每一個(gè) Page Cache 包含若干 Buffer Cache。內(nèi)存管理系統(tǒng)和 VFS 只與 Page Cache 交互，內(nèi)存管理系統(tǒng)負(fù)責(zé)維護(hù)每項(xiàng) Page Cache 的分配和回收，同時(shí)在使用 memory map 方式訪問時(shí)負(fù)責(zé)建立映射；VFS 負(fù)責(zé) Page Cache 與用戶空間的數(shù)據(jù)交換。而具體文件系統(tǒng)則一般只與 Buffer Cache 交互，它們負(fù)責(zé)在外圍存儲設(shè)備和 Buffer Cache 之間交換數(shù)據(jù)。Page Cache、Buffer Cache、文件以及磁盤之間的關(guān)系如圖 2 所示，Page 結(jié)構(gòu)和 buffer_head 數(shù)據(jù)結(jié)構(gòu)的關(guān)系如圖 3 所示。在上述兩個(gè)圖中，假定了 Page 的大小是 4K，磁盤塊的大小是 1K。本文所講述的，主要是指對 Page Cache 的管理。
在 Linux 內(nèi)核中，文件的每個(gè)數(shù)據(jù)塊最多只能對應(yīng)一個(gè) Page Cache 項(xiàng)，它通過兩個(gè)數(shù)據(jù)結(jié)構(gòu)來管理這些 Cache 項(xiàng)，一個(gè)是 radix tree，另一個(gè)是雙向鏈表。Radix tree 是一種搜索樹，Linux 內(nèi)核利用這個(gè)數(shù)據(jù)結(jié)構(gòu)來通過文件內(nèi)偏移快速定位 Cache 項(xiàng)，圖 4 是 radix tree的一個(gè)示意圖，該 radix tree 的分叉為4(22)，樹高為4，用來快速定位8位文件內(nèi)偏移。Linux(2.6.7) 內(nèi)核中的分叉為 64(26)，樹高為 6(64位系統(tǒng))或者 11(32位系統(tǒng))，用來快速定位 32 位或者 64 位偏移，radix tree 中的每一個(gè)葉子節(jié)點(diǎn)指向文件內(nèi)相應(yīng)偏移所對應(yīng)的Cache項(xiàng)。
另一個(gè)數(shù)據(jù)結(jié)構(gòu)是雙向鏈表，Linux內(nèi)核為每一片物理內(nèi)存區(qū)域(zone)維護(hù)active_list和 inactive_list兩個(gè)雙向鏈表，這兩個(gè)list主要用來實(shí)現(xiàn)物理內(nèi)存的回收。這兩個(gè)鏈表上除了文件Cache之外，還包括其它匿名 (Anonymous)內(nèi)存，如進(jìn)程堆棧等。
4 、文件Cache的預(yù)讀和替換
Linux內(nèi)核中文件預(yù)讀算法的具體過程是這樣的：對于每個(gè)文件的第一個(gè)讀請求，系統(tǒng)讀入所請求的頁面并讀入緊隨其后的少數(shù)幾個(gè)頁面(不少于一個(gè)頁面，通常是三個(gè)頁面)，這時(shí)的預(yù)讀稱為同步預(yù)讀。對于第二次讀請求，如果所讀頁面不在Cache中，即不在前次預(yù)讀的group中，則表明文件訪問不是順序訪問，系統(tǒng)繼續(xù)采用同步預(yù)讀；如果所讀頁面在Cache中，則表明前次預(yù)讀命中，操作系統(tǒng)把預(yù)讀group擴(kuò)大一倍，并讓底層文件系統(tǒng)讀入 group中剩下尚不在Cache中的文件數(shù)據(jù)塊，這時(shí)的預(yù)讀稱為異步預(yù)讀。無論第二次讀請求是否命中，系統(tǒng)都要更新當(dāng)前預(yù)讀group的大小。此外，系統(tǒng)中定義了一個(gè)window，它包括前一次預(yù)讀的group和本次預(yù)讀的group。任何接下來的讀請求都會(huì)處于兩種情況之一：第一種情況是所請求的頁面處于預(yù)讀window中，這時(shí)繼續(xù)進(jìn)行異步預(yù)讀并更新相應(yīng)的window和group；第二種情況是所請求的頁面處于預(yù)讀window之外，這時(shí)系統(tǒng)就要進(jìn)行同步預(yù)讀并重置相應(yīng)的window和group。圖5是Linux內(nèi)核預(yù)讀機(jī)制的一個(gè)示意圖，其中a是某次讀操作之前的情況，b是讀操作所請求頁面不在window中的情況，而c是讀操作所請求頁面在window中的情況。
Linux內(nèi)核中文件Cache替換的具體過程是這樣的：剛剛分配的Cache項(xiàng)鏈入到inactive_list頭部，并將其狀態(tài)設(shè)置為active，當(dāng)內(nèi)存不夠需要回收Cache時(shí)，系統(tǒng)首先從尾部開始反向掃描active_list并將狀態(tài)不是referenced的項(xiàng)鏈入到 inactive_list的頭部，然后系統(tǒng)反向掃描inactive_list，如果所掃描的項(xiàng)的處于合適的狀態(tài)就回收該項(xiàng)，直到回收了足夠數(shù)目的 Cache項(xiàng)。Cache替換算法如圖6的算法描述偽碼所示。
Mark_Accessed(b) {
if b.state==(UNACTIVE && UNREFERENCE)
b.state = REFERENCE
else if b.state == (UNACTIVE && REFERENCE)
{
b.state = (ACTIVE && UNREFERENCE)
Add X to tail of active_list
}
else if b.state == (ACTIVE && UNREFERENCE)
b.state = (ACTIVE && REFERENCE)
}
Reclaim()
{
if active_list not empty and scan_num
圖6 Linux的Cache替換算法描述
5 、文件Cache相關(guān)API及其實(shí)現(xiàn)
Linux內(nèi)核中與文件Cache操作相關(guān)的API有很多，按其使用方式可以分成兩類：一類是以拷貝方式操作的相關(guān)接口，如read/write/sendfile等，其中sendfile在2.6系列的內(nèi)核中已經(jīng)不再支持；另一類是以地址映射方式操作的相關(guān)接口，如 mmap等。
第一種類型的API在不同文件的Cache之間或者Cache與應(yīng)用程序所提供的用戶空間buffer之間拷貝數(shù)據(jù)，其實(shí)現(xiàn)原理如圖7所示。
第二種類型的API將Cache項(xiàng)映射到用戶空間，使得應(yīng)用程序可以像使用內(nèi)存指針一樣訪問文件，Memory map訪問Cache的方式在內(nèi)核中是采用請求頁面機(jī)制實(shí)現(xiàn)的，其工作過程如圖8所示。
首先，應(yīng)用程序調(diào)用mmap（圖中1），陷入到內(nèi)核中后調(diào)用do_mmap_pgoff（圖中2）。該函數(shù)從應(yīng)用程序的地址空間中分配一段區(qū)域作為映射的內(nèi)存地址，并使用一個(gè)VMA（vm_area_struct）結(jié)構(gòu)代表該區(qū)域，之后就返回到應(yīng)用程序（圖中3）。當(dāng)應(yīng)用程序訪問mmap所返回的地址指針時(shí)（圖中4），由于虛實(shí)映射尚未建立，會(huì)觸發(fā)缺頁中斷（圖中5）。之后系統(tǒng)會(huì)調(diào)用缺頁中斷處理函數(shù)（圖中6），在缺頁中斷處理函數(shù)中，內(nèi)核通過相應(yīng)區(qū)域的VMA結(jié)構(gòu)判斷出該區(qū)域?qū)儆谖募成洌谑钦{(diào)用具體文件系統(tǒng)的接口讀入相應(yīng)的Page Cache項(xiàng)（圖中7、8、9），并填寫相應(yīng)的虛實(shí)映射表。經(jīng)過這些步驟之后，應(yīng)用程序就可以正常訪問相應(yīng)的內(nèi)存區(qū)域了。
6 、小結(jié)
文件Cache管理是Linux操作系統(tǒng)的一個(gè)重要組成部分，同時(shí)也是研究領(lǐng)域一個(gè)很熱門的研究方向。目前，Linux內(nèi)核在這個(gè)方面的工作集中在開發(fā)更有效的Cache替換算法上，如LIRS(其變種ClockPro)、ARC等。