Rate Monotonic Scheduling

A Wikipédiából, a szabad enciklopédiából

Rate Monotonic Scheduling angol kiefejezés jelentése független taskok dinamikus ütemezése.

Periodikus, független hard real-time taskok ütemezésének klasszikus algoritmusa egyprocesszoros rendszerben: a rate monotonic algoritmus (azaz: a leggyakoribb először), melyet 1973-ban publikáltak. Ez egy statikus task prioritásokon nyugvó dinamikus preemptív algoritmus, amely a taskokat illetően az alábbiakat tételezi fel:

  • Az összes kemény határidővel rendelkező task periodikus.
  • Minden task független egymástól: nincsen precedencia, vagy kölcsönös kizárási kényszer.
  • A határidő minden task esetében a periódus idővel egyezik.
  • Minden task kiszámítási ideje előre ismert és konstans (C_i).
  • Az átkapcsolási idők (context switching) elhanyagolhatók.
  • A kihasználási/hasznosítási tényezőre teljesül, hogy
U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(\sqrt[n]{2} - 1)

ahol n az ütemezett taskok száma, C_i az i-edik task végrehajtásához szükséges idő, T_i pedig ezen task periódusideje.

A statikus prioritás hozzárendelés úgy történik, hogy a legkisebb periódusú task kapja a legnagyobb prioritást. Ha a task periódusok a legkisebb periódus egészszámú többszörösei, akkor egy processzoros rendszerben elérhető a \mu = 1 elvi maximum.

Forrás[szerkesztés | forrásszöveg szerkesztése]