Copyright © 2011 Omar Kermia. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

This paper focuses on real-time nonpreemptive multiprocessor scheduling with precedence and strict periodicity constraints. Since this problem is NP-hard, there exist several approaches to resolve it. In addition, because of periodicity constraints our problem stands for a decision problem which consists in determining if, a solution exists or not. Therefore, the first criterion on which the proposed heuristic is evaluated is its schedulability. Then, the second criterion on which the proposed heuristic is evaluated is its execution time. Hence, we performed a schedulability analysis which leads to a necessary and sufficient schedulability condition for determining whether a task satisfies its precedence and periodicity constraints on a processor where others tasks have already been scheduled. We also present two multiperiodic applications.