Name
Abstract | ||
|---|---|---|
This paper presents an algorithm, called Earliest Deadline Critical Laxity (EDCL), for scheduling sporadic task systems on multiprocessors. EDCL is a derivative of the Earliest Deadline Zero Laxity (EDZL) algorithm. Each job is assigned a priority based on the well-known Global Earliest Deadline First (G-EDF) algorithm, as long as its laxity - the amount of time from the earliest possible time of job completion to the deadline of job - is above a certain value. The priority is however promoted to the highest level once the laxity falls below this certain value in order to meet the deadline. Priority promotions are aligned with arrivals and completions of jobs under EDCL to avoid additional scheduler invocations, while EDZL can promote priorities arbitrarily. As compared with EDZL, EDCL reduces runtime overhead and implementation cost, but still strictly dominates G-EDF in schedulability. Schedulability tests for EDCL are derived through theoretical analysis, and sustainability properties are also considered. Our simulation results demonstrate that EDCL is competitive to EDZL in schedulability with a smaller number of scheduler invocations, and it also outperforms traditional EDF-based algorithms. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.sysarc.2011.01.002 | Journal of Systems Architecture - Embedded Systems Design |
Keywords | Field | DocType |
earliest deadline zero laxity,priority promotion,sustainability analysis,possible time,real-time systems,certain value,schedulability analysis,global edf-based scheduling,earliest deadline,critical laxity,well-known global earliest deadline,traditional edf-based algorithm,laxity-driven priority promotion,earliest deadline first,additional scheduler invocation,job completion,multiprocessor scheduling,real time systems | Metrical task system,Multiprocessor scheduling,Scheduling (computing),Computer science,Parallel computing,Real-time computing,Earliest deadline first scheduling,Distributed computing | Journal |
Volume | Issue | ISSN |
57 | 5 | Journal of Systems Architecture |
Citations | PageRank | References |
6 | 0.43 | 24 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shinpei Kato | 1 | 951 | 62.18 |
| Nobuyuki Yamasaki | 2 | 338 | 30.45 |