- 學位論文
內文切換即時排程演算法之研究
A Study on the Scheduling Algorithm for Real Time Context Switching
摘要
隨著人們對於即時多媒體服務如影音串流及網路電話等的需求與日俱增，如何提供品質良好的即時多媒體應用，早已成為一項重要的議題。目前影響即時多媒體品質的很多原因中，影響最大的不外乎為網路連線品質或是處理器排程的效能表現。在過去的處理器排程方法中，大多把焦點放在如何公平地分配或是預留資源給不同類型的工作，或是就工作的重要性來排定程序處理的優先順序；這些排程方法中，大多沒有考慮記憶體搬移或儲存程序資訊所必須耗費的時間，也就是「內文切換」對處理器效能的影響，而事實上，過度頻繁的內文切換會讓處理器花費額外不需要的時間在記憶體的搬移上，使真正用在運算程式碼上的資源被壓縮、運算時間被拉長。對於即時多媒體的應用，還會影響它的表現，例如延遲時間與jitter變大，導致聲音或影像的品質變差。 在本篇論文中，將考慮內文切換對處理器資源的影響，提出「減耗型」及「預知型」兩種排程演算法；其中「減耗型」排程法之設計原理為減少不必要之內文切換的次數，使系統資源的使用上更為經濟，進而保障即時多媒體應用的品質；「預知型」排程法之設計原理為在接受新的即時多媒體連線時，根據其應用類型而將此連線所需之資源分配給它，確保每一即時連線皆能擁有充足的運算資源，進而保障多媒體應用的表現。此二項設計經由模擬驗證其效能並與Earliest Deadline First（EDF）、First Come First Serve（FIFO）和Start-time Fair Queueing（SFQ）之演算法比較，經驗證，其中減耗型排程法在系統可能滿載的情形下，可以有效地提升處理器之效能，提升即時多媒體應用的品質；預知型排程在犧牲非即時部分程序品質的情形下，則有最好的即時多媒體品質表現。
並列摘要
With the growth of the demand for real time multimedia services (such as video streaming, and VoIP, etc), providing high quality real time services becomes an issue. Among the many factors affecting the performance, the connection speed and the efficiency of the CPU scheduling algorithm are the main factors. In the past CPU scheduling algorithms, they usually focus on how to fairly allocate or reserve resources for different processes, or arrange the processing sequence based on these processes priority. Among these scheduling algorithms, they usually do not consider the effect of the Context-Switch on the CPU efficiency, that is, the expending time on memory movement and the process information storage. In fact, frequent Context-Switching may lead to high overhead, and lengthen the computing time of processes. Further more, it may affect the quality of real time processes, for example, leading to larger delay, jitter, dropping ratio, etc. In this thesis, we consider the effect of Context-Switch on CPU efficiency and propose two CPU scheduling algorithms, called “Context-Switch Overhead aware” and “Pre-Informed” scheduling algorithm. The design philosophy of Context-Switch Overhead aware scheduling algorithm is to reduce the number of Context-Switch operations, to make the resource usage more efficient, and then increase the quality of real time multimedia applications. When new real time requests arrive, the Pre-Informed scheduling algorithm will allocate required resources to these tasks based on their application types. It will then ensure every real time request has enough computing resource to protect and improve the performance of the multimedia application. The efficiency of these two designs is validated by simulation experiments, and then are compared with Earliest Deadline First (EDF), First Come First Serve (FIFO), and Start-time Fair Queueing (SFQ) scheduling algorithms. In CPU overloaded situation, the Context-Switch Overhead aware scheduling algorithm can raise the effective efficiency of the system, and then promote the quality of the real time application. If the demand of the performance of non real time processes is not high, the quality of the real time multimedia applications of Pre-Informed scheduling algorithm is the best.
參考文獻
延伸閱讀
- 曾威竣（2014）。適用於部分更新LMS演算法之切換式時變步階設計〔碩士論文，國立宜蘭大學〕。華藝線上圖書館。https://doi.org/10.6820/NIU.2014.00023
- 吳柏鋒（2004）。改進最佳成對序列比對之修剪演算法〔碩士論文，元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611291803
- Wen, W. H. (2008). 多核心即時系統上的線上排程問題研究 [doctoral dissertation, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2008.00604
- 林雯涵（2011）。A Single Machine Scheduling Problem With Weighted Learning Effect〔碩士論文，國立虎尾科技大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0028-2207201120491600
- 鍾乙銓（2012）。A Novel Distributed Scheduling Algorithm for Vehicular Networks〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2012.01254