MEMS也即微機電系統，電子專業的朋友對MEMS都具備一定認識。在往期文章中，小編對MEMS交換、MEMS封裝等有所介紹。為增進大家對MEMS的了解程度，本文中小編將對MEMS存儲設備的請求調度算法以及數據布局策略予以介紹。

　　引言

　　MEMS（MicroElectromechanicalSystem，微機電系統）存儲器是一種新型存儲器件，具有高密度、低功耗、非易失、多探針并行訪問等特點，相對于傳統磁盤具有明顯優勢。可以填補RAM和磁盤之間的性能差距，可在計算機系統中承擔多種角色，為新型高性能海量存儲系統結構研究帶來新思路和新方法。

　　MEMS存儲設備的請求調度算法

　　（一）磁盤的請求調度算法

　　第一種是最簡單的、性能最差的先來先服務（FCFS）：第二種算法是循環查找（CLOOKLBN）。這種算法是按照LBN升序的方式進行服務，也就是說當所有請求的LBN都落后于當前請求的LBN話，就從涉及到最小LBN的請求開始服務：第三種是最短尋址時間優先（sSTF—BN），主要思想是選擇具有最小尋址延遲的請求，但是在實際應用中卻很少使用。因為很少有主機操作系統具有用計算實際尋址距離或者預測尋址時問的信息，考慮到磁盤LBN到物理位置的映射的關系，大部分的SSTF算法使用的是最近訪問的LBN和目標LBN之間的距離作為訪問時間的近似，這種簡化對磁盤是有效的：第四種是最短定位時間優先算法（SPTF），選擇具有最小定位延遲的請求，對磁盤來說，SPTF算法與其它算法顯著的不同在于它需要考慮尋道時間和旋轉延遲。

　　將四種調度算法應用到Atalalok上，統計隨機負載在不同的請求到達頻率下Atlasl0k的響應時間。FCFS的性能是四種調度算法中性能最差的，同時，FCFS的性能隨著負載請求的增加性能最快達到飽和。SSTFesLBN的性能比CLOOKLBN要好，SPTF的性能最好，而且SPTF性能達到飽和的速度最慢。

　　前三種調度算法（（FCFSCLOOKLBN和SSTFesLBN）可以利用主機的軟件系統簡單有效的實現。考慮到磁盤LBN到物理位置的映射關系，實現這三種調度算法不需要詳細的設備信息，只需要根據請求的LBN號來選擇要服務的請求。SPTF算法通常是在磁盤驅動器的固件中實現，SPTF算法需要磁盤狀態的準確信息、LBN到物理位置的映射信息、尋址時間和旋轉延遲的準確預測信息等。

　　（二）MEMS存儲設各請求調度算法

　　為了方便的將MEMS存儲設備應用到計算機系統中，MEMS存儲設備利用與磁盤相同的接口。為了證明現有的磁盤請求調度算法同樣適用于MEMS存儲設備，將上節中四種磁盤的請求調度算法應用到MEMS存儲設備上。多數的請求調度算法，如SSTFLBN和CLOOKLBN，只需要知道LBN的信息，將LBN之間的距離作為定位時間的估計。SPTF算法涉及到尋址時間和旋轉延遲。而MEMS存儲設備只存在x軸和Y軸方向的尋址，沒有旋轉延遲。與磁盤相同的是，尋址時間是一維的，接近一個線性的LBN空間。與磁盤不同的是，MEMS存儲設備在兩個方向的尋址是并行完成的，選擇較大的作為實際的尋址時間。由于x軸方向存在穩定時間，x軸方向的尋址時間總是比Y軸大。如果Y軸的尋址時間比較大，SPTF的性能僅比SSTF略有優勢。利用Disksim。將磁盤的調度算法應用到MEMS存儲設備上，統計不同的請求到達頻率的隨機負載下的平均響應時間。

　　四種調度算法在MEMS存儲設備上具有和磁盤類似的性能：FCFS性能最差，SPTF性能最好。但是，FCFS和基于LBN的算法之問的差距比磁盤小。因為在MEMS存儲設備尋址時間在整個服務時間中占很大比例。CLOOKLBN和SSTFLBN性能差距要比磁盤小。

　　三數據布局策略

　　（一）小粒度非順序訪問

　　MEMS存儲設備數據訪問具有與磁盤類似的特性，短距離尋址比長距離尋址要快。與磁盤不同的是，由于彈簧的回復力的存在，使得不同位置上觸動器作用力的影響不同。彈簧作用力對每個tip的訪問區域不同位置的影響。彈簧的作用力隨著sled位移的增加而增大，對于短距離來說定位時間反而較長。因此，在考慮查找小粒度、常用的數據項的時候，除了考慮尋址距離，還要考慮sled距中心位置的距離。

　　（二）大粒度順序訪問

　　MEMS存儲設備和磁盤的流傳輸速率相似：Atals10K的流傳輸速率是17，3-25，2MB/s，MEMS存儲設備的流傳輸速率為75，9MB/s。MEMS存儲設備的定位時間比磁盤低一個數量級，對MEMS存儲設備來說，定位時間對于大批量數據傳輸影響很小。例如：一個256KB的讀請求在X軸不同位置上的服務時間，在1250個柱面的不同請求之間的服務時間僅差10%。同時減少了大粒度、順序傳送的數據對局部性的需求。但是，對磁盤來說，尋址距離是影響尋址時間的重要因素。同樣，對一個256KB大小的請求，長距離尋址時間可以使整個服務時間增加1倍。

　　（三）雙向數據布局

　　為充分利用MEMS存儲設備的訪問特性，引入了一種雙向布局策略。小數據存放在最中間的小區域中，大的、順序的流數據存放在外圍的小區域中。這種策略可以采用5X5的網格方式實現。

　　在假設各個請求內部不存在相關性的前提下，比較雙向布局、“organpipe”布局和一種優化的磁盤布局的性能。在“organpipe”布局策略中，最經常訪問的文件存放在磁盤最中間的磁道上，使用頻率稍差的文件存放在中間磁道的兩側，最不經常使用的文件存放在靠近最內部和最外部磁道上。這種布局策略對磁盤是優化的，缺點是需要根據文件的使用頻率定期的移動文件，還需要維護文件的一些狀態來記錄文件的使用頻率。
責任編輯人：CC