A feasible decision algorithm for rate monotonic and deadline monotonic scheduling

The rate monotonic scheduling algorithm is a com-monly used task scheduling algorithm for periodic real-time task systems. This paper discusses feasibility de-cision fo r a given real-time task system b y the rate monotonic scheduling algorithm. It presents a new necessary a n d suficient condition fo r a given task sys-tem to be feasible, and a new feasibility decision algo-rithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This algorithm can be applied to the inverse-deadline scheduling algorithm, which is an extension of the rate monotonic scheduling algorithm.