Rate Monotonic Scheduling

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ások

• Rate Monotonic algoritmus