內(nèi)存網(wǎng)格調(diào)度方法分析

盧俊文，崔建峰，肖 蕾，莊蔚蔚，謝小竹

（廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院，福建廈門361024）

內(nèi)存網(wǎng)格調(diào)度方法分析

盧俊文，崔建峰，肖 蕾，莊蔚蔚，謝小竹

（廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院，福建廈門361024）

內(nèi)存網(wǎng)格研究目的是在物理內(nèi)存不足之時(shí)，各個(gè)節(jié)點(diǎn)之間共享物理內(nèi)存.在分析內(nèi)存訪問速度、U-disk訪問速度、網(wǎng)絡(luò)帶寬的基礎(chǔ)上，提出了一種網(wǎng)格內(nèi)存調(diào)度方法及內(nèi)存管理框架.在某個(gè)網(wǎng)格節(jié)點(diǎn)內(nèi)存不足之時(shí)，網(wǎng)格節(jié)點(diǎn)可以共享各個(gè)節(jié)點(diǎn)之間的內(nèi)存，從而提高內(nèi)存容量.通過分析其他節(jié)點(diǎn)內(nèi)存讀取時(shí)間、U-disk讀取時(shí)間、與本地硬盤讀取時(shí)間的差異，決定是否采用其他網(wǎng)格節(jié)點(diǎn)的內(nèi)存或者U-disk內(nèi)存.實(shí)驗(yàn)表明，提出的內(nèi)存網(wǎng)格擴(kuò)展了內(nèi)存容量，減少了內(nèi)存替換概率，提高了性能.

內(nèi)存；內(nèi)存網(wǎng)格；調(diào)度方法；網(wǎng)格數(shù)據(jù)庫；時(shí)間延遲

隨著應(yīng)用程序的功能越來越復(fù)雜，計(jì)算越來越多，不僅對CPU提出了更高的要求，而且對內(nèi)存的容量也提出了挑戰(zhàn)，內(nèi)存不足經(jīng)常導(dǎo)致程序無法運(yùn)行.解決內(nèi)存不足的最好方法是增加物理內(nèi)存，但是這種方法有許多弊端，關(guān)閉機(jī)器，對內(nèi)存進(jìn)行更換或增加內(nèi)存，但是由于計(jì)算機(jī)內(nèi)存插槽數(shù)量有限，還有一些計(jì)算機(jī)由于受保修等限制，不允許自行打開機(jī)箱.相對這些問題，更難的是內(nèi)存讀取速度與硬盤讀取速度之間的差距［1］.

相關(guān)學(xué)者在對內(nèi)存訪問速度，U-disk訪問速度，網(wǎng)絡(luò)帶寬分析的基礎(chǔ)之上，提出了很多解決方法. IMDB（Memory database system）是一種常駐內(nèi)存數(shù)據(jù)庫，其將需要訪問的數(shù)據(jù)庫存在內(nèi)存之中，使多個(gè)處理器能共享同一個(gè)內(nèi)存，并按智能方法實(shí)現(xiàn)共享.文獻(xiàn) ［2］等探討了智能電網(wǎng)中，網(wǎng)格內(nèi)存的內(nèi)存分配和回收方法.文獻(xiàn) ［3］介紹了一種在集群之中，各個(gè)節(jié)點(diǎn)之間利用網(wǎng)格內(nèi)存共享方法，這種方法對內(nèi)存密集型作業(yè)非常有利，但對非內(nèi)存密集型作業(yè)沒有太好的表現(xiàn)［4］.隨著web技術(shù)的房展，RAM Server和Net Server被用來在共享多余的物理內(nèi)存.Windows Vista介紹了一種新的增加內(nèi)存的方法Windows ReadyBoost，該技術(shù)可將用戶的可移動(dòng)存儲(chǔ)器當(dāng)做內(nèi)存，U-disk提高內(nèi)存容量，而不需要打開機(jī)箱，這種方法主要還是基于機(jī)器自身配置進(jìn)行擴(kuò)展，并未考慮到附近節(jié)點(diǎn)內(nèi)存供應(yīng)情況.文獻(xiàn) ［5］分析了網(wǎng)格延遲因素，對網(wǎng)格內(nèi)存的影響.文獻(xiàn) ［6］提出了一種基于服務(wù)的內(nèi)存共享框架-DPRG（Distributed paging RAM grid）.他在研究大規(guī)模內(nèi)存共享屬性和特性的基礎(chǔ)之上，設(shè)計(jì)了優(yōu)化算法訪問網(wǎng)格資源［7］，其算法主要集中在內(nèi)存的讀取優(yōu)化方面進(jìn)行的.文獻(xiàn) ［8］通過分析訪問數(shù)據(jù)的時(shí)空本地性，分析了高效的內(nèi)存管理方法.現(xiàn)有的方法主要缺陷是并沒有考慮到內(nèi)存網(wǎng)格節(jié)點(diǎn)之間的連接帶寬及網(wǎng)格節(jié)點(diǎn)本身可以提供的U-disk擴(kuò)展.本文在分析網(wǎng)格內(nèi)存連接帶寬、U-disk讀取速度等影響因素基礎(chǔ)之上，提出一種基于共享物理內(nèi)存的調(diào)度方法，實(shí)現(xiàn)各個(gè)網(wǎng)格節(jié)點(diǎn)多余內(nèi)存之間的共享，以減少內(nèi)存訪問及替換的次數(shù)，增加內(nèi)存再次訪問的概率，提高計(jì)算的速度和能力.

1 內(nèi)存網(wǎng)格的可能性分析

研究發(fā)現(xiàn)，硬盤由于旋轉(zhuǎn)速度不同，延遲范圍從5～35 ms，而RAM延遲范圍在52～255 μs.物理內(nèi)存的訪問速度是硬盤的訪問速度數(shù)百倍.網(wǎng)絡(luò)延遲大概數(shù)百μs，而對于局域網(wǎng)，速度更快.此外，硬盤及可移動(dòng)閃存 （U-disk）的訪問速度基本差不多.Windows ReadyBoost是一種利用可移動(dòng)閃存來增加內(nèi)存容量的方法，把U-disk的空間當(dāng)作系統(tǒng)內(nèi)存使用，使用ReadyBoost技術(shù)可以使隨機(jī)磁盤讀取性能原則上較傳統(tǒng)的硬盤提高80～100倍.因此，設(shè)計(jì)一個(gè)內(nèi)存網(wǎng)格是可能的.

C.R提出的DPRG［9］包含5種網(wǎng)格節(jié)點(diǎn)和2種頁面訪問服務(wù).網(wǎng)格節(jié)點(diǎn) （available node，busy node，head node，user node和intermediate node）只有一種狀態(tài)，并且通過頁面服務(wù)，可以從一種狀態(tài)變成另外一種狀態(tài).頁面服務(wù)基于OSGA（open grid service architecture）［10］，為所有網(wǎng)格節(jié)點(diǎn)提供統(tǒng)一的訪問接口.實(shí)際上，網(wǎng)格節(jié)點(diǎn)狀態(tài)的改變，需要交換數(shù)據(jù)，可能導(dǎo)致帶寬的浪費(fèi)，而且狀態(tài)轉(zhuǎn)變難以控制.為解決上述問題，本文提出的內(nèi)存網(wǎng)格如圖1所示.其中，RGD（RAM grid database）負(fù)責(zé)記錄各個(gè)網(wǎng)格節(jié)點(diǎn)的空閑內(nèi)存，GRSC（grid RAM scheduling center）負(fù)責(zé)網(wǎng)格內(nèi)存的調(diào)度工作.當(dāng)一個(gè)網(wǎng)格節(jié)點(diǎn)擁有足夠多的空閑物理內(nèi)存，先向RGD注冊，然后才能為其他用戶提供內(nèi)存服務(wù)；當(dāng)一個(gè)網(wǎng)格節(jié)點(diǎn)需要回收內(nèi)存，GRSC將立即作出相應(yīng)動(dòng)作，對分配的內(nèi)存進(jìn)行調(diào)度，保證回收盡快執(zhí)行.

