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

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

1 引言

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

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

第2類是預(yù)定帶寬或時延的I/O調(diào)度算法，這類算法用于滿足用戶的預(yù)定帶寬或者預(yù)定時延，如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]等算法。這些算法在滿足預(yù)定帶寬或時延的條件下，提高任務(wù)的吞吐量。

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

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

2 相關(guān)工作

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

2.1 I/O請求服務(wù)時間模型

其中，旋轉(zhuǎn)時延與磁盤轉(zhuǎn)速相關(guān)，傳輸時延等于I/O請求除以數(shù)據(jù)傳輸率。結(jié)合式(1)和式(2)，可計算I/O請求的服務(wù)時間。

2.2 AS預(yù)期策略

2.2.1 AS預(yù)期原理

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

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

2.2.2 AS預(yù)期機制狀態(tài)轉(zhuǎn)換

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

圖1 預(yù)期機制狀態(tài)轉(zhuǎn)換

2.3 AS執(zhí)行流程

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

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

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

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

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

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

圖2 預(yù)期調(diào)度算法的處理流程

3 WPCAS調(diào)度策略

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

3.1 進程歸類模塊(PC)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 WPCAS算法設(shè)計與復(fù)雜性分析

3.3.1 WPCAS算法設(shè)計

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

算法1WPCAS調(diào)度算法

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

輸出：預(yù)期周期大小

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

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

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

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

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

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

3.3.2 WPCAS算法復(fù)雜性分析

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

4 性能測試

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

1)IOzone生成的順序負載。

2)IOzone生成的隨機負載。

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

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

4.1 測試工具

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

4.2 性能指標(biāo)

實驗性能評價參數(shù)主要有：

1)吞吐量；

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

3)偽空閑周期的長度。

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

4.3 實現(xiàn)方法

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

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

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

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

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

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

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

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

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

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

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

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

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

4.5 Postmark生成的Web服務(wù)器負載

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

表1 Postmark生成的Web服務(wù)器負載

5 結(jié)束語

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

[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.