A Guaranteed Real-time Scheduling Algorithm for (m,k)-firm Deadline-constrained Tasks on Multiprocessors

Abstract

We present a guaranteed real-time scheduling algorithm for multiple real-time tasks subject to (m, k)-firm deadlines on homogeneous multiprocessors. The scheduling objective of the proposed algorithm is to provide guaranteed performance by bounding the probability of missing (m, k)-firm deadline constraints while improving the probability of deadline satisfactions as much as possible. This goal is established to satisfy the minimum requirements expressed by (m, k)-firm deadlines and simultaneously provide the best possible quality of service. We first introduce a novel abstraction for reasoning about the execution behaviors of tasks constrained by (m, k)-firm deadlines on multiprocessors. Based on it, we propose a guaranteed real-time scheduling algorithm for (m, k)-firm deadline-constrained tasks on multiprocessors. We analytically establish that the proposed algorithm provides assurance on the bounded probability of missing (m, k)-firm constraints. Experimental studies validate our analytical results and confirm the effectiveness and superiority of the proposed scheme in achieving our scheduling objective.