Improving OCBP-based scheduling for mixed-criticality sporadic task systems

Chuancai Gu, Nan Guan, Qingxu Deng, Wang Yi

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

7 Citations (Scopus)

Abstract

Scheduling mixed-criticality systems is a challenging problem. Recently a number of new techniques are developed to schedule such systems, among which an approach called OCBP has shown interesting properties and drawn considerable attentions. OCBP explores the job-level priority order in a very flexible manner to drastically improve the system schedulability. However, the job priority exploration in OCBP involves nontrivial overheads. In this work, we propose a new algorithm LPA (Lazy Priority Adjustment) based on the OCBP approach, which improves the state-of-the-art OCBP-based scheduling algorithm PLRS in both schedulability and run-time efficiency. Firstly, while the time-complexity of PLRS' online priority management is quadratic, our new algorithm LPA has linear time-complexity at run-time. Secondly, we present an approach to calculate tighter upper bounds of the busy period size, and thereby can greatly reduce the run-time space requirement. Thirdly, the tighter busy period size bounds also improve the schedulability in terms of acceptance ratio. Experiments with synthetic workloads show improvements of LPA in all the above three aspects.
Original languageEnglish
Title of host publication2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2013
PublisherIEEE Computer Society
Pages247-256
Number of pages10
DOIs
Publication statusPublished - 1 Jan 2013
Externally publishedYes
Event2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2013 - Taipei, Taiwan
Duration: 19 Aug 201321 Aug 2013

Conference

Conference2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2013
Country/TerritoryTaiwan
CityTaipei
Period19/08/1321/08/13

ASJC Scopus subject areas

  • Computer Science Applications
  • Software

Cite this