一種基於文件系統緩存的自適應預讀取方法

2023-11-03 21:52:12

專利名稱：一種基於文件系統緩存的自適應預讀取方法
技術領域：
本發明涉及一種對磁碟進行讀寫搮作的方法，尤其是一種在讀寫過程 中，基於文件系統緩存的預讀取方法。
背景技術：
無論是讀操作還是寫操作，磁碟驅動器存取通常比內存存取慢得多。 對於一般的設備操作，當用戶需要進行讀寫操作時，直接對磁碟進行數據 讀寫，這種磁碟操作方式非常慢，因此容易阻塞應用程式，同時由於沒有 優化磁頭，需要頻繁的移動磁頭，效率也很低。文件系統緩存層就是為了解決這個問題而設計的。它的基本思想是在上層用戶的磁碟操作與實際 的設備操作之間添加了 一個數據緩衝區，利用這個緩衝區來實現磁碟操作 性能的優化。文件系統緩存層的主要功能有三個保存最近使用的數據塊， 減少讀取塊設備的次數；優化寫操作，減少磁頭移動次數；提供預讀取功能。由於上層文件系統組織文件時儘量把同 一個文件安排在連續的空間 中，因此應用程式從塊設備中讀取當前扇區時，鄰接扇區的內容也有很大 可能下次被使用到。使用預讀取功能，可以在獲取當前扇區的數據時，把 鄰接的指定個數的扇區數據也獲取並存放在緩存區中，以免下次需要使用 這些數據時再把硬碟磁頭移動到指定位置進行獲取，以減少磁頭移動次 數。這個功能在緩存足夠大的情況下，對於多任務訪問不同的連續文件時 性能有很大提高。但是，如果預讀取算法使用不當，則會對性能有一定負面影響。因為 被預讀取的數據並不一定^皮使用到，此時預讀取的這些無用數據反而會增 加上層應用等待從磁碟獲取數據的時間。並且緩存區的大小並不是無限大 的，在緩存滿的情況下，需要淘汰緩存中的其它數據來存放預取的數據，因此可能發生預取的址圾數據替換了緩存中的有用數據的情況。在嵌入式文件系統中，預取操作實現得比較簡單，通常是按照預先分 配的緩存區大小來確定預讀取區的大小，每次進行預取搡作時從磁碟中讀 取的扇區數在初始化時就已經確定好了 。這種預取操作沒有複雜的算法設 計，在讀取連續文件時效率很高，但是當文件比較零散時，有可能預讀取 到過多的垃圾數據。發明內容本發明的目的在於提供一種基於文件系統緩存的自適應預讀取管理 用以減少預讀取的垃圾扇區數。本發明的技術方案包括一種基於文件系統緩存的自適應預讀取方法，包括以下步驟(1) 建立預讀取扇區使用記錄；(2) 每次執行預讀取操作時，在所述預讀取扇區使用記錄中，記錄 預讀取的扇區數；(3) 使用預讀取的扇區時，在所述預讀取扇區使用記錄中，記錄使 用的預讀取扇區數；(4) 根據以前的預讀取扇區數和預讀取扇區的使用數，計算出以前 預讀取扇區的使用率，並才艮據該使用率來確定當前預讀取操作中預讀取的 扇區數。進一步，上述步驟(l)中，建立N個預讀取扇區使用記錄，分別記 錄最接近當前預讀取操作的以前N次預讀取操作的預讀取扇區的使用情 況。進一步，所述每個記錄至少包括預讀取扇區數和預讀取扇區使用數兩 個欄位，並且所述步驟(2)中，在預讀取扇區數欄位中，記錄某次預讀 取操作預讀取的扇區數量；所述步驟(3)中，在預讀取扇區使用數欄位 中，記錄對該次預讀取扇區的使用數量。進一步，所述步驟(2)包括預先設定預讀取扇區數的最大值，首 次執行預讀取操:作時預讀取的扇區數不大於該最大值。進一步，所述步驟(2)還包括將每次預讀取的扇區存放在一個緩 存塊中，並在緩存塊控制結構中，給每個存放預讀取扇區的緩存塊賦予一 個索引值，記錄該緩存塊存放的扇區是通過哪次預讀取操作預讀取的；所 述步驟(3)包括在使用存放預讀取扇區的緩存塊時，根據所述索引值 確定所使用的扇區是通過哪次預讀取操作預讀取的，並在記錄該次預讀取 操作預讀取的扇區數的記錄中，記錄使用的預讀取扇區數。進一步，上述方法包括所述步驟(4)中，計算出每個記錄中預讀 取扇區使用數和預讀取扇區數的比值，作為一次預讀取操作預讀取的扇區 的使用率；計算出N次預讀取操作預讀取的扇區的平均使用率，再乘以 所述預先設定的預讀取扇區數的最大值，得出當前預讀取操作的預讀取扇 區數。上述方法中，所述步驟(1)進一步可包括每個記錄還有一個權值 欄位，並為每個記錄分配一個權值，權值的分配原則是離當前預讀取操作 越近的記錄的權值越大，並且使所有權值的和為100%。進一步，所述步驟(4)中，計算出每個記錄中預讀取扇區使用數和 預讀取扇區數的比值，並乘以該記錄對應的權值，得出每次預讀取操作預 讀取的扇區的加權使用率；將N次預讀取的扇區的加權使用率相加，並 乘以預先設定的預讀取扇區數的最大值，得出當前預讀取操作的預讀取扇 區數。本發明所提供的方法，由於在每次預讀取時都會通過前面多次預讀取 數據的使用比率來確定本次預讀取數據的大小，因此相比現有技術使用一 個固定預取值的算法，減少了垃圾扇區數的讀取。而且本發明記錄的歷史 信息內敘艮少，計算邏輯簡單，比較適合嵌入式系統中文件系統緩存的管 理。附困說明圖l是預讀取扇區使用記錄的數據結構示意圖; 圖2是文件系統緩存塊控制結構示意圖； 圖3是採用本發明方法的讀寫搡作流程圖； 圖4是一種離散文件的分布示意圖。
具體實施方式
以下結合附圖及較佳實施例，對本發明的實施方式進行較為詳細的說明。本發明的方法能對基於文件系統緩存的預讀取數據大小進行自適應 調整，其包括以下基本處理步驟建立預讀取扇區使用記錄；每次執行預讀取操作時，在所述預讀取數據使用記錄中，記錄預讀取 的扇區數；使用預讀取的扇區時，在所述預讀取數據使用記錄中，記錄使用的預 讀取扇區數；根據以前的預讀取扇區數和預讀取扇區的使用數，計算出以前預讀取 扇區的使用率，並根據該使用率來確定當前預讀取操作中預讀取的扇區數。本發明的預讀取扇區使用記錄的數據結構至少包括預讀取扇區數和 預讀取扇區使用數兩個欄位。圖l是預讀取扇區使用記錄的數據結構示意圖，其中有預讀取的扇區欄位。圖l所示的實施例中，數據結構還包括有權值(adcPreReadPower)欄位。adcPreReadBlocks表示每次執行預讀取操作時預讀取的扇區數， adcPreReadUsedBlocks表示adcPreReadBlocks個扇區中被使用的扇區數， adcPreReadUsedBlocks與adcPreReadBlocks的比值就是預讀取扇區的使用率。本發明為了使預讀取的扇區數儘可能接近實際使用的扇區數量，可記 錄並統計多次以前的預讀取操作的預讀取扇區的使用率。

圖1所示的實施例中，設定預讀取扇區使用記錄的個數共有N個，分別記錄最接近當前 預讀取操作的以前N次預讀取操作的預讀取扇區的使用情況。上層用戶創建塊設備時，對塊設備的控制結構進行初始化，同時對預 讀取扇區使用記錄的數據結構進行初始化。當有N個記錄時，首先對N 個記錄的數據結構進行初始化。預讀取扇區4吏用記錄初始化時，將adcPreReadBlocks和 adcPrcReadUsedBlocks的值都i殳置為1,即歷史的預讀取扇區使用率為 100%。可以為每個記錄分配一個權值來表示其在總的使用率中佔的比重， 權值的分配原則是離當前預取操作越近的記錄的權值越大，並且N個權 值的和應為100%。如圖l所示，權值共有N個，從權值l、權值2到權 值N按遞減的順序排列，指針l總是指向權值l，表示最近一次預讀取操 作預讀取的扇區的使用率的權值。根據文件系統緩存區的大小，設定一個 預讀取的最大值MAX—READ AHEAD,首次預讀取扇區的數量不大於 MAX_READAHEAD。圖1中，指針2總是指向最近一次預讀取扇區使用記錄所在的位置。 指針2的值在0到N-1之間循環遞增，達到N-1後，重新從O開始。 從磁碟中預讀取塊後，把預讀取的扇區數填入指針2當前值加1的位置上 的記錄的adcPreReadBlocks欄位中，並把該記錄的adcPreReadUsedBlocks 欄位設置為O,然後指針2的當前值加1，使指針2繼續指向最近一次預 讀取數據使用記錄所在的位置。在文件系統緩存的控制結構中有一個總的索引值globallndex，該值初 始化時為0，每次執行預讀取操作後該值就遞增1。圖2是文件系統緩存塊控制結構示意圖，每個緩存塊控制結構中都有 一個索引值index,及一個預讀取屬性欄位bPreRead。當把該緩存塊用來 存儲預讀取的扇區時，把globallndex賦給該緩存塊控制結構的index,標 記該緩存塊是在哪次預讀取操作時獲取的，並且把該緩存塊控制結構中的預讀取屬性欄位.bPreRead i殳為TRUE,表示該緩存塊是通過預讀取獲取 的。圖3是本發明的讀寫操作流程圖。對於讀緩存塊搡作，首先判斷所讀 的緩存塊的控制結構的bPreRead欄位是否為TRUE,如果不為TRUE,表 示該緩存塊不是通過預讀取方式獲取的，不用把該緩存塊使用信息記錄到 預讀取扇區使用記錄中；如果bPreRead欄位為TRUE,還要繼續判斷 globallndex與緩存塊控制結構中的index差值是否小於等於N,如杲大於 N，則這個緩存塊的使用信息不在統計的範圍之內；如果小於等於N，則 把index模上N,就可以得到該緩存塊使用信息記錄的位置。把該位置上 的adcPreReadUse犯locks欄位加1，並把該緩存塊控制結構的bPreRead 欄位設為FALSE,表示該緩存塊的使用信息已記錄到預讀取扇區使用記 錄中，下次使用時不再記錄。對於寫緩存塊操作，首先判斷是否按扇區方式來寫。如果是按字節方 式寫，則該緩存塊的使用信息與上述的讀操作一樣記錄在預讀取扇區使用 記錄中；如果是按扇區邊界對齊寫，則該預讀取的緩存塊是屬於預讀取的 垃圾數據，把該緩存塊控制結構中的bPreRead欄位設為FALSE。在發起預讀取搮作時，要計算本次預讀取扇區的數量。 首先要計算以前預讀取扇區的使用率，將該使用率乘以預先設定的預讀取扇區數的最大值MAX—READ AHEAD,即得出本次預讀取扇區的數量。當有N個記錄時，可以計算出N個記錄的預讀取扇區的平均使用率 將該平均使用率乘以預先設定的預讀取扇區數的最大值，即得出本次預讀 取扇區的數量。為了使預讀取的扇區數儘可能接近實際使用的扇區數，還可以計算出 N個記錄的加權使用率adcUseRate，計算公式如下所示adcUseRate=adcPreReadUsedBlocks(i)/adcPreReadBlocks(i)* adcPreReadPower(j)其中i是從圖1所示的指針2作為起始值，每次遞減該值，當遞減到O後再從N - 1開始遞減；j是從指針1作為起始值，每次遞增該值，當遞 增到N - 1後再從0開始遞增。按上迷公式計算N次，可得到N個使用率，N個使用率的和便是預 讀取數據的加權使用率。把加權使用率乘上預先設定的預讀取扇區數的最 大值MAX—READ AHEAD,就得到本次預讀取的扇區數。圖4所示為硬碟一段連續的空間，其中白色部分是某文件佔用的空 間，上面的數字是文件的邏輯扇區號，灰色部分不屬於該文件空間。圖4 中的文件屬於佔用空間不連續的文件。採用現有技術的固定值預讀取方 法，如果把預讀取大小固定設為16，則每次預讀取時都會讀取12個扇區 的垃圾數據；採用本發明的方法，如果把MAX一READAHEAD設為16， 使用上述的自適應算法，則會慢慢收斂到合適的預讀取大小，減少了垃圾 數據的讀取。可見，採用本發明的自適應預讀取方法，在文件內容分布離散的情況 下，可以顯著減少垃圾數據的讀取。而且由於計算方法簡單，即使在文件 內容連續的情況下，相比使用固定預讀取大小的方法，性能也不會下降。應當說明的是，上述具體實施例僅僅是為闡述本發明的方法而列舉的 較佳實施方式，不應理解為對本發明的專利保護範圍的限制，本發明的專 利保護範圍應以所附權利要求為準。
權利要求
1. 一種基於文件系統緩存的自適應預讀取方法，包括以下步驟(1)建立預讀取扇區使用記錄；(2)每次執行預讀取操作時，在所述預讀取扇區使用記錄中，記錄預讀取的扇區數；(3)使用預讀取的扇區時，在所述預讀取扇區使用記錄中，記錄使用的預讀取扇區數；(4)根據以前的預讀取扇區數和預讀取扇區的使用數，計算出以前預讀取扇區的使用率，並根據該使用率來確定當前預讀取操作中預讀取的扇區數。
2. 如權利要求l所述的方法，其特徵在於所述步驟(l)中，建立 N個預讀取扇區使用記錄，分別記錄最接近當前預讀取操作的以前N次 預讀取操作的預讀取扇區的使用情況。
3. 如權利要求2所述的方法，其特徵在於所述每個記錄至少包括 預讀取扇區數和預讀取扇區使用數兩個欄位。
4. 如權利要求3所述的方法，其特徵在於所述步驟(2)中，在預 讀取扇區數欄位中，記錄某次預讀取操作預讀取的扇區數量；所述步驟(3 ) 中，在預讀取扇區使用數欄位中，記錄對該次預讀取扇區的使用數量。
5. 如權利要求4所述的方法，其特徵在於所述步驟(2)進一步包 括，預先設定預讀取扇區數的最大值，首次執行預讀取操作時預讀取的扇 區數不大於該最大值。
6. 如權利要求4所述的方法，其特徵在於所述步驟(2)進一步包 括，將每次預讀取的扇區存放在一個緩存塊中，並在緩存塊控制結構中， 給每個存放預讀取扇區的緩存塊賦予一個索引值，記錄該緩存塊存放的扇 區是通過哪次預讀取操作預讀取的。
7. 如權利要求6所述的方法，其特徵在於所述步驟(3)中，在使 用某個緩存塊中存放的預讀取扇區時，根據該緩存塊的索引值確定所使用的扇區是通過哪次預讀取操作預讀取的，並在記錄該次預讀取操作預讀取 的扇區數的記錄中，記錄使用的預讀取扇區數。
8. 如權利要求7所述的方法，其特徵在於所述步驟(4)中，計算 出每個記錄中預讀取扇區使用數和預讀取扇區數的比值，作為 一次預讀取 操作預讀取的扇區的使用率；計算出N次預讀取操作預讀取的扇區的平 均使用率，再乘以所述預先設定的預讀取扇區數的最大值，得出當前預讀 取操作的預讀取扇區數。
9. 如權利要求7所述的方法，其特徵在於所述步驟(1)進一步包 括，每個記錄還包括一個權值欄位，並為每個記錄分配一個權值，權值的 分配原則是離當前預讀取操作越近的記錄的權值越大，並且使所有權值的 和為100%。
10. 如權利要求9所述的方法，其特徵在於所述步驟(4)中，計 算出每個記錄中預讀取扇區使用數和預讀取扇區數的比值，並乘以該記錄 對應的權值，得出每次預讀取操作預讀取的扇區的加權使用率；將N次 預讀取的扇區的加權使用率相加，並乘以預先設定的預讀取扇區數的最大 值，得出當前預讀取操作的預讀取扇區數。
全文摘要
一種基於文件系統緩存的自適應預讀取方法，包括以下步驟(1)建立預讀取扇區使用記錄；(2)每次執行預讀取操作時，在所述預讀取扇區使用記錄中，記錄預讀取的扇區數；(3)使用預讀取的扇區時，在所述預讀取扇區使用記錄中，記錄使用的預讀取扇區數；(4)根據以前的預讀取扇區數和預讀取扇區的使用數，計算出以前預讀取扇區的使用率，並根據該使用率來確定當前預讀取操作中預讀取的扇區數。
文檔編號G06F17/30GK101231637SQ200710002448
公開日2008年7月30日 申請日期2007年1月22日 優先權日2007年1月22日
發明者周立超, 童小九, 陸小飛, 黃文偉 申請人:中興通訊股份有限公司