圖1 內(nèi)存網(wǎng)格構(gòu)架Fig.1 A RAM grid architecture

對于User node及Available node的定義如下：

User node：指自身內(nèi)存不夠，利用其它節(jié)點(diǎn)內(nèi)存的網(wǎng)格節(jié)點(diǎn).

Available node：指自身擁有足夠多的內(nèi)存資源.這些物理內(nèi)存包括RAM及U-disk.每個(gè)節(jié)點(diǎn)監(jiān)控自己的內(nèi)存利用率，并基于內(nèi)存供需狀況，決定自身內(nèi)存共享原則.網(wǎng)格節(jié)點(diǎn)向RGD匯報(bào)自身狀況，并擁有不共享自身內(nèi)存的權(quán)限.

2 網(wǎng)格內(nèi)存共享調(diào)度框架

基于上節(jié)分析，內(nèi)存網(wǎng)格能提高網(wǎng)格節(jié)點(diǎn)的內(nèi)存表現(xiàn).當(dāng)網(wǎng)格節(jié)點(diǎn)需要更多內(nèi)存，GRSC負(fù)責(zé)從其他網(wǎng)格節(jié)點(diǎn)借調(diào)更多內(nèi)存，滿足網(wǎng)格節(jié)點(diǎn)需求.內(nèi)存網(wǎng)格的邏輯視圖如圖2.

圖2 網(wǎng)格內(nèi)存調(diào)度構(gòu)架Fig.2 Framework of memory scheduIing

對于每個(gè)網(wǎng)格節(jié)點(diǎn)，LR（local record）記錄給其他網(wǎng)格節(jié)點(diǎn)提供的內(nèi)存頁面情況.當(dāng)某個(gè)網(wǎng)格節(jié)點(diǎn)內(nèi)存不足時(shí)，這個(gè)網(wǎng)格節(jié)點(diǎn)可能從其他節(jié)點(diǎn)獲得更多物理內(nèi)存.如果一個(gè)網(wǎng)格節(jié)點(diǎn)獲得更多物理內(nèi)存，那么這些被分配的內(nèi)存就被這個(gè)網(wǎng)格節(jié)點(diǎn)獨(dú)占.有時(shí)，從其他節(jié)點(diǎn)獲得物理內(nèi)存并不是一種好的方法，不能提供網(wǎng)格節(jié)點(diǎn)表現(xiàn).定義一個(gè)共享的內(nèi)存頁面范圍延遲如下：

Tnett表示網(wǎng)絡(luò)延遲，Tnetd傳輸延遲，Disksize表示硬盤容量，Speednet表示網(wǎng)絡(luò)帶寬.在本文，基于局域網(wǎng)的研究［9］，Tnett=5 μs，Tnetd=3.0 ms，Disksize=4 kb；Speednet=8 MB/s（1～125 MB/s）

本地硬盤的讀取時(shí)間為：

Tmove表示硬盤查找時(shí)間，Td表示硬盤轉(zhuǎn)半圈的時(shí)間，Twait表示硬盤訪問鄰數(shù)據(jù)塊的延遲，Disksize表示硬盤塊的容量，Speeddisk表示硬盤讀取速度.對于典型的硬盤［9］，其參數(shù)取值如下：Tmove=4.9 ms，Td= 3.0 ms，Speeddisk=80 MB/s，Twait=0.2 ms，Disksize=4 KB.

如果Delaygrid＞Delayharddisk，網(wǎng)格節(jié)點(diǎn)就不能從其他網(wǎng)格節(jié)點(diǎn)內(nèi)存獲得資源.因?yàn)榇藭r(shí)，其他網(wǎng)格節(jié)點(diǎn)的內(nèi)存，并不能真正提高需要內(nèi)存的網(wǎng)格節(jié)點(diǎn)的表現(xiàn).

