Budgeted generalized rate monotonic analysis for the partitioned, yet globally scheduled uniprocessor model

Jung Eun Kim, Tarek Abdelzaher, Lui Sha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper solves the challenge of offline response time analysis of independent periodic tasks with constrained deadlines early in the software development cycle, under generalized rate-monotonic scheduling. CPU budgets are allocated to different applications and each application is composed of multiple periodic tasks that must share the same budget. Physical application requirements impose specifications on task periods and deadlines from the very beginning, but unlike the common assumption in traditional response time analysis, task execution times are not known. This is because task execution times depend on the exact system implementation, which is not finalized until later in the development cycle. Questions facing designers become: will my task meet its deadline given lack of knowledge of other tasks' execution times? What is the smallest deadline that my task can meet? These questions are traditionally addressed by using a two level scheduler: CPU is partitioned and assigned to application, and task priorities are determined within the scope of an application, and when server becomes active it schedules the tasks locally. Such two level scheduling approach introduces priority inversion across applications. In our approach, different applications' tasks are globally scheduled and yet the CPU resource is still partitioned and assigned to applications as a CPU budget. We schedule all the tasks globally while enforcing application budgets. The proposed new form of response time analysis is called budgeted generalized rate-monotonic analysis to compute the maximum response time for each task given only application budgets and task periods, but without knowledge of task execution times. We formulate this schedulability problem as a mixed integer linear programming problem and demonstrate a solution that computes the exact worst-case response times. Evaluation shows that our solution outperforms, in terms of schedulability, both global utilization bounds and mechanisms that attain temporal modularity via resource partitioning.

Original languageEnglish (US)
Title of host publicationProceedings - 21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages221-231
Number of pages11
ISBN (Electronic)9781479986033
DOIs
StatePublished - May 14 2015
Event21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015 - Seattle, United States
Duration: Apr 13 2015Apr 16 2015

Publication series

NameProceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
Volume2015-May
ISSN (Print)1545-3421

Other

Other21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015
CountryUnited States
CitySeattle
Period4/13/154/16/15

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Budgeted generalized rate monotonic analysis for the partitioned, yet globally scheduled uniprocessor model'. Together they form a unique fingerprint.

  • Cite this

    Kim, J. E., Abdelzaher, T., & Sha, L. (2015). Budgeted generalized rate monotonic analysis for the partitioned, yet globally scheduled uniprocessor model. In Proceedings - 21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015 (pp. 221-231). [7108445] (Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS; Vol. 2015-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/RTAS.2015.7108445