Global multiprocessor scheduling of aperiodic tasks using time-independent priorities
| Document type: | Conference Papers |
|---|---|
| Peer reviewed: | Yes |
| Author(s): | Lars Lundberg, Håkan Lennerstad |
| Title: | Global multiprocessor scheduling of aperiodic tasks using time-independent priorities |
| Conference name: | 9th IEEE Real-Time and Embedded Technology and Applications Symposium |
| Year: | 2003 |
| Pagination: | 170-180 |
| ISBN: | 0-7695-1956-3 |
| Publisher: | IEEE COMPUTER SOC |
| City: | TORONTO, CANADA |
| ISI number: | 000183433500019 |
| Organization: | Blekinge Institute of Technology |
| Department: | Department of Software Engineering and Computer Science (Institutionen för programvaruteknik och datavetenskap) Dept. of Software Engineering and Computer Science S-372 25 Ronneby +46 455 38 50 00 http://www.bth.se/eng/ipd/ |
| Language: | English |
| Abstract: | We provide a constant time schedulability test for a 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 - root7 = 35.425%, the server can accept incoming aperiodic tasks and guarantee that the deadlines of all accepted tasks will be met. 35.425% utilization is also a threshold for a task to be characterized as heavy. The bound U-threshold = 3 - root7 approximate to 35.425% is easy-to-use, but not sharp if we know the number of processors in the multiprocessor. For a server 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(m)(x) = 2(1-x)/(2+ root2+2x)+x/m. By using this function, the performance of the multiprocessor 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: | Software Engineering\General |