在內(nèi)存網(wǎng)格之中，需要面對的一個(gè)難題是U-disk能自由出入，因此，一些物理內(nèi)存需要交換數(shù)據(jù).內(nèi)存網(wǎng)格不可能大到能為所有網(wǎng)格節(jié)點(diǎn)提供足夠多的內(nèi)存.因此，可以利用內(nèi)存頁面替換策略來替換掉不用的內(nèi)存頁面.常用的替換策略包括FIFO（first-in first-out），LRU（least recently used）和OPT（optimal replacement algorithm）.OPT難以實(shí)現(xiàn)，因此，在模擬實(shí)驗(yàn)中，我們在內(nèi)存網(wǎng)格中測試FIFO策略.

當(dāng)一個(gè)available node需要物理內(nèi)存時(shí)，它先向GSRC申請，GSRC負(fù)責(zé)將內(nèi)存信息遷移到其他available nodes，并在RGD中進(jìn)行記錄.以這種方法，保證本地資源的最高利用權(quán)限.為了保持LR和RGD的一致性，當(dāng)GSRC改變RGD中的記錄時(shí)，LR也及時(shí)更改內(nèi)存頁面記錄.

3 結(jié)果與分析

假設(shè)一個(gè)作業(yè)需要從一個(gè)數(shù)組A獲得數(shù)據(jù)，A包含1 000個(gè)元素，每個(gè)元素A［i］的大小是一個(gè)內(nèi)存頁面的大小，假設(shè)內(nèi)存有300個(gè)頁面，內(nèi)存替換策略采用FIFO.對于網(wǎng)格內(nèi)存，如果一個(gè)網(wǎng)格節(jié)點(diǎn)發(fā)現(xiàn)一個(gè)需要讀或者寫的頁面不在內(nèi)存之中，先從LR中查找，如果有記錄，那么根據(jù)LR從網(wǎng)格內(nèi)存訪問.如果沒有足夠多的內(nèi)存空間，用FIFO策略對頁面進(jìn)行替換，并且被替換掉的頁面存于內(nèi)存中，假設(shè)每個(gè)網(wǎng)格節(jié)點(diǎn)提供100，200，300，400，500個(gè)頁面，我們將比較內(nèi)存和內(nèi)存網(wǎng)格在不同方面的表現(xiàn).

表1顯示，內(nèi)存網(wǎng)格能減少內(nèi)存訪問及替換次數(shù)，同時(shí)，增加了內(nèi)存再次訪問概率.這表明內(nèi)存網(wǎng)格不但為網(wǎng)格節(jié)點(diǎn)提供物理內(nèi)存，而且提高了計(jì)算能力，因?yàn)槿表撔枰狢PU進(jìn)行管理調(diào)度.

表1 內(nèi)存和內(nèi)存網(wǎng)格對比1TabIe 1 Difference of RAM and grid RAM（case 1）

第二個(gè)模式試驗(yàn)研究網(wǎng)格節(jié)點(diǎn)的表現(xiàn)，假設(shè)一個(gè)網(wǎng)格擁有100，300，700，900內(nèi)存頁面，網(wǎng)格內(nèi)存提供500個(gè)內(nèi)存頁面.頁面替換算法采用FIFO.表2顯示，物理內(nèi)存具有關(guān)鍵作用，隨物理內(nèi)存的增加，替換次數(shù)明顯減少.當(dāng)物理內(nèi)存大于需求時(shí)，網(wǎng)格內(nèi)存并沒有作用.

表2 內(nèi)存和內(nèi)存網(wǎng)格對比2TabIe 2 Difference of RAM and grid RAM（case 2）

4 結(jié)語

本文提出了一種內(nèi)存網(wǎng)格構(gòu)架，當(dāng)內(nèi)存不足時(shí)，網(wǎng)格節(jié)點(diǎn)可以共享各個(gè)節(jié)點(diǎn)之間的內(nèi)存，從而提高內(nèi)存容量.內(nèi)存網(wǎng)格以物理內(nèi)存及U-disk為調(diào)度資源，在所有網(wǎng)格節(jié)點(diǎn)之間共享.本文的頁面替換策略是FIFO，如果能預(yù)測下一個(gè)訪問頁面，能進(jìn)一步提高網(wǎng)格內(nèi)存的表現(xiàn).這將是進(jìn)一步研究的方向.近年來，內(nèi)存網(wǎng)格也被一些實(shí)際系統(tǒng)所采用，如多通道處警系統(tǒng)［11］，磁盤緩存系統(tǒng)［12］等.隨著云計(jì)算［13］的發(fā)展，如何在云節(jié)點(diǎn)之間共享內(nèi)存將是一個(gè)待解決的難題.

