File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Performance guarantee for online deadline scheduling in the presence of overload

TitlePerformance guarantee for online deadline scheduling in the presence of overload
Authors
KeywordsMathematics computers
Algorithms
Measurement
Performance
Theory
Verification
Issue Date2001
PublisherSociety for Industrial and Applied Mathematics.
Citation
The 12th Annual ACM - SIAM Symposium on Discrete Algorithms, Washington, DC., 7-9 January 2001. In The Annual ACM - SIAM Symposium on Discrete Algorithms Proceedings, 2001, p. 755-764 How to Cite?
AbstractEarliest 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 Identifierhttp://hdl.handle.net/10722/45631
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorTo, KKen_HK
dc.date.accessioned2007-10-30T06:30:41Z-
dc.date.available2007-10-30T06:30:41Z-
dc.date.issued2001en_HK
dc.identifier.citationThe 12th Annual ACM - SIAM Symposium on Discrete Algorithms, Washington, DC., 7-9 January 2001. In The Annual ACM - SIAM Symposium on Discrete Algorithms Proceedings, 2001, p. 755-764en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45631-
dc.description.abstractEarliest 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.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofThe Annual ACM - SIAM Symposium on Discrete Algorithms Proceedings-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectMathematics computersen_HK
dc.subjectAlgorithms-
dc.subjectMeasurement-
dc.subjectPerformance-
dc.subjectTheory-
dc.subjectVerification-
dc.titlePerformance guarantee for online deadline scheduling in the presence of overloaden_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1071-9040&volume=&spage=755&epage=764&date=2001&atitle=Performance+guarantee+for+online+deadline+scheduling+in+the+presence+of+overloaden_HK
dc.identifier.emailLam, TW: twlam@cs.hku.hk-
dc.identifier.authorityLam, TW=rp00135-
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-64049107305-
dc.identifier.hkuros57741-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-64049107305&selection=ref&src=s&origin=recordpage-
dc.identifier.spage755-
dc.identifier.epage764-
dc.identifier.scopusauthoridLam, TW=7202523165-
dc.identifier.scopusauthoridTo, KK=36785812300-
dc.customcontrol.immutablesml 160105 - merged-
dc.provenanceUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats