:BETRIEBSSYSTEM: Scheduling-Algorithmen :BETRIEBSSYSTEM: Scheduling-AlgorithmenBedeutet, 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.
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!
Ziel: Gesammtwartezeit aller Prozesse minimierten, Voraussetzung: Rechenzeit der Prozesse lässt sich abschätzen, nimm den kürzesten Prozess zuerst!
Nach dem Ende eines Prozesses wird aus den wartenden Prozessen der mit der höchsten Priorität ausgewählt und gestartet.
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.
Welches Verfahren wird angewendet bei Prozeduren, die nicht unterbrochen werden dürfen? Beispiele für solche Prozeduren?
- 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.
| 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 | .. |
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!!
Wie lange sollte ein Quantum dauern? Vor- und Nachteile von langen, bzw. kurzen Quanten...
Welche implizite Annahme gilt bei Round-Robin?
Welche Wirkungen haben bei Round-Robin ein zu kleines (zu großes) Quantum?
Entwickeln Sie eine grafische Darstellung einer Liste von 5 Prozessen, die nach Round-Robin-Scheduling abgearbeitet werden.
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.
Welche Strategie ist nun besser? Zwei Kriterien:
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 |
| CPU | Warteschlange | ||
|---|---|---|---|
| A: 20 ZE | B: 8 ZE | C: 4 ZE | |
|
|
||||||||||||||||||||||||||||
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!
|
|
||||||||||||||||||||||||||||
| 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!
|
|
||||||||||||||||||||||||||||
Quellen:
