With the strong demand for computing capacity in industrial applications and the rapid development of the hardware industry in recent years, multiprocessor platforms have been widely used in real-time embedded systems. The quest for performance has led to existing multiprocessor platforms often featuring complex interconnected hardware components and multiple levels of cache. This brings negative interference to the execution of tasks and challenges the predictability of real-time systems. However, existing non-preemptive execution models are an effective solution to eliminate these negative effects. In addition to this, the tasks that modern real-time systems process are becoming increasingly complex. Traditional sequential task models cannot cope with this situation and a stronger expressive model is required. A directed acyclic graph (DAG) that can express the complexity and parallelism of these tasks is a suitable model.

In this thesis, we focus on priority-based scheduling algorithms for multiple parallel DAG tasks on non-preemptive multiprocessor platforms, investigating, analysing, and improving existing global and partitioned scheduling algorithms.

We propose the concept of stacks to simulate a multi-processor platform and apply release-time tuning techniques based on its simulation of a task set in a hyperperiod. This allows us to impose tighter constraints on the execution of each job released from a task set in a fine-grained manner. We improved the existing priority-based global scheduling algorithm through the release-time tuning technique mentioned above. We also tried to construct a partitioned scheduling algorithm using the simulation results of stacks, i.e. so that all jobs are restricted to run on only one processor, consistent with the simulation results. Furthermore, to compare different scheduling algorithms more efficiently and to facilitate future researchers, we have developed the evaluation framework, a customisable experimental platform that includes DAG generation, application of scheduling algorithms, generation and analysis of the test results, allowing users to specify their experiments according to their goals.

Experiments with randomly generated workloads show that our improved algorithm consistently outperforms the state-of-the-art priority-based scheduling algorithm for different task graph structures and parameter configurations.

Since its introduction in 2007, ROS (Robot Operating System) has become one of the most popular framework for developing automated solutions in a variety of applications, ranging from automotive to manufacturing. Meeting safety-critical timing requirements is a crucial element in many fields where ROS is present. The ROS community has introduced several improvements to allow developers to create more time-predictable implementations, with the introduction of ROS2 being the major step forward. In the following thesis, we examine structure of ROS2 to discover task scheduling and data distribution related challenges that developers will face when trying to implement latency-sensitive ROS2 applications based on periodic tasks. We propose a set of improvements that allow to mitigate presented challenges. A prototype of a new scheduling mechanisms embedded within ROS2 logic is introduced to combine both callback scheduling and efficient intra-process data exchange. Furthermore, by exploring possible new ROS2 extensions, we address scenarios where applications have to dynamically adjust to temporary changes in timing-constraints. We extend the existing ROS2 APIs with an option to easily create new scheduling policies to handle specific requirements for each application without the need for any kernel level scheduler modifications.

The temporal correctness of safety-critical systems is typically guaranteed via a response-time analysis, whose goal is to determine the worst-case response time (WCRT) of a set of input jobs when they are scheduled by a given scheduling policy on a computing resource.
However, response-time analysis is a hard problem to solve, with most variations of the problem being NP-hard. Recently, Nasri et al. have introduced an exact reachability-based response-time analysis that is based on exploring the space of possible decisions that a scheduler can take for a set of jobs/tasks. Their solution is at least three orders of magnitude faster than other exact response-time analyses and scales well.

Despite its current success in scalability, the schedule-abstraction-based analysis still faces one big fundamental limitation: in the reachability graph that it builds, each edge can only include one single scheduling decision. As a result, as soon as there are large uncertainties in the release time or execution time of the jobs in the input job set, the number of states generated by the schedule-abstraction graph grows exponentially because the analysis will try to explore all (valid) combinations of ordering between jobs.

We improve the scalability of the schedule-abstraction-based analysis by introducing partial-order reduction (POR) rules that allow combining multiple scheduling decisions on one edge and hence avoiding combinatorial exploration of all possible orderings between jobs in cases where there are large uncertainties. Our solution is an exact schedulability analysis and provides a safe response-time analysis that reduces the size of the graph while only introducing a small overestimation on the WCRT of the jobs.

