File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Performance guarantee for EDF under overload

TitlePerformance guarantee for EDF under overload
Authors
KeywordsEarliest deadline first
Extra-resource analysis
Firm deadline scheduling
Online algorithms
Issue Date2004
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor
Citation
Journal Of Algorithms, 2004, v. 52 n. 2, p. 193-206 How to Cite?
AbstractEarliest deadline first (EDF) is a widely used algorithm for online deadline scheduling. It has been known for long that EDF is optimal for scheduling an underloaded, single-processor system; recent results on the extra-resource analysis of EDF further revealed that EDF when using moderately faster processors can achieve optimal performance in the underloaded, multi-processor setting. This paper initiates the extra-resource analysis of EDF for overloaded systems, showing that EDF supplemented with a simple form of admission control can provide a similar performance guarantee in both the single and multi-processor settings. © 2003 Elsevier Inc. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/48426
ISSN
2011 Impact Factor: 0.5
2012 SCImago Journal Rankings: 0.469
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorNgan, TWJen_HK
dc.contributor.authorTo, KKen_HK
dc.date.accessioned2008-05-22T04:12:41Z-
dc.date.available2008-05-22T04:12:41Z-
dc.date.issued2004en_HK
dc.identifier.citationJournal Of Algorithms, 2004, v. 52 n. 2, p. 193-206en_HK
dc.identifier.issn0196-6774en_HK
dc.identifier.urihttp://hdl.handle.net/10722/48426-
dc.description.abstractEarliest deadline first (EDF) is a widely used algorithm for online deadline scheduling. It has been known for long that EDF is optimal for scheduling an underloaded, single-processor system; recent results on the extra-resource analysis of EDF further revealed that EDF when using moderately faster processors can achieve optimal performance in the underloaded, multi-processor setting. This paper initiates the extra-resource analysis of EDF for overloaded systems, showing that EDF supplemented with a simple form of admission control can provide a similar performance guarantee in both the single and multi-processor settings. © 2003 Elsevier Inc. All rights reserved.en_HK
dc.format.extent163141 bytes-
dc.format.extent3039 bytes-
dc.format.extent3039 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgoren_HK
dc.relation.ispartofJournal of Algorithmsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectEarliest deadline firsten_HK
dc.subjectExtra-resource analysisen_HK
dc.subjectFirm deadline schedulingen_HK
dc.subjectOnline algorithmsen_HK
dc.titlePerformance guarantee for EDF under overloaden_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0196-6774&volume=52&issue=2&spage=193&epage=206&date=2004&atitle=Performance+guarantee+for+EDF+under+overloaden_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepostprinten_HK
dc.identifier.doi10.1016/j.jalgor.2003.10.004en_HK
dc.identifier.scopuseid_2-s2.0-3042816683en_HK
dc.identifier.hkuros91566-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-3042816683&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume52en_HK
dc.identifier.issue2en_HK
dc.identifier.spage193en_HK
dc.identifier.epage206en_HK
dc.identifier.isiWOS:000222810800006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridNgan, TWJ=6602433224en_HK
dc.identifier.scopusauthoridTo, KK=36785812300en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats