File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.jalgor.2003.10.004
- Scopus: eid_2-s2.0-3042816683
- WOS: WOS:000222810800006
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Performance guarantee for EDF under overload
Title | Performance guarantee for EDF under overload |
---|---|
Authors | |
Keywords | Earliest deadline first Extra-resource analysis Firm deadline scheduling Online algorithms |
Issue Date | 2004 |
Publisher | Academic 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? |
Abstract | Earliest 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 Identifier | http://hdl.handle.net/10722/48426 |
ISSN | 2011 Impact Factor: 0.500 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Ngan, TWJ | en_HK |
dc.contributor.author | To, KK | en_HK |
dc.date.accessioned | 2008-05-22T04:12:41Z | - |
dc.date.available | 2008-05-22T04:12:41Z | - |
dc.date.issued | 2004 | en_HK |
dc.identifier.citation | Journal Of Algorithms, 2004, v. 52 n. 2, p. 193-206 | en_HK |
dc.identifier.issn | 0196-6774 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/48426 | - |
dc.description.abstract | Earliest 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.extent | 163141 bytes | - |
dc.format.extent | 3039 bytes | - |
dc.format.extent | 3039 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | text/plain | - |
dc.format.mimetype | text/plain | - |
dc.language | eng | en_HK |
dc.publisher | Academic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor | en_HK |
dc.relation.ispartof | Journal of Algorithms | en_HK |
dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | - |
dc.subject | Earliest deadline first | en_HK |
dc.subject | Extra-resource analysis | en_HK |
dc.subject | Firm deadline scheduling | en_HK |
dc.subject | Online algorithms | en_HK |
dc.title | Performance guarantee for EDF under overload | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+overload | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.description.nature | postprint | en_HK |
dc.identifier.doi | 10.1016/j.jalgor.2003.10.004 | en_HK |
dc.identifier.scopus | eid_2-s2.0-3042816683 | en_HK |
dc.identifier.hkuros | 91566 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-3042816683&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 52 | en_HK |
dc.identifier.issue | 2 | en_HK |
dc.identifier.spage | 193 | en_HK |
dc.identifier.epage | 206 | en_HK |
dc.identifier.isi | WOS:000222810800006 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Ngan, TWJ=6602433224 | en_HK |
dc.identifier.scopusauthorid | To, KK=36785812300 | en_HK |
dc.identifier.issnl | 0196-6774 | - |