目錄

• 1. 概述
• 2. 緩衝區的設計
  • 2.1 緩衝區頭部
  • 2.2 緩衝區的結構
  • 2.3 緩衝區的檢索演算法
    • 2.3. 申請一個緩衝區演算法 getblk
    • 2.3.2 釋放一個緩衝區演算法 brelse
    • 2.3.3 讀一個磁碟塊 bread
    • 2.3.4 讀一個磁碟並預讀另一個磁碟塊 breada
    • 2.3.5 寫餐盤塊 bwrite
• 3. 總結
• Reference

1. 概述

操作系統對文件系統的一切存取操作，內核都能通過每次直接從磁碟上讀或往磁碟上寫來實現。磁碟和 RAM 的速度之間差別很大。由於兩者速度的不匹配性，在操作系統實際運行的過程中可能會出現以下問題：

1. 磁碟機械運動速度大大低於處理的運行速度；
2. 多線程併發運行，少量的磁碟（通道），I/O 操作將會成為瓶頸所在；
3. 數據訪問的隨機性，磁碟忙閑不均。

為瞭解決上面的問題，Unix 設計者在設計內核時，通過保持一個稱為數據緩衝區高速緩衝（ buffer cache）（簡稱高速緩衝）的內部數據緩衝區池來試圖減小對磁碟的存取頻率。具體的解決辦法如下：

1. 建立一個成為數據緩衝的高速緩衝的內部數據緩衝區池（buffer pool）來存放使用的數據；

2. 寫數據時

   把數據儘量長時間的保存在緩衝池中，延遲寫出到磁碟上，以備後續使用。

   也就是說在寫數據時，並不是真正的把數據直接寫在磁碟上，而是先寫到緩衝池中，供後續進程使用，儘量少的減少與磁碟交互的頻率。

3. 讀數據時

   現在緩衝池中查找已有的數據，如果沒有，再從磁碟中讀取，並保存的緩衝池中，使用的時候再從緩衝池取。

從寫數據和讀數據的操作過程中我們可以看出，通過緩衝區的引入，使得進程更多的與緩衝區來進行交換數據，儘量少的減少磁碟的讀寫頻率，提高讀寫速度。

2. 緩衝區的設計

緩衝區池由若幹緩衝區組成，每一個緩衝區由兩部分組成：一個含有磁碟上的數據的存儲器數組及一個用來標識該緩衝區的緩衝頭部（buffer header）。其示意圖如下所示：

但是，由於數據緩衝區的首部和存儲區之間有一一對應的關係，所以通常把兩者統稱為緩衝區。

註意：緩衝區是緩衝區池中數據存儲的基本單位。

2.1 緩衝區頭部

緩衝區的頭部定義如下：

struct buf{
    緩衝區標註			//標識緩衝區的的狀態即是否被使用
    緩衝區連接指針		  //向前向後串成鏈表
    空閑緩衝區鏈表指針	//用來鏈接空閑緩衝區
    設備號              //用來標識緩衝區
    塊號
    union{				//緩衝區中的數據類型
        數據塊
        超級快
        柱面塊
        i節點塊
    }b_un
    其他控制信息
}

為了便於理解我們用一個圖來表示其結構。

2.2 緩衝區的結構

在詳細說明緩衝區的結構之前我們有必要瞭解一下緩衝區在設計的過程中所遵循的原則：

1. 存放有剛使用過的數據儘量長時間地保留在記憶體中，以便馬上還要使用時能在記憶體中找到；
2. 需要騰出記憶體空間時，把很久都未使用過（即最近最少使用）的數據交換到磁碟上去。這些數據馬上還要使用的可能性最小。

緩衝區在實現的過程中，其核心維護了一個空閑緩衝區鏈表，它按照最近被使用的先後次序排列。空閑鏈表是一個以空閑緩衝區鏈表頭開始的“雙向迴圈鏈表”。鏈表的開始和結束都以鏈表頭為標誌。其具體結構如下圖所示：

緩衝區操作的具體過程如下：

1. 取用任意空閑緩衝區

   從空閑緩衝區鏈表的表頭位置取下一個空閑緩衝區，後面的空閑緩衝區依次向前移動。以上圖為例，取空閑緩衝區時，會取走空閑緩衝區 1，然後空閑緩衝區 2-n，會一次向前移動。

   

1. 釋放一個空閑緩衝區

   把這個裝有數據的空閑緩衝區附加到空閑鏈表的鏈尾，只有當該空閑緩衝區所裝數據出錯時才掛到鏈頭的後邊。

   

2. 取用裝有指定內容的空閑緩衝區

   從鏈表頭開始查找，找到後取下使用，用完後放到鏈尾。

當系統不斷從鏈頭取用空閑緩衝區，又把使用過的（裝有數據的）緩衝區掛到鏈尾，一個裝有有效數據的緩衝區就會逐漸向鏈表頭移動。在鏈表頭位置的就是“最近最少使用”的空閑緩衝區。

