Modifizierter rate-monotonic Algorithmus zur Planung periodischer Aufgaben mit verschobenen Fristen

Die Frist einer Anfrage ist der Zeitpunkt, zu dem ihre Ausführung abgeschlossen sein muss. Die Frist der Anfrage in einem beliebigen Zeitraum einer Aufgabe mit verschobener Frist ist ein Zeitpunkt nach dem Ende des Zeitraums. Die Autoren beschreiben einen semi-statischen prioritätsgesteuerten Algorithmus zur Planung periodischer Aufgaben mit verschobenen Fristen: Jede Aufgabe wird zwei Prioritäten zugewiesen, die höhere für alte Anfragen und die niedrigere für die aktuelle Anfrage. Dieser Algorithmus wird als modifizierter rate-monotonic Algorithmus bezeichnet und basiert auf dem bekannten rate-monotonic Algorithmus. Es wird gezeigt, dass der modifizierte rate-monotonic Algorithmus optimal ist, wenn die Frist jeder Aufgabe um maximal (1, gamma -1) Perioden oder mehr verschoben wird, wobei gamma das Verhältnis zwischen der längsten und der kürzesten Periode ist. Wenn die Frist jeder Aufgabe um eine Periode der Aufgabe verschoben wird, kann jede Menge von n unabhängigen Aufgaben, deren Gesamtnutzung gleich oder kleiner als (1+n(2/sup 1/n/-1))/2 ist, durch diesen Algorithmus realisiert werden. Diese Schranke nähert sich 0,845, wenn n gegen Unendlich geht.