Design and Implemenation of a Self-Adaptive Disk Schduling Algorithm Using Cross-Layer Information

Abstract

In the last decade, the performance improvement of hard disk drives have laggedpainfully far behind that of the processors. This gap is getting more widened with theextremely performance improvement of CPU technologies. For example, CPU technology hasbeen upgraded from hyperthreading to multi-core while the performance of a disk is stillconstrained by its mechanical operations. There have been many researches proposed to breakthe disk bottleneck. However, due to the layered architecture, most of previous schemes relyon single-layered knowledge to improve its algorithm. Due to the narrow informationobtained in each layer, the performance improvement of each layer is thus limited.Consequently, we propose this research project to design and implement a self-adaptivedisk scheduling algorithm utilizing cross-layer optimization. Firstly, we will design across-layered architecture that enables information sharing among each layer. After designingthe architecture, we then determine what information can be explored in each layer. Finally,we will design a flexible and self-adaptive disk scheduling algorithm that can automaticallyadapt its behavior according to the current information and status explored by each layer. Wewill implement our architecture and algorithm in the Linux kernel to experiment and verifyour proposed scheme.By this project, we will investigate and propose a cross-layer optimization scheme todisk storage subsystem. Besides, we will also design and implement a more efficient diskscheduling algorithm to enhance the performance of disk accesses, and so as to decrease theperformance gap between CPUs and disks.

從hyperthreading 到multi-core，隨著CPU 技術的快速進展，如何進一步提升硬碟的效能，縮短硬碟和CPU 在速度上的差異已經是一件刻不容緩的事。雖然之前有許多研究探討如何提升硬碟的存取效率，不過，如同網路協定，硬碟檔案I/O 的存取架構也被區分為數個層級。因此，以往的研究多只侷限於單一層級內部的效能改善，也就是只利用單一層級的資訊來改善此一層級的演算法。因為單一層級內部的資訊有限，這樣的分層架構因而限制了每一層級在效能上進一步提升的可能性。有鑑於此，我們提出了這個研究計畫，設計並實作一個可利用跨階層資訊，具備彈性、可自我調整的硬碟排程演算法。首先，我們將設計一個應用於硬碟檔案I/O、跨階層資訊分享的系統架構；其次，我們將決定每一個層級可以提供分享的資訊；有了這些資訊之後，我們將設計一個硬碟排程演算法，可以根據不同跨階層的資訊，自我調整以適應於當時各個層級的環境與特色。最後，我們將實作於Linux 作業系統，驗證並實驗我們所提出的方法。經由本研究計畫，我們將對如何達到跨階層資訊分享的架構與設計有一完整的探討，並將提出一個更具有效率的硬碟排程演算法，縮短硬碟和電腦系統內其它電子元件在速度上的落差。