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.

For any real-time system, being predictable with respect to time is a basic necessity. The combination of a preemptive execution model and a multiprocessor platform poses a challenge when analysing the predictability of a system. In this thesis, we present a new type of framework for the worst-case response time analysis for preemptive tasks scheduled on multiprocessor platforms. The proposed framework analyses this worst-case response time by building a schedule abstraction graph that abstracts all the execution scenarios that occur in the system. Since preemptive tasks scheduled on a multiprocessor platform creates a large state space of execution scenarios to explore, a schedule abstraction graph can easily face a state space explosion problem. A novel methodology has been introduced in this thesis, that allows us to eliminate state space explosion altogether. We used this new schedule abstraction graph framework to initially develop an analysis for uniprocessor platforms and compare it to the state-of-the-art. We then explain how the analysis can be extended from uniprocessor to multiprocessor platforms.

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.

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.