Multiprocessor Preemptive Scheduling Algorithm for Hard Real-Time Systems

Abstract

This research is concerned with one of the problems of the scheduling of processes in hard real-time systems. It presents an algorithm which finds a multiprocessor feasible preemptive schedule whenever one exists for a set of processes on M identical processors(have the same speed). This schedule must satisfY a given set of release times, deadlines, precedence, and exclusion constraints defined on the segments of these processes and it can be used in a multiprocessor hard real-time system to automate pre-run-time scheduling of processes where an arbitrary precedence and exclusion relations are assumed on these processes. This algorithm is used to find a feasible schedule whenever one exists, and by computing a lower bound on the lateness of the schedule(the maximum lateness between processes)it can also inform the user whether the schedule can not be a feasible one(lower bound> 0). This algorithm uses branch-and-bound strategy, that is, it uses a search tree to find a feasible schedule, and at each node it stores the . partial information that is different from the information stored at its ancestor nodes.