基于負載特性和服務時間評估改進的AS調度算法

陳金忠，姚念民，蔡紹濱，孫美玲

(哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150000)

1 引言

隨著CPU與內存速度的不斷提高，存儲系統(tǒng)成為計算機性能的瓶頸。I/O調度層已經成為存儲系統(tǒng)不可或缺的一部分[1,2]。I/O調度算法大致分為3大類。

第1類是實時任務I/O調度算法，這類算法主要是在保證任務實時性的條件下，最大化任務的吞吐量。SCAN-EDF[3]將相同截止時間的請求劃分到同一組，然后在每一組內應用SCAN算法進行掃描。SCAN-EDF只對相同截止時間的任務按磁頭移動方向調度，其性能取決于具有相同截止時間任務的數目。為了對更多任務進行優(yōu)化，DM-SCAN(deadline-modification-SCAN)[4]將任務的截止時間修改為最短任務的截止時間dmin，將任務的完成時間不超過截止時間dmin的所有任務劃分到同一組，然后在組內應用SCAN算法調度提高任務的吞吐量。RG-SCAN[5](reschedulable-group-SCAN)引用了RG-group的概念。它首先尋找包含最多任務數的集合，集合中所有任務的完成時間不超過任務的截止時間，此集合稱為RG-group，然后對RG-group應用SCAN算法來提高任務的吞吐量。RG-SCAN不需要修改任務的截止時間。SCAN-EDF、DM-SCAN和RG-SCAN都是在組內進行任務調度，屬于局部調度算法。GSR(global seek-optimizing real-time)[6]根據磁頭移動方向將任務分組，然后在保證實時性的前提下，在組與組之間調度任務，以達到吞吐量的最大化。GSR是全局調度算法。

第2類是預定帶寬或時延的I/O調度算法，這類算法用于滿足用戶的預定帶寬或者預定時延，如DVT(differential virtual time)[7]、Hybrid[8]、Argon[9]、pClock[10]、adaptive DRR(deficit round-robin)[11]、MBAC(measurement-based admission control)[12]和BFQ(budget fair queuing)[13]等算法。這些算法在滿足預定帶寬或時延的條件下，提高任務的吞吐量。

第3類調度算法是為了提高吞吐量而設計的算法，主要有SCAN、LOOK、SSTF(shortest seek time first)、NOOP(no operation)、Deadline、AS(anticipatory scheduling)和 CFQ(completed fairness queuing)等調度算法[14～17]。這些算法旨在減少磁頭移動的距離。NOOP、CFQ、Deadline和AS是當前Linux I/O調度層常用的調度算法。NOOP實現了最簡單的FIFO隊列，所有的請求除了合并之外，采用先來先服務的策略。CFQ為每個進程分配一個隊列，按照I/O請求的扇區(qū)地址進行排序，每個進程的I/O請求以循環(huán)的方式服務。CFQ對于每個進程都是完全公平的。相對于NOOP來說，先到來的請求不一定先服務，CFQ可能出現I/O請求餓死的現象。Deadline在CFQ的基礎上，為每個I/O請求分配了截止時間，解決了餓死的問題。CFQ和Deadline考慮的焦點在于滿足零散I/O請求上，對于連續(xù)的I/O請求，比如順序讀，并沒有做優(yōu)化。并且這些調度算法都是持續(xù)性工作的[18]，一旦服務完I/O請求，立即調度當前隊列I/O請求。為了滿足隨機I/O和順序I/O混合的場景。預期調度算法(AS)在請求提交完之后并不立即處理當前隊列中的I/O請求，而是等待一段空閑時間，以等待下一個鄰近的請求被提交，等待周期為6 ms。這樣給應用程序提供了提交相鄰磁道位置的I/O請求的機會，從而減少磁頭尋道的距離。但AS存在兩點不足。第一，不同負載特性的I/O請求對AS的性能產生很大影響。對于I/O密集型的應用程序，2個I/O請求到達時間間隔可能很小(<6 ms)，使用6 ms的預期周期，顯然浪費了時間。對于I/O請求時間間隔較大的應用程序(>6 ms)，使用6 ms的預期周期，必然會增加預期失敗的次數。第二，AS只根據當前隊列中I/O請求的磁道位置而沒有根據I/O請求的服務時間來決定是否預期下一個請求，這就導致預期不準確。