另一方面，為了提高緩衝區的使用效率，避免在取用緩衝區的時候逐個判斷緩衝區中的內容，緩衝區在設計的時候按照不同的用途將空閑緩衝區分為四類：

• 0#空閑緩衝區鏈表：存放系統文件超級快
• 1#空閑緩衝區鏈表：存放通常使用的數據塊
• 2#空閑緩衝區鏈表：存放延遲寫、無效數據或者錯誤內容
• 3#空閑緩衝區鏈表：存放沒有對應存儲空間的緩衝區首部

空閑緩衝區按照不同的用途進行分類，這樣有一個最大的好處，程式在使用不同數據的時候只需要按照數據的類型到制定的某個空閑緩衝區鏈表中查找而不需要查找所有的空閑緩衝區鏈表。

另外可能某些讀者會有疑問，我們設計 3#緩衝區鏈表有什麼用？按理來說緩衝區和外存的空間應該是一一對應的怎麼會出現沒有對應存儲空間的緩衝區這應的情況發生哪？

為了回答這個問題，我們首先要知道，unix 在設計之初，系統的穩定性就是其重要的指標，我們設定這樣一個場景，某台伺服器在運行過程中與某個緩衝區對應的磁碟壞掉了。在這種情況下，為了保證系統的穩定性，我們不可能重啟伺服器，重新實現緩衝區和磁碟空間的映射。因此我們設計出 3#空閑緩衝區鏈表，這樣，上邊沒有存儲空間的緩衝區都會被掛載到該空閑緩衝區鏈表中。當系統運維人員，更換完存儲空間後，系統再將該緩衝區從 3#空閑緩衝區中調出，從而保證系統運行的穩定性。

當核心需有一個空閑緩衝區時，它根據要裝入的數據類型，從相應的空閑緩衝區鏈表的表頭位置取下一個空閑緩衝區，裝入個磁碟數據塊；

根據該數據塊所對應的設備號和塊號數據對計算其 hashed（散列、雜湊）值，根據其 hashno 的值放入到相應 hash 鏈表的鏈頭。

其中 hashed 計算規則如下：

\[hashno =( (diskno + blkno) / RND) \% BUFHSZ \]

• disko：設備號
• blkno：塊號
• BUFHSZ：最大 hash 值，通常為 63。
• RND：隨機數，其值為：RND= MAXBSIZE/ DEV BSIZE MAXBSIZE：最大文件系統塊的大小 DEV
• BSIZE：物理設備塊大小

經過前邊知識的鋪墊下邊我們就可以詳細瞭解下緩衝池的具體結構：

從圖中我們可以看到，一個緩衝區只有當它是空閑狀態時，它才同時處在 hash 鏈表和空閑鏈表中。如果不空閑，則它只能處在某一個 hash 鏈表中在空閑緩衝區鏈表中的緩衝區一定在某個 hash 鏈表中；在 hash 鏈表中的緩衝區不一定在空閑鏈中。不存在脫離 hash 鏈表的另一個空閑的緩衝區鏈表。
緩衝池中的緩衝區個數是固定不變的，每個緩衝區在不同時刻存放著不同的磁碟數據塊，具有不同的 hash 值，因此處在不同的 hash 鏈表中緩衝區中的數據與某個磁碟數據塊一一對應，這種對應有兩個特點：
①一個磁碟數據塊在緩衝池中最多只能有一個副本；
②緩衝區與數據塊的對應是動態的，LRU 數據塊將被釋放。

緩衝區的使用過程如下：

如果要找特定緩衝區，根據 has hno 從相應的 hash 鏈表的表頭處開始逐個向後查找；如果找到，則直接取用，並將其移動到 hash 鏈的鏈頭；如果未找到，則從相應的空閑緩衝區鏈表的表頭處取下一個空閑緩衝區，填入相應數據，重新計算其 hashed，並放到新的 hash 鏈表的表頭；

釋放緩衝區時，將該緩衝區仍保留在原 hash 隊列中，同時掛接到空閑緩衝區鏈表的表尾。（同時在兩個隊列中）

2.3 緩衝區的檢索演算法

在 UNX 文件系統中的下層，即直接與邏輯存儲設備聯繫的部分，包含如下基本演算法：

• gebk：申請一個緩衝區
• brelse：釋放一個緩衝區
• bread：讀一個磁碟塊
• bread：讀一個磁碟塊，預讀另一個磁碟塊
• bwrite：寫磁碟塊

2.3. 申請一個緩衝區演算法 getblk

根據緩衝池的結構，核心申請一個緩衝區分配個磁碟塊時，可能出現的五種典型狀況：
①該塊已在 hash 隊列中，並且緩衝區是空閑的；
②hash 隊列中找不到該塊，需從空閑鏈表中分配一個緩衝區；
③hash 隊列中找不到該塊，在從空閑鏈表中分配一個緩衝區時，發現該空閑緩衝區標記有“延遲寫”，核心必須寫出緩衝區內容到磁碟上，再重新分配一個空閑緩衝區
④hash 隊列中找不到該塊，並且空閑鏈表已空；
⑤該塊已在 hash 隊列中，但該緩衝區目前狀態為“忙”。

