一種面向網(wǎng)格資源預留的索引鏈表研究

吳黎兵，于天水，何炎祥，李 飛

(1.武漢大學計算機學院，湖北武漢 430072;2.武漢大學軟件工程國家重點實驗室，湖北武漢 430072)

在高性能計算網(wǎng)格環(huán)境中，資源分布在各個不同地域和管理域中，由不同的組織擁有和操作，并且在策略和安全機制上各有不同。站點的自治性，資源的動態(tài)性和異構(gòu)性需要一種有效機制來聯(lián)合分配位于多個站點上的資源。資源預留可以保證任務在開始執(zhí)行時獲得資源，而在網(wǎng)格這種資源動態(tài)性很強的環(huán)境中，任務能如期執(zhí)行可大大提高整個網(wǎng)格系統(tǒng)的資源利用率和系統(tǒng)性能。由于資源預留還可以實現(xiàn)網(wǎng)格服務的QoS保證，因而資源預留是網(wǎng)格資源管理中一種普遍采用的機制，也成為網(wǎng)格資源管理的研究熱點。

目前網(wǎng)格資源預留機制從理論到實際應用的關鍵在于提高自身的處理性能，以便用盡可能小的代價，為用戶提供更高QoS保證的網(wǎng)格服務。資源預留要求接納控制的數(shù)據(jù)結(jié)構(gòu)必須能夠快速高效地查詢資源的實驗情況。實驗表明，資源預留中有60%以上的時間用于對數(shù)據(jù)結(jié)構(gòu)的處理，而這僅僅是提供最簡單的預留服務，如果請求全部潛在的高級預留服務(如在掃描探測資源時間間隔時)，則與數(shù)據(jù)結(jié)構(gòu)相關的處理達到總處理時間的90%［1］。可見為了最小化處理時間，對數(shù)據(jù)結(jié)構(gòu)的改進是最能影響整個處理時間的，對數(shù)據(jù)結(jié)構(gòu)的優(yōu)化可以在較大程度上提高資源提前預留服務的處理速度。

1 現(xiàn)有數(shù)據(jù)結(jié)構(gòu)

現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)分為基于離散時間(時隙)和基于連續(xù)時間兩類。時隙是一個固定的時間間隔，它是資源預留的時間單位，其代表是基于時隙的數(shù)組，文獻［2］中提出了一種基于時隙數(shù)組的數(shù)據(jù)結(jié)構(gòu)，并將這種基于時隙的數(shù)組與其他基于時隙的數(shù)據(jù)結(jié)構(gòu)(如線段樹［3］和二叉搜索樹［4］)相比，結(jié)果顯示無論是消耗的時間還是消耗的存儲空間，基于時隙的數(shù)組性能都有優(yōu)越性。因此，筆者選擇時隙數(shù)組作為比較對象之一，且僅選擇這一種基于時隙的數(shù)據(jù)結(jié)構(gòu)。文獻［5］指出了基于時隙的數(shù)據(jù)結(jié)構(gòu)有兩個比較明顯的缺陷，一是時隙的定義是一個挑戰(zhàn)，太長的時隙會降低精度，太短的時隙會浪費時間和存儲空間;二是將時間分割成時隙會導致可利用帶寬的減少。

文獻［6］提出了一種基于單鏈表的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)是基于連續(xù)時間的，并且可以動態(tài)地回收存儲，其實驗結(jié)果表明，這種基于單鏈表的數(shù)據(jù)結(jié)構(gòu)對存儲空間的消耗要遠少于時隙數(shù)組，并且在請求量不是很大時，在時間消耗上也要大大優(yōu)于時隙數(shù)組。因此，筆者選擇這種基于單鏈表的數(shù)據(jù)結(jié)構(gòu)作為比較對象之一，且針對單鏈表中請求接納時間和請求搜索時間性能不理想的問題，提出了一種改進的索引鏈表。

文獻［7］提出一種基于帶寬預留的資源樹，它是樹形數(shù)據(jù)結(jié)構(gòu)的典型代表。但是文獻［6］的仿真結(jié)果表明，該數(shù)據(jù)結(jié)構(gòu)無論在消耗的時間還是消耗的存儲空間上與時隙數(shù)組或單鏈表相比，都存在著較大的差距。

2 索引鏈表

2.1 預留請求定義

一個接納控制程序必須維護一個合適的數(shù)據(jù)結(jié)構(gòu)來存儲管理區(qū)域中的預留資源信息。當請求到達時，需要檢查參數(shù)，并決定是否有足夠的資源用來預留和分配。每一個預留請求都由一系列參數(shù)來描述，筆者采用文獻［6］中預留請求的定義方法:

其中，bw為預留帶寬;ts，te分別為開始時間和結(jié)束時間。