針對AS算法存在以上2個方面的不足，提出了一種改進的基于負載特性和服務時間評估的AS調度算法(WPCAS)，主要分為進程歸類模塊(PC)和服務時間評估模塊(STE)。PC模塊通過分析負載的訪問特性，為不同類型的負載設置不同的預期周期。STE模塊根據I/O請求的服務時間決定是否預期下一個I/O請求。相比于AS，WPCAS不僅適應了負載的動態(tài)變化，而且使預期更加準確。因此，本文提出的WPCAS調度算法在吞吐量和偽空閑周期等方面的性能都優(yōu)于傳統(tǒng)的AS調度算法。

2 相關工作

Linux I/O子系統(tǒng)主要包括虛擬文件系統(tǒng)、頁面高速緩存、通用塊設備層和I/O調度層。Linux內核的調度算法集中于I/O調度層，主要有以下4種調度算法：NOOP、Deadline、CFQ 和AS。

2.1 I/O請求服務時間模型

其中，旋轉時延與磁盤轉速相關，傳輸時延等于I/O請求除以數據傳輸率。結合式(1)和式(2)，可計算I/O請求的服務時間。

2.2 AS預期策略

2.2.1 AS預期原理

AS執(zhí)行完成當前讀請求，并不立即執(zhí)行隊列的下一個請求，而是預留6 ms的時間窗口去等待下一個即將到來的請求。如果下一個到來的請求與當前已完成請求的磁道位置是鄰近的，那么將會極大提高I/O的性能。為了預期下一個請求，AS算法維護每類進程歷史I/O請求的平均到達時間間隔和磁道位置信息[20]。

AS預期原理：AS根據I/O請求的磁道位置判斷從當前隊列挑選的請求是不是“最優(yōu)”請求。如果挑選出I/O請求的磁道位置與當前磁頭位置的距離小于進程歷史相鄰I/O請求磁道位置之差的平均值，就認為此請求是“最優(yōu)”請求，從而立即服務該請求。否則，啟動定時器，預期下一個請求[20]。

2.2.2 AS預期機制狀態(tài)轉換

圖1顯示了AS的預期機制狀態(tài)轉換圖。當上一個I/O請求完成時，處于FINISHED狀態(tài)，I/O調度層根據上一節(jié)提到的預期原理判斷是否預期下一個請求。如果預期下一個I/O請求，那么啟動定時器，并將定時器的超時時間設置為6 ms，進入了WAITING狀態(tài)。否則，直接調度當前隊列中的I/O請求，進入SCHEDULING狀態(tài)。當定時器超時，表示預期失敗，那么從當前隊列選取I/O請求進行服務，進入SCHEDULING狀態(tài)。當預期成功時，服務預期到的I/O請求，也進入SCHEDULING狀態(tài)。此后，將I/O請求分發(fā)到通用塊設備層中進行調度，進入RUNNING狀態(tài)。當執(zhí)行完I/O請求時，又回到了FINISHED狀態(tài)。

圖1 預期機制狀態(tài)轉換

2.3 AS執(zhí)行流程

Linux I/O調度層的AS算法 具有以下幾個特征。

1)近似單向電梯算法,可以向后尋道的最大磁道距離為1 024×1 024個扇區(qū)。

2)為讀寫操作指定不同的超時時間，讀超時時間為125 ms，寫超時時間為250 ms。

3)讀寫操作采用批處理的策略。為讀batch與寫batch分配不同的超時時間，讀batch超時時間為500 ms，寫batch超時時間為125 ms。

4)預期周期：AS為I/O請求指定6 ms的預期周期，期望下一個請求鄰近于當前請求。

圖2描述了AS算法的執(zhí)行流程。AS維護FIFO隊列和SORT隊列。FIFO隊列是按照I/O請求到達時間進行排序的隊列，SORT隊列是按照I/O請求的磁道位置與當前磁頭位置的距離遠近進行排序的。首先，如果FIFO隊列中有超過截止時間的請求，就馬上服務這個請求，并從FIFO隊列和SORT隊列刪除該請求。否則，根據預期原理決定是否預期下一個I/O請求。然后,AS調度算法將當前隊列中的I/O請求或者是預期到的I/O請求分發(fā)到通用塊設備層的調度隊列中去。最后，由磁盤驅動器來完成數據的實際傳輸。

圖2 預期調度算法的處理流程

3 WPCAS調度策略

