![]() |
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 |