An engineering approach to synchronization based on overrun for compositional real-time systems

U. Keskin, M.M.H.P. Heuvel, van den, R.J. Bril, J.J. Lukkien, M. Behnam, T. Nolte

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
133 Downloads (Pure)


Hierarchical scheduling frameworks (HSFs) provide means for composing complex real-time systems from well-defined independently developed and analyzed subsystems. To support shared logical resources requiring mutual exclusive access in two-level HSFs, overrun without payback has been proposed as a mechanism to prevent budget depletion during resource access arbitrated by the stack resource policy (SRP). In this paper, we revisit the global schedulability analysis of synchronization protocols based on SRP and overrun without payback for fixed-priority scheduled HSFs. We derive a new global schedulability analysis based on the observation that the overrun budget is merely meant to prevent budget depletion during global resource access. The deadline of a subsystem therefore only needs to hold for its normal budget rather than the sum of the normal and overrun budget. Our novel analysis is considerably simpler than an earlier, initially improved analysis, which improved both the original local and global schedulability analyses. We evaluate the new analysis based on an extensive simulation study and compare the results with the existing analysis. Our simplified analysis does not significantly affect schedulability compared to the initially improved analysis. It is therefore proposed as a preferable engineering approach to synchronization protocols for compositional real-time systems. We accordingly present the implementation of our improvement in an OSEK-compliant real-time operating system to sketch its applicability in today's industrial automotive standards. Both implementation and run-time overheads are discussed providing measured results.
Original languageEnglish
Title of host publicationProceedings of the 6th IEEE International Symposium on Industrial Embedded Systems (SIES 2011, Vasteras, Sweden, June 15-17, 2011)
PublisherInstitute of Electrical and Electronics Engineers
ISBN (Print)978-1-61284-818-1
Publication statusPublished - 2011


Dive into the research topics of 'An engineering approach to synchronization based on overrun for compositional real-time systems'. Together they form a unique fingerprint.

Cite this