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 (${\displaystyle C_{i}}$).
• Az átkapcsolási idők (context switching) elhanyagolhatók.
• A kihasználási/hasznosítási tényezőre teljesül, hogy

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({\sqrt[{n}]{2}}-1)}$

ahol ${\displaystyle n}$ az ütemezett taskok száma, ${\displaystyle C_{i}}$ az i-edik task végrehajtásához szükséges idő, ${\displaystyle 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 ${\displaystyle \mu =1}$ elvi maximum.

Források

• Rate Monotonic algoritmus^{[halott link]}

• Informatikai portál • összefoglaló, színes tartalomajánló lap