綜上所述，AS有2個特點。第一，預期周期為固定的6 ms。第二，根據當前隊列中I/O請求的磁道位置與當前磁頭位置的距離是否小于進程歷史相鄰I/O請求磁道位置之差的平均值，決定是否預期下一個I/O請求。AS有2點不足。首先，不同負載特性的I/O請求會對AS的性能產生很大影響。對于I/O密集型的應用程序，2個I/O請求的到達時間間隔可能很小(<6 ms)，使用6 ms的預期周期，顯然浪費了時間。對于I/O請求時間間隔較大的應用程序(>6 ms)，使用6 ms的預期周期，必然會增加預期失敗的次數。其次，根據I/O請求的磁道位置來判斷是否預期，不夠準確。為了更好地適應負載變化和更準確的預期I/O請求，提出了一種改進的基于負載特性和服務時間評估的AS調度算法(WPCAS)，它包括進程歸類模塊(PC)和服務時間評估模塊(STE)。PC模塊主要功能是根據I/O請求的負載特性，將進程歸類并設置為不同的預期周期。STE模塊的主要功能是根據I/O請求的服務時間來判斷是否預期下一個I/O請求。

3.1 進程歸類模塊(PC)

AS對所有的負載都使用固定的預期周期(6ms)，不能適應負載的動態(tài)變化。本文提出了進程歸類的方法，其基本思想是根據負載特性決定預期周期的大小，將不同類別的進程映射為不同的預期周期。進程歸類模塊首先找出I/O請求到達時間間隔最密集的區(qū)域，然后將這個區(qū)域對應的到達時間間隔作為預期周期。下面給出一些定義。

定義1Tthink：I/O請求的到達時間間隔。

定義2概率密度函數f(Tthink)表示Tthink的概率密度。

定義3分布函數F(Tthink)表示Tthink的分布。

定義4Map(i)表示進程i映射的預期周期。

假設I/O請求的到達時間間隔在0到20 ms之間。由定義可知

其中，Tas表示預期成功的平均等待時間，定義為預期成功所花費的總時延除以預期成功的I/O請求數。γ是pa,b的門限值。當pa,b≥γ，那么選擇整數j∈[a,b]，作為進程的預期周期。當pa,b＜γ，選擇Tas作為預期周期。因此，進程歸類模塊根據Map函數動態(tài)調整預期周期的長度，適應了負載的動態(tài)變化。

3.2 服務時間評估模塊(STE)

針對AS根據I/O請求的磁道位置來判斷是否預期下一個I/O請求，提出了更精確的基于服務時間的預期策略。其基本思想是比較當前隊列I/O請求的服務時間和預期情況下I/O請求服務時間的大小，決定是否預期。

定義5Si表示剛服務完的第i個I/O請求的磁道位置，表示從當前隊列挑選的I/O請求的磁道位置，此請求是離當前磁頭位置最近的。表示預期成功的I/O請求的磁道位置。

定義6一個I/O請求的三元組指I/O請求i的尋道延遲，Tr指I/O請求的旋轉延遲，取決于磁盤轉速。Tt指I/O請求的傳輸延遲，取決于數據傳輸率。

定義7進程歷史相鄰I/O請求的磁道位置之差的平均值aseek_dist定義如下：

其中，Ts表示預期成功的服務時間，Tf表示預期失敗的服務時間。假設Tas表示預期成功平均等待時間。Taf表示預期失敗的平均等待時間，預期周期為Pms，則Taf等于預期周期P。顯然，預期成功的服務時間Ts等于預期到I/O請求的尋道時延，旋轉時延，傳輸時延和預期成功的平均等待時延之和，如式(9)所示

根據式(9)和式(10)，式(11)表示為

3.3 WPCAS算法設計與復雜性分析

3.3.1 WPCAS算法設計

WPCAS算法主要包括2個部分，分別是進程歸類模塊和服務時間評估模塊。進程歸類模塊為不同類型的負載設置不同的預期周期，并輸出預期周期大小。服務時間評估模塊比較SORT隊列當前I/O請求的服務時間和預期情況下I/O請求的服務時間，決定是否預期下一個I/O請求。如果預期下一個I/O請求，設置預期標志(anticipated_flag=1)，否則，設置預期標志(anticipated_flag=0)。WPCAS算法的形式化描述如下。

算法1WPCAS調度算法

輸入：I/O請求狀態(tài)信息

輸出：預期周期大小

