Competitive deadline scheduling via additional or faster processors

Competitive deadline scheduling via additional or faster processors

0.00 Avg rating0 Votes
Article ID: iaor2008160
Country: United Kingdom
Volume: 6
Issue: 2
Start Page Number: 213
End Page Number: 223
Publication Date: Mar 2003
Journal: Journal of Scheduling
Authors: , , ,
Abstract:

This paper studies on-line scheduling in a single-processor system that allows preemption. The aim is to maximize the total value of jobs completed by their deadlines. It is known that if the on-line scheduler is given a processor faster (say, two times faster) than the off-line scheduler, then there exists an on-line algorithm called SLACKER that can achieve an O(1) competitive ratio. In this paper, we show that using additional unit-speed processors instead of a faster processor is a possible but not cost effective way to achieve an O(1) competitive ratio. Specifically, we find that – Θ(log k) unit-speed processors are required, where k is the importance ratio. Another contribution of this paper is an improved analysis of the competitiveness of SLACKER; this new analysis enables us to show that SLACKER, when extended to multi-processor systems, can still guarantee an O(1) competitive ratio.

Reviews

Required fields are marked *. Your email address will not be published.