Bi-Level Deadline Scaling for Admission Control in Mixed-Criticality Systems
Authors:
- Alejandro MasrurAMAlejandro Masrur
- Dirk MullerDMDirk Muller
- Matthias WernerMWMatthias Werner
- 1 August 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 100-109
Abstract
In some cases, tasks may be allowed to migrate from one processor to another, e.g., Due to hardware failures or for workload balancing. If a mixed-criticality setting is considered, it is necessary to decide whether new tasks with different levels of criticality may be accepted by a processor without compromising the already running tasks. Since this decision has to be taken on-line, there is a need for fast but yet accurate schedulability tests for mixed-criticality systems. In this paper, we consider that the EDF-VD algorithm is used to schedule tasks on the different processors. EDF-VD assigns virtual deadlines to high-criticality tasks, i.e., It uniformly downscales their real deadlines, to account for a potential increase in their execution demand. A deadline scaling factor is hence computed for the whole processor. However, in the case where the increase in computation demand strongly differs from one task to another, scaling deadlines uniformly makes EDF-VD incur pessimism. Of course, a scaling factor can be computed for every single task, however, this leads to a considerably more complex algorithm which cannot be used in an on-line setting. As a result, we propose an intermediate solution by introducing a bi-level deadline scaling. This way, high-criticality tasks that experience a small increase of workload are assigned one scaling factor, whereas tasks with a large increase of workload are assigned a separate scaling factor. Our experiments show that the proposed approach dominates the original EDF-VD algorithm while it does not increase complexity allowing for constant-time admission control in mixed-criticality systems.Keywords
This publication has 19 references indexed in Scilit:
- PUB: Path Upper-Bounding for Measurement-Based Probabilistic Timing Analysis2014
- Time-Analysable Non-Partitioned Shared Caches for Real-Time Multicore Systems2014
- Bounding and shaping the demand of generalized mixed-criticality sporadic task systemsReal-Time Systems, 2013
- An Elastic Mixed-Criticality Task Model and Its Scheduling Algorithm2013
- The worst-case execution-time problem—overview of methods and survey of toolsACM Transactions on Embedded Computing Systems, 2008
- Measuring the Performance of Schedulability TestsReal-Time Systems, 2005
- Experimental evaluation of code properties for WCET analysis2004
- Load adjustment in adaptive real-time systems2002
- Elastic task model for adaptive rate control2002
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973