多媒體系統之即時磁碟排程研究

Abstract

多媒體系統對磁碟的存取要求和一般作業系統不同，不僅有其特定之啟始 時間，亦有其特定之完成期限。因此，多媒體磁碟排程研究不僅要達成最 佳之輸出入存取量，更須符合相關之即時限制。本論文針對多媒體系統中 之即時磁碟排程問題，發展多個有效的演算法。所提出之演算法以最早期 限優先(EDF)即時排程做為輸入。在第一個方法中，我們使用『最佳插入( BFI)』法來增進排程之輸出入存取量。而第二個方法，則是採用『橫掃式 群組重排(SGR)』法來重覆地改進排程之輸出入存取量。而橫掃的次數則 為輸入之工作個數。在每一次橫掃中，輸入之工作將被分割成相連的固定 大小群組。而同一群組的工作，則將重排以改進排程結果。除此之外，我 們也介紹一種簡化的SGR(SSGR)法，其橫掃的次數僅為給定之群組大小。 此方法之時間複雜度與傳統的SCAN-EDF法相同，而所得的效果則較佳。在 第三個方法中，我們介紹基於『最大可SCAN群組(MSG)』之『期限更改 SCAN(DMS)』法。此方法不同於SGR法之處，在其用於重排之群組大小並不 固定，而是根據輸入的問題本身作動態調整。此種方式直覺上即會較傳統 固定群組大小的方式好。接下來我們考慮的是兩個結合廣域BFI法及局部 DMS法的演算法。在第一個『DMS或BFI(DMSoBFI)』法中，我們使用一個簡 單的法則，來決定DMS或BF何者較適於所輸入的問題。在第二個『DMS且 BFI(DMSaBFI)』法中，我們先用DMS法來進行局部處理，接著再用BFI法來 進行廣域處理。而這兩種結合方式的輸出入存取量，都較單用DMS法或單 用BFI法為佳。和傳統的SCAN-EDF法相較，所提出之DMSaBFI法在輸出入存 取量上有24%的增進，而在所能支援的要求方面亦有50%的增進。最後，我 們將所提出之演算法實作於UnixWare2.01作業系統上。 Different from the conventional systems, disk requests started on different release times have their assigned deadlines in multimedia systems. Thus, the research issue of disk scheduling is not only to maximize the I/O throughput but also to meet the timing constraints. In this thesis, several algorithms are presented to schedule real-time disk requests in multimedia systems. Our first algorithm applies the best-fit-insertion (BFI) scheme to improve the I/O throughput of the real-time earliest-deadline-first schedule. This global inserting method can obtain better scheduling results than that of the conventional approaches. The second algorithm applies the sweeping-group-reschedule (SGR) strategy to iteratively improve the input schedule. In SGR, the group rescheduling procedure is repeated n times where n is the number of requests. At each iteration, requests in the schedule are decomposed into sets of successive requests, called groups. Requests in the same group are rescheduled to obtain better I/O throughput. We have also introduced a simplified version of SGR (SSGR) which executes only p sweeping iterations where p is the specified group size. Experiments show that SSGR has better solution results than that of SCAN-EDF under the same time complexity. The third approach presented is the deadline-modification-scan (DMS) algorithm with the introduction of maximum-scanable-group (MSG). Different from SGR with constant-sized groups, the sizes of MSGs are automatically decided by the input requests themselves. This approach would be better than the conventional constant-sized schemes. Our next approaches are two hybrid methods proposed to combine the local and the global seek-optimizing schemes. The DMSoBFI approach applies a simple huristic rule to determine which solution scheme would be more suitable for the input requests. Another hybrid algorithm, called DMSaBFI, is started by using DMS to manipulate the local seek-optimization of the real-time requests. Then, BFI is applied to manipulate the global seek-optimization. These hybrid approaches have better I/O throughput than that of either DMS or BFI. Comparing to SCAN-EDF, the proposed DMSaBFI method can obtain 24% improvements in I/O throughput and 50% improvements in supported requests. We have implemented the proposed algorithm to the UnixWare 2.01 operating systems. The implementation results are consistent to our simulations.