制式多處理器下即時排程的增進

Improvements on On-Line Uniform Multiprocessors Scheduling

朱百一(Bie-I Chu)

指導教授 ： 薛智文

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.01306

摘要

無資料

關鍵字

即時 ； 制式 ； 多處理器 ； 最佳 ； 線上 ； 演算法 ； 排程

並列摘要

Scheduling periodic tasks on multiprocessor platform in a hard-real-time environment is one of the fundamental problems in computer science. In this thesis, we consider the problem of on-line scheduling a set of n independent periodic tasks on m uniform processors. We present an optimal scheduling algorithm in the sense that the algorithm is able to schedule any feasible set to meet all deadlines. From previous works, the optimal algorithm gave an O(n) bound for number of task migration and an O(n lg n) bound for time complexity on each rescheduling. But for our algorithm, we reduce both number of task migration and time complexity to O(1) and O(lg n) respectively. Our algorithm
also guarantees minimal schedule length for scheduling non-periodic tasks on uniform multiprocessors.

並列關鍵字

real-time ； uniform ； multiprocessor ； optimal ； on-line ； algorithm ； scheduling

參考文獻

[1] S.K. Baruah, N.K. Cohen, C.G. Plaxton, and D.A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600–625, June 1996.

[2] Shih-Ying Chen and Chih-Wen Hsueh. Optimal dynamic-priority real-time scheduling algorithms for uniform multiprocessors. In Proc. IEEE Real-Time Systems Symposium, pages 147–156, Barcelona, Spain, December 2008.

[3] Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen. An optimal real-time scheduling algorithm for multiprocessors. RTSS, pages 101–110, Oct. 2006.

[4] M.L. Dertouzos and A.K Mok. Multiprocessor online scheduling of hard-real-time tasks. IEEE Transcation on Software Engineering, 15(12):1497–1506, Dec. 1989.

[5] S. Funk, J. Goossens, and S. Baruah. On-line scheduling on uniform multiprocessors. IEEE Real-Time Systems Symposium, pages 183–192, Dec. 2001.