Literatur - wi.f4.htw-berlin.dewi.f4.htw-berlin.de/.../AI-BS-WS15/Folien/BS-13/13-BS-Scheduling-2.pdf · [13-2] Quade, Jürgen: Embedded Linux lernen mit dem Raspberry Pi. dpunkt,

Betriebssysteme - WS 2015/16 - Teil 13/Scheduling 2

Literatur

[13-1] Quade, Jürgen; Mächtel, Michael: Moderne Realzeitsysteme kompakt. dpunkt, 2012

[13-2] Quade, Jürgen: Embedded Linux lernen mit dem Raspberry Pi. dpunkt, 2014

[13-3] Eißenlöffel, Thomas: Embedded-Software entwickeln. dpunkt, 2012


Übersicht

• Zustände für Tasks

• Scheduling-Strategien

• Prioritätsinversion

• Scheduling mit mehreren CPUs


Scheduler

• Scheduling = Verfahren der Zuordnung von Betriebsmittel an Task (Zusammenfassung von Threads und Prozessen)

• Betriebsmittel können sein:– CPU

– Platten/SSD

– Kritische Abschnitte

• Scheduler = Komponente im Kernel zur Realisierung eines Scheduling-Verfahrens

• Zentral für den Scheduler ist ein Plan:– Kurzfristige Pläne

– Mittel/Langfristige Pläne

• Die Pläne beruhen u.a. auf– Task-Zuständen

– Verbrauchte CPU-Zeit

– (späteste) Zeitpunkte der Ausführung


Zustände von Tasks (Konzept) I

Zustand Bedeutung Ort

running Die Task besitzt gerade die CPU bzw. wird so behandelt, als ob sie läuft.

RAM

ready Die Task wartet auf die Benutzung der CPU. RAM

waiting Die Task wartet auf die Beendigung eines I/O-Vorgangs.

RAM

sleeping Die Task wartet längere Zeit auf einen Zeitpunkt, an dem sie die CPU haben will.

RAM

swapped Teile oder die gesamte Task liegen nicht im RAM. PlatteSSD


ready

Zustände von Tasks (Konzept) II

running

waiting sleeping

swapped

Blau: Mittel/Langfristig

Braun: Kurzfristig

create

Das Terminieren kann aus jedem Zustand heraus erfolgen.


Linux – etwas realistischer

Quelle: http://opensourceforgeeks.blogspot.de/2014/03/processes-and-threads-in-linux.html


Ziele des Schedulings

• Permanente Ausnutzung der CPU

• Maximale Anzahl von bearbeiteten Taskspro Zeiteinheit (Systemdurchsatz)

• Niedrige durchschnittliche Wartezeit

• Minimale Antwort-/Reaktionszeit

• Jeder Taskwechsel kostet Zeit,d.h. häufiges Umschalten ist nicht gut.

• Fairness/Gerechtigkeit

• Einhaltung von Prioritäten

• Minimaler Aufwand für das Scheduling selbst

Systemsicht

Benutzungssicht

Allgemein


Preemptive und Non-Preemptive

• Preemptive oder unterbrechendes Scheduling = Es besteht die Möglichkeit, dass ein rechnender Task die CPU abgibt, wenn der Scheduler dies entscheidet.

Dies wird manchmal als Entzug der CPU bezeichnet.

• Non-Preemptive oder nicht unterbrechendes Scheduling = kooperatives Scheduling = Eine rechnende Task gibt die CPU nur explizit geplant ab, wenn– sie terminiert, oder

– sie auf ein Ereignis wartet (I/O, z.B.).


Zeitpunkte für Scheduling-Entscheidungen

• Terminieren

• Erzeugen

• Warten auf ein Ereignis, z.B.– Beendigung von I/O

– Erfolgte IPC

– Warten in einer Semaphore

• I/O-Interrupt

• Freiwillige Abgabe der CPU

• Timer-Interrupt

Ereignisse einer Task

