Towards pragmatic solutions for two-level hierarchical scheduling - Part I: A basic approach for independent applications

Resource reservation has been proposed in the literature as a means to prevent temporal interference between applica-tions. With applications consisting of one or more real-time tasks, resource reservation inherently involves multiple levels of scheduling, i.e. a scheduling hierarchy. This document considers two-level hierarchical scheduling for independent applications in cost-constrained systems, using fixed-priority pre-emptive scheduling (FPPS) for tasks. We aim at pragmatic solutions for such systems, which allow efficient implementations of budgets and simple analysis for tasks. Given the complexity and pessimism of the analysis for tasks for existing approaches and based on the observation that budgets are design artifacts, we consider a basic approach, where budgets are time-triggered and all budgets have the same period. Using jitter analysis as an example, it is shown that existing analytic results for real-time tasks under FPPS can be easily converted to two-level hierarchical scheduling for this approach by viewing the unavailability of a budget as an artificial highest priority task. We show that the conversion equally well applies to the approaches described in [12, 17, 18], amongst others. We briefly consider an advanced approach where budgets have harmonic periods, and show that the conversion is not straightforward for such an approach.