Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling
 
conference paper

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling

Karrenbauer, Andreas
•
Rothvoß, Thomas  
2009
17th Annual European Symposium on Algorithms (ESA'09)
17th Annual European Symposium on Algorithms (ESA'09)

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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-04128-0_39
Web of Science ID

WOS:000279102100039

Author(s)
Karrenbauer, Andreas
Rothvoß, Thomas  
Date Issued

2009

Publisher

Springer

Publisher place

Berlin

Published in
17th Annual European Symposium on Algorithms (ESA'09)
Series title/Series vol.

Lecture Notes in Computer Science; 5757

Start page

432

End page

443

Subjects

Average case analysis

•

Periodic scheduling

URL

URL

http://algo2009.itu.dk/esa-2009
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent placeEvent date
17th Annual European Symposium on Algorithms (ESA'09)

Copenhagen

September 7–9, 2009

Available on Infoscience
June 3, 2009
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/40330
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés