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 http://www.tek.bth.se/ |
| Authors e-mail: | hln@bth.se, llu@bth.se |
| 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 |