2.2 基于單鏈表的數(shù)據(jù)結(jié)構(gòu)

文獻［6］不僅提出了基于單鏈表的數(shù)據(jù)結(jié)構(gòu)，還提出了與該結(jié)構(gòu)配套的預處理及回收等思想，并通過仿真實驗來證明該結(jié)構(gòu)有著不錯的存儲性能和接納性能。

基于單鏈表的數(shù)據(jù)結(jié)構(gòu)為:

其中，ts為預留請求的開始時間，bw為當前節(jié)點的時間段內(nèi)已經(jīng)被預留的帶寬。因此一個節(jié)點所覆蓋的時間段是從p1-＞ts到 p2-＞ts。p2為p1的下一個節(jié)點。鏈表最后一個節(jié)點的next為空。它表示最后一個節(jié)點p所覆蓋的時間段是從p-＞ts到結(jié)束。通常最后一個節(jié)點的bw值為0，因為在p所覆蓋的時間段內(nèi)沒有帶寬被預留。

文獻［6］還描述了插入、預處理與回收的思想。首先，鏈表中僅有一個頭節(jié)點 head(0，0，null)。當預留請求 req(ts，te，bw)到達，且請求被允許(判斷剩余的帶寬是否足夠預留)，1個或2個新節(jié)點將被加入鏈表中。他們在鏈表中的位置由其開始時間決定。檢查和插入工作需要在每一次請求到達后完成。

為了避免每一次都從頭節(jié)點開始尋找合適的位置，利用一個“l(fā)ocal”指針來標識前一次請求搜索到的開始節(jié)點。為了實現(xiàn)它，需要搜集一個給定時段內(nèi)的所有預留請求，并按它們的開始時間排序，然后再一起對它們進行接納控制。同時，可以通過釋放過期的節(jié)點來回收內(nèi)存。過期節(jié)點是指所覆蓋的時間段遠遠早于當前時間的節(jié)點。

筆者分別對上述的算法思想進行了實現(xiàn)。其中預處理只是排序問題，這里不再敘述。對于回收，選擇每隔一個固定的時間進行(在實驗中這個時間是100 s)，因為回收得太過頻繁會降低整個數(shù)據(jù)結(jié)構(gòu)的性能。

資源回收算法中empty函數(shù)的功能是清空鏈表，即將一個鏈表完全釋放掉，實現(xiàn)較容易，這里不再敘述。

單鏈表資源回收算法描述如下:

單鏈表的插入算法是比較繁瑣的，它涉及到多種情況，在這里提供一種實現(xiàn)方法如下:

下面討論結(jié)束節(jié)點的情況:

生成新節(jié)點，插入到兩節(jié)點之間。

上面只是描述了插入算法的實現(xiàn)過程，具體實現(xiàn)中還涉及帶寬bw的修改，local指針的指向等問題，限于篇幅，在這里不再描述。

2.3 索引鏈表數(shù)據(jù)結(jié)構(gòu)

以上對單鏈表的算法思想進行了描述并給出了實現(xiàn)的關鍵算法，但該結(jié)構(gòu)還存在很多弊端。首先，即使經(jīng)過了預處理，每次在移動節(jié)點的過程中還是不能迅速定位，在檢查與插入階段都要浪費很多時間;其次，資源預留的其他模塊對該鏈表進行搜索時，必須從頭節(jié)點開始查找，搜索效率較低。

針對單鏈表存在的上述問題，筆者提出了一種改進的數(shù)據(jù)結(jié)構(gòu)，稱為索引鏈表。其核心思想如下:

定義一個額外的索引數(shù)組，為保證查找速度，這個數(shù)組要盡量短小(如在實驗中，所定義的索引數(shù)組是indexs［101］)。該數(shù)組中的每一個元素都指向單鏈表中的一個節(jié)點，這種指向符合某種散列函數(shù)。

例如indexs［1］指向 ts=10的節(jié)點，它符合i=ts/10的散列函數(shù)，同樣，ts=550的節(jié)點由indexs［55］指向。如果在單鏈表中并沒有ts=55的這個節(jié)點，那么此時索引數(shù)組中indexs［55］指向頭節(jié)點head。這是因為在初始化過程中，索引數(shù)組的所有元素都被指向頭節(jié)點head。

在插入過程中，如果某一預留請求req，有req(ts)%10==0，則這個請求形成的新節(jié)點就由索引數(shù)組indexs［ts/10］指向。圖1示意了這種索引鏈表的結(jié)構(gòu)［8］。

圖1 索引鏈表示意圖

