2024-03-29T01:32:57Z
https://ojs.dagstuhl.de/index.php/lites/oai
oai:ojs.dagstuhl.de:article/36
2016-02-18T09:51:01Z
lites:ART
driver
Computation Offloading for Frame-Based Real-Time Tasks under Given Server Response Time Guarantees
Toma, Anas S. M.
Chen, Jian-Jia
Computation offloading
Task scheduling
Real-time systems
Software and its engineering
Scheduling
Computer systems organization
Real-time systems
Computation offloading has been adopted to improve the performance of embedded systems by offloading the computation of some tasks, especially computation-intensive tasks, to servers or clouds. This paper explores computation offloading for real-time tasks in embedded systems, provided given response time guarantees from the servers, to decide which tasks should be offloaded to get the results in time. We consider frame-based real-time tasks with the same period and relative deadline. When the execution order of the tasks is given, the problem can be solved in linear time. However, when the execution order is not specified, we prove that the problem is NP-complete. We develop a pseudo-polynomial-time algorithm for deriving feasible schedules, if they exist. An approximation scheme is also developed to trade the error made from the algorithm and the complexity. Our algorithms are extended to minimize the period/relative deadline of the tasks for performance maximization. The algorithms are evaluated with a case study for a surveillance system and synthesized benchmarks.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2014-11-14
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i002-a002
10.4230/LITES-v001-i002-a002
Leibniz Transactions on Embedded Systems; Vol. 1 No. 2 (2014); 02:1–02:21
2199-2002
10.4230/LITES-v001-i002
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i002-a002/lites-v001-i002-a002-pdf
Copyright (c) 2014 Anas S. M. Toma, Jian-Jia Chen
oai:ojs.dagstuhl.de:article/37
2016-02-18T09:50:54Z
lites:ART
driver
TLM.open: a SystemC/TLM Frontend for the CADP Verification Toolbox
Helmstetter, Claude
Model checking
Verification
Simulation
SystemC
Transactional modeling
Hardware
Hardware validation
Functional verification
Transaction-level verification
SystemC/TLM models, which are C++ programs, allow the simulation of embedded software before hardware low-level descriptions are available and are used as golden models for hardware verification. The verification of the SystemC/TLM models is an important issue since an error in the model can mislead the system designers or reveal an error in the specifications. An open-source simulator for SystemC/TLM is provided but there are no tools for formal verification.In order to apply model checking to a SystemC/TLM model, a semantics for standard C++ code and for specific SystemC/TLM features must be provided. The usual approach relies on the translation of the SystemC/TLM code into a formal language for which a model checker is available.We propose another approach that suppresses the error-prone translation effort. Given a SystemC/TLM program, the transitions are obtained by executing the original code using g++ and an extended SystemC library, and we ask the user to provide additional functions to store the current model state. These additional functions generally represent less than 20% of the size of the original model, and allow it to apply all CADP verification tools to the SystemC/TLM model itself.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2014-04-25
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i001-a002
10.4230/LITES-v001-i001-a002
Leibniz Transactions on Embedded Systems; Vol. 1 No. 1 (2014); 02:1-02:18
2199-2002
10.4230/LITES-v001-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i001-a002/lites-v001-i001-a002-pdf
Copyright (c) 2014 Claude Helmstetter
oai:ojs.dagstuhl.de:article/40
2016-02-18T09:50:53Z
lites:ART
driver
A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays
Lunniss, Will
Altmeyer, Sebastian
Davis, Robert I.
Real-time systems
Fixed priority
EDF
Pre-emptive scheduling
Cache related pre-emption delays
Software and its engineering
Software organization and properties
Software functional properties
Correctness
Real-time schedulability
In multitasking real-time systems, the choice of scheduling algorithm is an important factor to ensure that response time requirements are met while maximising limited system resources. Two popular scheduling algorithms include fixed priority (FP) and earliest deadline first (EDF). While they have been studied in great detail before, they have not been compared when taking into account cache related pre-emption delays (CRPD). Memory and cache are split into a number of blocks containing instructions and data. During a pre-emption, cache blocks from the pre-empting task can evict those of the pre-empted task. When the pre-empted task is resumed, if it then has to re-load the evicted blocks, CRPD are introduced which then affect the schedulability of the task. In this paper we compare FP and EDF scheduling algorithms in the presence of CRPD using the state-of-the-art CRPD analysis. We find that when CRPD is accounted for, the performance gains offered by EDF over FP, while still notable, are diminished. Furthermore, we find that under scenarios that cause relatively high CRPD, task layout optimisation techniques can be applied to allow FP to schedule tasksets at a similar processor utilisation to EDF. Thus making the choice of the task layout in memory as important as the choice of scheduling algorithm. This is very relevant for industry, as it is much cheaper and simpler to adjust the task layout through the linker than it is to switch the scheduling algorithm.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2014-04-14
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i001-a001
10.4230/LITES-v001-i001-a001
Leibniz Transactions on Embedded Systems; Vol. 1 No. 1 (2014); 01:1-01:24
2199-2002
10.4230/LITES-v001-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i001-a001/lites-v001-i001-a001-pdf
Copyright (c) 2014 Will Lunniss, Sebastian Altmeyer, Robert I. Davis
oai:ojs.dagstuhl.de:article/41
2016-02-18T09:51:00Z
lites:ART
driver
Blocking Optimality in Distributed Real-Time Locking Protocols
Brandenburg, Björn Bernhard
Distributed multiprocessor real-time systems
Real-time locking
Priority inversion
Blocking optimality
real-time systems
synchronization
Lower and upper bounds on the maximum priority inversion blocking (pi-blocking) that is generally unavoidable in distributed multiprocessor real-time locking protocols (where resources may be accessed only from specific synchronization processors) are established. Prior work on suspension-based shared-memory multiprocessor locking protocols (which require resources to be accessible from all processors) has established asymptotically tight bounds of Ω(m) and Ω(n) maximum pi-blocking under suspension-oblivious and suspension-aware analysis, respectively, where m denotes the total number of processors and n denotes the number of tasks. In this paper, it is shown that, in the case of distributed semaphore protocols, there exist two different task allocation scenarios that give rise to distinct lower bounds. In the case of co-hosted task allocation, where application tasks may also be assigned to synchronization processors (i.e., processors hosting critical sections), Ω(Φ · n) maximum pi-blocking is unavoidable for some tasks under any locking protocol under both suspension-aware and suspension-oblivious schedulability analysis, where Φ denotes the ratio of the maximum response time to the shortest period. In contrast, in the case of disjoint task allocation (i.e., if application tasks may not be assigned to synchronization processors), only Ω(m) and Ω(n) maximum pi-blocking is fundamentally unavoidable under suspension-oblivious and suspension-aware analysis, respectively, as in the shared-memory case. These bounds are shown to be asymptotically tight with the construction of two new distributed real-time locking protocols that ensure O(m) and O(n) maximum pi-blocking under suspension-oblivious and suspension-aware analysis, respectively.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2014-09-12
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i002-a001
10.4230/LITES-v001-i002-a001
Leibniz Transactions on Embedded Systems; Vol. 1 No. 2 (2014); 01:1-01:22
2199-2002
10.4230/LITES-v001-i002
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i002-a001/lites-v001-i002-a001-pdf
Copyright (c) 2014 Björn Bernhard Brandenburg
oai:ojs.dagstuhl.de:article/43
2018-01-08T10:43:32Z
lites:ART
driver
From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation
Carle, Thomas
Potop-Butucaru, Dumitru
Sorel, Yves
Lesens, David
Time-triggered
Off-line real-time scheduling
Temporal partitioning
Computer systems organization
Real-time systems
Our objective is to facilitate the development of complex time-triggered systems by automating the allocation and scheduling steps. We show that full automation is possible while taking into account the elements of complexity needed by a complex embedded control system. More precisely, we consider deterministic functional specifications provided (as often in an industrial setting) by means of synchronous data-flow models with multiple modes and multiple relative periods. We first extend this functional model with an original real-time characterization that takes advantage of our time-triggered framework to provide a simpler representation of complex end-to-end flow requirements. We also extend our specifications with additional non-functional properties specifying partitioning, allocation, and preemptability constraints. Then, we provide novel algorithms for the off-line scheduling of these extended specifications onto partitioned time-triggered architectures à la ARINC 653. The main originality of our work is that it takes into account at the same time multiple complexity elements: various types of non-functional properties (real-time, partitioning, allocation, preemptability) and functional specifications with conditional execution and multiple modes. Allocation of time slots/windows to partitions can be fully or partially provided, or synthesized by our tool. Our algorithms allow the automatic allocation and scheduling onto multi-processor (distributed) systems with a global time base, taking into account communication costs. We demonstrate our technique on a model of space flight software system with strong real-time determinism requirements.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2015-11-30
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v002-i002-a001
10.4230/LITES-v002-i002-a001
Leibniz Transactions on Embedded Systems; Vol. 2 No. 2 (2015); 01:1-01:30
2199-2002
10.4230/LITES-v002-i002
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v002-i002-a001/lites-v002-i002-a001-pdf
Copyright (c) 2015 Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens
oai:ojs.dagstuhl.de:article/45
2016-02-18T09:50:58Z
lites:ART
driver
Randomized Caches Considered Harmful in Hard Real-Time Systems
Reineke, Jan
Real-time systems
Caches
Randomization
WCET analysis
Computer systems organization~Real-time system architecture
Theory of computation~Caching and paging algorithms
Hardware~Safety critical systems
We investigate the suitability of caches with randomized placement and replacement in the context of hard real-time systems. Such caches have been claimed to drastically reduce the amount of information required by static worst-case execution time (WCET) analysis, and to be an enabler for measurement-based probabilistic timing analysis. We refute these claims and conclude that with prevailing static and measurement-based analysis techniques caches with deterministic placement and least-recently-used replacement are preferable over randomized ones.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2014-06-10
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i001-a003
10.4230/LITES-v001-i001-a003
Leibniz Transactions on Embedded Systems; Vol. 1 No. 1 (2014); 03:1-03:13
2199-2002
10.4230/LITES-v001-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i001-a003/lites-v001-i001-a003-pdf
Copyright (c) 2014 Jan Reineke
oai:ojs.dagstuhl.de:article/49
2016-02-18T09:51:03Z
lites:ART
driver
Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor
Guo, Zhishan
Baruah, Sanjoy K.
Mixed criticalities
Varying-speed processor
Preemptive uniprocessor scheduling
Real-time schedulability
A mixed criticality (MC) workload consists of components of varying degrees of importance (or "criticalities"); the more critical components typically need to have their correctness validated to greater levels of assurance than the less critical ones. The problem of executing such a MC workload upon a preemptive processor whose effective speed may vary during run-time, in a manner that is not completely known prior to run-time, is considered.Such a processor is modeled as being characterized by several execution speeds: a normal speed and several levels of degraded speed. Under normal circumstances it will execute at or above its normal speed; conditions during run-time may cause it to execute slower. It is desired that all components of the MC workload execute correctly under normal circumstances. If the processor speed degrades, it should nevertheless remain the case that the more critical components execute correctly (although the less critical ones need not do so).In this work, we derive an optimal algorithm for scheduling MC workloads upon such platforms; achieving optimality does not require that the processor be able to monitor its own run-time speed. For the sub-case of the general problem where there are only two criticality levels defined, we additionally provide an implementation that is asymptotically optimal in terms of run-time efficiency.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2014-11-17
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i002-a003
10.4230/LITES-v001-i002-a003
Leibniz Transactions on Embedded Systems; Vol. 1 No. 2 (2014); 03:1–03:19
2199-2002
10.4230/LITES-v001-i002
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v001-i002-a003/lites-v001-i002-a003-pdf
Copyright (c) 2014 Zhishan Guo, Sanjoy K. Baruah
oai:ojs.dagstuhl.de:article/51
2018-01-08T10:43:59Z
lites:ART
driver
Randomized Caches Can Be Pretty Useful to Hard Real-Time Systems
Mezzetti, Enrico
Ziccardi, Marco
Vardanega, Tullio
Abella, Jaume
Quiñones, Eduardo
Cazorla, Francisco J.
Real-time systems
Probabilistic WCET
Randomized caches
Computer systems organization~Real-time system architecture
Theory of computation~Probabilistic computation
Computer systems organization~Special purpose systems
Cache randomization per se, and its viability for probabilistic timing analysis (PTA) of critical real-time systems, are receiving increasingly close attention from the scientific community and the industrial practitioners. In fact, the very notion of introducing randomness and probabilities in time-critical systems has caused strenuous debates owing to the apparent clash that this idea has with the strictly deterministic view traditionally held for those systems. A paper recently appeared in LITES (Reineke, J. (2014). Randomized Caches Considered Harmful in Hard Real-Time Systems. LITES, 1(1), 03:1-03:13.) provides a critical analysis of the weaknesses and risks entailed in using randomized caches in hard real-time systems. In order to provide the interested reader with a fuller, balanced appreciation of the subject matter, a critical analysis of the benefits brought about by that innovation should be provided also. This short paper addresses that need by revisiting the array of issues addressed in the cited work, in the light of the latest advances to the relevant state of the art. Accordingly, we show that the potential benefits of randomized caches do offset their limitations, causing them to be - when used in conjunction with PTA - a serious competitor to conventional designs.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2015-03-23
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v002-i001-a001
10.4230/LITES-v002-i001-a001
Leibniz Transactions on Embedded Systems; Vol. 2 No. 1 (2015); 01:1-01:10
2199-2002
10.4230/LITES-v002-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v002-i001-a001/lites-v002-i001-a001-pdf
Copyright (c) 2015 Enrico Mezzetti, Marco Ziccardi, Tullio Vardanega, Jaume Abella, Eduardo Qui\~{n}ones, Francisco J. Cazorla
oai:ojs.dagstuhl.de:article/60
2016-06-29T13:57:54Z
lites:ART
driver
A Survey on Static Cache Analysis for Real-Time Systems
Lv, Mingsong
Guan, Nan
Reineke, Jan
Wilhelm, Reinhard
Yi, Wang
Hard real-time
Cache analysis
Worst-case execution time
Surveys and overviews
Real-time systems are reactive computer systems that must produce their reaction to a stimulus within given time bounds. A vital verification requirement is to estimate the Worst-Case Execution Time (WCET) of programs. These estimates are then used to predict the timing behavior of the overall system. The execution time of a program heavily depends on the underlying hardware, among which cache has the biggest influence. Analyzing cache behavior is very challenging due to the versatile cache features and complex execution environment. This article provides a survey on static cache analysis for real-time systems. We first present the challenges and static analysis techniques for independent programs with respect to different cache features. Then, the discussion is extended to cache analysis in complex execution environment, followed by a survey of existing tools based on static techniques for cache analysis. An outlook for future research is provided at last.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2016-06-29
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a005
10.4230/LITES-v003-i001-a005
Leibniz Transactions on Embedded Systems; Vol. 3 No. 1 (2016); 05:1-05:48
2199-2002
10.4230/LITES-v003-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a005/lites-v003-i001-a005-pdf
Copyright (c) 2016 Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi
oai:ojs.dagstuhl.de:article/61
2016-06-29T13:57:54Z
lites:ART
driver
Programming Language Constructs Supporting Fault Tolerance
Houben, Christina
Houben, Sebastian
Fault tolerance
Functional safety
PEARL
Embedded systems
Software engineering
Control Structures and Microprogramming~Control Structure Reliability
Testing
and Fault-Tolerance
Programming Languages
Language Constructs and Features
Computers in Other Systems
Real-time
Advanced Driver Assistance Systems
Space Flight
In order to render software viable for highly safety-critical applications, we describe how to incorporate fault tolerance mechanisms into the real-time programming language PEARL. Therefore, we present, classify, evaluate and illustrate known fault tolerance methods for software. We link them together with the requirements of the international standard IEC 61508-3 for functional safety. We contribute PEARL-2020 programming language constructs for fault tolerance methods that need to be implemented by operating systems, and code-snippets as well as libraries for those independent from runtime systems.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2016-06-10
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a001
10.4230/LITES-v003-i001-a001
Leibniz Transactions on Embedded Systems; Vol. 3 No. 1 (2016); 01:1-01:20
2199-2002
10.4230/LITES-v003-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a001/lites-v003-i001-a001-pdf
Copyright (c) 2016 Christina Houben and Sebastian Houben
oai:ojs.dagstuhl.de:article/62
2016-06-29T13:57:54Z
lites:ART
driver
Optimal Scheduling of Periodic Gang Tasks
Goossens, Joël
Richard, Pascal
Real-time systems
Scheduling
Parallel tasks
Computer systems organization
Real-time systems
Embedded and cyber-physical systems
Software and its engineering
Process management
Scheduling
Multithreading
Theory of computation
Design and analysis of algorithms
Scheduling algorithms
The gang scheduling of parallel implicit-deadline periodic task systems upon identical multiprocessor platforms is considered. In this scheduling problem, parallel tasks use several processors simultaneously. We propose two DPFAIR (deadline partitioning) algorithms that schedule all jobs in every interval of time delimited by two subsequent deadlines. These algorithms define a static schedule pattern that is stretched at run-time in every interval of the DPFAIR schedule. The first algorithm is based on linear programming and is the first one to be proved optimal for the considered gang scheduling problem. Furthermore, it runs in polynomial time for a fixed number m of processors and an efficient implementation is fully detailed. The second algorithm is an approximation algorithm based on a fixed-priority rule that is competitive under resource augmentation analysis in order to compute an optimal schedule pattern. Precisely, its speedup factor is bounded by (2-1/m). Both algorithms are also evaluated through intensive numerical experiments.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2016-06-29
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a004
10.4230/LITES-v003-i001-a004
Leibniz Transactions on Embedded Systems; Vol. 3 No. 1 (2016); 04:1-04:18
2199-2002
10.4230/LITES-v003-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a004/lites-v003-i001-a004-pdf
Copyright (c) 2016 Joël Goossens and Pascal Richard
oai:ojs.dagstuhl.de:article/63
2016-06-29T13:57:54Z
lites:ART
driver
Modeling Power Consumption and Temperature in TLM Models
Moy, Matthieu
Helmstetter, Claude
Bouhadiba, Tayeb
Maraninchi, Florence
Power consumption
Temperature control
Virtual prototype
SystemC
Transactional modeling
Hardware - Power and energy - Power estimation and optimization - Chip-level power issues
Many techniques and tools exist to estimate the power consumption and the temperature map of a chip. These tools help the hardware designers develop power efficient chips in the presence of temperature constraints. For this task, the application can be ignored or at least abstracted by some high level scenarios; at this stage, the actual embedded software is generally not available yet.However, after the hardware is defined, the embedded software can still have a significant influence on the power consumption; i.e., two implementations of the same application can consume more or less power. Moreover, the actual software power manager ensuring the temperature constraints, usually by acting dynamically on the voltage and frequency, must itself be validated. Validating such power management policy requires a model of both actuators and sensors, hence a closed-loop simulation of the functional model with a non-functional one.In this paper, we present and compare several tools to simulate the power and thermal behavior of a chip together with its functionality. We explore several levels of abstraction and study the impact on the precision of the analysis.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2016-06-29
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a003
10.4230/LITES-v003-i001-a003
Leibniz Transactions on Embedded Systems; Vol. 3 No. 1 (2016); 03:1-03:29
2199-2002
10.4230/LITES-v003-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a003/lites-v003-i001-a003-pdf
Copyright (c) 2016 Matthieu Moy, Claude Helmstetter, Tayeb Bouhadiba, and Florence Maraninchi
oai:ojs.dagstuhl.de:article/64
2018-11-19T15:56:24Z
lites:ART
driver
Errata for Three Papers (2004-05) on Fixed-Priority Scheduling with Self-Suspensions
Bletsas, Konstantinos
Audsley, Neil C.
Huang, Wen-Hung
Chen, Jian-Jia
Nelissen, Geoffrey
real-time
scheduling
self-suspension
worst-case response time analysis
Embedded systems
Real-time systems
Real-time schedulability
The purpose of this article is to (i) highlight the flaws in three previously published works [Audsley, 2004a; Audsley, 2004b; Bletsas, 2005] on the worst-case response time analysis for tasks with self-suspensions and (ii) provide straightforward fixes for those flaws, hence rendering the analysis safe.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2018-05-30
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v005-i001-a002
10.4230/LITES-v005-i001-a002
Leibniz Transactions on Embedded Systems; Vol. 5 No. 1 (2018); 02:1-02:20
2199-2002
10.4230/LITES-v005-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v005-i001-a002/lites-v005-i001-a002-pdf
Copyright (c) 2018 Konstantinos Bletsas, Neil C. Audsley, Wen-Hung Huang, Jian-Jia Chen, Geoffrey Nelissen
oai:ojs.dagstuhl.de:article/65
2016-06-29T13:57:54Z
lites:ART
driver
Real-Time Scheduling on Uni- and Multiprocessors based on Priority Promotions
Pathan, Risat Mahmud
Real-Time Systems
Priority Promotion
Schedulability Analysis
Schedulability Condition
Real-time systems
Process management
Scheduling
Embedded and cyber-physical systems
This paper addresses the problem of real-time scheduling of a set of sporadic tasks on uni- and multiprocessor platform based on priority promotion. A new preemptive scheduling algorithm, called Fixed-Priority with Priority Promotion (FPP), is proposed. In FPP scheduling, tasks are executed similar to traditional fixed-priority (FP) scheduling but the priority of some tasks are promoted at fixed time interval (called, promotion point) relative to the release time of each job. A policy called Increase Priority at Deadline Difference (IPDD) to compute the promotion points and promoted priorities for each task is proposed. FPP scheduling prioritizes jobs according to Earliest-Deadline-First (EDF) priority when all tasks' priorities follow IPDD policy.It is known that managing (i.e., inserting and removing) jobs in the ready queue of traditional EDF scheduler is more complex than that of FP scheduler. To avoid such problem in FPP scheduling, a simple data structure and efficient operations to manage jobs in the ready queue are proposed. In addition, techniques for implementing priority promotions with and without the use of a hardware timer are proposed.Finally, an effective scheme to reduce the average number of priority promotions is proposed: if a task set is not schedulable using traditional FP scheduling, then promotion points are assigned only to those tasks that need them to meet the deadlines; otherwise, tasks are assigned traditional fixed priorities without any priority promotion. Empirical investigation shows the effectiveness of the proposed scheme in reducing overhead on uniprocessor and in accepting larger number of task sets in comparison to that of using state-of-the-art global schedulability tests for multiprocessors.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2016-06-10
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a002
10.4230/LITES-v003-i001-a002
Leibniz Transactions on Embedded Systems; Vol. 3 No. 1 (2016); 02:1-02:29
2199-2002
10.4230/LITES-v003-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v003-i001-a002/lites-v003-i001-a002-pdf
Copyright (c) 2016 Risat Mahmud Pathan
oai:ojs.dagstuhl.de:article/68
2017-02-28T07:13:57Z
lites:ART
driver
A Note on the Period Enforcer Algorithm for Self-Suspending Tasks
Chen, Jian-Jia
Brandenburg, Björn B.
Period Enforcer
Deferred Execution
Self-suspension
Blocking
Real-time systems
Real-time schedulability
Synchronization
The period enforcer algorithm for self-suspending real-time tasks is a technique for suppressing the "back-to-back" scheduling penalty associated with deferred execution. Originally proposed in 1991, the algorithm has attracted renewed interest in recent years. This note revisits the algorithm in the light of recent developments in the analysis of self-suspending tasks, carefully re-examines and explains its underlying assumptions and limitations, and points out three observations that have not been made in the literature to date: (i) period enforcement is not strictly superior (compared to the base case without enforcement) as it can cause deadline misses in self-suspending task sets that are schedulable without enforcement; (ii) to match the assumptions underlying the analysis of the period enforcer, a schedulability analysis of self-suspending tasks subject to period enforcement requires a task set transformation for which no solution is known in the general case, and which is subject to exponential time complexity (with current techniques) in the limited case of a single self-suspending task; and (iii) the period enforcer algorithm is incompatible with all existing analyses of suspension-based locking protocols, and can in fact cause ever-increasing suspension times until a deadline is missed.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2017-02-28
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i001-a001
10.4230/LITES-v004-i001-a001
Leibniz Transactions on Embedded Systems; Vol. 4 No. 1 (2017); 01:1-01:22
2199-2002
10.4230/LITES-v004-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i001-a001/lites-v004-i001-a001-pdf
Copyright (c) 2016 Jian-Jia Chen and Björn B. Brandenburg
oai:ojs.dagstuhl.de:article/76
2017-02-28T07:13:57Z
lites:ART
driver
Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results
Kluge, Florian
Real-time Scheduling
(m
k)-Firm Real-Time Tasks
Scheduling algorithms
The concept of a firm real-time task implies the notion of a firm deadline that should not be missed by the jobs of this task. If a deadline miss occurs, the concerned job yields no value to the system. For some applications domains, this restrictive notion can be relaxed. For example, robust control systems can tolerate that single executions of a control loop miss their deadlines, and still yield an acceptable behaviour. Thus, systems can be developed under more optimistic assumptions, e.g. by allowing overloads. However, care must be taken that deadline misses do not accumulate. This restriction can be expressed by the model of (m,k)-firm real-time tasks that require that from any k consecutive jobs at least m are executed successfully. In this article, we extend our prior work on the MKU scheduling heuristic. MKU uses history-cognisant utility functions as means for making decisions in overload situations. We present new theoretical results on MKU and on other schedulers for (m,k)-firm real-time tasks. Based on extensive simulations, we assess the performance of these schedulers. The results allow us to identify task set characteristics that can be used as guidelines for choosing a scheduler for a concrete use case.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2017-02-28
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i001-a002
10.4230/LITES-v004-i001-a002
Leibniz Transactions on Embedded Systems; Vol. 4 No. 1 (2017); 02:1-02:25
2199-2002
10.4230/LITES-v004-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i001-a002/lites-v004-i001-a002-pdf
Copyright (c) 2016 Florian Kluge
oai:ojs.dagstuhl.de:article/78
2018-11-19T15:56:24Z
lites:ART
driver
Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions
Alahmad, Bader Naim
Gopalakrishnan, Sathish
Mixed criticalities
Probability distribution
Real time systems
Scheduling
Chance constrained Markov decision process
Linear programming
Randomized policy
Mathematics of computing~Markov processes
Software and its engineering~Real-time systems software
Software and its engineering~Real-time schedulability
We pose the problem of scheduling Mixed Criticality (MC) job systems when there are only two criticality levels, Lo and Hi -referred to as Dual Criticality job systems- on a single processing platform, when job demands are probabilistic and their distributions are known. The current MC models require that the scheduling policy allocate as little execution time as possible to Lo-criticality jobs if the scenario of execution is of Hi criticality, and drop Lo-criticality jobs entirely as soon as the execution scenario's criticality level can be inferred and is Hi. The work incurred by "incorrectly" scheduling Lo-criticality jobs in cases of Hi realized scenarios might affect the feasibility of Hi criticality jobs; we quantify this work and call it Work Threatening Feasibility (WTF). Our objective is to construct online scheduling policies that minimize the expected WTF for the given instance, and under which the instance is feasible in a probabilistic sense that is consistent with the traditional deterministic definition of MC feasibility. We develop a probabilistic framework for MC scheduling, where feasibility is defined in terms of (chance) constraints on the probabilities that Lo and Hi jobs meet their deadlines. The probabilities are computed over the set of sample paths, or trajectories, induced by executing the policy, and those paths are dependent upon the set of execution scenarios and the given demand distributions. Our goal is to exploit the information provided by job distributions to compute the minimum expected WTF below which the given instance is not feasible in probability, and to compute a (randomized) "efficiently implementable" scheduling policy that realizes the latter quantity. We model the problem as a Constrained Markov Decision Process (CMDP) over a suitable state space and a finite planning horizon, and show that an optimal (non-stationary) Markov randomized scheduling policy exists. We derive an optimal policy by solving a Linear Program (LP). We also carry out quantitative evaluations on select probabilistic MC instances to demonstrate that our approach potentially outperforms current MC scheduling policies.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2018-05-30
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v005-i001-a001
10.4230/LITES-v005-i001-a001
Leibniz Transactions on Embedded Systems; Vol. 5 No. 1 (2018); 01:1-01:30
2199-2002
10.4230/LITES-v005-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v005-i001-a001/lites-v005-i001-a001-pdf
Copyright (c) 2018 Bader Naim Alahmad and Sathish Gopalakrishnan
oai:ojs.dagstuhl.de:article/79
2018-01-08T10:46:08Z
lites:ART
driver
Dynamic and Static Task Allocation for Hard Real-Time Video Stream Decoding on NoCs
Mendis, Hashan R.
Audsley, Neil C.
Indrusiak, Leandro Soares
Real-time multimedia
Task mapping
Network-on-chip
On-chip resource management
Hard real-time (HRT) video systems require admission control decisions that rely on two factors. Firstly, schedulability analysis of the data-dependent, communicating tasks within the application need to be carried out in order to guarantee timing and predictability. Secondly, the allocation of the tasks to multi-core processing elements would generate different results in the schedulability analysis. Due to the conservative nature of the state-of-the-art schedulability analysis of tasks and message flows, and the unpredictability in the application, the system resources are often under-utilised. In this paper we propose two blocking-aware dynamic task allocation techniques that exploit application and platform characteristics, in order to increase the number of simultaneous, fully schedulable, video streams handled by the system. A novel, worst-case response time aware, search-based, static hard real-time task mapper is introduced to act as an upper-baseline to the proposed techniques. Further evaluations are carried out against existing heuristic-based dynamic mappers. Improvements to the admission rates and the system utilisation under a range of different workloads and platform sizes are explored.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2017-07-07
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i002-a001
10.4230/LITES-v004-i002-a001
Leibniz Transactions on Embedded Systems; Vol. 4 No. 2 (2017); 01:1-01:25
2199-2002
10.4230/LITES-v004-i002
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i002-a001/lites-v004-i002-a001-pdf
Copyright (c) 2017 Hashan R. Mendis, Neil C. Audsley, and Leandro Soares Indrusiak
oai:ojs.dagstuhl.de:article/81
2018-01-08T10:46:08Z
lites:ART
driver
EMSBench: Benchmark and Testbed for Reactive Real-Time Systems
Kluge, Florian
Rochange, Christine
Ungerer, Theo
Real-time benchmark
WCET Analysis
Engine Management System
Computer systems organization
Real-time systems
Software and its engineering
Real-time systems software
Benchmark suites for real-time embedded systems (RTES) usually contain only pure computations that are often used in this domain. They allow to evaluate computing performance, but do not reproduce the complexity and behaviour that is typical for such systems. Actual RTES have to interact with the physical environment, which is often reflected by code that is executed concurrently. In this article, we present the software package EMSBench that mimics such complex behaviour, and highlight some of its use cases. The benchmark code ems of EMSBench is based on the open-source engine management system (EMS) FreeEMS. Additionally, EMSBench contains a trace generator (tg) that provides input signals for ems and enables to execute ems close to reality. We provide detailed descriptions of the ems's execution behaviour and of trace generation. EMSBench can be used as test or benchmark program to compare different hardware platforms, e.g. in terms of schedulability. Also, we use EMSBench as a benchmark for static worst-case execution time (WCET) analysis and compare these results to measurements performed on existing hardware. Our results based on the OTAWA WCET estimation tool show WCET overestimations by the static analysis from 11.9% to 41.1% depending on the complexity of the analysed functions.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2017-07-07
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i002-a002
10.4230/LITES-v004-i002-a002
Leibniz Transactions on Embedded Systems; Vol. 4 No. 2 (2017); 02:1-02:23
2199-2002
10.4230/LITES-v004-i002
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i002-a002/lites-v004-i002-a002-pdf
Copyright (c) 2017 Florian Kluge, Christine Rochange, and Theo Ungerer
oai:ojs.dagstuhl.de:article/85
2018-11-19T15:56:24Z
lites:ART
driver
A Static Analysis for the Minimization of Voters in Fault-Tolerant Circuits
Burlyaev, Dmitry
Fradet, Pascal
Girault, Alain
Digital Circuits
Fault-tolerance
Optimization
Static Analysis
Triple Modular Redundancy
Hardware~Model checking
Hardware~Redundancy
We present a formal approach to minimize the number of voters in triple-modular redundant (TMR) sequential circuits. Our technique actually works on a single copy of the TMR circuit and considers a large class of fault mo dels of the form “at most 1 Single-Event Upset (SEU) or Single-Event Transient (SET) every k clock cycles”. Verification-based voter minimization guarantees that the resulting TMR circuit (i) is fault tolerant to the soft-errors defined by the fault model and (ii) is functionally equivalent to the initial TMR circuit. Our approach operates at the logic level and takes into account the input and output interface specifications of the circuit. Its implementation makes use of graph traversal algorithms, fixed-point iterations, and binary decision diagrams (BDD). Experimental results on the ITC’99 benchmark suite indicate that our method significantly decreases the number of inserted voters, yielding a hardware reduction of up to 55% and a clock frequency increase of up to 35% compared to full TMR. As our experiments show, if the SEU fault-model is replaced with the stricter fault-model of SET, it has a minor impact on the number of removed voters. On the other hand, BDD-based modelling of SET effects represents a more complex task than the modelling of an SEU as a bit-flip. We propose solutions for this task and explain the nature of encountered problems. We address scalability issues arising from formal verification with approximations and assess their efficiency and precision.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2018-10-15
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v005-i001-a004
10.4230/LITES-v005-i001-a004
Leibniz Transactions on Embedded Systems; Vol. 5 No. 1 (2018); 04:1-04:26
2199-2002
10.4230/LITES-v005-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v005-i001-a004/lites-v005-i001-a004-pdf
Copyright (c) 2018 Dmitry Burlyaev, Pascal Fradet, and Alain Girault
oai:ojs.dagstuhl.de:article/88
2018-01-08T10:46:08Z
lites:ART
driver
Per Processor Spin-Based Protocols for Multiprocessor Real-Time Systems
Afshar, Sara
Behnam, Moris
Bril, Reinder J.
Nolte, Thomas
Resource sharing
Real-time systems
Multiprocessors
Spin-locks
Computer systems organization~Real-time systems
Software and its engineering~Multiprocessing / multiprogramming / multitasking
Software and its engineering~Real-time schedulability
This paper investigates preemptive spin-based global resource sharing protocols for resource-constrained real-time embedded multi-core systems based on partitioned fixed-priority preemptive scheduling. We present preemptive spin-based protocols that feature (i) an increased schedulability ratio of task sets and reduced response jitter of tasks compared to the classical non-preemptive spin-based protocol, (ii) similar memory requirements for the administration of waiting tasks as for the non-preemptive protocol whilst only causing (iii) a minimal increase of the minimal number of required stacks per core from one to at most two, and (iv) strong progress guarantees to tasks. We complement these protocols with a unified worst-case response time analysis that specializes to the classical analysis for the non-preemptive protocol. The paper includes a comparative evaluation of the preemptive protocols and the non-preemptive protocol based on synthetic data.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2018-01-08
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i002-a003
10.4230/LITES-v004-i002-a003
Leibniz Transactions on Embedded Systems; Vol. 4 No. 2 (2017); 03:1–03:30
2199-2002
10.4230/LITES-v004-i002
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v004-i002-a003/lites-v004-i002-a003-pdf
Copyright (c) 2017 Sara Afshar, Moris Behnam, Reinder J. Bril, and Thomas Nolte
oai:ojs.dagstuhl.de:article/96
2021-07-16T13:55:00Z
lites:ART
driver
Local Planning Semantics: A Semantics for Distributed Real-Time Systems
Dellabani, Mahieddine
Combaz, Jacques
Bensalem, Saddek
Bozga, Marius
Distributed Real-Time Systems
Timed Automata
Formal Verification
Theory of computation~Formal languages and automata theory
Design, implementation and verification of distributed real-time systems are acknowledged to be very hard tasks. Such systems are prone to different kinds of delay, such as execution time of actions or communication delays implied by distributed platforms. The latter increase considerably the complexity of coordinating the parallel activities of running components. Scheduling such systems must cope with those delays by proposing execution strategies ensuring global consistency while satisfying the imposed timing constraints. In this paper, we investigate a formal model for such systems as compositions of timed automata subject to multiparty interactions, and propose a semantics aiming to overcome the communication delays problem through anticipating the execution of interactions. To be effective in a distributed context, scheduling an interaction should rely on (as much as possible) local information only, namely the state of its participating components. However, as shown in this paper these information is not always sufficient and does not guarantee a safe execution of the system as it may introduce deadlocks. Moreover, delays may also affect the satisfaction of timing constraints, which also corresponds to deadlocks in the former model. Thus, we also explore methods for analyzing such deadlock situations and for computing deadlock-free scheduling strategies when possible.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2019-02-18
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a001
10.4230/LITES-v006-i001-a001
Leibniz Transactions on Embedded Systems; Vol. 6 No. 1 (2019); 01:1-01:27
2199-2002
10.4230/LITES-v006-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a001/lites-v006-i001-a001-pdf
Copyright (c) 2019 Mahieddine Dellabani, Jacques Combaz, Saddek Bensalem, and Marius Bozga
http://creativecommons.org/licenses/by/3.0/de/deed.en
oai:ojs.dagstuhl.de:article/97
2018-11-19T15:56:24Z
lites:ART
driver
The Semantic Foundations and a Landscape of Cache-Persistence Analyses
Reineke, Jan
caches
persistence analysis
WCET analysis
Computer systems organization~Real-time system architecture
Theory of computation~Caching and paging algorithms
Hardware~Safety critical systems
We clarify the notion of cache persistence and contribute to the understanding of persistence analysis for caches with least-recently-used replacement.To this end, we provide the first formal definition of persistence as a property of a trace semantics. Based on this trace semantics we introduce a semantics-based, i.e., abstract-interpretation-based persistence analysis framework.We identify four basic persistence analyses and prove their correctness as instances of this analysis framework.Combining these basic persistence analyses via two generic cooperation mechanisms yields a lattice of ten persistence analyses.Notably, this lattice contains all persistence analyses previously described in the literature. As a consequence, we obtain uniform correctness proofs for all prior analyses and a precise understanding of how and why these analyses work, as well as how they relate to each other in terms of precision.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2018-08-02
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v005-i001-a003
10.4230/LITES-v005-i001-a003
Leibniz Transactions on Embedded Systems; Vol. 5 No. 1 (2018); 03:1-03:52
2199-2002
10.4230/LITES-v005-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v005-i001-a003/lites-v005-i001-a003-pdf
Copyright (c) 2018 Jan Reineke
oai:ojs.dagstuhl.de:article/98
2021-07-16T08:51:20Z
lites:ART
driver
Improving WCET Evaluation using Linear Relation Analysis
Raymond, Pascal
Maiza, Claire
Parent-Vigouroux, Catherine
Jahier, Erwan
Halbwachs, Nicolas
Carrier, Fabienne
Asavoae, Mihail
Boutonnet, Rémy
Worst Case Execution Time estimation
Infeasible Execution Paths
Abstract Interpretation
Software and its engineering~Real-time systems software
The precision of a worst case execution time (WCET) evaluation tool on a given program is highly dependent on how the tool is able to detect and discard semantically infeasible executions of the program. In this paper, we propose to use the classical abstract interpretation-based method of linear relation analysis to discover and exploit relations between execution paths. For this purpose, we add auxiliary variables (counters) to the program to trace its execution paths. The results are easily incorporated in the classical workflow of a WCET evaluator, when the evaluator is based on the popular implicit path enumeration technique. We use existing tools - a WCET evaluator and a linear relation analyzer - to build and experiment a prototype implementation of this idea.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2019-02-18
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a002
10.4230/LITES-v006-i001-a002
Leibniz Transactions on Embedded Systems; Vol. 6 No. 1 (2019); 02:1-02:28
2199-2002
10.4230/LITES-v006-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a002/lites-v006-i001-a002-pdf
Copyright (c) 2018 Pascal Raymond, Claire Maiza, Catherine Parent-Vigouroux, Erwan Jahier, Nicolas Halbwachs, Fabienne Carrier, Mihail Asavoae, and Rémy Boutonnet
http://creativecommons.org/licenses/by/3.0/de/deed.en
oai:ojs.dagstuhl.de:article/99
2021-07-16T08:51:20Z
lites:ART
driver
A Survey of Probabilistic Timing Analysis Techniques for Real-Time Systems
Davis, Robert I.
Cucu-Grosjean, Liliana
Probabilistic
real-time
timing analysis
Computer systems organization~Real-time systems
This survey covers probabilistic timing analysis techniques for real-time systems. It reviews and critiques the key results in the field from its origins in 2000 to the latest research published up to the end of August 2018. The survey provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas: static probabilistic timing analysis, measurement-based probabilistic timing analysis, and hybrid methods. In addition, research on supporting mechanisms and techniques, case studies, and evaluations is also reviewed. The survey concludes by identifying open issues, key challenges and possible directions for future research.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2019-05-14
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a003
10.4230/LITES-v006-i001-a003
Leibniz Transactions on Embedded Systems; Vol. 6 No. 1 (2019); 03:1-03:60
2199-2002
10.4230/LITES-v006-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a003/lites-v006-i001-a003-pdf
Copyright (c) 2019 Robert I. Davis and Liliana Cucu-Grosjean
oai:ojs.dagstuhl.de:article/100
2021-07-16T08:51:20Z
lites:ART
driver
A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems
Davis, Robert I.
Cucu-Grosjean, Liliana
Probabilistic
real-time
schedulability analysis
scheduling
Computer systems organization
Real-time systems
This survey covers schedulability analysis techniques for probabilistic real-time systems. It reviews the key results in the field from its origins in the late 1980s to the latest research published up to the end of August 2018. The survey outlinesfundamental concepts and highlights key issues. It provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas as well as research on supporting techniques. The survey concludes by identifying open issues, key challenges and possible directions for future research.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2019-05-14
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a004
10.4230/LITES-v006-i001-a004
Leibniz Transactions on Embedded Systems; Vol. 6 No. 1 (2019); 04:1-04:53
2199-2002
10.4230/LITES-v006-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a004/lites-v006-i001-a004-pdf
Copyright (c) 2019 Robert I. Davis and Liliana Cucu-Grosjean
oai:ojs.dagstuhl.de:article/102
2021-07-16T08:51:20Z
lites:ART
driver
Elastic Scheduling for Parallel Real-Time Systems
Orr, James
Gill, Chris
Agrawal, Kunal
Li, Jing
Baruah, Sanjoy
Parallel real-time tasks
multiprocessor federated scheduling
elasticity coefficient
Software and its engineering~Real-time schedulability
Computer systems organization~Real-time system architecture
Computer systems organization~Real-time system specification
Computer systems organization~Embedded software
The elastic task model was introduced by Buttazzo et al.~in order to represent recurrent real-time workloads executing upon uniprocessor platforms that are somewhat flexible with regards to timing constraints. In this work, we propose an extension of this model and apply it to represent recurrent real-time workloads that exhibit internal parallelism and are executed on multiprocessor platforms. In our proposed extension, the elasticity coefficient - the quantitative measure of a task's elasticity that was introduced in the model proposed by Buttazzo et al. - is interpreted in the same manner as in the original (sequential) model. Hence, system developers who are familiar with the elastic task model in the uniprocessor context may use our more general model as they had previously done, now for real-time tasks whose computational demands require them to utilize more than one processor.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
2019-05-14
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a005
10.4230/LITES-v006-i001-a005
Leibniz Transactions on Embedded Systems; Vol. 6 No. 1 (2019); 05:1-05:14
2199-2002
10.4230/LITES-v006-i001
eng
https://ojs.dagstuhl.de/index.php/lites/article/view/LITES-v006-i001-a005/lites-v006-i001-a005-pdf
Copyright (c) 2019 James Orr, Chris Gill, Kunal Agrawal, Jing Li, and Sanjoy Baruah