Our key idea is to identify subsets of jobs for which the combinatorial exploration of all orderings is irrelevant to the schedulability of the job set. Exploring these combinations is irrelevant when all scenarios lead to a system state without encountering a deadline miss in any of those scenarios. Dispatching such jobs can be considered in a single step (that combines all those scheduling decisions), which further defers the state-space explosion.

We show that our solution is able to reduce the runtime of the analysis by five orders of magnitude on average, and the number of explored states by 98% on average in comparison to the original schedule-abstraction-based analysis of Nasri et al. for randomly generated periodic task sets. This achievement comes with a negligible cost of an average 0.1% increase in the WCRT of the jobs. This shows that POR allows us to analyze even more task sets than the original and has the potential to scale even further.

ROS 2 is a well-known software framework for the development of robotic applications. The open-source project enjoys active interest and participation from both academia and industry in applications spanning from autonomous vehicles to industrial robotics. ROS 2's success is underpinned by its disposition for collaborative development as well as its rich third-party package system. This has enabled developers to rapidly design, apply, and share their work while abstracting away the tedium of reimplementing common software constructs. Since the incarnation of ROS 1, ROS has shifted its focus away from medium-power workstations towards embedded systems. These efforts have born out ROS 2, a revision of the original ROS concept with a goal of supporting real-time applications.

Unfortunately, ROS 2 suffers from several major drawbacks that diminish its feasibility for applications with real-time requirements. Its idomatic C++ library contains an executor with a noncomformant callback scheduling model, which is neither priority aware or capable of preemptive callback execution. This makes ROS 2 considerably less time-predictable, as high-priority callbacks may suffer from priority inversions, and common real-time scheduling policies cannot be applied. Furthermore, ROS 2 is built upon a distributed messaging system, with system functions split across callbacks linked through a publish-subscribe communication mechanism. This frustrates the development of solutions for ROS, as it still requires developers cope with distributed chains of execution that must contend with precedence relations, synchronisation devices, and message passing overhead.

In response to these deficiencies, this thesis presents five major contributions: (1) two new executor implementations, with support for both callback prioritisation and preemptive callback execution. (2) a new priority-synthesis algorithm, which uses a graph model to map a set of callback-chain priorities to callbacks within ROS applications. (3) A simple feasibility test for ROS 2 applications based on callback chains. (4) A schedulability test for ROS 2 applications with harmonic chains. (5) A novel testing framework, which integrates the priority-synthesis algorithm, and enables the easy and rapid generation of test applications for development purposes.

The evaluation reveals that the new executors deliver superior performance in metrics such as worst-case response time, deadline misses, and jitter. On applications with up to 60% utilisation under rate-monotonic scheduling, the new executor implementations deliver no deadline misses, as opposed to the standard executor encountering them at just 10%. Finally, on high priority chains, the new executors can deliver up to 1300% times less jitter over the standard.

Ultrawideband technology can be used to measure the distance between two device equipped with ultrawideband transceivers. Multiple ultrawideband devices known as anchors can localize a device that supports ultrawideband communication after each anchor measures the distance between itself and the device. The anchor and the tag can measure the distance between themselves by measuring the time of flight of the ultrawideband messages exchanged between them. If the location of the anchors are known, the location of the device can be computed. However, errors in range measurements can cause errors in localization of the device. There are many sources that can cause errors in the measured range between the anchor and the tag. For example, when the tag transmits a signal, and the path between the anchor and the tag is blocked, the signal may be attenuated to such an extent that it may go undetected at the anchor, causing the anchor to measure the time of arrival of a delayed reflection. In this thesis, we aim to find a solution to improve the ranging accuracy when an anchor is equipped with two antennas. We target approaches that can be implemented on an embedded processor with limited resources. In order to improve the ranging accuracy, we first investigate various machine learning based classifiers that can identify non-line of sight and line of sight signals. Next, for each of the classified signal, we train and test various machine learning based regression models that will predict the true distance from the distance measured by the anchor. We conclude the thesis, by assessing the robustness of the derived classification and regression models by evaluating the range improvements in measurements taken in different scenarios.

