Accelerated Simply Periodic Task Sets for RM Scheduling

International audienceThe article examines rate-monotonic scheduling (RMS). The focus is on efficient schedulability tests of high sensitivity.Accelerated simply periodic task sets (ASPTSs) are constructed by shortening task periods in order to obtain a transformed – simply periodic – task set where each period is an integer divisor of all longer periods. The article presents a new heuristic for partitioned multiprocessor (MP) scheduling based on Specialization with respect to r (Sr) and Distance-Constrained Tasks (DCT) which use ASPTSs first described by Han and Tyan [9, 10]. They have al- ready shown the advantage of Sr and DCT over the Liu/Layland (LL) and the Burchard (Bu) bound in terms of sensitivity. First, the article compares Sr and DCT as well with other uniprocessor scheduling criteria, both theoretically and empirically. Next, these tests are applied to MP scheduling. Theory is followed by a case study and an empirical investigation with randomised task sets. Related approaches are thoroughly examined and summarised in a scheme where the central role of ASPTSs becomes obvious.The article shows that Sr and DCT provide a very good trade-off between maximizing the scheduling test sensitivity (no unnecessary hardware) and minimizing the test’s computational complexity (towards real-time decisions on schedulability)