Real-time multiprocessor scheduling : feasibility issues

International audienceThe use of computers to control safety-critical real-time functions has increased rapidly over the past few years. As a consequence, real-time systems --- computer systems where the correctness of each computation depends on both the logical results of the computation and the time at which these results are produced --- have become the focus of much study. Since the concept of "time" is of such importance in real-time application systems, and since these systems typically involve the sharing of one or more resources among various contending processes, the concept of scheduling is integral to real-time system design and analysis. Scheduling theory as it pertains to a finite set of requests for resources is a well-researched topic. However, requests in real-time environment are often of a recurring nature. Such systems are typically modelled as finite collections of simple, highly repetitive tasks, each of which generates jobs in a very predictable manner. These jobs have upper bounds upon their worst-case execution requirements, and associated deadlines. We are interested in global scheduling of periodic task systems upon identical multiprocessor platforms. More precisely, we present the main steps that one should follow when he/she searches for feasibility intervals in the multiprocessor case. Contrary to the uniprocessor case, if a feasible schedule (obtained in the multiprocessor case) repeats from some time instant, then it is not obvious that a feasibility interval exists. This property remains true only for predictable scheduling algorithms. Otherwise, we deal with scheduling "anomalies"