Author : 杜家強
Publisher : Open Dissertation Press
ISBN 13 : 9781374723351
Total Pages : 70 pages
Book Rating : 4.7/5 (233 download)
Book Synopsis ON-LINE DEADLINE SCHEDULING UN by : 杜家強
Download or read book ON-LINE DEADLINE SCHEDULING UN written by 杜家強 and published by Open Dissertation Press. This book was released on 2017-01-27 with total page 70 pages. Available in PDF, EPUB and Kindle. Book excerpt: This dissertation, "On-line Deadline Scheduling Under Relaxed Metrics of Optimality" by 杜家強, Kar-keung, To, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled On-line Deadline Scheduling under Relaxed Metrics of Optimality submitted by Kar-Keung To for the degree of Doctor of Philosophy at The University of Hong Kong in August 2000. In this thesis, we study on-line algorithms that schedule jobs with deadlines to one or more processors. By the nature of job deadlines, such scheduling algorithms are classified into hard-deadline algorithms and firm-deadline algorithms. Traditionally, on-line algorithms are measured by metrics like optimality and competitiveness. They compare the on-line algorithm against an off-line adversary, which has full knowledge of the future. Previous results on on-line deadline scheduling were very negative, re- vealing that for most settings, no on-line algorithm can be optimal or achieves constant competitive ratio. This resulted in a situation that although algorithms for deadline scheduling are needed practically, none of them can provide theoretically sound perfor- mance guarantee. Kalyanasundaram and Pruhs [JACM 2000] proposed using relaxed metrics to analyze scheduling algorithms. Such metrics give the on-line algorithms more resources than the off-line adversary, compensating for the lack of future infor- mation experienced by the on-line algorithms. Although this direction seems plausi- ble, the study of optimal deadline scheduling under such metrics has been limited to hard-deadline algorithms. This thesis furthers the study, showing better algorithms for optimal hard-deadline scheduling and extending the study to the more general firm- deadline setting. For multiprocessor hard-deadline scheduling, we give a new algorithm that achieves optimality with less speedy processors than previous algorithms. We also derive a new lower bound of processor speed required by any hard-deadline algorithm to be optimal. For the more general setting of firm-deadline scheduling, we analyze a simple algorithm EDF-AC, which augments EDF (the popular Earliest-Deadline-First algorithm) with a simple notion of admission control. We show that EDF-AC is optimal using speedy processors in both uniprocessor and multiprocessor settings. This is the first result achieving optimality in firm-deadline scheduling. Furthermore, we propose studying the effect of the extra speed required for optimality when extra processors are also available. We find that, for most algorithms we study, the extra speed can be arbitrarilyreduced when enough extra processors are available. The metric of competitiveness can be relaxed just like the metric of optimality. Kalyanasundaram and Pruhs showed a uniprocessor firm-deadline algorithm that is competitive when faster processors are available. We improve their result, lowering the competitive ratio by using a better analysis without modifying the algorithm. More- over, we extend their algorithm to the multiprocessor setting and show that the extended algorithm achieves the same competitive ratio. DOI: 10.5353/th_b3014088 Subjects: Scheduling Real-time data processing Computer algorithms
