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.

Keywords:

• Guaranteed dynamic priority assignment
• Real-time systems
• (m,k)-firm deadline

Additional information

Notes on contributors

Hyeonjoong Cho

Hyeonjoong Cho is an Associate Professor in the Department of Computer and Information at Korea University. He received the PhD degree in computer engineering from Virginia Polytechnic Institute and State University (Virginia Tech) in 2006. His research focuses on real-time scheduling, enery-aware scheduling for embedded systems, human computer interactions, etc. E-mail: [email protected]

Yeonhwa Gong

Yeonhwa Gong is a researcher in the Department of Computer and Information Science, Korea University. She received the MS and BS degree in the same department from Korea University. Her research has focused on real-time scheduling algorithms for multi-core architectures, multimedia services, etc. E-mail: [email protected]