在定位或查詢過程中，首先按散列式i=ts/10來查詢索引數(shù)組 indexs［i］，如果該元素指向head，則向前移動一個(i-1)，直至找到一個合適的元素，或者搜索失敗。例如定位ts=555的節(jié)點，有散列式 i=ts/10，可查詢數(shù)組元素 indexs［55］，該元素指向 ts=550的節(jié)點。如果 indexs［55］指向head，則依次向前查找，搜索最近的可用節(jié)點(指針指向鏈表中其他節(jié)點，而不是指向head節(jié)點);如果找不到，直至搜索失敗。

搜索失敗有兩種情況，當沒有l(wèi)ocal指針時，一直搜索到索引數(shù)組的最小元素(關于最小元素后面會有說明，它不總是 indexs［0］);當有 local指針時，搜索到local指針前的最后一個元素時就應該停止。

隨著時間的推移，ts的值會越來越大，總會有超過索引數(shù)組邊界的時候。為了防止這種溢出，必須將索引數(shù)組設計為環(huán)形，以循環(huán)利用數(shù)組的存儲空間。

數(shù)組的循環(huán)是這樣實現(xiàn)的:定義一個值min，該值為數(shù)組的最小值，很顯然初始時min=0。當資源回收時(每隔100 s)，也同時對索引鏈表進行資源回收。其實現(xiàn)方法如下:

由于每過100 s，索引數(shù)組相應有10個元素已經(jīng)過期，因此，回收這10個元素，同時將最小值min加10。為了使索引數(shù)組循環(huán)起來，在定位與插入的時候也要相應地判斷ts是否已大于門限值1000，其實現(xiàn)方法如下:

變量說明:x，sign都是int型變量，而local是文獻［6］中提到的local指針。

這里忽略了節(jié)點合并的問題，插入過程中可能會出現(xiàn)這種情況，時間相鄰的兩個節(jié)點p1，p2;原本p1-＞bw！=p2-＞bw，但某次插入后可能會出現(xiàn)p1-＞bw==p2-＞bw。這時兩個節(jié)點中有一個是冗余的，應該合并。但筆者舍棄了這種操作，一方面是這種情況出現(xiàn)的概率較低;另一方面是合并必須在插入過程中加入額外的檢查和操作，這樣就大大影響了插入操作的性能。

3 測試與評估

3.1 發(fā)送端環(huán)境

發(fā)送端由一組隨機數(shù)發(fā)生器來實現(xiàn)，其產(chǎn)生一系列的資源提前預留請求。請求的數(shù)據(jù)結(jié)構(gòu)中帶寬(bw)遵循(100，1000)范圍內(nèi)的均勻分布，單位為kB。開始時間(ts)遵循(20，80)范圍內(nèi)的均勻分布，單位為s。持續(xù)時間(td)遵循參數(shù)為0.01的指數(shù)分布，單位為s。隨機發(fā)生時間遵循參數(shù)為1的泊松分布，單位為s。實際測試過程中可以同時模擬多個發(fā)送端(測試環(huán)境為Linux操作系統(tǒng)，同時開多個shell窗口運行多個發(fā)送端)，以增加資源請求的發(fā)生速度［9-10］。

3.2 評估指標

所采取的評估指標主要有3個:內(nèi)存需求，請求接納時間和請求搜索時間。其中內(nèi)存需求是指數(shù)據(jù)在運行過程中所消耗的內(nèi)存;請求接納時間是指數(shù)據(jù)結(jié)構(gòu)的檢查與插入時間;請求搜索時間是指其他程序在掃描和搜索數(shù)據(jù)結(jié)構(gòu)時所耗費的時間。

內(nèi)存需求與請求接納時間通過實際的測試，按照真實的數(shù)據(jù)來評估各個數(shù)據(jù)結(jié)構(gòu)的性能。而請求搜索時間無需測試，從數(shù)據(jù)結(jié)構(gòu)本身的特點即可說明各個數(shù)據(jù)結(jié)構(gòu)間的差異。

3.3 測試結(jié)果

圖2所示為在兩倍速率環(huán)境下(同時開兩個發(fā)送端)，4種數(shù)據(jù)結(jié)構(gòu)的請求接納時間。由圖2可見，索引鏈表有比較明顯的優(yōu)勢，單鏈表和雙鏈表緊隨其后，二者的性能比較接近。

圖2 請求接納時間比較圖

其中，單鏈表和雙鏈表的曲線呈鋸齒形，這與回收間隔時間有關，每次回收之后，速度會有所提高。而時隙數(shù)組的性能比較穩(wěn)定，這是由于它沒有不確定因素。索引鏈表的性能呈不規(guī)則狀，是由于每次用索引定位成功的幾率所導致的差異，但是其總體性能要明顯優(yōu)于其他數(shù)據(jù)結(jié)構(gòu)。

圖3所示為在兩倍速率環(huán)境下，4種數(shù)據(jù)結(jié)構(gòu)的內(nèi)存需求。筆者對于3種鏈表(單鏈表、雙鏈表和索引鏈表)只測試了其中單鏈表的內(nèi)存消耗，由于雙鏈表和索引鏈表的內(nèi)存消耗是在單鏈表的基礎上增加一個定值，因此不需要重復測試，而時隙數(shù)組保持一個固定值。由圖3可見，單鏈表的內(nèi)存需求略優(yōu)于索引鏈表和雙鏈表。

圖3 內(nèi)存需求比較圖

3種鏈表的鋸齒形曲線是由回收函數(shù)造成的，索引鏈表比單鏈表增加了索引數(shù)組的內(nèi)存需求(404 B)，而雙鏈表比單鏈表每個節(jié)點增加了4 B(前向指針)。因此在節(jié)點數(shù)目大于101個時，索引鏈表的內(nèi)存需求要優(yōu)于雙鏈表，而在實驗中的大部分時間節(jié)點數(shù)目都大于101個。

至于請求搜索時間，從數(shù)據(jù)結(jié)構(gòu)的特性就可以分析出，不需要進行測試。時隙數(shù)組是隨機搜索，可在非常短的時間內(nèi)完成。由于目標地址由數(shù)組起始地址+偏移量所得，通過基址尋址可直接得到，因此它的搜索效率是最優(yōu)的。而單鏈表和雙鏈表只支持順序搜索，因此比索引鏈表效率要低。這一點在測試接納時間時就已得到驗證，因為索引鏈表比單鏈表改進的就是搜索定位的速度。單鏈表和雙鏈表兩者的搜索速度幾乎一樣。

4 結(jié)論

一個性能優(yōu)良的數(shù)據(jù)結(jié)構(gòu)對資源預留有著至關重要的意義，筆者挑選了3種比較有代表性的數(shù)據(jù)結(jié)構(gòu)(時隙數(shù)組、單鏈表和雙鏈表)作為比較對象，并提出了一種新的數(shù)據(jù)結(jié)構(gòu)，即索引鏈表，在Linux平臺采用C語言進行了完整的實現(xiàn)。測試結(jié)果表明:

(1)索引鏈表表現(xiàn)出了良好的性能，它在各方面都有出色的表現(xiàn)，接納時間是最優(yōu)的，內(nèi)存需求僅次于單鏈表，搜索時間僅次于時隙數(shù)組。

(2)單鏈表和雙鏈表表現(xiàn)基本持平，處于中上游水平，單鏈表在內(nèi)存需求上是最節(jié)省的。

(3)時隙數(shù)組在搜索時間上性能最好，它受發(fā)送端的影響較大，時隙的確定和數(shù)組的長度，都與發(fā)送端請求產(chǎn)生的密度和速度有關。

［1］ZHANG H，KEAHEY K，ALLCOCK W.Providing data transfer with QoS as agreement-based service［C］//Proceeding of the IEEE International Conference on Services Computing.［S.l.］:IEEE Computer Society，2004:344-353.

［2］BURCHARD L O，HEISS H U.Performance evaluation of data structures for admission control in bandwidth brokers［R］.Berlin:Communications and Operating Systems Group，Technical University of Berlin，2002.

［3］NILSSON A，CHEN J，CARLSSON S.An efficient data structure for advance bandwidth reservation on the internet［R］.CSEE:Lulea University of Technology，2008.

［4］SIM K M.Grid resource negotiation:survey and new directions［C］//IEEE Transactions on Systems，Man，and Cybernetics.［S.l.］:［s.n.］，2010:1-13.

［5］BURCHARD L，HEISS H U.Performance issues of bandwidth reservation for grid computing［C］//Proceedings of the 15th Symposium on Computer Archetecture and High Performance Computing(SBACPAD'03).［S.l.］:［s.n.］，2003:25-29.

［6］XIONG Q，WU C L，XING J B，et al.A linked-list data structure for advance reservation admission control［C］//ICCNMC 2005，LNCS 3619.［S.l.］:［s.n.］，2005:901–910.

［7］WANG T，CHEN J E.Bandwidth tree:a data structure for routing in networks with advanced reservations［C］//Performance，Computing，and Communications Conference，21st IEEE International.［S.l.］:［s.n.］，2002:37-44.

［8］QU M C.Storage resource reservation method for data grid［J］.Journal of Harbin Institute of Technology，2010，42(3):432-436.

［9］CUCINAOTTA T，KONSTANTELI K，VARVARIGOU T.Advance reservations for distributed real-time workflows with probabilistic service guarantees［C］//Proceedings of 2009 IEEE International Conference on Service-Oriented Computing and Applications(SOCA，2009).［S.l.］:［s.n.］，2009:1-8.

［10］RAJAH K，RANKA S，YE X.Advance reservations and scheduling for bulk transfers in research networks［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20(8):1682-1697.