Rate Monotonic (RM)

Hier wird angenommen, dass alle Ereignisse periodisch sind mit einer stabilen Auftretenszeit. Ereignisse mit kleinerer Periode haben eine höhere Priotität gegenüber jenen mit einer größeren Periode:

$$T_{i} < T_{j} \Longrightarrow p_{i} > p_{j}$$

Damit gibt es eine feste Prioritätenverteilung. Die zugehörigen periodischen Tasks sind präemptiv (preemptable). Die kleinste obere Schranke (least upper bound, lub) $U_{lub}$ für den RM-Algorithmus wurde von Liu und Layland (1973)[61] berechnet als

$$U_{lub } = n(2^{1/n)} - 1)$$

Diese kleinste obere Schranke ist etwas pessimistisch, d.h. sie fällt manchmal ein negatives Urteil, obgleich sich die Tasmenge evtl. noch erfüllen liese. Eine etwas positivere Formel fanden Bini, Butzzo, Butazzo (2001/3) mit der Formel

$$U_{lub } = \prod_{i=1}^{n}(U_{i}+1) \le 2$$

Für die Taskmenge aus dem Beispiel 2.7 sind im Bild 4.4 die Werte mittels der beiden ULB-Formeln berechnet worden. Man kann sehen, daß beide Formeln zu pessimistisch sein können. Beide berechnen einen Wert, der 'zu hoch' ist bezogen auf die theoretisch unterstellte Schranke, denn im konkreten Fall kann man die Taskmenge planen (vgl. Zeitdiagramm 2.7).

Figure 4.4: Beispiel Berechnung ULB bei RM-Prioritaetsregel