Guaranteeing Response Times for Aperiodic Tasks in Global Multiprocessor Scheduling

Document type: Journal Articles
Article type: Original article
Peer reviewed: Yes
Author(s): Håkan Lennerstad, Lars Lundberg
Title: Guaranteeing Response Times for Aperiodic Tasks in Global Multiprocessor Scheduling
Journal: Real Time Systems
Year: 2007
Volume: 35
Issue: 2
Pagination: 135-151
ISSN: 0922-6443
Publisher: Kluwer Academic Publishers
City: Dordrecht
ISI number: 000242831400002
Organization: Blekinge Institute of Technology
Department: School of Engineering - Dept. Mathematics and Science, School of Engineering - Dept. of Systems and Software Engineering (Sektionen för teknik – avd. för matematik och naturvetenskap, Sektionen för teknik – avd. för programvarusystem)
School of Engineering S- 371 79 Karlskrona, School of Engineering S- 372 25 Ronneby
+46 455 38 50 00
Authors e-mail:,
Language: English
Abstract: We provide a constant time schedulability test for an on-line multiprocessor server handling aperiodic tasks. Dhall's effect is avoided by dividing the tasks in two priority classes based on task utilization: heavy and light. We prove that if the load on the multiprocessor server stays below U threshold = 3 - root 7 approximately equals 35.425%, the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. The same number 35.425% is also a threshold for a task to be characterized as heavy. The bound U threshold = 3 - root 7 approximately equals 35.425% is easy-to-use, but not sharp if we know the number of processors in the multiprocessor system. Assuming the server to be equipped with m processors, we calculate a formula for the sharp bound U threshold (m), which converges to U threshold from above as m -> infinity . The results are based on a utilization function u(x) = 2(1 - x)/(2 + root 2+2x). By using this function, the performance of the multiprocessor server can in some cases be improved beyond U threshold(m) by paying the extra overhead of monitoring the individual utilization of the current tasks.
Subject: Mathematics\Discrete Mathematics
Computer Science\Computersystems
Keywords: multiprocessors, response times