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}\le 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 algoritmusSablon:Halott link