Implementation and Variations of an Efficient Scheduling Algorithm for Non-Preemptive Independent Multiprocessor Tasks

Stefan Andrei¹, S.Kami Makki¹, Quentin Mayo²

Abstract

Given a task set, determining the minimum number of processors for which the task set is feasible is at least a NP-hard problem. There exist very few results that estimate the number of processors for which a task set is feasible. For example, Andrei et al. provide an upper estimation; that can be calculated in polynomial time, of the number of processors for which a task set is unfeasible. Given a task set and a fixed number of processors, the scheduling problem is, in general, NP-hard. For the uniprocessor platform, there exist fix traditional scheduling techniques for which the scheduling problem can be solved in polynomial time: Earliest Deadline First (EDF) and Least Laxity First (LLF). However, it is known that these two techniques are not anymore optimal for the multi-processor platforms. Andrei et at. described in 2010 an improved and polynomial time complexity scheduling algorithm for independent non-preemptive tasks for multi-processor platforms.

                 This website describes a Java programming language implementation of the scheduling algorithm described by Andrei et al. and an extensive comparison with the EDF and LLF techniques. Our conclusion is promising because according to the large number of generated task sets, some implementations of Algorithm B provided feasible scheduling for 31.4% compared with 20.53% using LLF and 16% using EDF.