2.5D shape display is a recent idea in the market that emerged as a platform of interaction between a computer and human. 2.5D shape display is essentially a grid-like matrix consisting of actuators and pins moving up and down in vertical motion to create pseudo-3D images. Focused as a visual display in some applications and as a medium of input or output in others, this technology holds a lot of potentials to be explored in present and future applications since it is a unique type of hardware that can actually show images in a real world. Recently, many such platforms have been created by the use of different hardware solutions and have found applications in gaming interface, physical telepresence, dynamic objects etc. Some research areas that can still be explored are applications for the blind, building and object modelling etc. With advances in applications, there is a need for hardware with higher resolution at a lower cost. Also, being an interact-able display, safety and comfort of the user is of utmost importance. This has been seen to be lacking in the existing projects. In this thesis, we focus on designing a prototype for building a safe display with minimal cost. We then go on to understand safety and comfort for the chosen display prototype and design some safe actuation algorithms. These are later evaluated using a combination of an experimental survey and simulation to find and propose a good solution for safe 2.5D shape displays.

With the growth in the complexity of real-time embedded systems, there is an increasing need for tools and techniques to understand and compare the observed runtime behavior of a system with the expected one. Since many realtime applications require periodic interactions with the environment, one of the fundamental problems in guaranteeing/monitoring their temporal correctness is to be able to infer the periodicity of certain events in the system. The practicability of a period inference tool, however, depends on both its accuracy and robustness (resilience) against noise in the output trace of the system, e.g., when the system trace is impacted by events that have a non-deterministic nature such as the presence of aperiodic tasks, release jitters and runtime execution-time variations of the tasks.
This work (i) presents a period inference framework that uses regression-based machine-learning (RBML) methods, (ii) thoroughly investigates the accuracy and robustness of different families of RBML methods in the presence of uncertainties in the system parameters, and (iii) proposes further accuracy improvements by deriving candidate pruning rules based on the inherent properties of the underlying scheduling policies. We show, on both synthetically generated traces and traces from actual systems, that our solutions can reduce the error of period estimation by two to three orders of magnitudes w.r.t. state of the art. Also, our methods showed to be robust against most sources of disturbance.

Gang scheduling, has long been adopted by the high-performance computing community as a way to reduce the synchronization overhead between related threads. Gang schedulling allows for several threads to execute in lock steps without suffering from long busy-wait periods or be penalised by large context-switch overheads. If several threads use the same data, it also reduces the number of memory transactions by allowing the program to load those data only once for all threads rather than once per thread. To avoid reloading large amount of data after each preemption and hence incur large execution-time overheads, in this work, we assume that the tasks adhere to a limited-preemptive execution model. We further assume that each gang task is moldable, that is, it has a minimum and a maximum number of cores on which it may be executed. The actual execution time of a job depends then on the number of cores allocated by the scheduler at run-tiem. In this work, we consider the case for which tasks are scheduled according to a global job-level fixed priority scheduling algorithm, and present a worst-case response time analysis for limited-preemptive moldable gang tasks. Additionally, we propose a new scheduling policy to improve the
schedulability of moldable gang tasks.

With the proliferation of multicore platforms, the embedded systems world has shifted more and more towards multiprocessing to make use of high computing power and increased cyber functionalities. Although today multiprocessor platforms have been extensively adopted by real-time embedded systems, there exists a need for tools and techniques that can accurately assess the temporal correctness of a system. In terms of multiprocessor systems, this is coupled with fundamental challenges, since these systems, as we find them today, make use of complex hardware components, resource sharing and memory architectures, which negatively affect the timing predictability of such systems. Spin-based locking protocols, which are used to ensure mutual exclusion when sharing resources in a system, and a non-preemptive execution model have been found to help mitigate the adverse effect on the timing predictability, since they allow for less interruptions, which results in reduced cache evictions and a better estimate of worst-case execution times. While this improves the overall timing predictability of such systems, to date, there exists no response-time analysis that can analyze multiprocessor systems that globally execute non-preemptive tasks sharing resources protected by spin locks. Motivated by the lack of analysis tools for systems that consider non-preemptive global scheduling and the access to shared resources, this work provides the first analysis for global job-level fixed-priority (JLFP) scheduling policies and FIFO- or priority-ordered spin locks. To do so, it extends the family of schedule-abstraction-based analysis to model the access to shared resources in a highly accurate manner. The proposed analysis computes response-time bounds for a set of resource-sharing jobs subject to release jitter and execution-time uncertainties by implicitly exploring all possible execution scenarios using state-abstraction and state-pruning techniques. A large-scale empirical evaluation of the proposed analysis shows it to be substantially less pessimistic than simple execution-time inflation methods (i.e., a straightforward extension of existing response-time analysis tools for non-preemptive tasks that do not share resources), thanks to the explicit modeling of contention for shared resources and a scenario-aware blocking analysis.

