Task Scheduler

Question

Hatte eine interessante Diskussion mit einigen Kollegen über die beste scheduling-Strategien für Echtzeit-Aufgaben, aber nicht jeder hatte ein gutes Verständnis der gemeinsamen oder nützlich scheduling-Strategien.

Für deine Antwort, bitte wählen Sie eine Strategie und gehen über es in detail, statt eine kleine info auf mehrere Strategien.Wenn Sie etwas hinzufügen möchten, um jemand anderes die Beschreibung und Sie ist kurz, einen Kommentar hinzuzufügen, anstatt eine neue Antwort (wenn es sich um lange oder nützlich ist, oder einfach eine viel bessere Beschreibung, dann verwenden Sie bitte eine Antwort)

• Was ist die Strategie beschreibt den Allgemeinen Fall auf (vorausgesetzt, die Leute wissen, was eine task queue, Semaphoren, locks und andere Betriebssystem-Grundlagen außerhalb der scheduler selbst)
• Was ist diese Strategie optimiert für (Aufgabe Latenz -, Effizienz -, Echtzeit -, jitter -, Ressourcen-sharing, etc.)
• Es ist Echtzeit, oder kann es gemacht werden Echtzeit

Aktuelle Strategien:

• Priority-Based Preemptive
• Niedrigsten power langsamsten Uhr

-Adam

Answer 1

Wie beschrieben in einem Beitrag mit dem Titel Real-Time Task Scheduling for Energy-Aware Embedded Systems, Swaminathan und Chakrabarty beschreiben die Herausforderungen der real-time task scheduling in low-power - (embedded -) Geräte mit mehrfach-Prozessor-Geschwindigkeit und den Stromverbrauch profile zur Verfügung.Der scheduling-Algorithmus Sie beschreiben (und wird gezeigt werden, dass nur etwa 1% schlechter als die optimale Lösung in tests) hat eine interessante Art und Weise der Terminierung von Aufgaben nennen Sie die LEDF Heuristik.

Aus dem Papier:

Die niedrig-Energie-earliest deadline first Heuristik oder einfach LEDF, ist ein Erweiterung der bekannten frühesten deadline first (EDF) - Algorithmus.Die Betrieb LEDF ist wie folgt:LEDF verwaltet eine Liste von allen veröffentlicht Aufgaben, die so genannte "ready-list".Wenn Aufgaben veröffentlicht werden, wird die Aufgabe mit den Nächster Termin ist so gewählt, ausgeführt.Eine überprüfung durchgeführt, um zu sehen, wenn der task-Frist eingehalten werden kann durch Ausführung bei der geringeren Spannung (- Geschwindigkeit).Wenn der Termin eingehalten werden kann, LEDF weist die geringere Spannung an den Aufgabe und die Aufgabe der Ausführung beginnt.Während der task-Ausführung, andere Aufgaben können geben Sie die system.Diese Aufgaben angenommen werden platziert werden automatisch auf die "ready-list".LEDF wählt erneut die Aufgabe, mit nächste Frist ausgeführt werden.Als lange gibt es Aufgaben warten auf ausgeführt, LEDF nicht halten die pro- cessor im Leerlauf.Dieser Vorgang wird wiederholt, bis Sie alle Aufgaben wurden geplant.

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 real-time scheduling ist eine interessante und sich entwickelnde problem als kleine, low-power-Geräte immer mehr allgegenwärtig geworden.Ich denke, dies ist ein Bereich, in dem wir sehen werden, viele weitere Forschungs-und ich freue mich, Schritt zu halten!

Answer 2

Eine gemeinsame Echtzeit-scheduling-Regelung ist die Verwendung von priority-based preemptive multitasking.
Die einzelnen Aufgaben zugewiesen ist, eine andere Priorität.
Die höchste Priorität der Aufgabe auf die Warteschlange werden die Aufgabe, die ausgeführt wird.Es wird ausgeführt, bis es entweder auf die CPU (D. H.Verzögerungen, wartet auf eine semaphore, etc...) oder eine höhere Priorität Aufgabe wird sofort ausgeführt werden.

Der Vorteil dieses Systems ist, dass der Systementwickler hat volle Kontrolle darüber, welche Aufgaben ausgeführt werden, was Priorität.Der scheduling-Algorithmus ist auch einfach und sollte deterministisch sein.

Auf der anderen Seite, tasks mit niedriger Priorität möglicherweise verhungert für die CPU.Dies würde bedeuten, ein design-problem.