New Slack-Monotonic Schedulability Analysis of Real-Time Tasks on Multiprocessors

Abstract—In this paper, multiprocessor scheduling of a set of real-time periodic tasks with implicit deadlines is addressed. We propose two static priority-assignment policies, called policy Pbound and policy Psearch. Common for both policies is that a subset of a given task set is assigned the slack-monotonic priority while each of the other tasks is assigned the highest static-priority. The tasks are scheduled on m processors using preemptive global multiprocessor scheduling algorithm. First, we show that the utilization bound of global mul-tiprocessor scheduling using our proposed policy Pbound is higher than any other existing state-of-the-art static-priority multiprocessor scheduling. Second, using the utilization infor-mation of individual task of a given task set, we propose our second priority assignment policy Psearch. We show that global multiprocessor scheduling using policy Psearch dominates that of using Pbound in the sense that any task set schedulable using Pbound is also schedulable using Psearch and not conversely. I