［1］BURGER D C，HYDER R S，MILLER B P，et al.Paging tradeoffs in distributed-shared-memory multiprocessors［C］// Proceedings of Conference on High Performance Networking and Computing.Washington D C：IEEE，1994：590-599.

［2］LEE S J，SHON T S.Physical memory collection and analysis in smart grid embedded system［J］.Mobile Networks and Applications，2014，19（3）：382-391.

［3］FEELEY M J，MORGAN W E，PIGHIN F H，et al.Implementing global memory management in a workstation cluster［C］//Proceedings of the fifteenth ACM symposium on Operating systems principles.New York：ACM，1995：201-212.

［4］ACHARYA A，SETIA S.The utility of exploiting idle memory for data-intensive computations［R］.Santa Barbara：University of California at Santa Barbara，1998.

［5］HE X F，YANG X Y，LI R，et al.A novel delay-resilient remote memory attestation for smart grid，wireless algorithms，systems，and applications［J］.Lecture Notes in Computer Science，2013，7992：88-99.

［6］CHU R，XIAO N，ZHUANG Y，et al.A distributed paging RAM grid system for wide-area memory sharing［C］//Proc of the 20th Int’l Parallel and Distributed Processing Symp.Rhodes Island：IEEE，2006：88.

［7］PATTERSON D A.Latency lags bandwidth［J］.Communications of the ACM，2004，47：71-75.

［8］TOCZEK T.Stéphane mancini efficient memory management for uniform and recursive grid traversal，algorithmarchitecture matching for signal and image［J］.Lecture Notes in Electrical Engineering，2011，73：27-51.

［9］CHU R，LU X C，XIAO N.A data prefetching algorithm for ram grid［J］.Journal of Software（In Chinese），2006，17（11）：2 234-2 244.

［10］FOSTER I，KESSELMAN C，NICK J，et al.Grid services for distributed system integration［J］.Computer，2002，35（7）：37-46.

［11］張卉，張素偉.于內(nèi)存網(wǎng)格的多通道接處警系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) ［J］.計(jì)算機(jī)與現(xiàn)代化，2014（9）：111-115.

［12］田甜，褚瑞，謝健聰.基于內(nèi)存網(wǎng)格的磁盤緩存設(shè)計(jì)與實(shí)現(xiàn) ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（4）：1-4.

［13］JAMES A，CHUNG J Y.Business and industry specific cloud：challenges and opportunities［J］.Future Generation Computer Systems，2015，48：39-45.

Research on Memory Distributing and Sharing of RAM Grid

LU Jun-wen，CUI Jian-feng，XIAO Lei，ZHUANG Wei-wei，XIE Xiao-zhu
（School of Computer&Information Engineering，Xiamen University of Technology，Xiamen 361024，China）

Based on the analysis of the speed of RAM and U-disk and network widths，we proposed an approach of physical memory sharing of grid nodes and RAM grid managing.Memory can be shared among grid nodes so that their storage capacity is enhanced.Through an analysis of the difference in access time between different grid nodes，the U-disk and the local hard disk，we can decide whether it is efficient to get free physical memory from other grid nodes or U-disk.Simulation test proves that the proposed grid extends RAM，reduces its rate of replacement，and enhances its performance.

memory；RAM grid；sharing；grid database；latency time

TP31

A

1673-4432（2015）03-0075-05

（責(zé)任編輯 曉 軍）

2015-01-19

2015-06-18

盧俊文 （1981-），男，實(shí)驗(yàn)師，碩士，研究方向?yàn)榍度胧较到y(tǒng)、網(wǎng)格計(jì)算.E-mail：jwlu@xmut. edu.cn