Einführung

Real-Time Scheduling-Algorithmen → Rate Montonic(RM)

Der Algorithmus RM (Rate Montonic) von Liu und Layland (1973) ist wohl der bekannteste Scheduling-Algorithmus für unabhängige periodische Task. Er basiert auf folgende Annahmen:

Die rechte Seite der Gleichung hat für große Werte von n einen Wert von ungefähr 0,7:
Gleichung 1:

Aus Gleichung 1 ergibt sich, dass ein gewisser Teil der Rechenleistung des Prozessors nicht genutzt werden kann, um sicherzustellen, dass keine Task ihre Deadline verpasst. Wenn die oben genannten sechs RM-Annahmen erfüllt sind, werden alle Deadlines eingehalten.

Beim Algorithmus RM handelt es sich um einen präemptiven Scheduling-Algorithmus mit statischen Prioritäten. Die Priorität der Tasks ist eine monoton fallende Funktion ihrer Periode bzw. eine monoton steigende Funktion der Ausführungsrate. Anders ausgedrückt haben Tasks mit einer kurzen Periode eine höhere Priorität, wohingegen Tasks mit langer Periode eine geringere Priorität haben.

Das Scheduling der Task erfolgt nach den so vergebenen Prioritäten. Beginnt die Periode eines Tasks, wird überprüft, ob der gerade ausgeführte Task eine niedrigere Priorität hat bzw. eine längere Periode. Ist dies der Fall, wird die Ausführung unterbrochen und der neue Task beginnt mit seiner Ausführung.

 
Einführung > Real-Time Scheduling-Algorithmen > Rate Montonic(RM)

zurück weiter

Startseite   Tutorials   Einführung