step1統(tǒng)計進程I/O請求的歷史狀態(tài)信息，包括磁道位置和到達時間間隔、預期失敗的請求數、預期失敗所花費的總時延、預期成功的請求數和預期成功所花費的總時延。

step2計算預期成功率(ps)、預期失敗率(pf)和預期成功的平均等待時間(Tas)。

step3根據式(3)和式(4)，計算最佳的預期周期范圍，再由式(6)，得到每類進程的最佳預期周期大小。然后，設置并輸出每類進程的預期周期大小。

step4計算調度SORT隊列當前I/O請求的服務時間和預期情況下I/O請求的服務時間并進行比較。如果，設置預期標志(anticipated_flag=1)，表示預期下一個I/O請求。否則，設置預期標志(anticipated_flag=0)，表示調度SORT隊列的當前I/O請求。

step5若FIFO隊列有超過截止時間的I/O請求，則將該請求分發(fā)到通用塊設備層的調度隊列，進行處理。否則，轉入step6。

step6如果anticipated_flag=0，則將SORT隊列的當前I/O請求插入通用塊設備層的調度隊列，等待磁盤驅動器完成數據傳輸。否則，根據step3得到預期周期的長度,設置定時器的超時時間，等待下一個I/O請求到達。如果定時器超時，預期失敗請求數加1，服務SORT隊列的當前I/O請求。否則，預期成功請求數加1，服務預期到的I/O請求。

3.3.2 WPCAS算法復雜性分析

假設進程類別為m，每類進程歷史I/O請求數為n,那么WPCAS需要記錄mn個I/O請求，即空間復雜度為O(mn)。PC模塊的時間復雜度為O(m)，STE模塊的時間復雜度為O(mn)。所以WPCAS算法的時間復雜度為O(m+mn)。因此，WPCAS算法是可行的。

4 性能測試

在Linux 2.6.20內核對AS算法進行修改，增加了PC和STE 2個模塊。分別對吞吐量，預期成功的平均時延和偽空閑周期[18]進行了測試。為了測量真實的磁盤性能，繞過了Linux頁面高速緩存，使用直接I/O測試。主要包含以下幾種負載。

1)IOzone生成的順序負載。

2)IOzone生成的隨機負載。

3)Postmark生成的Web服務器負載。

通過測試對比了NOOP、CFQ、Deadline、AS、WPCAS和95%-Heuristic[18]等調度算法的性能。

4.1 測試工具

采用IOzone和Postmark作為負載測試工具。IOzone[20]是一個文件系統(tǒng)的benchmark工具，可以測試不同的操作系統(tǒng)中文件系統(tǒng)和磁盤的讀寫性能。 Postmark[21]主要用于測試文件系統(tǒng)在郵件系統(tǒng)或電子商務系統(tǒng)中的性能，其特點是：頻繁、大量地存取小文件，可生成Web服務器負載、數據庫負載和Email負載等。

4.2 性能指標

實驗性能評價參數主要有：

1)吞吐量；

2)預期成功的平均等待時延；

3)偽空閑周期的長度。

偽空閑周期長度定義為預期失敗的總時延除以總的預期請求數。顯然，這個值越小，平均響應時間越小。

4.3 實現方法

實驗測試中，在Linux 2.6.20內核block/blkdev.h頭文件的io_context結構體加入了鏈表inv_d。在block/as-iosched.c文件的as_update_iohist記錄最近n個請求的到達時間間隔，并存入鏈表inv_d。在as_antic_update_rq加入了2個計數器as_scount和as_stime，記錄預期成功的請求數和預期成功所花費的總時延。在as_antic_timout函數中加入了2個計數器as_fcount和as_ftime，記錄預期失敗的請求數和預期失敗所花費的總時延。然后添加函數as_antic_dertermined和as_class_proccess。as_class_proccess根據進程歸類模塊為不同負載指定的預期周期。as_antic_determined根據服務時間評估模塊決定是否預期下一個請求。

4.4 順序負載和隨機負載測試

使用IOzone生成512 KB大小的文件，測試NOOP、Deadline、CFQ、AS和WPCAS在10、40、80類進程下的吞吐量。以進程類別數等于40為例，順序負載配置為:#root/iozone–i0–i1–r4096–t40–s100–I–Rresult.xls。其中，–i0表示順序寫、–i1表示順序讀、–r表示測試塊大小、–t表示進程類別數、–s表示測試文件大小、–I表示繞過文件系統(tǒng)緩存，直接對磁盤進行讀寫。–R表示產生excel的輸出日志。隨機負載配置為：#root/iozone–i2–r4096–t40–I–Rresult.xls。其中，–i2表示隨機讀寫負載。實驗中分別對10、40、80類進程下的順序負載和隨機負載測試了50次，對3種情況下的測試結果分別求平均值并進行比較。

