硬碟即時排程演算法之研究

Abstract

對即時硬碟排程而言，我們不僅要減少每個行程的硬碟存取時間，同時也必須符合行程的即時限制。以往的方法，如SCAN-EDF和DM-SCAN，利用SCAN演算法來重排輸入排程以減少行程的服務時間。然而，這些方法只有當行程有相同的期限或是在某一有限的區域內，才可以利用SCAN重排，因此所得到的效能有限。例如，在DM-SCAN中，SCAN演算法只有對『每一個最大可SCAN群組(MSG)』，中的行程做重排。除此之外，輸入排程必須是最早期限優先(EDF)的排程。雖然在DM-SCAN中，他們提出了一個更改期限演算法將輸入的以非最早期限優先的排程轉換為最早期限優先(EDF)的排程，但是，因為更改過後的期限小於原本的期限，所以，可被重排的行程將減少，系統的的效能也因此受到影響。 在本論文□，我們提出了一些方法來解決上述的缺失。首先，我們介紹『增大的可重排區域 (E-MSG)』，藉由移除以往MSG一些不必要的限制，一個E-MSG是多個MSG的集合。此外，我們也提出了以『可重排區域(R-Group)』觀念為基礎的RG-SCAN演算法。和以往的演算法不同的是，RG-SCAN對輸入的排程沒有特殊的需求。因此，即使輸入是一個非最早期限優先的排程，RG-SCAN也不需要對任何行程的期限做修改。另外，在重排每一個R-Group後，行程的服務時間將減少，RG-SCAN也利用這個時間空隙而擴展到同時服務即時性及非即時性的行程輸入。 再者，隨著硬體技術的快速進展，現在的硬碟大都配備越來越大的快取記憶體。因此，硬碟的快取記憶體不再只是一個調和硬碟和匯流排速度的緩衝區，它可以暫存相當多的資料來服務更多的行程而避免產生真正的硬碟存取動作。在本論文中，我們也提出了多個cache-aware的即時硬碟排程演算法，藉由在硬碟即時排程中考慮硬碟快取記憶體的因素，使得排程演算法也可以幫助快取記憶體的取代演算法來降低存取快取記憶體失敗的機率。而且，經由考慮硬碟快取記憶體，即時排程演算法對時間的考慮也會更加精確。

For real-time disk scheduling, our goal is to minimize disk access time while guaranteeing tasks’ timing constraints. Previous approaches, such as SCAN-EDF or DM-SCAN (Deadline-Modification-SCAN), applied the SCAN scheme to reschedule service sequence of input tasks to reduce tasks' service time. However, the performance is limited as the seek-optimizing SCAN scheme is only applied to tasks with the same deadline or within a confined group. For example, in DM-SCAN, groups of tasks that can be successfully rescheduled by SCAN under specified real-time requirements are selected, which are called MSGs (Maximum-Scannable-Groups). In addition, input schedule must be in Earliest-Deadline-First (EDF) sequence. In DM-SCAN, a deadline modification scheme was employed to obtain a pseudo EDF sequence from non-EDF ordered input tasks. Because the modified deadlines were earlier than the original ones, number of tasks that could be rescheduled is decreased and thus data throughput is reduced. In this dissertation, we propose methods to solve above problems. First, the concept of Enlarged-Maximum-Scannable-Group (E-MSG) is introduced. By removing excess constraints on MSG, E-MSG merges several MSGs as a new reschedulable group. In addition, we propose RG-SCAN Reschedulable-Group-SCAN (RG-SCAN), a new real-time disk scheduling algorithm using the concept of Reschedulable-Group (R-Group). Differing from previous approaches, RG-SCAN has no limitation on the input task’s sequence. As a result, given a non-EDF schedule, the deadline modification is never used. Besides, by exploiting the service time’s reduction after rescheduling tasks in each R-Group, RG-SCAN has been extended to serve mixed real-time and non-real-time workloads. Furthermore, with the drastically improvement in hardware design technology, modern disk drives are equipped with increased capacity of on-disk cache buffer. As a result, instead of just being a speed-matching buffer, disk cache also services much more disk requests without incurring the physical disk access. We propose cache-aware real-time disk scheduling algorithms to consider caching effect during scheduling. The scheduling algorithm can thus help the cache replacement scheme to minimize the cache miss ratio. In addition, the timing consideration of a real-time scheduling algorithm is more accurate as the cache effect is taken into consideration.