While multiprocessor platforms have been widely adopted by the embedded systems industry in the past couple of years, there are still fundamental challenges about their timing predictability for applications with real-time timing constraints. The common-off-the-shelf (COTS) multiprocessor platforms typically use complex hardware components, interconnects and multi-level caches which are designed to deliver higher average-case performance. However, these features negatively impact the worst-case performance as they increase the interference of tasks on shared hardware resources. One effective software-based solution to counteract these issues is to use the non-preemptive execution model.

Despite its positive impact on timing predictability, non-preemptive execution causes a potential blocking problem which can decrease the ability to guarantee all timing constraints of the system. It is also known that scheduling non-preemptive periodic tasks on multiprocessor platforms is an NP-hard problem.

In this thesis, we focus on non-preemptive execution of sequential as well as parallel real-time tasks upon multiprocessor platforms and investigate, extend, and improve the state of the art on global, partitioned, and semi-partitioned scheduling approaches for the problem.

We provide the first necessary test for partition-ability, i.e., a test that can determine whether a given task set cannot be partitioned on a given number of cores regardless of the partitioning policy. This test allows us to quantify the pessimism of the existing partitioning heuristics as well as obtain the limits of partitioned scheduling.
We further introduce the first non-work-conserving global scheduling policy and show that despite the fact that it improves over the existing global scheduling policies, it is not as effective as the partitioned scheduling strategies.

We extend a sustainable scheduling algorithm designed for uni-processor platforms to multiprocessor ones to improve the performance of partitioning heuristics. A sustainable scheduling algorithm does not have timing anomalies and hence it is easier to analyze and can have better scheduling results.

Furthermore, we introduce the first semi-partitioned non-preemptive scheduling solution for multiprocessor platforms. Our solution is able to schedule some of the task sets for which it is impossible to find a partitioning solution. Finally, we compare the overheads and memory consumption of various scheduling approaches (including ours) on a bare-metal multiprocessor hardware platform, i.e., a 4 processor Raspberry Pi board. We show that our sustainable scheduler has a very low overhead while it out-performs other solutions in terms of schedulability.

Real-time systems are bound to timing constraints. These constraints are meant to ensure that the application exhibits predictable behavior by having bounded response times. The worst case execution time (WCET) is an important property of programs, which must be bounded to allow for a response time analysis of tasks. While estimation of the WCET is a difficult problem, modern commercial off-the-shelf processors with multiple processor cores make the WCET estimation problem even harder to solve, because of the existence of shared hardware resource contention among co-running tasks. This work proposes a parametric WCET estimation tool, with which configurable and reproducible experiments can be created to investigate the co-runners’ problem for specific task sets. The created tool runs on two hardware platforms, both featuring ARM Cortex quad core processors. Three different benchmarks suites are implemented in the tool, which can be configured to run in arbitrary combinations on the processor cores. These are a set of synthetic benchmarks meant to stress the memory system, a subset of the Mälardalen WCET benchmark suite and a subset of the San Diego vision benchmark suite. The value of the tool is demonstrated through three sets of experiments. With these experiments, the effects of shared hardware resources are investigated in detail. We show that the experienced slowdown is highly dependent on multiple factors. First, a major factor is the sensitivity to the co-runners’ effects of the task itself. Two extremes are investigated, from a task being insensitive to a task being highly sensitive. Another factor is the size of the input data, which is shown to be a major contributor to the experienced slowdown. Finally, we evaluate the delayed execution of co-running tasks, which in some cases has a significant effect on the experienced slowdown. When we consider a task’s slowdown as a function of the delayed execution of its co-runners, the knowledge on this function’s behavior for specific tasks provides an optimization strategy that could be used to mitigate the problem of shared hardware resource contention.

