Multiprocessor Real-Time Systems with Shared Resources: Utilization Bound and Mapping

In real-time systems, both scheduling theory and resource access protocols have been studied extensively. However, there is very limited research on scheduling algorithms for real-time systems with shared resources, where the problem becomes more prominent with the emergence of multicore processors. In this paper, focusing on partitioned-EDF scheduling and MSRP resource access protocol, we study the utilization bound and efficient task mapping schemes for a set of periodic real-time tasks that access shared resources in multiprocessor/multicore systems. Specifically, with synchronization overhead being considered, we illustrate the schedulability anomaly for such systems. We develop the first synchronization-cognizant utilization bound and further analyze its non-monotonicity where the bound can decrease when more processors are deployed. Then, we show that finding the optimal mapping for tasks with shared resources is NP-hard. Based on a novel approach that iteratively tightens the synchronization overhead, we propose two efficient synchronization-cognizant task mapping algorithms (SC-TMA) with the goal of achieving better schedulability and balanced workload on deployed processors. Finally, the proposed SC-TMA schemes are evaluated through extensive simulations with synthetic tasks. The results show that, the schedulability ratio and (average) system load under SC-TMA are close to that of an INLP (Integer Non-Linear Programming) based solution for small task systems. When compared to the existing task mapping algorithms, SC-TMA obtain much better schedulability ratio and lower/balanced workload on all processors.