基于負(fù)載特性和服務(wù)時(shí)間評(píng)估改進(jìn)的AS調(diào)度算法

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

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

1 引言

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

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

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

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

針對(duì)AS算法存在以上2個(gè)方面的不足，提出了一種改進(jìn)的基于負(fù)載特性和服務(wù)時(shí)間評(píng)估的AS調(diào)度算法(WPCAS)，主要分為進(jìn)程歸類模塊(PC)和服務(wù)時(shí)間評(píng)估模塊(STE)。PC模塊通過分析負(fù)載的訪問特性，為不同類型的負(fù)載設(shè)置不同的預(yù)期周期。STE模塊根據(jù)I/O請(qǐng)求的服務(wù)時(shí)間決定是否預(yù)期下一個(gè)I/O請(qǐng)求。相比于AS，WPCAS不僅適應(yīng)了負(fù)載的動(dò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請(qǐng)求服務(wù)時(shí)間模型

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

2.2 AS預(yù)期策略

2.2.1 AS預(yù)期原理

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

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

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

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

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

2.3 AS執(zhí)行流程

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

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

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

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

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

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

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

3 WPCAS調(diào)度策略

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

3.1 進(jìn)程歸類模塊(PC)

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

定義1Tthink：I/O請(qǐng)求的到達(dá)時(shí)間間隔。

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

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

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

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

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

3.2 服務(wù)時(shí)間評(píng)估模塊(STE)

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

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

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

定義7進(jìn)程歷史相鄰I/O請(qǐng)求的磁道位置之差的平均值aseek_dist定義如下：

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

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

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

3.3.1 WPCAS算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

4 性能測(cè)試

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

1)IOzone生成的順序負(fù)載。

2)IOzone生成的隨機(jī)負(fù)載。

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

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

4.1 測(cè)試工具

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

4.2 性能指標(biāo)

實(shí)驗(yàn)性能評(píng)價(jià)參數(shù)主要有：

1)吞吐量；

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

3)偽空閑周期的長(zhǎng)度。

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

4.3 實(shí)現(xiàn)方法

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

4.4 順序負(fù)載和隨機(jī)負(fù)載測(cè)試

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

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

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

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

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

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

4.4.2 隨機(jī)讀寫512 KB大小文件的吞吐量

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

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

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

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

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

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

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

5 結(jié)束語

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

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