Browsing by Author "Nasri, Mitra"
Now showing 1 - 5 of 5
Results Per Page
Sort Options
- From Code to Weakly Hard Constraints: A Pragmatic End-to-End Toolchain for Timed CPublication . Natarajan, Saranya; Nasri, Mitra; Broman, David; Brandenbur, Björn B.; Nelissen, GeoffreyComplex real-time systems are traditionally developed in several disjoint steps: (i) decomposition of applications into sets of recurrent tasks, (ii) worst-case execution time estimation, and (iii) schedulability analysis. Each step is already in itself complex and error-prone, and the composition of all three poses a nontrivial integration problem. In particular, it is challenging to obtain an end-to-end analysis of timing properties of the whole system due to practical differences between the interfaces of tools for extracting task models, execution time analysis, and schedulability tests. To address this problem, we propose a seamless and pragmatic end-to-end compilation and timing analysis toolchain, where source programs are written in a real-time extension of C, called Timed C. The toolchain automatically translates timing primitives into executable code, measures execution times, and verifies temporal correctness using an extended schedulability test for non-preemptive generalized multiframe task sets. Novel aspects of our approach are: (i) both soft and firm tasks can be expressed at the programming language level and stated timing requirements are automatically verified by the schedulability test, and (ii) the schedulability test outputs per-job response-time information that enables a new approach to sensitivity analysis. Specifically, we perform a weakly hard sensitivity analysis that determines the worst-case execution time margins for the strongest still-satisfied (M;K) constraint, where M = m_1 + … + m_N denotes the number of deadline misses across the entire task set, and K = {k_1; … ; k_N} is the set of windows of interest of the different tasks. The toolchain is implemented as a source-to-source compiler, freely available as open source, and conveniently distributed as a Docker container.
- Increasing Fixed-Priority Schedulability using Non-Periodic Load ShapersPublication . Nasri, Mitra; Nelissen, GeoffreyMany real-time systems use fixed-priority scheduling (FPS) for three main reasons: (i) it is easy to understand, configure and analyze, (ii) it has low runtime overhead, and (iii) it is widely implemented in operating systems. Moreover, it is enforced by some standards such as Autosar for safety-critical real-time applications since it avoids unbounded delays in the case of overload in the system. However, FPS is not optimal since it may prioritize the execution of a high-priority task over a task with an urgent deadline. In this work, we introduce load-shaping (LS); a technique that shapes the workload of tasks to limit their impact on the system's schedulability while improving their safety. LS is implemented using a reservation server for each task. Each server has a budget that replenishes with a given pattern, which might not necessarily be periodic. In this work, we discuss the open problems regarding parameter assignment for load-shaping techniques.
- A New Approach for Limited Preemptive Scheduling in Systems with Preemption OverheadPublication . Nasri, Mitra; Nelissen, Geoffrey; Fohler, GerhardThis paper considers the problem of reducing the number of preemptions in a system with periodic tasks and preemption overhead. The proposed solution is based on the key observation that for periodic task sets, the task with the smallest period plays an important role in determining the maximum interval of time during which a lower priority task can be executed without being preempted. We use this property to build a new limited preemptive scheduling algorithm, named RSLP, based on fixed-priority scheduling. In RS-LP, the length of each task’s non-preemptive region is varying during the system execution so as to keep the preemptions aligned with the releases of the highest priority task. This simple mechanism allows us to reduce the overall number of preemptions. The proposed algorithm, decides whether or not to preempt the currently executing task based on the maximum blocking tolerance of the higher priority tasks. In any case, the preemptions are authorized only at release instants of the task with the smallest period, thereby limiting the maximum number of preemptions to the number of releases of the highest priority task. Moreover, in this paper, we provide two different preemption overhead aware schedulability tests for periodic and loose-harmonic task sets (i.e., where each period is an integer multiple of the smallest period), together with a lower bound on the maximum number of preemptions. To conclude, extensive experiments comparing RS-LP with the state of the art limited preemptive scheduling algorithms are finally presented.
- A Response-Time Analysis for Non-Preemptive Job Sets under Global SchedulingPublication . Nasri, Mitra; Nelissen, Geoffrey; B. Brandenburg, BjörnAn effective way to increase the timing predictability of multicore platforms is to use non-preemptive scheduling. It reduces preemption and job migration overheads, avoids intra-core cache interference, and improves the accuracy of worst-case execution time (WCET) estimates. However, existing schedulability tests for global non-preemptive multiprocessor scheduling are pessimistic, especially when applied to periodic workloads. This paper reduces this pessimism by introducing a new type of sufficient schedulability analysis that is based on an exploration of the space of possible schedules using concise abstractions and state-pruning techniques. Specifically, we analyze the schedulability of non-preemptive job sets (with bounded release jitter and execution time variation) scheduled by a global job-level fixed-priority (JLFP) scheduling algorithm upon an identical multicore platform. The analysis yields a lower bound on the best-case response-time (BCRT) and an upper bound on the worst-case response time (WCRT) of the jobs. In an empirical evaluation with randomly generated workloads, we show that the method scales to 30 tasks, a hundred thousand jobs (per hyperperiod), and up to 9 cores.
- Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks under Global SchedulingPublication . Nasri, Mitra; Nelissen, Geoffrey; Brandenburg, Björn B.Most recurrent real-time applications can be modeled as a set of sequential code segments (or blocks) that must be (repeatedly) executed in a specific order. This paper provides a schedulability analysis for such systems modeled as a set of parallel DAG tasks executed under any limited-preemptive global job-level fixed priority scheduling policy. More precisely, we derive response-time bounds for a set of jobs subject to precedence constraints, release jitter, and execution-time uncertainty, which enables support for a wide variety of parallel, limited-preemptive execution models (e.g., periodic DAG tasks, transactional tasks, generalized multi-frame tasks, etc.). Our analysis explores the space of all possible schedules using a powerful new state abstraction and state-pruning technique. An empirical evaluation shows the analysis to identify between 10 to 90 percentage points more schedulable task sets than the state-of-the-art schedulability test for limited-preemptive sporadic DAG tasks. It scales to systems of up to 64 cores with 20 DAG tasks. Moreover, while our analysis is almost as accurate as the state-of-the-art exact schedulability test based on model checking (for sequential non-preemptive tasks), it is three orders of magnitude faster and hence capable of analyzing task sets with more than 60 tasks on 8 cores in a few seconds.