Batching earliest deadline first scheduling

TitleBatching earliest deadline first scheduling
Publication TypeConference Paper
Year of Publication1999
AuthorsMoghaddas, M., and B. Hamidzadeh
Conference NameObject-Oriented Real-Time Dependable Systems, 1999. WORDS 1999 Fall. Proceedings. 5th International Workshop on
Pagination29 -34
Keywordsarrived task batch, batch processing (computers), batching algorithms, deadline compliance, dynamic scheduling tradeoff, earliest-deadline-first scheduling, performance, real-time systems, real-time tasks, schedule quality, scheduling, scheduling algorithm invocation frequency, software performance evaluation, task prioritization policy, task set size, time constraints

Investigates the trade-off in the dynamic scheduling of real-time tasks, between the frequency at which the scheduling algorithm is invoked, the size of the task set to which the scheduling (prioritization) policy is applied at every invocation, and the quality of the resulting schedules in terms of deadline compliance. We identify two classes of algorithms, one of which forms a batch of arrived tasks and which schedules and executes all tasks in a batch before considering other tasks that arrive in the meantime. The other class accounts for and schedules arrived tasks more frequently and applies the scheduling policy to all available tasks. We compare the performance of a batching and a non-batching technique, both of which apply an earliest-deadline-first (EDF) policy to prioritize tasks. An experimental evaluation of the proposed algorithms shows that our batching algorithms outperform their non-batching counterparts under tighter time constraints


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2020 The University of British Columbia