Wie in einem Papier in niedrigen , Swaminathan und Chakrabarty beschreiben die Herausforderungen der Echtzeit-Aufgabenplanung dem Titel beschrieben - Leistungsfähige (eingebettete) Geräte mit mehreren Prozessorgeschwindigkeiten und Stromverbrauchsprofilen verfügbar. Der Scheduling-Algorithmus, den sie skizzieren (und es wird gezeigt, dass er nur etwa 1% schlechter als eine optimale Lösung in Tests ist), hat eine interessante Möglichkeit, Aufgaben zu planen, die sie die LEDF-Heuristik nennen.
Vom Papier:
Die Niedrigenergie früheste Frist ersten heuristischen oder einfach LEDF, ist eine Erweiterung des bekannte früheste Frist ersten (EDF) -Algorithmus. Die Operation von LEDF ist wie folgt: LEDF unterhält eine Liste aller freigegebenen Aufgaben, die "Bereit-Liste" genannt. Wenn die Aufgaben freigegeben sind, wird die Aufgabe mit der nächstliegenden Frist als ausgeführt. Eine Überprüfung wird durchgeführt, um zu sehen, wenn die Task-Frist von bei der niedrigeren Spannung (Geschwindigkeit) erfüllt werden kann. Wenn die Frist eingehalten werden kann, weist LEDF die niedrigere Spannung der Task zu und die Task beginnt mit der Ausführung. Während der Ausführung der Task können andere Tasks des Typs in das System gelangen. Diese Aufgaben werden angenommen, um automatisch auf der "Bereit-Liste" platziert werden. LEDF wählt erneut die Aufgabe mit der nächsten auszuführenden Frist aus. Wie Solange Aufgaben warten auf ausgeführt werden, hält LEDF nicht die Pro- Leerlauf. Dieser Vorgang wird wiederholt, bis alle Aufgaben geplant wurden.
Und in Pseudo-Code:
Repeat forever {
if tasks are waiting to be scheduled {
Sort deadlines in ascending order
Schedule task with earliest deadline
Check if deadline can be met at lower speed (voltage)
If deadline can be met,
schedule task to execute at lower voltage (speed)
If deadline cannot be met,
check if deadline can be met at higher speed (voltage)
If deadline can be met,
schedule task to execute at higher voltage (speed)
If deadline cannot be met,
task cannot be scheduled: run the exception handler!
}
}
Es scheint, dass Echtzeit-Scheduling ein interessantes und ich entwickelnden Problem so klein ist, werden Low-Power-Geräte mehr allgegenwärtig. Ich denke, das ist ein Bereich, in dem wir weitere Forschungsprojekte finden werden, und ich freue mich darauf, auf dem Laufenden zu bleiben!