MezData-Logo Lösungen Button :BETRIEBSSYSTEM: Scheduling-Algorithmen

Nicht verdrängende Strategien (non-präemptiv)

Bedeutet, daß der Prozessor den Prozessen nicht vom Scheduler entzogen wird. Folge: "hängt" ein Prozess, hängt damit auch das ganze System!

Kooperatives Multitasking: z.B. Mac OS 9 - lange Prozesse machen freiwillig mal Pause und geben den anderen Prozessen eine Chance. Ziel: Verbesserung der Antwortzeiten.

First Come, First Served (FCFS) Eingangsreihenfolge

Ein Prozess verfügt über den Prozessor, bis er beendet ist, erst dann kann ein neuer Prozess gestartet werden. Strategie ist nicht verdrängend, daher sind Verluste durch Prozesswechsel minimal. Vorteil: Einfach Nachteil: Lange Antwortzeiten möglich!

Shortest Job First (SJF) Prozesslänge

Ziel: Gesammtwartezeit aller Prozesse minimierten, Voraussetzung: Rechenzeit der Prozesse lässt sich abschätzen, nimm den kürzesten Prozess zuerst!

Highest Priority First (non-präemptiv) (HPF-n)

Nach dem Ende eines Prozesses wird aus den wartenden Prozessen der mit der höchsten Priorität ausgewählt und gestartet.

Verdrängende Strategien (präemptiv)

Präemptives Multitasking ist heute gebräuchlich, der Scheduler wird in bestimmten Zeitintervallen aufgerufen und entscheidet, welcher Prozess als nächster dran ist, der alte Prozess kann verdrängt werden. Ein "hängender" (z.B. Endlosschleife) Prozess reißt nicht mehr das ganze System in den Abgrund (Blue Screen).

Wichtige Voraussetzung ist hierbei ein Schutz des Speicherbereiches der "schlafenden" Prozesse, eine Unterbrechung wird ihnen nicht mitgeteilt.

FrageWelches Verfahren wird angewendet bei Prozeduren, die nicht unterbrochen werden dürfen? Beispiele für solche Prozeduren?

Der Scheduler ist auch nur ein Prozess

- aber bei präemtivem Multitasking ein Besonderer! Er muss "mächtig" und "unbeirrbar" sein, wenn er hängt steht das System!

Wie kann man das erreichen?

Nicht ohne Grund gibt es ganze Vorlesungsserien zum Thema Betriebssysteme, es ist ein recht komplexes Gebiet...

Merke: Zwischen zwei Zeitscheiben wird bei "echtem" präemtiven Multitasking der Scheduler als eigener Prozess mit sehr hoher Priorität aufgerufen! D.h. am Ende einer Zeitscheibe muss der letzte Prozess auf jeden Fall unterbrochen werden -> erzwungener Prozesswechsel.

Kosten des Prozesswechsels

Prozesswechsel zwischen Beispiel Zeiteinheiten
User A User B Mehraufwand: Prozess A wird durch Prozess B ersetzt 8
User A User A Prozess A erhält wieder den Prozessor, kann preisgünstiger sein als Wechsel A-B 5

Wie viel Zeit kostet es, zwischen Prozessen zu wechseln, bei einem Wechsel muss die Umgebung des aktuellen Prozesses gesichert und die neue Umgebung geladen werden. Hier kann es je nach Implementierung des BS unterschiedliche Zeiten geben:

Mögliches Szenario:

Prozesse Prozess A Scheduler Prozess B Scheduler Prozess B ..
Zeiteinheiten 15 8 15 5 15 ..

Round-Robin-Scheduling (RR) Zeitscheibenverfahren

Alle rechenbereite Prozesse werden in einer Warteschlange angeordnet. Der vorderste Prozess wird aus der Schlange genommen und bekommt ein festes Quantum (eine Zeitscheibe) Prozessorzeit. Ist er nach dieser Zeit nicht fertig, wird er wieder hinten in die Schlange angestellt. Neue Prozesse werden auch hinten angestellt.

Implizite Annahme: alle Prozesse sind gleich wichtig!!

FrageWie lange sollte ein Quantum dauern? Vor- und Nachteile von langen, bzw. kurzen Quanten...

FrageWelche implizite Annahme gilt bei Round-Robin?

FrageWelche Wirkungen haben bei Round-Robin ein zu kleines (zu großes) Quantum?

FrageEntwickeln Sie eine grafische Darstellung einer Liste von 5 Prozessen, die nach Round-Robin-Scheduling abgearbeitet werden.

Prioritäts-Scheduling (präemptiv): Highest Priority First (HPF-p)

Jedem Prozess wird eine Priorität zugewiesen, und der ausführbereite Prozess mit der höchsten Priorität wird ausgeführt. Um zu verhindern, dass Prozesse mit einer hohen Priorität zu lange ausgeführt werden, erniedrigt der Scheduler die Priorität des gerade ausgeführten Prozesses bei jeder Uhrunterbrechung (Zeitscheibe). Fällt dabei seine Priorität unter die Priorität eines anderen Prozesses, wird ein Prozesswechsel durchgeführt.

Wie entscheidet der Scheduler bei Fällen gleicher Priorität?

Hinweis: Nach einer "Epoche" (relativ lange Zeiteinheit bzgl. Zeitscheibe) werden die Prioritäten wieder "hoch" (d.h. auf den ursprünglichen Wert) gesetzt.

Bewertung der Strategien (Kriterien)

Welche Strategie ist nun besser? Zwei Kriterien:

Beispiele zur Berechnung für einzelne Scheduling-Strategien

Die Kandidaten, drei Prozesse tauchen sehr kurz hintereinander in der Arena auf mit folgenden Eigenschaften:

Kandidat Länge
(Zeiteinheiten)
Priorität
(hoch = wichitig)
A 20 3
B 8 2
C 4 1

Arena 1: First Come First Serve (FCFS)

CPU Warteschlange
A: 20 ZE B: 8 ZE C: 4 ZE
Wartezeiten
A 0  
B 20
C 28 Mittelwert
Summe 48 / 3 = 16
Verweilzeiten
A 20  
B 28
C 32 Mittelwert
Summe 80 / 3 = ca. 27

Arena 2: Round Robin (RR)

Zeitraster (Zeitscheibenlänge, Quantum) ist hier 5 Zeiteinheiten.

Hinweis: Prozesswechselzeit kann berücksichtigt werden!

Zeiteinheiten 5 5 4 5 3 5 5
aktiver Prozeß A B C A B A A

Hinweis: Bei Unterschreitung des Quantums (Prozess ist früher fertig) kann entweder mit dem nächsten Prozess weitergemacht werden oder bis zum Ende des Quantums ein Leerlauf erfolgen. Hier kein Leerlauf!

Wartezeiten
A 12  
B 14
C 10 Mittelwert
Summe 36 / 3 = 12
Verweilzeiten
A 32  
B 22
C 14 Mittelwert
Summe 68 / 3 = ca. 23

Arena 3: Prioritäts-Scheduling (präemptiv): Highest Priority First (HPF-p)

Zeiteinheiten 5 5 5 4 3 5 5
aktiver Prozeß A B A C B A A
Priorität A 3 2 2 1 1 1 1
Priorität B 2 2 1 1 1 - -
Priorität C 1 1 1 1 - - -

Wichtig: Priorität kleiner als 1 gibt es nicht!

Wartezeiten
A 12  
B 14
C 15 Mittelwert
Summe 41 / 3 = ca. 14
Verweilzeiten
A 32  
B 22
C 19 Mittelwert
Summe 73 / 3 = ca. 24

Quellen: