Limited carry-in technique for real-time multi-core scheduling

作者：Lee Jinkyu; Shin Insik^*

来源：Journal of Systems Architecture, 2013, 59(7): 372-375.

DOI：10.1016/j.sysarc.2013.05.012

• Real-time systems
• Schedulability analysis
• Limited carry-in technique
• Real-time multi-core scheduling

Schedulability analysis has been widely studied to provide offline timing guarantees for a set of real-time tasks. The so-called limited carry-in technique, which can be orthogonally incorporated into many different multi-core schedulability analysis methods, was originally introduced for Earliest Deadline First (EDF) scheduling to derive a tighter bound on the amount of interference of carry-in jobs at the expense of investigating a pseudo-polynomial number of intervals. This technique has been later adapted for Fixed-Priority (FP) scheduling to obtain the carry-in bound efficiently by examining only one interval, leading to a significant improvement in multi-core schedulability analysis. However, such a successful result has not yet been transferred to any other non-FP scheduling algorithms. Motivated by this, this paper presents a generic limited carry-in technique that is applicable to any work-conserving algorithms. Specifically, this paper derives a carry-in bound in an algorithm-independent manner and demonstrates how to apply the bound to existing non-FP schedulability analysis methods for better schedulability.

• 出版日期2013-8