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

Date

2013-01

Authors

Han, Jian-Jun
Zhu, Dakai
Wu, Xiaodong
Yang, Laurence T.
Jin, Hai

Journal Title

Journal ISSN

Volume Title

Publisher

UTSA Department of Computer Science

Abstract

In real-time systems, both scheduling theory and resource access protocols have been studied extensively. However, there is very limited research focusing on scheduling algorithms specifically for real-time systems with shared resources, where the problem becomes more prominent with the emergence of multicore processors. In this paper, focusing on the partitioned-EDF scheduling with the MSRP resource access protocol, we study the utilization bound and efficient task mapping schemes for a set of periodic real-time tasks running on a multicore/multiprocessor system with shared resources. Specifically, we first illustrate the scheduling anomaly where the tasks are schedulable when being mapped on to fewer but not more processors due to synchronization overhead. Then, with such synchronization overhead being considered, we develop a synchronization-cognizant utilization bound. Moreover, we show that finding the optimal mapping of tasks with shared resources is NP-hard and propose two efficient synchronization-cognizant task mapping algorithms (SC-TMA) that rely on the new tightened synchronization overhead and have 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.

Description

Keywords

real-time systems, multiprocessor, periodic tasks, shared resources, partitioned scheduling, utilization bound

Citation

Department

Computer Science