File Download
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Performance guarantee for online deadline scheduling in the presence of overload
Title | Performance guarantee for online deadline scheduling in the presence of overload |
---|---|
Authors | |
Keywords | Mathematics computers Algorithms Measurement Performance Theory Verification |
Issue Date | 2001 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | The 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC., 7-9 January 2001. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, p. 755-764 How to Cite? |
Abstract | Earliest deadline first (EDF) is a widely-used online algorithm for scheduling jobs with deadlines in real-time systems. Yet, existing results on the performance guarantee of EDF are limited to underloaded systems [6,12,14]. This paper initiates the study of EDF for overloaded systems, attaining similar performance guarantees as in the underloaded setting. Specifically, we show that EDF with a simple form of admission control is optimal for scheduling on both uniprocessor and multiprocessors when moderately faster processors are available (our analysis actually admits a tradeoff between speed and extra processors). This is the first result attaining optimality under overload. Another contribution of this paper is an improved analysis of the competitiveness for weighted deadline scheduling. |
Persistent Identifier | http://hdl.handle.net/10722/45631 |
ISSN | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | To, KK | en_HK |
dc.date.accessioned | 2007-10-30T06:30:41Z | - |
dc.date.available | 2007-10-30T06:30:41Z | - |
dc.date.issued | 2001 | en_HK |
dc.identifier.citation | The 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC., 7-9 January 2001. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, p. 755-764 | en_HK |
dc.identifier.issn | 1071-9040 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/45631 | - |
dc.description.abstract | Earliest deadline first (EDF) is a widely-used online algorithm for scheduling jobs with deadlines in real-time systems. Yet, existing results on the performance guarantee of EDF are limited to underloaded systems [6,12,14]. This paper initiates the study of EDF for overloaded systems, attaining similar performance guarantees as in the underloaded setting. Specifically, we show that EDF with a simple form of admission control is optimal for scheduling on both uniprocessor and multiprocessors when moderately faster processors are available (our analysis actually admits a tradeoff between speed and extra processors). This is the first result attaining optimality under overload. Another contribution of this paper is an improved analysis of the competitiveness for weighted deadline scheduling. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. | en_HK |
dc.relation.ispartof | Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms | - |
dc.rights | © 2001 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms in 2001, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Mathematics computers | en_HK |
dc.subject | Algorithms | - |
dc.subject | Measurement | - |
dc.subject | Performance | - |
dc.subject | Theory | - |
dc.subject | Verification | - |
dc.title | Performance guarantee for online deadline scheduling in the presence of overload | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Lam, TW: twlam@cs.hku.hk | - |
dc.identifier.authority | Lam, TW=rp00135 | - |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.scopus | eid_2-s2.0-64049107305 | - |
dc.identifier.hkuros | 57741 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-64049107305&selection=ref&src=s&origin=recordpage | - |
dc.identifier.spage | 755 | - |
dc.identifier.epage | 764 | - |
dc.publisher.place | United States | - |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | - |
dc.identifier.scopusauthorid | To, KK=36785812300 | - |
dc.customcontrol.immutable | sml 160105 - merged | - |
dc.identifier.issnl | 1071-9040 | - |