本文将針對UNIX磁盤緩沖的原理及配置設定回收展開讨論，并在最後用OO觀點來對緩沖進行模組化。
概述
在UNIX家族的核心中，都有一個buffer cache，用于緩沖磁盤與檔案系統之間的資料交換。這是個子產品不僅包含記憶體管理功能，還提供了一套算法來管理該記憶體中緩沖的資料，如延遲寫等等。
為了減少記憶體碎片，提高通路效率，減少系統調用的次數，在大多數複雜/龐大的軟體系統中都會用到記憶體池或者對象緩沖等來管理記憶體。然而，記憶體是一片雷區，在管理記憶體時，需要特别小心，如果造成洩漏，就會導緻系統記憶體耗盡。在應用程式中，這不算大問題，因為它總要退出運作。退出後，其未釋放的資源會被系統自動回收。在核心中情況就不一樣了，洩露了一塊記憶體，就少掉了一塊，通常隻有通過reboot來回收了。
對于核心而言，還有一個重要的問題就是同步問題。這是任何一個核心開發者都需要時刻注意的問題：搶占、中斷等都是導緻需要同步的一個重要原因。同步還帶來了核心函數/系統調用的重入問題，是以在開發核心時需要時刻小心。因為UNIX System V是非搶占式核心，也就是核心執行期間不會被其他程序搶占，除非程序自動讓出處理器，是以不需要特别考慮同步，但是中斷是必須考慮的。
說到中斷和搶占，有幾個概念需要了解：程序上下文、中斷上下文；使用者态、核心态。一個程序執行中，可以在核心态或使用者态執行，但處于程序上下文；中斷是一個特例：不屬于任何程序，處于中斷上下文，運作在核心态。……有點扯遠了……咳…… 羅嗦了這麼半天，下面言歸正傳。
原理及實作
UNIX System V的磁盤緩沖稱為buffer cache，該緩沖位于檔案系統和磁盤驅動層中間，用于緩沖系統對磁盤的通路，并降低對磁盤操作的頻度。系統初始化時配置設定了一些緩沖形成緩沖池，每個緩沖元素包括兩部分：資料和緩沖描述。有些時候将資料及其描述合稱為緩沖。一塊緩沖可以由邏輯裝置号以及其映射的磁盤塊的塊号來辨別。
磁盤塊與緩沖池中的元素是一一對應關系，否則将導緻資料不一緻。當需要讀一個磁盤塊時，核心首先從該緩沖池中查找，如果找到，則直接讀取緩沖，如果未找到，則配置設定一個緩沖，并從磁盤中讀取資料。這就需要一個最近最少使用算法來決定配置設定哪個緩沖。當需要寫一塊磁盤時，首先寫到緩沖池中以便後續通路能夠高效地進行。當找不到可用的緩沖時，先将某個緩沖寫到磁盤（延遲寫），然後再寫到該緩沖。
為了管理該緩沖池，利用了兩種資料結構：哈希隊列（hash Q）和雙向連結清單（double-linked list）。這兩個資料結構中存放的元素是稱為buffer header的結構體，該結構體如圖所示：
其中，狀态包括：
1、buffer的閑/忙（鎖住/解鎖）；
2、資料有效；
3、延遲寫；
4、正在讀/寫；
5、有程序在等待該buffer的釋放。
對于hash Q和free list的使用也比較簡單：hash Q存放已經配置設定的buffer，而free list上存的都是空閑的buffer。如果某空閑buffer是回收利用的，那麼，其不但鍊在free list上，還鍊在了hash Q上（注：初始化後buffer都存放在free list上，并沒有鍊到hash Q上）。
那麼，這些buffer将如何進行配置設定和回收呢？原理很簡單，就是一些hash Q和double-linked list的操作。隻不過這些操作涉及到一些配置設定邏輯（算法）。下面是典型的兩種狀态：
在配置設定buffer時，有5種典型的情況：
1、在hash Q上找到需要的buffer（代表一個磁盤塊），且該buffer可用；
2、在hash Q上找到需要的buffer，但該buffer正忙；
3、沒有在hash Q上找到需要的buffer，從free list配置設定；
4、沒有在hash Q上找到需要的buffer，從free list配置設定，但該buffer狀态為delay-write；
5、沒有在hash Q上找到需要的buffer，free list也為空；
這樣我們就得到getblk實作的僞代碼：
struct buffer header * getblk(檔案系統号，塊号)
{
while ( 沒有找到buffer )
if (該block在hash Q上)
if (buffer正忙) /* 第2種情況 */
sleep_on(buffer釋放的事件); /* 參考UNIX的加鎖解鎖：等待事件及喚醒 */
}
else
将buffer标記為正忙; /* 第1種情況 */
從free list中删除該buffer;
傳回該buffer的指針;
if (free list上沒有可用buffer) /* 第5種情況 */
sleep_on(buffer釋放的事件);
continue;
從free list删除該buffer;
if (該buffer狀态是delay-write) /* 第4種情況 */
異步将該緩沖寫到磁盤;
/* 第3種情況 */
從舊的hash Q上删除該buffer;
将該buffer放到新的hash Q;
第一種情況相當簡單，不做說明。第三種情況，将從free list隊首取出一個buffer（最近最少使用算法），并将其放到對應的hash Q上。第四種情況，kernel發現該buffer标志為delay-write，是以，将執行異步寫。而請求該buffer的程序将從free list上下一個元素開始繼續查找。第五種情況， 程序将在該buffer池的等待隊列上等待任何一個buffer可用。
第二種情況最為複雜，因為這裡涉及到多個程序競争同一個buffer的問題，出現這種情況時，會有多個程序在該buffer的等待隊列上等待該buffer（注意與第5種情況的等待的差別）。當程序A得到一個buffer之後進入睡眠。這時，程序B也請求該buffer，發現該buffer忙，是以在對該buffer标記為“in-demand（有需要）”，然後将自己放到該buffer的等待隊列上睡眠。同樣可能有程序C進行該操作了。這樣，當喚醒該隊列上的程序時，B和C都被喚醒，當C先執行時，鎖定了該buffer，因為其他原因進入睡眠，輪到B執行，這是B應當檢查該buffer是否被鎖住，同時還要檢查該buffer是否被C程序配置設定給了其他的塊。如果是後者，B應該再次查找hash
Q甚至free list。
在這裡，由核心保證所有睡眠的程序都能夠被喚醒，是以不存在永久的睡眠。理論上會有程序“餓死”，永遠睡眠（如第四種情況，很多程序在睡眠，然而某個程序卻始終沒有得到buffer），但由于buffer很多，基本上不會有程序“餓死”。
另外需要留意的是中斷問題。因為對于buffer list和hash Q的操作都是對全局資料的操作，需要禁用中斷來防止重入——delay-write導緻異步寫，寫完後會在中斷中處理buffer的釋放。由于這裡的算法比較簡單，僅僅列出了最主要的沖突（呵呵，拽一下），是以，一般來說實作都會比較困難。如Linux 2.6.22和0.99.15代碼較長，且完成的功能比這裡列出的複雜一些。下面是Linux 0.99.15的實作（注：由于Linux 0.99.15的實作與上面的僞代碼最相近，是以采用它作為示例。另：省略掉某些不影響說明的代碼）：
#define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)
struct buffer_head * getblk(dev_t dev, int block, int size)
struct buffer_head * bh, * tmp;
int buffers;
static int grow_size = 0;
repeat:
bh = get_hash_table(dev, block, size); //在hash Q上查找，找不到則得到NULL，如果找到的buffer忙，則sleep
if (bh) {
if (bh->b_uptodate && !bh->b_dirt) // 第1、2種情況
put_last_free(bh);
return bh;
//在hash Q上沒找到。第3、4、5種情況
……
for (tmp = free_list; buffers-- > 0 ; tmp = tmp->b_next_free) {
if (!bh || BADNESS(tmp)<BADNESS(bh)) {
bh = tmp;
if (!BADNESS(tmp))
break;
if (!bh) {
if (!grow_buffers(GFP_ATOMIC, size))
sleep_on(&buffer_wait);
goto repeat;
wait_on_buffer(bh);
if (bh->b_count || bh->b_size != size)
goto repeat; // 不符合要求，重試查找，先在hash Q上找，然後是free list
if (bh->b_dirt) { // 延遲寫，第4種情況
sync_buffers(0,0);
goto repeat; // 重試查找，先在hash Q上找，然後是free list
// 第3種情況：重置該buffer的屬性，并作适當的操作。
remove_from_queues(bh); // 從舊的hash Q上删除該buffer， 并從free list中将其删除
bh->b_dev=dev;
bh->b_blocknr=block;
insert_into_queues(bh); //将該buffer放到新的hash Q
使用完buffer之後，必然要歸還該buffer：
void brelse(struct buffer header * 要釋放的buffer)
喚醒所有在等待任意buffer的程序;
喚醒所有在等待該buffer的程序;
禁用中斷;
if (buffer内容有效且buffer是新的)
将該buffer放到free list尾部;
将該buffer放到free list隊首;
将該buffer設定為空閑;
開啟中斷;
不多闡述了，下面是Linux 0.99.15的實作：
void brelse(struct buffer_head * buf)
if (!buf)
return;
wait_on_buffer(buf); //等待所有共享該buffer的程序釋放
if (buf->b_count) {
if (--buf->b_count)
wake_up(&buffer_wait); //喚醒所有等待的程序
printk("VFS: brelse: Trying to free free buffer\n");
用OO方法模組化
從OO觀點來看buffer的模型——使用hash Q和free list來管理該buffer池——buffer header更像是使用了繼承，繼承了hash Q和free list的操作，因為buffer header中，指向hash Q元素和free list元素的指針并不是buffer header的屬性，是以完全可以将他們分離出來：
因為采用繼承的方式，我們對于資料結構的使用就固定為hash Q和free list，不利于修改為其他的資料結構。這樣的話也向核心其他部分暴露了緩沖池的内部實作。而使用模闆的方式，不但便于修改，而且還可以利用其他的資料結構來實作緩沖模型。對于使用buffer cache的子產品來說，隻要保留有該資料結構的引用或指針即可。
從圖中可以很容易得到繼承方式的C++代碼，此處大緻列出模闆的C++代碼：
template <class T>
class DLinkedList
public:
T * Append(const T * newNode);
T * Insert(const T * newNode);
T * Allocate();
private:
T * elem;
T * pre;
T * next;
};
template <class TElem, class TKey>
class HashQ
boolean Enqueue(const TElem * newNode, const TKey * aKey);
TElem * Search(const TKey * aKey);
DLinkedList<TElem> * header[4];
可以封裝一個buffer cache類：
class BufferCache // Singleton
BufferHeader * GetBlock();
BufferHeader * ReleaseBlock();
static BufferCache * GetBufferCache(BufferHeader * pBuf);
BufferCache();
static BufferHeader * pool;
static HashQ<BufferHeader, int> * pHashQ;
static DLinkedList<BufferHeader> * pFreeList;
static Lock * aLock;
statci Interrupt * aIntr;
BufferCache也可以定義為一個模闆類。
可以執行如下語句來初始化（非構造函數）：
BufferHeader * pool = new BufferHeader[n];
HashQ<BufferHeader> * pHashQ = new HashQ<BufferHeader, int>;
DLinkedList<BufferHeader> * pFreeList = new DLinkedList<BufferHeader>;
for (int i = 0; i < n; ++i )
pFreeList->Append(pool +i); // 初始化時所有元素全部在free list上
使用BufferCache來配置設定/回收buffer：
BufferCache * pBufCache = BufferCache.GetBufferCache();
BufferHeader * pBuf = pBufCache.GetBlock();
pBufCache.ReleaseBlock(pBuf);
類似的記憶體/緩沖管理對于應用程式的開發也具有指導意義，是以，研究buffer cache，并在開發應用程式時使用類似的技術，将會得到更加靈活、穩定、健壯的程式。
個人膚淺的了解，且未研究更多的細節，如有偏差，請高手指正！
題外話：對于hash Q和Free List，可以在内部封裝iterator用于周遊，當然，可以作為private方法（這兩個類的可複用程度将降低），也可以作為public的方法來提高這兩個類的可複用程度）
參考：
The Design of The UNIX Operation System, by Maurice J. Bach
Linux Kernel Source Code v0.99.15, by Linus Torvalds
Linux Kernel Source Code v2.6.22, by Linux Torvalds and Linux community.
The C++ Programming Language, 3rd, by Bjarne Stroustup
Design Patterns, by GOF
Copyleft (C) raof01.
本文可以用于除商業外的所有用途。此處“用途”包括（但不限于）拷貝/翻譯（部分或全部），不包括根據本文描述來産生代碼及思想。若用于非商業，請保留此權利聲明，并标明文章原始位址和作者資訊；若要用于商業，請與作者聯系（[email protected]），否則作者将使用法律來保證權利。