  This research addresses the multiprocessor scheduling problem of hard
real-time systems, and it especially focuses on optimal and global schedulers
when practical constraints are taken into account. First, we propose an
improvement of the optimal algorithm BF. We formally prove that our adaptation
is (i) optimal, i.e., it always generates a feasible schedule as long as such a
schedule exists, and (ii) valid, i.e., it complies with the all the
requirements. We also show that it outperforms BF by providing a computing
complexity of O(n), where n is the number of tasks to be scheduled. Next, we
propose a schedulability analysis which indicates a priori whether the
real-time application can be scheduled by our improvement of BF without missing
any deadline. This analysis is, to the best of our knowledge, the first such
test for multiprocessors that takes into account all the main overheads
generated by the Operating System.

Operating Systems;Distributed, Parallel, and Cluster Computing