Im folgenden wird nur noch das CPU-Scheduling betrachtet, alle anderenArten, z.B. Plattenzugriff-Scheduling oder Scheduling des Plattenarms,arbeiten analog.


Eine Beobachtung

• Tasks arbeiten fast immer in kurzen Schüben:

• Burst = Zeitabschnitt, in dem eine Task in einem Stück die CPU benutzt bzw. benutzen will, Deutsch: Stoß

• In den Pausen dazwischen wird auf ein Ereignis gewartet, meistens auf die Beendigung von I/O.

• Typisch ist (Beispiel):

I/OI/O

Keine CPU

CPU benutzt

Burst Burst Burst Burst


Überblick Verfahren

• Batch/Hintergrund-Tasks– First-Come-First-Served (FCFS)

– Shortest Job First (SJF)

– Shortest Remainung Time Next (SRTN)

• Interaktive Tasks– High Priority First (HPF)

– Round Robin (RR)

• Echtzeit-Tasks– High Priority First (HPF)

– Earliest Deadline First (EDF)


First-Come-First-Served (FCFS)

• Non-Preemptives Scheduling

• Burst-Dauer ist bekannt

• Beispiel

Task Burst Zeit

T1 24

T2

6

T3

3

T1

T2 T

3T

1T

2 T3

Situation 1: Reihenfolge T

1, T

2, T

3

Mittlere Wartezeit: (0+24+30)/3=18

Situation 2:Reihenfolge T

2, T

3, T

1


• Bevorzugung von Langläufern

• Zum Zeitpunkt der Entscheidung müssen alle Kandidaten bekannt sein


Shortest Job First (SJF)

• Non-Preemptives Scheduling


• Beispiel

Task Burst Zeit

T1

24

T2

6

T3 3

T1T

2T3

Situation 1: Reihenfolge T1, T2, T3


• Zum Zeitpunkt der Entscheidung müssen alle Kandidaten bekannt sein

• Bevorzugung von Task mit kurzen Burst-Zeiten


Shortest Remaining Time Next (SRTN) I

• Preemptives Scheduling


• Es bekommt die Task die CPU, die vom ihrem Burst die kürzeste Restzeit noch hat.

• Variante:– Maximale Burst-Dauer wird begrenzt.

– Jede Task bekommt eine Zeitscheibe als max. Burst-Dauer zugewiesen


Shortest Remaining Time Next (SRTN) II - Beispiel

Task Burst Zeit Ankunft

T1

24 0

T2

6 2

T3

3 3

T1

T2T

3

SJF ohne Preemptive: Reihenfolge T

1, T

2, T

3


T1T

1T

2 T3 T2

SJF/SRTF mit Preemptive: Reihenfolge T

1, T

2, T

3

Mittlere Wartezeit: (0+2+3)/3=1.7

Die mittlere Wartezeit ist bei SRTF minimal.

Beim Preemtive-Scheduling sind die Task-Umschaltungen häufiger, auchverlängert sich die Bearbeitungszeit, dafür sinkt in der Regel die Wartezeit.


Abschätzung der zukünftigen Burst-Dauer

• Aus der Vergangenheit lernen, z.B. gewichtete Mittelwertbildung:

• sn+1= f*tn+(1-f)*sn

sn: Schätzung zum Zeitpunkt n

tn: Tatsächliche Burst-Dauer zum Zeitpunkt n

f: Faktor zwischen 0 und 1

• Ist der Faktor f 0, dann findet kein Lernen statt, denn die Schätzung ist immer gleich.Zu kleine Werte: zu langsame Anpassungen an Trends

• Ist der Faktor f 1, dann findet kein Lernen statt, denn der letzte tatsächliche Wert ist die zukünftige Schätzung, was zu hektischen Verhalten führt.Zu große Werte: hohe Schwankungen, kaum Glättungen

• Je größer der Wert für f ist, desto schneller wird die Vergangenheit vergessen.


High Priority First I

• Der Task mit der höchsten Priorität erhält die CPU und behält sie unabhängig davon, ob inzwischen Tasks mit höherer Priorität die CPU haben wollen, solange bis der Burst beendet ist.