具體演算法的思路如下：

演算法 getblk
輸入:文件系統號
塊號
輸出:現在能被磁碟塊使用的上了鎖的緩衝區
{
    while(沒有找到緩衝區) 
    {
        if(塊在散列隊列中) 
        {
            if(空閑鏈表中無緩衝區)	//第五種情況
            {
            	sleep(等候“緩衝區變為空閑”事件);
           		continue;
            }
			為緩衝區標記上"忙";      //第一種情況

            從空閑鏈表上摘下緩衝區;
            return(緩衝區);
        }
      else	//塊不在散列隊列中
      {
          if(空閑鏈表中無緩衝區)	//第四種情況
          {
              sleep(等待“任何緩衝區為空閑”事件);
              continue;	//回到while迴圈
          }
          //第二種情況找到一個空閑緩衝區
          把舊散列隊列中摘下緩衝區;
          把緩衝區投入到新的散列隊列中去;
          return(緩衝區);
      }
    } 
}

2.3.2 釋放一個緩衝區演算法 brelse

演算法 brelse
輸入:上鎖狀態的緩衝區
輸出:無
{
    喚醒正在等待"無論哪個緩衝區變為空閑"這一事件的所有進程;
    喚醒正在等待"這個緩衝區變為空閑"這一事件的所有進程;
    提高處理機執行級別以封鎖中斷;
    if(緩衝區內容有效且緩衝區非"舊")
    	將緩衝區送入空閑鏈表尾部;
    else
    	將緩衝區送入空閑鏈表頭部;
    降低處理機執行級別以允許中斷;
    給緩衝區解鎖;
}

2.3.3 讀一個磁碟塊 bread

整個過程如下：

1. 由 getblk 演算法申請一個可用的緩衝區
2. 如果緩衝區中的內容有效，則直接返回該緩衝區
3. 如果緩衝區中的內容無效，則啟動磁碟去讀所需的數據塊
4. 等待磁碟操作完成後返回

演算法 bread
輸入:文件系統號
輸出:含有數據的緩衝區
{
    得到該塊的緩衝區(演算法 getblk);
    if(緩衝區數據有效)
   	 return(緩衝區);
    啟動磁碟讀;
    slep(等待"讀盤完成"事件);
    return(緩衝區)
}

2.3.4 讀一個磁碟並預讀另一個磁碟塊 breada

預讀的前提：
程式是在一個有限的空間內運行，程式對數據的訪問是可預見的。
預讀的命中率：
不一定達到 100%,但良好的系統結構和演算法可使命中率達到較高的水平
預讀的結果：
放在緩衝池內，以免需要的時候再去啟動磁碟讀數據塊。

演算法 bread
輸入:(1)立即讀的文件系統塊號
	 (2)非同步讀的文件系統塊號
輸出:含有立即讀的數據的緩衝區
{
   if(第一塊不在高速緩衝中) 
   {
       為第一塊獲得緩衝區(getblk);
       if(緩衝區內容無效)
           啟動磁碟度;
   }
    if(第二塊不在高速緩衝中)
    {
        為第二塊獲得緩衝區(getblk);
        if(緩衝區數據有效)
            釋放緩衝區(brelse);
        else
            啟動磁碟讀;
    }
    if(如果第一塊在高速緩衝中)
    {
        讀第一塊(bread);
        return 緩衝區;
    }
    sleep(第一個緩衝區包含有效數據的事件);
    return 緩衝區
}

2.3.5 寫餐盤塊 bwrite

寫操作分為兩種，一種是同步寫，另一種是非同步寫，這兩種操作的根本區別在於本進程在進行寫操作時，是否等待磁碟驅動程式完成操作後所發出的中斷信號。如果等則是同步寫，否則為非同步寫。

演算法 bwrite
輸入:緩衝區
輸出:無
{
    啟動磁碟寫;
    if(IO同步)
    {
        sleep(等待"O完成"事件);
    	釋放緩衝區( brelse);
    }  
    else if(緩衝區標記著延遲寫)
    {
       為緩衝區做標記以放到空閑緩衝區鏈表頭部; 
    }
}

3. 總結

unix 操作系統引入高速緩衝之後帶來了極大的便利，但同時也有一些不足之處。下邊我們分別總結下告訴緩衝的優點以及其缺點。

優點：

1. 提供了對磁碟塊的統一的存取方法
2. 消除了用戶對用戶緩衝區中數據的特殊對齊需要
3. 減少了磁碟訪問的次數，提高了系統的整體 MO 效率
4. 有助於保持文件系統的完整性

缺點：

1. 數據未及時寫盤而帶來的風險
2. 額外的數據拷貝過程，大量數據傳輸時影響性能

Reference

[1] unix 操作系統的設計