An Efficient Real-time Disk-scheduling Framework with Adaptive Quality Guarantee

具可調整品質保證的高效率即時硬碟排程架構

蔡承翰(Cheng-Han Tsai)

指導教授 ： 黃泰一 ； 金仲達

國立清華大學/電機資訊學院/資訊工程學系/博士(2008年)

摘要

多媒體伺服器需要即時硬碟排程式演算法來提供即時串流等時性的資料。 傳統的硬碟排程演算法致力於提供優良的，但不被保證的服務品質，所以非週期性工作的回應時間總是被犧牲來追求完美的串流服務品質。 在這篇論文裡，我們提出一個全新的即時硬碟排程演算法，稱為WRR-SCAN~(Weighted-Round-Robin-SCAN)，在可變動資料率及有限非週期性工作回應時間的前提下，對所有服務中的串流提供服務品質保證。 WRR-SCAN將一個即時串流切分成必要及非必要的工作，系統將服務任何一個串流只要它的必要工作可以確定在期限前完成。 服務與否的決定可以在O(1)的時間完成，因為WRR-SCAN保留固定的頻寬給每個即時串流。 在系統執行的同時，WRR-SCAN以一個積極的方式來動態回收沒有使用到的頻寬，回收的頻寬將被使用在服務非必要的任務或是其他的非週期性工作。 為了確定WRR-SCAN的潛力，我們用一個系列的模擬來比較WRR-SCAN及SCAN-EDF的效能；SCAN-EDF是最具代表性的即時硬碟排程演算法。 實驗結果指出WRR-SCAN成功地提供非週期性任務一個被保證的最小資料率，同時所有的即時任務也可以在期限前完成。

關鍵字

可調整性品質保證 ； 即時硬碟排程演算法

並列摘要

A multimedia server requires a real-time disk-scheduling algorithm to deliver isochronous data for real-time streams. Traditional disk-scheduling algorithms focus on providing good quality in a best-effort manner. In this paper, we propose a novel real-time disk-scheduling algorithm called WRR-SCAN (Weighted-Round-Robin-SCAN) to provide quality guarantees for all in-service streams encoded at variable bit rates and bounded response times for aperiodic jobs. WRR-SCAN divides a real-time stream into guaranteed jobs and optional jobs. The admission control admits a stream as long as its guaranteed jobs are satisfied. Such a decision is made in O(1) time as WRR-SCAN reserves a fixed weight for each stream. WRR-SCAN incorporates an aggressive policy to dynamically reclaim unused bandwidth during run-time. The reclaimed bandwidth is used to serve optional jobs or more aperiodic jobs. We conducted a set of simulations to compare WRR-SCAN with a set of referred disk-scheduling algorithms. The evaluations are conducted on a commonly-used disk simulator with traces from a real multimedia server. The experimental results show that WRR-SCAN provides significantly better quality for real-time streams and yields considerably shorter response times for aperiodic jobs.

並列關鍵字

Adaptive Quality Guarantee ； real-time disk-scheduling algorithms ； weighted round-robin

參考文獻

[8] H.-P. Chang, R.-I. Chang, W.-K. Shin, and R.-C. Chang. Cache-Aware

[15] W.-C. Feng, P. P. Mishra, and K. K. Ramakishnan. A Comparison of

[10] T.-S. Chen, W.-P. Yang, and R. C. T. Lee. Amortized Analysis of Some

[61] Y. Wang, S. Panwar, S. Lin, and S. Mao. Wireless video transport using

[1] A. L. Narasimha Reddy and J. Wyllie. I/O Issues in a Multimedia