• Gefahr des Verhungerns niedrig priorisierter Tasks

Non-Preemptive

Preemptive

• Der Task mit der höchsten Priorität erhält die CPU und behält sie solange bis eine Tasks mit höherer Priorität die CPU haben will oder bis der Burst beendet ist.

• Gefahr des Verhungerns niedrig priorisierter Tasks


High Priority First II - Praxis

• Die Tasks werden entsprechend ihrer Priorität in Warteschlangen eingereiht.

• Innerhalb einer Schlange haben alle Tasks dieselbe Priorität: FCFS

• Eine niedrige Nummer der Schlange bedeutet höhere Priorität.

• Eine Warteschlange wird abgearbeitet, wenn alle Warteschlangen höherer Priorität leer sind.

• Dies erfolgt mit/ohne CPU-Entzug (Preemptive).

Priorität 0

Priorität 1

Priorität N

...

CPU


High Priority First III - Verhungern

• Ein niedriger Prioritätswert (Integer) bedeutet höhere Priorität.

• Um das Verhungern zu verhindern, wird die Wartezeit in eine Erhöhung der Priorität – also zu einer Erniedrigung des Integer-Wertes umgewandelt.

• Dies führt erst zum Nach-Vorne-Schieben in der Warteschlange und dann zum Verschieben in die nächst höhere.

• Im Extremfall befinden sich alle Tasks in der obersten Warteschlange.

Diese Form des High Priority First – also das Arbeiten mit Queues gleichberechtigter Tasks – wird auch einfach Priority Scheduling genannt.


Round Robin I

• Preemptives Scheduling

• Burst-Dauer ist auf eine Zeitscheibe begrenzt.

• Alle Tasks sind gleichwertig.

• Die Reihenfolge bestimmt FCFS.

• Gerechtes/faires Verfahren

• Beispiel

Task Burst Zeit Ankunft

T1

24 0

T2

6 2

T3 3 3

Länge derZeitscheibe

NötigeTaskwechsel

1 16

2 9

3 5

Übliche Größen für Zeitscheiben liegen zwischen 20 und 50 ms.


Round Robin II

• Sind die Zeitscheiben sehr kurz, kommt es zu Verlusten durch (zu) viele Task-Wechsel.

• Sind die Zeitscheiben zu lang, kommt nähert sich Round Robin zur FCFS-Strategie mit Benachteiligung langer Burst-Zeiten.

• Round Robin kann auch mit der Idee des Shortest Remaining Time Next kombiniert werden, so dass angefangene Zeitscheiben mit höherer Priorität beendet werden:Beendet eine Task aufgrund von Warten vorzeitig seine Zeitscheibe, so kommt sie nach dem Warten vorne in die Queue mit der reduzierten Zeitscheibe (wie bei SRTN).


Kurzzeitiges Höher-Priorisieren

• Nach jedem Warten auf I/O, nicht nach einem Warten aufgrund Synchronisation oder nach Warten auf IPC

• Wenn Interaktivität verbessert werden soll: Nach jedem Warten wird die Priorität kurzzeitig erhöht.

• Jede Task innerhalb eines kritischen Abschnitts bei Preemptiven Strategien

• Zur Vermeidung von Priority Inversionen (Echtzeitsysteme)

Es gibt gute Gründe für eine kurzzeitige Erhöhung der Priorität:


Round Robin mit HPF kombiniert

• Wie bei High Priority First haben die Queues eine Priorität.

• Innerhalb einer Queue wird mit Round Robin gearbeitet, also mit festen Zeitscheiben.

• Nach jedem Durchlauf der Queue N wird ein Element aus der Queue N+1 ausgewählt.

• Eine lange Wartezeit kann durch Wechsel der Queues kompensiert werden.

Priorität 0

Priorität 1

Priorität N

...

CPU

Echtzeit-Tasks

Interaktive Tasks

Hintergrund-Tasks


Variante mit unterschiedlichen Zeitscheiben I

