請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10525完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 薛智文 | |
| dc.contributor.author | Bie-I Chu | en |
| dc.contributor.author | 朱百一 | zh_TW |
| dc.date.accessioned | 2021-05-20T21:36:29Z | - |
| dc.date.available | 2010-08-18 | |
| dc.date.available | 2021-05-20T21:36:29Z | - |
| dc.date.copyright | 2010-08-18 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-08-16 | |
| dc.identifier.citation | [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. [6] K.S. Hong and J.Y.-T. Leung. On-line scheduling of real-time tasks. RTSS, pages 244–250, Dec. 1988. [7] Edward C. Horvath, Shui Lam, and Ravi Sethi. A level algorithm for preemptive scheduling. Journal of the ACM, 24(1):32–43, January 1977. [8] C. L. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 10(1):46–61, 1973. [9] Jane W. S. Liu and C. L. Liu. Performance analysis of heterogeneous multiprocessor computing systems. Computer Architectures and Networks, 1974. [10] Jane W. S. Liu and Ai-Tsung Yang. Optimal scheduling of independent tasks on heterogeneous computing systems. ACM Annual Conference, 1:38–45, 1974. [11] R.R. Muntz and E.G. Coffman. Optimal preemptive scheduling on two-processor systems. IEEE Transactions on Computers, (11):1014–1020, Nov. 1969. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10525 | - |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-20T21:36:29Z (GMT). No. of bitstreams: 1 ntu-99-R97922158-1.pdf: 349828 bytes, checksum: 75d3fe025c530b6a99252f203f0fae38 (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | 1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Multiprocessor Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Optimal Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.3 On-line Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Contributions and Organizations . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Definitions, Assumptions, and Feasibility Condition for Uniform Multipro- cessors 5 2.1 Definitions and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Feasibility Condition for Uniform Multiprocessors . . . . . . . . . . . . . . . . . 7 2.3 Independent Feasible Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Separability of Feasible Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Precaution Cut Greedy Algorithm and The T-Ler Plane 12 3.1 T-Ler Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Definitions in One T-Ler Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 Events in One T-Ler Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.4 The Precaution Cut Greedy Algorithm . . . . . . . . . . . . . . . . . . . . . . . 18 4 Optimal Scheduling Algorithm for Uniform Processors 21 4.1 Task Groups and Group Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 The Random Divide Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Proof of Optimality of RD Scheduling Algorithm . . . . . . . . . . . . . . . . . 27 4.4 The Precaution Group Merge Algorithm . . . . . . . . . . . . . . . . . . . . . . 31 4.5 Proof of Optimality of PGM Scheduling Algorithm . . . . . . . . . . . . . . . . 34 4.6 The Preprocessed Precaution Group Merge Algorithm . . . . . . . . . . . . . . . 41 4.7 Proof of Optimality of PPGM Scheduling Algorithm . . . . . . . . . . . . . . . 44 5 Complexity Analysis 49 5.1 Analysis of RD Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2 Analysis of PGM Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . . 51 5.3 Analysis of PPGM Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . 52 6 Conclusions 54 Bibliography 55 | |
| dc.language.iso | en | |
| dc.title | 制式多處理器下即時排程的增進 | zh_TW |
| dc.title | Improvements on On-Line Uniform Multiprocessors Scheduling | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳敬,張榮貴 | |
| dc.subject.keyword | 即時,制式,多處理器,最佳,線上,演算法,排程, | zh_TW |
| dc.subject.keyword | real-time,uniform,multiprocessor,optimal,on-line,algorithm,scheduling, | en |
| dc.relation.page | 57 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2010-08-17 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-99-1.pdf | 341.63 kB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。