在混合式硬碟上以CPU排程感知的資料放置演算法

A Scheduling Aware Data Placement Algorithm for Hybrid Hard Drive

劉彥伶(Liu, Yenling)

指導教授 ： 羅習五

國立中正大學/工學院/資訊工程學系/碩士(2012年)

摘要

NAND flash memory drives較傳統硬碟有低耗電、高抗震、體積小、random I/O效能高的優點，因此有很多mobile system都採用NAND flash memory drives當作它們的secondary storage device，如：PDA、MP3 player；但傳統硬碟在價格、容量以及對sequential I/O效能上，仍有較高的優勢；因此，混合式硬碟(hybrid hard-disk drive)的產生，正是結合了NAND flash memory drives與傳統硬碟的優點(如：較大的容量、較好的I/O 效能)。

在本論文中，我們使用virtual blocking time來代表某個I/O對於使用者經驗的重要性；virtual blocking time的概念是從Linux中的complete fair scheduling (CFS)演算法所推導出來的；我們藉由將那些virtual blocking time較長的I/O放到flash drives中，以增進使用者經驗；最後以實驗來驗證我們所提出的演算法在效能的表現。

關鍵字

混合式硬碟 ； 完全公平排程

並列摘要

Comparing to hard disk drives, NAND flash memory drives have the advantages of low power consumption, high shock resistance, small size, and good random I/O performance. Therefore, many mobile systems, such as PDA and MP3 player, use NAND flash memory drive as a secondary storage device. However, a hard disk drive still has the advantages in prices, capacity, and sequential I/O performance. Hence, it would be better to have a hybrid drive having both advantages (e.g., higher capacity and I/O performance) of NAND flash memory drive and hard disk drive.

In this thesis we use virtual blocking time to indicate the importance of an I/O to user experience. The concept of virtual blocking time is derived from Linux's scheduling algorithm named complete fair scheduling (CFS). To improve user experience, we allocate an I/O having longer virtual blocking time in a flash drive. Extensive experiments have been performed to illustrate the performance of the proposed algorithm.

並列關鍵字

hybrid hard-disk drive ； complete fair scheduling

參考文獻

[2] V. Vellanki and A. Chervenak. A cost-benefit scheme for high performance predictive prefetching. InProceedings of the ACM/IEEE Conference on Supercomputing, 1999.

[3] Xiaoning Ding, Song Jiang, Feng Chen, Kei Davis, and Xiaodong Zhang. Diskseen: exploit-ing disk layout and access history to enhance i/o prefetch. In Proceedings of the USENIX Annual Technical Conference, 2007.

[5] Yang Liu, Jianzhong Huang, Changsheng Xie, and Qiang Cao. Raf: A random access first cache management to improve ssd-based disk cache. InProceedings of the Fifth IEEE Inter-national Conference on Networking, Architecture and Storage, 2010.

[14] T. Bisson, S.A. Brandt, and D.D.E. Long. Nvcache: Increasing the effectiveness of disk spin-down algorithms with caching. InProceedings of the 14th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2006.

[15] Feng Chen, Song Jiang, and Xiaodong Zhang. Smartsaver: Turning flash drive into a disk energy saver for mobile computers. InProceedings of the 2006 International Symposium on Low Power Electronics and Design, 2006.