• Nach jedem Warten oder nach der Erzeugung kommt die Task in die Queue 0 und erhält 1x nach FCFS eine Zeitscheibe von 8 ms.

• Reicht dies nicht, kommt die Task in Queue 1 und erhält 1x nach FCFS eine Zeitscheibe von 16 ms. Queue 1 wird nur bei leerer Queue 0 abgearbeitet.

• Reicht das immer noch nicht, kommt die Task in Queue 2 und erhält nach Round-Robin die CPU, wobei diese Queue nur bei leeren Queues 0 und 1 abgearbeitet wird.

Queue 0

Queue 1

Queue 2

Zeitscheibe 8 ms (Beispiel)

Zeitscheibe 16 ms (Beispiel)

Round Robin, Zeitscheibe 32 ms (Beispiel)


Variante mit unterschiedlichen Zeitscheiben II

• Dieses Verfahren ist ein Beispiel für eine Multi-Level-Feedback-Queue.

• Es bevorzugt Tasks mit kurzen Burst-Zeiten und I/O-intensive Tasks, benachteiligt aber Langläufer.

• Es gibt noch andere Varianten, z.B.1) Jede Queue arbeitet nach Round Robin.

2)Beendet eine Task ihre Zeitscheibe mit einem Warten, so verbleibt sie in der Queue (wenn sie im Zustand ready wieder ist).

3)Verbraucht sie die Zeitscheibe und möchte weiterhin die CPU, so wandert sie in die nächst niedrigere Queue.

4)Verbraucht sie dann kurze Zeitscheiben, wird sie wieder höher gestuft.


Earliest Deadline First (EDF)

• Wenn Tasks bis spätestens zu einem bestimmten Zeitpunkt gearbeitet haben müssen, wird die Zeit bis zu dieser Deadline zur Grundlage der Bestimmung der Priorität benutzt.

• Je kürzer diese Zeit, desto höher die Priorität.

• Dies ist typisch für Tasks, die zyklisch immer wiederkehrende Dinge tun müssen und einen ungefähr immer gleichen Aufwand benötigen.

• So etwas erfolgt in Realzeitsystemen mit festen Aufgaben.

• Es wird der späteste Startzeitpunkt berechnet (Deadline – Laufzeit) sowie die Zeitdifferenz zu diesem Zeitpunkt.


Phänomen der Prioritätsinversion I

• Bei priorisierten Verfahren gibt es noch eine kleine Schwierigkeit:

Wenn eine Task mit hoher Priorität auf eine Task mit niedrigerer Priorität warten muss, widerspricht dies der höheren Priorität.

• Das kann z.B. bei einem p() vor einem kritischen Abschnitt passieren:– Task L (mit niedriger Priorität) betritt den kritischen Abschnitt.

– Dann kommt Task H (mit hoher Priorität), führt das p() zu diesem belegten Abschnitt aus und muss auf Task L warten.

• Prioritätsinversion = Situation, in der (für eine unzumutbar lange Zeit) eine Task auf eine andere warten muss, die eine niedrigere Priorität besitzt


Phänomen der Prioritätsinversion II

• Verschärfung der Situation durch Tasks mit drei Prioritätsstufen:1)Task L (mit niedriger Priorität) betritt den kritischen Abschnitt.

2)Dann kommt Task H (mit hoher Priorität), führt das p() zu diesem belegten Abschnitt aus und muss auf Task L warten.

3)Task M mit mittlerer Priorität (L<M<H) verdrängt nun Task L, so dass Task H noch länger warten muss.

• In der obigen Situation erhält eine Task mindestens die Priorität der an der Spitze der Warteliste wartenden Task:1)Task L (mit niedriger Priorität) betritt den kritischen Abschnitt.

2)Dann kommt Task H (mit hoher Priorität), führt das p() zu diesem belegten Abschnitt aus und muss auf Task L warten.

3)Task L erbt die Priorität H. Nun kann Task M mit mittlerer Priorität die Task L nicht mehr verdrängen.

