loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Robustness Results Concerning EDF Scheduling upon Uniform Multiprocessors
September 2003 (vol. 52 no. 9)
pp. 1185-1195
ASCII Text
x 
 
Sanjoy Baruah, Shelby Funk, Jo? Goossens, "Robustness Results Concerning EDF Scheduling upon Uniform Multiprocessors," IEEE Transactions on Computers, vol. 52, no. 9, pp. 1185-1195, September, 2003.
 
 
BibTex
x
 
@article{ 10.1109/TC.2003.1228513,
author = {Sanjoy Baruah and Shelby Funk and Jo? Goossens},
title = {Robustness Results Concerning EDF Scheduling upon Uniform Multiprocessors},
journal ={IEEE Transactions on Computers},
volume = {52},
number = {9},
issn = {0018-9340},
year = {2003},
pages = {1185-1195},
doi = {http://doi.ieeecomputersociety.org/10.1109/TC.2003.1228513},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Computers
TI - Robustness Results Concerning EDF Scheduling upon Uniform Multiprocessors
IS - 9
SN - 0018-9340
SP1185
EP1195
EPD - 1185-1195
A1 - Sanjoy Baruah,
A1 - Shelby Funk,
A1 - Jo? Goossens,
PY - 2003
KW - Uniform multiprocessors
KW - hard-real-time systems
KW - resource augmentation
KW - earliest deadline first
KW - robustness.
VL - 52
JA - IEEE Transactions on Computers
ER -
 

Abstract—Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s x t) units of execution. The earliest-deadline-first (EDF) scheduling of hard-real-time systems upon uniform multiprocessor machines is considered. It is known that online algorithms tend to perform very poorly in scheduling such hard-real-time systems on multiprocessors; resource-augmentation techniques are presented here that permit online algorithms in general (EDF in particular) to perform better than may be expected given these inherent limitations. It is shown that EDF scheduling upon uniform multiprocessors is robust with respect to both job execution requirements and processor computing capacity.

[1] 1185 M. Dertouzos, Control Robotics: The Procedural Control of Physical Processors Proc. IFIP Congress, pp. 807-813, 1974.[2] M.L. Dertouzos and A.K. Mok, Multiprocessor On-Line Scheduling of Hard-Real-Time Tasks IEEE Trans. Software Eng., vol. 15, no. 12, pp. 1497-1505, 1989.[3] K. Hong and J. Leung, On-Line Scheduling of Real-Time Tasks Proc. Real-Time Systems Symp., pp. 244-250, Dec. 1988.[4] B. Kalyanasundaram and K. Pruhs, Speed Is as Powerful as Clairvoyance Proc. 36th Ann. Symp. Foundations of Computer Science (FOCS '95), pp. 214-223, Oct. 1995.[5] C.L. Liu and J.W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” J. ACM, vol. 20, no. 1, pp. 40-61, 1973.[6] A. Mok, Task Management Techniques for Enforcing ED Scheduling on a Periodic Task Set Proc. Fifth IEEE Workshop Real-Time Software and Operating Systems, pp. 42-46, May 1988.[7] A.K. Mok, Fundamental Design Problems of Distributed Systems for Hard Real-Time Environments, Doctoral Thesis TR-297, MIT, Laboratory for Computer Science, Cambridge, Mass., 1983.[8] C.A. Phillips, C. Stein, E. Torng, and J. Wein, Optimal Time-Critical Scheduling via Resource Augmentation Proc. 29th Ann. ACM Symp. Theory of Computing, pp. 140-149, May 1997.

Index Terms:
Uniform multiprocessors, hard-real-time systems, resource augmentation, earliest deadline first, robustness.
Citation:
Sanjoy Baruah, Shelby Funk, Jo? Goossens, "Robustness Results Concerning EDF Scheduling upon Uniform Multiprocessors," IEEE Transactions on Computers, vol. 52, no. 9, pp. 1185-1195, Sept. 2003, doi:10.1109/TC.2003.1228513
Usage of this product signifies your acceptance of the Terms of Use.