4.4.1 順序讀寫512 KB文件的吞吐量

圖3～圖5顯示了I/O調度算法在順序負載下的吞吐量。圖3和圖4表明，當進程類別較少時，NOOP和Deadline在順序負載下的吞吐量比其他I/O調度算法都高。圖5表明，當進程類別數較多時，由于不同進程的I/O請求持續(xù)交錯的到達，I/O請求的連續(xù)性遭到破壞，所以NOOP和Deadline的吞吐量比其他I/O調度算法低。對于順序負載，WPCAS的吞吐量比AS提高了10.9%左右。AS算法為每類進程分配固定的預期周期（6 ms），對于順序請求的負載，AS雖然能夠預測到下一個到達的連續(xù)請求，但也造成了某些密集I/O(到達時間間隔小于6 ms)長時間的等待。而WPCAS算法不但能夠準確的預測下一個連續(xù)的請求，而且根據進程特性為每類進程分配不同的預期周期，能夠適應負載的動態(tài)變化。因此，WPCAS算法的吞吐量比AS高。

圖3 進程類別數為10，順序負載下各種I/O調度算法的吞吐量

圖4 進程類別數為40，順序負載下各種I/O調度算法的吞吐量

圖5 進程類別數為80，順序負載下各種I/O調度算法的吞吐量

4.4.2 隨機讀寫512 KB大小文件的吞吐量

圖6～圖8顯示了I/O調度算法在隨機負載下的吞吐量?？梢钥闯?，CFQ算法對于隨機讀寫吞吐量高于其他調度算法。這是由于CFQ為每個進程維護一個I/O隊列，各個進程發(fā)出的I/O請求以輪循的方式處理。因此，CFQ非常適合于隨機、零散的I/O請求。由于NOOP算法按照先來先服務進行調度，對于隨機負載，會造成磁頭的頻繁移動，增加尋道時延。因此，NOOP的隨機讀寫性低于AS和WPCAS。在隨機負載下，WPCAS比AS吞吐量提高了5%左右。這是由于在隨機負載下，每類進程的I/O請求的到達時間間隔差別很大，使采用固態(tài)預期周期長度的AS預期失敗或等待時間過長。而WPCAS根據負載特性動態(tài)改變預期周期的長度，使預期更加準確和高效。

圖6 進程類別數為10，隨機負載下各種I/O調度算法的吞吐量

圖7 進程類別數為40，隨機負載下各種I/O調度算法的吞吐量

圖8 進程類別數為80，隨機負載下各種I/O調度算法的吞吐量

4.5 Postmark生成的Web服務器負載

為了進一步評估WPCAS算法的性能，使用Postmark模擬真實的Web服務器負載，比較了95%-Heuristic、AS和WPCAS的性能。如表1所示，A-T、A-S和A-F分別表示總的預期請求數、預期成功的請求數和預期失敗的請求數。A-ST和A-FT分別表示預期成功所花費的總時延和預期失敗所花費的總時延。95%-Heuristic、AS和WPCAS的偽空閑周期長度分別為0.238 ms、0.113 ms和0.047 ms。WPCAS的吞吐量比AS和95%-Heuristic分別提高了24%和40%。這是由于訪問Web服務器的負載類型是動態(tài)變化的。例如，Web服務器上的某一“熱點”新聞，可能引起短時間內大量的I/O請求到達，I/O非常密集。在一段時間之后，這些“熱點”的新聞逐漸成為“冷門”，可能很長時間才會有I/O請求到達。AS算法對所有的負載采用固態(tài)的預期周期(6 ms)，增加了預期失敗的次數和預期成功的所花費的總時延。WPCAS針對不同類型的負載動態(tài)的調度預期周期的長度，適應了負載的動態(tài)變化。因此，WPCAS非常適用于Web服務器負載、網站訪問負載等。

表1 Postmark生成的Web服務器負載

5 結束語