4)Task L führt das v() aus und erhält wieder seine ursprüngliche niedrige Priorität.

Gegenmaßnahme: Prioritätsvererbung


Phänomen der Prioritätsinversion III

• Die zeitlich begrenzte Vererbung von Priorität gilt für jegliches Warten auf Ressourcen, z.B.:– Warten in p()

– Warten im receive() auf eine Nachricht

– Warten auf Freigabe von Speicher

• ... jedoch nicht beim Warten auf I/O.


Scheduling mit mehreren CPUs I

• Symmetrisches Multiprocessing = Alle CPUs haben dieselben Fähigkeiten und Geschwindigkeiten

• Asymmetrisches Multiprocessing = Einige der CPUs sind entweder langsamer als andere oder ihnen fehlen Fähigkeiten, z.B. Floating Point-Operationen

• Hier wird nur das symmetrische Multiprocessing behandelt.


Scheduling mit mehreren CPUs II – Variante 1

...

CPU1

CPU2

CPUn

...

• Jede CPU hat ihre eigenen Warteschlangen mit entsprechenden Prioritäten bzw. Zeitscheiben.

• Es wird ein eigenes Scheduling realisiert in einem "virtuellen" Scheduler, der nur für die eine betreffende CPU zuständig ist.


Scheduling mit mehreren CPUs III – Variante 1

1) Schlechte Verteilung der Belastung: einige CPUs sind überlastet, andere wenig belastet

2) Interrupts müssen von den CPUs bearbeitet werden, deren Task den I/O-Vorgang gestartet haben.

3) Zuordnung der Timer-Interrupts zu einer CPU muss erfolgen.

1) Cache nach Task-Wechsel hat meistens richtigen Inhalt.

2) Jede CPU hat einen Scheduler, der nur auf seine Queues zugreift, also wenige Kollisionen beim Zugriff auf Scheduling-Tabellen.

Vorteile

Nachteile

Die Punkte 2) haben den Sinn, dass möglichst selten mehrere CPUs auf dieselbenDatenstrukturen zugreifen. Denken Sie an Syscalls und Interrupts, die Auswirkungenauf die Scheduler-Tabellen haben. Das Ziel: Trennung in separate Bereiche.


Scheduling mit mehreren CPUs IV – Variante 2

CPU1

CPU2

CPUn

...

• Es gibt nur eine einzige Warteschlange bzw. Schlangensystem für alle CPUs.

• Ein globaler Scheduler regelt die CPU-Zuteilung.


Scheduling mit mehreren CPUs V – Variante 2

1) Cache nach Task-Wechsel hat meistens einen falschen Inhalt.

2) Zu einem Zeitpunkt darf nur ein Scheduler auf einer beliebigen CPU laufen, d.h. die CPUs müssen sich dazu abstimmen.

3) Hohe Wahrscheinlichkeit für Kollisionen beim Zugriff auf Scheduling-Tabellen

1) Guter Ausgleich der Belastung: alle CPUs sind gleich belastet.

2) Leicht zu implementieren

3) I/O-Interrupts können von beliebiger CPU bearbeitet werden.

4) Timer-Interrupts können von beliebiger CPU bearbeitet werden.

Vorteile

Nachteile


Scheduling mit mehreren CPUs VI – Variante 2

• Um diese Variante 2 zu verbessern, wird häufig ein Parameter für die "Affinität" eines Tasks zu einer CPU eingeführt.

• Oder: Bei der Task-Erzeugung wird die ID der CPU, auf der die Task ausschließlich laufen soll, angegeben.

• Mit diesen beiden Mechanismen wird ein Kompromiss zwischen den beiden Varianten realisiert.


Nach dieser Anstrengung etwas Entspannung....

Documents

Literatur - wi.f4.htw-berlin.dewi.f4.htw-berlin.de/.../AI-BS-WS15/Folien/BS-13/13-BS-Scheduling-2.pdf · [13-2] Quade, Jürgen: Embedded Linux lernen mit dem Raspberry Pi. dpunkt,