Capturing urgency and parallelism using quasi-deadlines for real-time multiprocessor scheduling

Cited 4 time in webofscience Cited 5 time in scopus
  • Hit : 618
  • Download : 0
Recent trends toward multi-core architectures in real-time embedded systems pose challenges in designing efficient real-time multiprocessor scheduling algorithms. We believe that it is important to take into consideration both timing constraints of tasks (urgency) and parallelism restrictions of multiprocessor platforms (parallelism) together when designing scheduling algorithms. Motivated by this, we define the quasi-deadline of a job as a weighted sum of its absolute deadline (capturing urgency) and its worst case execution time (capturing parallelism) with a system-level control knob to balance urgency and parallelism effectively. Using the quasi-deadline to prioritize jobs, we propose two new scheduling algorithms, called EQDF (earliest quasi-deadline first) and EQDZL (earliest quasi-deadline until zero laxity), that are categorized into joblevel fixed-priority (JFP) scheduling and job-level dynamic-priority GDP) scheduling, respectively. This paper provides a new schedulability analysis for EQDF/EQDZL scheduling and addresses the problem of priority assignment under EQDF/EQDZL by determining a right value of the system-level control knob. It presents optimal and heuristic solutions to the problem subject to our proposed EQDF and EQDZL analysis. Our simulation results show that EQDF and EQDZL can improve schedulability significantly compared to EDF and EDZL, respectively.
Publisher
ELSEVIER SCIENCE INC
Issue Date
2015-03
Language
English
Article Type
Article
Keywords

GLOBAL EDF SCHEDULABILITY; SPORADIC TASK SYSTEMS; PRIORITY ASSIGNMENT; PLATFORMS; ALGORITHM

Citation

JOURNAL OF SYSTEMS AND SOFTWARE, v.101, pp.15 - 29

ISSN
0164-1212
DOI
10.1016/j.jss.2014.11.019
URI
http://hdl.handle.net/10203/195591
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 4 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0