針對傳統(tǒng)AS調度算法的不足，提出了一種基于負載特性和服務時間評估改進的AS算法(WPCAS)。WPCAS分為進程歸類模塊(PC)和服務時間評估模塊(STE)兩部分。PC根據負載特性，動態(tài)調整預期周期的長度，從而適應負載動態(tài)變化。STE根據I/O請求的服務時間決定是否預期下一個I/O請求，使得預期更加的準確。通過對比實驗證明了在吞吐量、預期成功的平均時延和偽空閑周期長度等方面，WPCAS算法優(yōu)越于95%-Heuristic和AS算法。特別地，WPCAS算法非常適用于Web網絡服務器負載。

[1]WORTHINGTON B,GANGER G,PATT Y.Scheduling algorithms for modern disk drives[A].InACM Sigmetrics[C].1994.241-251.

[2] HUANG L,CHIUEH T.Implementation of a Rotation Latency Sensitive Disk Scheduler[R].Technical Report ECSL-TR81,SUNY,Stony Brook,2000.

[3] REDDY A L N,WYLLIE J.Disk scheduling in a multimedia I/O system[A]. Proc First ACM Int’l Conf Multimedia(MULTIMEDIA’93)[C].1993.225-233.

[4]CHANG R I,SHIH W K,CHANG R C.Deadline-modification-scan with maximum scannable-groupsformultimediareal-timedisk scheduling[A].Proceedings of the 19th IEEE Real-Time Systems Symposium[C].1998.40-49.

[5]CHANG H P,CHANG R I,SHIH W K,etal.Reschedulable-group-SCAN scheme for mixed real-time/non-real-time disk scheduling in a multimedia system[J].J Syst Software,2002,59(2):143-152.

[6]CHANG H P,CHANG R I,SHIH W K,et al.GSR:a global seek-optimizing real-time disk-scheduling algorithm,the journal of transactions in firm real-time database systems[J].Systems and Software,2007,80(2):198-215.

[7]KESAVAN M,GAVRILOVSKA A,SCHWAN K.Differential virtual time(DVT):rethinking I/O service differentiation for virtual machines[A].Proc of the 1st ACM Symposium on Cloud Computing,SoCC’10[C].ACM,New York(2010),2010.27-38.

[8] RIZZO L,VALENTE P.Hybrid:achieving deterministic fairness and high throughput in disk scheduling[A].Proc CCCT’04[C].2004.

[9]WACHS M,ABD-EL-MALEK M,THERESKA E,et al.Argon:performance insulation for shared storage servers[A].Proc of the 5th USENIX Conference on File and Storage Technologies(FAST’07)[C].San Jose,CA,USA,2007.61-76.

[10]GULATI A,MERCHANT A,VARMAN P J.Pclock:an arrival curve based approach for QoS guarantees in shared storage systems[J].SIGMETRICS Performance Evaluation Rev,2007,35(1):13-14.

[11]GULATI A,MERCHANT A,UYSAL M,et al.Efficient and Adaptive Proportional Share I/O Scheduling[R].Hewlett-Packard Pdf,2009.

[12]GANG P,CKER CHIUEH T.Availability and fairness support for storage qos guarantee in distributed computing systems[A]. ICDCS’08.The28th International Conference on 2008[C].2008.589-596.

[13]VALENTE P,CHECCONI F.High throughput disk scheduling with fair bandwidth distribution[J].IEEE Transactions on Computers,2010,59(9):1172-1186.

[14]http://mirror.linux.org.au/pub/linux.conf.au/2007/video/talks/123.pdf[EB/OL].2010.

[15]LOVE R.Linux Kernel Development[M].Developers Library Sams Publishing/Novel,2005.

[16]STOUPA K,VAKALIA.QoS-oriented negotiation in disk subsystems[J].Data and Knowledge Engineering Journal,2006,58(2):107-128.

[17]TANENBAUM A S.Modern Operating Systems[M].Second Ed Prentice Hall,Upper Saddle River,NJ,2001.

[18]LYER S,DRUSCHEL P.Anticipatory scheduling:a disk scheduling framework to overcome deceptive idleness in synchronous I/O[A].Proceedings of the 18th ACM Symposium on Operating Systems Principles[C].New York,NY,2001.

[19]RUEMMLER C,WILKES J.Anintroduction todiskdrive modeling[J].IEEE Comput,1994,27(3):16-28.

[20]IOzone file system benchmark[EB/OL].http://www.iozone.org.

[21]KATCHER J.Postmark:a New File System Benchmark[R].Technical Report TR 3022,NetworkAppliance,1997.