Switches that can be (re)programmed through the network programming language P4 are able to completely change – even while in the field – the way they process packets. While powerful, P4 code is inherently static, as it is written and installed to accommodate a particular network requirement. Writing new P4 code each time new requirements arise may be complex and limits our agility to deal with changes in network traffic and services. To solve that problem, we present two frameworks within this work: P4I/O and GP4P4. P4I/O is a new approach to data-plane programmability based on the philosophy of Intent-Based Networking. P4I/O provides an intent-driven interface that can be used to install and/or remove P4 programs on the switches when needed and which is easy to use. In particular, to realize P4I/O, we (1) describe an extensible Intent Definition Language (IDL), (2) create a repository of P4 code templates, which are parsed and merged based on the intents, (3) provide a technique to realize the resulting P4 program in a programmable switch, while accommodating intent modifications at any time, and finally (4) implement a proof-of-concept to demonstrate that intent modifications can be done on-the-fly. Our second framework, GP4P4, is a genetic programming approach able to autonomously generate programs for P4-programmable switches directly from network intents. We demonstrate that GP4P4 is able to generate various network functions in up to a few minutes; an important first step towards realizing the vision of ‘Self-Driving’ networks.

Feedback-analytics, describing themselves as, "A Dutch based start-up for companies interested in improving both customer feedback and their employee efficiency, Feedback-analytics aims to be a simple yet robust tool that allows you to identify and manage points of improvement that your company might need ” The company started from the ground up with on one single vision: Identify business inefficiencies and improve consumer satisfaction in the process. The proposed method is to gather feedback from consumers and converting this into data which can be analyzed by the company. The focus of the product is a web-based form system with logic built in; implementing an integrated form building system and converting data gathered from these forms into analytics. Implementing every functionality of such a system from scratch in the short amount of time given is naturally unfeasible, our group made it its main goal to have: a solid backend server foundation for the system, the main form builder interface complete with logic and a robust working database structure. This project covers a wide variety of courses from the bachelor programe, and we are very excited to have an opportunity to finally apply everything we’ve learned during bachelor in a full fledged real-world project.

Tock is an embedded operating system that can run multiple concurrent, mutually distrustful processes, concurrently. Tock is written in Rust, a novel system programming language enforcing type safety at compile-time, and takes advantage of Rust's strong safety features. However, since Tock allows user-level applications to be written in any language, Rust is not sufficient in guaranteeing memory safety for user-level Tock. To obtain memory isolation, Tock takes advantage of MPUs provided by recent microcontrollers. Although Tock is supposed to be fully architecture agnostic, it is at present only able to support the MPU of the Cortex-M architecture. The lack of an architecture-agnostic MPU interface, process manager and the corresponding MPU implementations is the biggest remaining hurdle in making Tock architecture independent. In order to create such an interface, this work performs an analysis of state-of-the-art MPUs, comparing their key features and constraints. A feasibility study for the design of an MPU interface in Tock is carried out, resulting in a number of general changes to the current implementation of Tock, and leading up to the design, implementation and evaluation of two MPU interfaces. The first is a region-based interface, aiming to have an abstraction that is straightforward and completely agnostic of what the MPU is used for. The second interface is a process-based interface, that utilizes knowledge of what it is applied for in order to provide a solution that is more efficient given the constraints and optimizations of an arbitrary MPU. Implementations for the Cortex-M, Kinetis K and nRF51 MPUs are created that match these interfaces, and in addition fundamental adaptations to process management in the Tock kernel are made. On the Hail development board, these changes reduce context switching time by 25.34%, but lead to a cost of 848 bytes or 1.0% in flash memory overhead. Most importantly, with the introduction of these interfaces, the biggest hurdle for Tock in becoming a multi-architecture operating system is overwon.