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

• 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 results1. © 2011 IEEE.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Keyword

Automotive standards

Complex real-time systems

Extensive simulations

Global resources

Hierarchical scheduling

Measured results

Real time operating system

Resource access

Runtimes

Schedulability

Schedulability analysis

Simplified analysis

Stack resource policies

Synchronization protocols

Budget control

Computer operating systems

Embedded systems

Hierarchical systems

Industry

Synchronization

Real time systems

Publication and Content Type

ref (subject category)

kon (subject category)