A new RM/DM low cost schedulability test

JOSÉ M. URRIZA; FRANCISCO E. PAEZ; MARIANO A. FERRARI; RICARDO CAYSSIALS; JAVIER D. OROZCO

Buenos Aires

Simposio; 2017 Eight Argentine Symposium and Conference on Embedded Systems (CASE); 2017

ACSE​ , Asociación Civil para la Investigación, Promoción y Desarrollo de los Sistemas Electrónicos Embebidos

This paper focuseson reducing the computational cost of iterative algorithms used toevaluate the schedulability of a Real-Time System scheduled by theRate Monotonic (RM) or Deadline Monotonic (DM) policies. Thesealgorithms calculate the worst case response time of each task of areal-time system. Several runtime strategies for fault tolerancemechanisms, power consumption methods and execution of non-real-timetasks, among others, require low computational cost schedulabilityalgorithms to be efficiently implemented in real applications. The algorithmproposed is based in mathematical properties of the real-timeschedulability test, that reduce noticeably the number of iterationsneeded to converge to the final solution. Through simulations, it isfound that the proposed algorithm produces a significant reduction inthe average temporal cost reaching in some cases, a complexityreduction from O(n^2) to O(n.log(n)), with respect to classicalschedulability algorithms.