Reference : WCET and Priority Assignment Analysis of Real-Time Systems using Search and Machine L...
Dissertations and theses : Doctoral thesis
Engineering, computing & technology : Computer science
Computational Sciences
WCET and Priority Assignment Analysis of Real-Time Systems using Search and Machine Learning
Lee, Jaekwon mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SVV >]
University of Luxembourg, ​​Luxembourg
Docteur en Informatique
Briand, Lionel mailto
Shin, Seung Yeob mailto
Pastore, Fabrizio mailto
Oriol, Manuel
Saadtmand, Mehrdad
[en] WCET estimation ; Priority assignment ; Schedulability Analysis ; Search-based Software Engineering ; Machine Learning ; Real-time systems
[en] Real-time systems have become indispensable for human life as they are used in numerous industries, such as vehicles, medical devices, and satellite systems. These systems are very sensitive to violations of their time constraints (deadlines), which can have catastrophic consequences. To verify whether the systems meet their time constraints, engineers perform schedulability analysis from early stages and throughout development. However, there are challenges in obtaining precise results from schedulability analysis due to estimating the worst-case execution times (WCETs) and assigning optimal priorities to tasks.
Estimating WCET is an important activity at early design stages of real-time systems. Based on such WCET estimates, engineers make design and implementation decisions to ensure that task executions always complete before their specified deadlines. However, in practice, engineers often cannot provide a precise point of WCET estimates and they prefer to provide plausible WCET ranges.
Task priority assignment is an important decision, as it determines the order of task executions and it has a substantial impact on schedulability results. It thus requires finding optimal priority assignments so that tasks not only complete their execution but also maximize the safety margins from their deadlines. Optimal priority values increase the tolerance of real-time systems to unexpected overheads in task executions so that they can still meet their deadlines. However, it is a hard problem to find optimal priority assignments because their evaluation relies on uncertain WCET values and complex engineering constraints must be accounted for.
This dissertation proposes three approaches to estimate WCET and assign optimal priorities at design stages. Combining a genetic algorithm and logistic regression, we first suggest an automatic approach to infer safe WCET ranges with a probabilistic guarantee based on the worst-case scheduling scenarios. We then introduce an extended approach to account for weakly hard real-time systems with an industrial schedule simulator. We evaluate our approaches by applying them to industrial systems from different domains and several synthetic systems. The results suggest that they are possible to estimate probabilistic safe WCET ranges efficiently and accurately so the deadline constraints are likely to be satisfied with a high degree of confidence. Moreover, we propose an automated technique that aims to identify the best possible priority assignments in real-time systems. The approach deals with multiple objectives regarding safety margins and engineering constraints using a coevolutionary algorithm. Evaluation with synthetic and industrial systems shows that the approach significantly outperforms both a baseline approach and solutions defined by practitioners. All the solutions in this dissertation scale to complex industrial systems for offline analysis within an acceptable time, i.e., at most 27 hours.
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Software Verification and Validation Lab (SVV Lab)
European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 694277) ; Mitacs through the Mitacs Accelerate program (IT23234) ; NSERC of Canada under the Discovery and CRC programs
H2020 ; 694277 - TUNE - Testing the Untestable: Model Testing of Complex Software-Intensive Systems

File(s) associated to this reference

Fulltext file(s):

Open access
UL_thesis_Jaekwon.pdfAuthor postprint2.87 MBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.