An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time SchedulingReportar como inadecuado




An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Presented at: 17th Annual European Symposium on Algorithms (ESA'09), Copenhagen, September 7–9, 2009 Published in: 17th Annual European Symposium on Algorithms (ESA'09), p. 432-443 Series: Lecture Notes in Computer Science 5757 Berlin: Springer, 2009

We introduce the "First Fit Matching Periods" algorithm for static-priority multiprocessor scheduling of periodic tasks with implicit deadlines and show that it yields asymptotically optimal processor assignments if utilization values are chosen uniformly at random. More precisely we prove that the expected waste is upper bounded by O(n^(3/4) * (log n)^(3/8)). Here the waste denotes the ratio of idle times, cumulated over all processors and n gives the number of tasks. The algorithm can be implemented to run in time O(n log n) and even in the worst case, an asymptotic approximation ratio of 2 is guaranteed. Experiments yield an expected waste proportional to n^0.70, indicating that the above upper bound on the expected waste is almost tight.

Keywords: Average case analysis ; Periodic scheduling Reference DISOPT-CONF-2009-002doi:10.1007/978-3-642-04128-0_39View record in Web of Science





Autor: Karrenbauer, Andreas; Rothvoß, Thomas

Fuente: https://infoscience.epfl.ch/record/138704?ln=en







Documentos relacionados