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

dc.contributor.authorHan, Jian-Jun
dc.contributor.authorZhu, Dakai
dc.contributor.authorWu, Xiaodong
dc.contributor.authorYang, Laurence T.
dc.contributor.authorJin, Hai
dc.description.abstractIn 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.
dc.description.departmentComputer Science
dc.publisherUTSA Department of Computer Science
dc.relation.ispartofseriesTechnical Report; CS-TR-2013-002
dc.subjectreal-time systems
dc.subjectperiodic tasks
dc.subjectshared resources
dc.subjectpartitioned scheduling
dc.subjectutilization bound
dc.titleMultiprocessor Real-Time Systems with Shared Resources: Utilization Bound and Mapping
dc.typeTechnical Report


Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
960.8 KB
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
1.86 KB
Item-specific license agreed upon to submission