Global schedulability analysis of a synchronization protocol based on replenishment-bounded overrun for compositional real-time systems
- 1 June 2012
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 7th IEEE International Symposium on Industrial Embedded Systems (SIES'12)
Abstract
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). The same mechanism can be applied to support scheduling techniques, such as fixed-priority scheduling with deferred preemption (FPDS), that aim at a reduction of the architecture-related preemption costs and may improve the feasibility of a system. Whereas the blocking times and overrun budgets for shared logical resources will typically be much smaller than the normal budget, these values may significantly increase for scheduling techniques such as FPDS. In this paper, we therefor consider replenishment-bounded overrun, i.e. the overrun ends upon a replenishment, because the normal budget becomes available again, which allows for larger overrun budgets. We show that the global schedulability analysis for this special kind of overrun has a number of anomalies: (i) the usual theorem for critical instant does not hold, (ii) maximal blocking does not necessarily lead to a maximal response time, and (iii) it is not sufficient to analyse a fixed amount of time (say, a number of hyperperiods). We present analysis for two subsystems.Keywords
This publication has 13 references indexed in Scilit:
- Improving Feasibility of Fixed Priority Tasks Using Non-Preemptive RegionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- An engineering approach to synchronization based on overrun for compositional real-time systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Tighter Schedulability Analysis of Synchronization Protocols Based on Overrun without Payback for Hierarchical Scheduling FrameworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Scheduling of semi-independent real-time components: Overrun methods and resource holding times.Published by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Z3: An Efficient SMT SolverLecture Notes in Computer Science, 2008
- Beyond Boolean SAT: Satisfiability modulo theoriesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Aperiodic servers in a deadline scheduling environmentReal-Time Systems, 1995
- A stack-based resource allocation policy for realtime processesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1990
- A note on preemptive scheduling of periodic, real-time tasksInformation Processing Letters, 1980
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973