Slack-based multiprocessor scheduling of aperiodic real-time tasks

We provide a constant time schedulability test and priority assignment algorithm for an on-line multiprocessor server handling aperiodic tasks. The so called Dhall's effect is avoided by dividing tasks in two priority classes based on their utilization: heavy and light. The improvement in this paper is due to assigning priority of light tasks based on slack-not on deadlines. We prove that if the load on the multiprocessor stays below (3 - root 5)/2 approximate to 38.197%, the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. This is better than the current state-of-the-art algorithm where the priorities of light tasks are based on deadlines (the corresponding bound is in that case 35.425%). The bound (3 - root 5)/2 can be improved if the number of processors m is known. There is a formula for the sharp bound U-threshold(m) = 3m-2-root 5m(2)-8m+4/2(m-1) which converges to (3 - root 5)/2 from above as m -> infinity. For m >= 3, the bound is higher (i.e., better) than the corresponding sharp bound for the state-of-the-art algorithm where the priorities of light tasks are based on deadlines. A simulation study also indicates that when m > 3 the best effort behavior of the priority assignment scheme suggested here is better than that of the traditional scheme where priorities are based on deadlines.