Response-Time Analysis for Non-Preemptive Global Scheduling with Spin Locks

Abstract

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.