A Comparison of Partitioning Strategies for Fixed Points-based Limited Preemptive Scheduling

• The increasing industrial demand for handling complex functionalities has influenced the design of hardware architectures for time critical embedded systems, during the past decade. Multi-core systems facilitate the inclusion of many complex functionalities, while, at the same time, inducing cache related overheads, as well as adding partitioning complexity to the overall system schedulability. One of the efficient paradigms for controlling and reducing the cache related costs in real-time systems is Limited Preemptive Scheduling (LPS), with its particular instance Fixed Preemption Points Scheduling (LP-FPPS), that has been shown to outperform other alternatives as well as has been supported by and investigated in the automotive domain. With respect to the partitioning constraints, Partitioned Scheduling has been widely used to pre-runtime allocate tasks to specific cores, resulting in a predictable cache-related preemption delays estimations. In this paper we propose to integrate LP-FPPS and Partitioned Scheduling on fixed-priority multicore real-time systems in order to increase the overall system schedulability.We define a new joint approach for task partitioning and preemption point selection, that is based on the computation of the maximum blocking tolerance upon each allocation, thus being able to quantify the schedulability of the taskset on each processor. Furthermore, we investigate partitioning strategies based on different heuristics, i.e. First Fit Decreasing and Worst Fit Decreasing, and priority and density taskset orderings. The evaluation performed on randomly generated tasksets shows that in the general case, no single partitioning strategy fully dominates the others. However, the evaluation results reveal that certain partitioning strategies perform significantly better with respect to the overall schedulability for specific taskset characteristics. The results also reveal that the proposed partitioning strategies outperform Fully Preemptive and Non-Preemptive partitioned scheduling in terms of successful partitioning.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

Real-Time Systems

Partitioned Scheduling

Limited Preemptive Scheduling

Fixed Preemption Points

Computer Science

datavetenskap

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)