A guaranteed real-time scheduling algorithm for (m,k)-firm deadline-constrained tasks on multiprocessors
Hyeonjoong Cho, Yeonhwa Gong · IETE Journal of Research · 2013
AbstractWe 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 ...