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 - 5~(1/2))/2≈ 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 - 5~(1/2))/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-5m~2-8m+4~(1/2/2(m-1)), which converges to (3 - 5~(1/2))/2 from above as m →∞. 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.