online read us now
Paper details
Number 4 - December 2015
Volume 25 - 2015
Maintaining the feasibility of hard real-time systems with a reduced number of priority levels
Muhammad Bilal Qureshi, Saleh Alrashed, Nasro Min-Allah, Joanna Kołodziej, Piotr Arabas
Abstract
When there is a mismatch between the cardinality of a periodic task set and the priority levels supported by the underlying
hardware systems, multiple tasks are grouped into one class so as to maintain a specific level of confidence in their accuracy.
However, such a transformation is achieved at the expense of the loss of schedulability of the original task set. We further
investigate the aforementioned problem and report the following contributions: (i) a novel technique for mapping unlimited
priority tasks into a reduced number of classes that do not violate the schedulability of the original task set and (ii) an
efficient feasibility test that eliminates insufficient points during the feasibility analysis. The theoretical correctness of both
contributions is checked through formal verifications. Moreover, the experimental results reveal the superiority of our work
over the existing feasibility tests by reducing the number of scheduling points that are needed otherwise.
Keywords
real-time systems, feasibility analysis, fixed-priority scheduling, rate monotonic algorithm, online scheduling