Einführung in Betriebssysteme

Hallo, Habr! Ich möchte Ihnen eine Serie von Übersetzungen einer interessanten Literatur — OSTEP — vorstellen. In diesem Material wird die Funktionsweise von Unix-ähnlichen Betriebssystemen ziemlich gründlich behandelt, insbesondere die Arbeit mit Prozessen, verschiedenen Planern, Speicher und anderen ähnlichen Komponenten, die ein modernes Betriebssystem ausmachen. Das Original aller Materialien können Sie hier ansehen hier. Bitte beachten Sie, dass die Übersetzung unprofessionell (relativ frei) durchgeführt wurde, aber ich hoffe, dass ich den allgemeinen Sinn bewahrt habe.

Die Laborarbeiten zu diesem Thema finden Sie hier:

Andere Teile:

Und Sie können auch meinen Kanal auf Telegramm =)

Einführung in den Scheduler

Kernproblem: Wie entwickelt man die Politik des Schedulers?
Wie sollten die grundlegenden Rahmenbedingungen für die Scheduler-Politik entwickelt werden? Welche wesentlichen Annahmen sollten getroffen werden? Welche Metriken sind wichtig? Welche grundlegenden Techniken wurden in früheren Computersystemen verwendet?

Annahmen zur Arbeitslast

Bevor wir mögliche Politiken diskutieren, machen wir zunächst einige vereinfachende Abschweifungen über die Prozesse, die im System gestartet wurden, die zusammen als Arbeitslastdefiniert werden. Die Definition der Arbeitslast ist ein kritischer Teil des Aufbaus von Politiken, und je mehr Sie über die Arbeitslast wissen, desto qualitativ hochwertiger wird die Politik, die Sie schreiben können.

Wir werden die folgenden Annahmen über die im System gestarteten Prozesse treffen, die manchmal auch als jobs (Jobs) bezeichnet werden. Praktisch alle diese Annahmen sind unrealistisch, aber notwendig, um das Denken zu entwickeln.

Jeder Job läuft die gleiche Zeit,
Alle Jobs werden gleichzeitig gestartet,
Ein gestarteter Job läuft bis zu seinem Abschluss,
Alle Jobs verwenden nur die CPU,
Die Laufzeit jedes Jobs ist bekannt.

Metriken des Schedulers

Neben einigen Annahmen zur Arbeitslast ist auch ein gewisses Vergleichsinstrument für verschiedene Planungsstrategien notwendig: die Metriken des Schedulers. Eine Metrik ist lediglich ein Maß für irgendetwas. Es gibt eine Reihe von Metriken, die verwendet werden können, um Scheduler zu vergleichen.

Als Beispiel verwenden wir die Metrik, die Durchlaufzeit (turnaround time) genannt wird. Die Durchlaufzeit eines Jobs wird als die Differenz zwischen der Abschlusszeit des Jobs und der Ankunftszeit des Jobs im System definiert.

Tturnaround = Tcompletion − Tarrival

Da wir angenommen haben, dass alle Jobs zur gleichen Zeit eingetroffen sind, ist Ta=0 und somit Tt=Tc. Dieser Wert wird sich natürlich ändern, wenn wir die oben genannten Annahmen ändern.

Eine andere Metrik ist die Fairness (Gerechtigkeit, Fairness). Leistung und Fairness sind oft gegensätzliche Merkmale in der Planung. Zum Beispiel kann ein Scheduler die Leistung optimieren, jedoch auf Kosten der Wartezeiten für andere Aufgaben, wodurch die Fairness verringert wird.

FIRST IN FIRST OUT (FIFO)

Der einfachste Algorithmus, den wir implementieren können, heißt FIFO oder first come (in), first served (out). Dieser Algorithmus hat mehrere Vorteile: Er ist sehr einfach zu implementieren und erfüllt alle unsere Annahmen, indem er seine Arbeit ziemlich gut erledigt.

Betrachten wir ein einfaches Beispiel. Angenommen, 3 Aufgaben wurden gleichzeitig gestellt. Aber nehmen wir an, dass Aufgabe A etwas früher als alle anderen angekommen ist, daher wird sie in der Ausführungsliste vor den anderen stehen, genau wie B im Verhältnis zu C. Nehmen wir an, dass jede von ihnen 10 Sekunden benötigt. Wie wäre in diesem Fall die durchschnittliche Ausführungszeit dieser Aufgaben?

Wenn wir die Werte rechnen — 10+20+30 und durch 3 teilen, erhalten wir eine durchschnittliche Ausführungszeit des Programms von 20 Sekunden.
Jetzt versuchen wir, unsere Annahmen zu ändern. Insbesondere die Annahme 1 und nehmen daher nicht mehr an, dass jede Aufgabe gleich lange ausgeführt wird. Wie wird sich FIFO diesmal verhalten?

Wie sich herausstellt, wirken sich unterschiedliche Ausführungszeiten der Aufgaben äußerst negativ auf die Produktivität des FIFO-Algorithmus aus. Angenommen, Aufgabe A benötigt 100 Sekunden, während B und C weiterhin jeweils 10 benötigen.

Wie aus der Abbildung hervorgeht, ergibt sich eine durchschnittliche Zeit für das System von (100+110+120)/3=110. Dieser Effekt wird genannt Konvoieffekt, wenn einige kurzfristige Verbraucher einer bestimmten Ressource hinter einem schwergewichtigen Verbraucher in der Schlange stehen. Das ist vergleichbar mit einer Warteschlange im Supermarkt, wenn vor Ihnen ein Käufer mit einem vollen Einkaufswagen steht. Die beste Lösung für dieses Problem ist, an eine andere Kasse zu wechseln oder sich zu entspannen und tief durchzuatmen.

Shortest Job First

Kann man eine solche Situation mit schweren Prozessen irgendwie lösen? Natürlich. Ein anderer Typ der Planung nennt sichShortest Job First (SJF). Sein Algorithmus ist ebenfalls recht primitiv — wie der Name schon sagt, werden zunächst die kürzesten Aufgaben nacheinander ausgeführt.

In diesem Beispiel wird das Ergebnis der Ausführung derselben Prozesse die durchschnittliche Durchlaufzeit der Programme verbessern und sie wird 50 statt 110, was praktisch doppelt so gut ist.

Somit scheint der SJF-Algorithmus für die gegebene Annahme, dass alle Aufgaben gleichzeitig ankommen, der optimalste Algorithmus zu sein. Unsere Annahmen erscheinen jedoch immer noch unrealistisch. Dieses Mal ändern wir Annahme 2 und stellen uns vor, dass Aufgaben zu beliebigen Zeiten ankommen können und nicht alle gleichzeitig. Welche Probleme könnte das mit sich bringen?

Stellen wir uns vor, dass Aufgabe A (100s) als erste ankommt und mit der Ausführung beginnt. Zu t=10 kommen die Aufgaben B und C an, von denen jede 10 Sekunden in Anspruch nimmt. Somit beträgt die durchschnittliche Ausführungszeit (100+(110-10)+(120-10))3 = 103. Was könnte der Scheduler tun, um die Situation zu verbessern?

Shortest Time-to-Completion First (STCF)

Um die Situation zu verbessern, lassen wir die Annahme 3 fallen, dass das Programm gestartet wird und bis zur Fertigstellung läuft. Außerdem benötigen wir Hardwareunterstützung und wie Sie sich denken können, werden wir einen Timer zum Unterbrechen der laufenden Aufgabe und zum Kontextwechsel. Dadurch kann der Scheduler etwas unternehmen, wenn die Aufgaben B und C ankommen — die Ausführung von Aufgabe A beenden und die Aufgaben B und C bearbeiten, um danach die Ausführung von Aufgabe A fortzusetzen. Ein solcher Scheduler wird genannt STCFoder Preemptive Job First.

Das Ergebnis dieses Schedulers wird folgendes Ergebnis haben: ((120-0)+(20-10)+(30-10))\/3=50. Somit wird dieser Scheduler noch optimaler für unsere Aufgaben.

Die Metrik Reaktionszeit (Response Time)

Somit, wenn wir die Laufzeit der Aufgaben und die Tatsache wissen, dass diese Aufgaben nur die CPU nutzen, wird STCF die beste Lösung sein. Früher waren diese Algorithmen recht effektiv. Allerdings verbringt der Benutzer heutzutage die meiste Zeit an der Konsole und erwartet eine produktive interaktive Interaktion. So entstand die neue Metrik — Antwortzeit (Response Time).

Die Antwortzeit wird wie folgt berechnet:

Tresponse=Tfirstrun−Tarrival

Somit wird die Antwortzeit für das vorherige Beispiel wie folgt sein: A=0, B=0, C=10 (abg=3,33).

Und der STCF-Algorithmus ist nicht so gut in Situationen, in denen drei Aufgaben gleichzeitig ankommen – er muss warten, bis die kleinen Aufgaben vollständig abgeschlossen sind. Somit ist der Algorithmus gut für die Durchlaufzeit-Metrik, aber schlecht für die Interaktivitäts-Metrik. Stellen Sie sich vor, Sie sitzen an einem Terminal und versuchen, Zeichen in einen Editor zu tippen, aber Sie müssten mehr als 10 Sekunden warten, weil eine andere Aufgabe den Prozessor beschäftigt. Das ist alles andere als angenehm.

Damit stehen wir vor einem anderen Problem – wie können wir einen Scheduler erstellen, der sensitiv auf die Reaktionszeit reagiert?

Round Robin

Um dieses Problem zu lösen, wurde ein Algorithmus entwickelt Round Robin (RR). Die Grundidee ist recht einfach: Anstatt Aufgaben bis zur vollständigen Fertigstellung auszuführen, führen wir eine Aufgabe für einen bestimmten Zeitraum (genannt Zeitscheibe) aus und wechseln dann zu einer anderen Aufgabe aus der Warteschlange. Der Algorithmus wiederholt diese Arbeit, bis alle Aufgaben abgeschlossen sind. Dabei muss die Ausführungszeit des Programms ein Vielfaches der Zeit sein, nach der der Timer den Prozess unterbricht. Zum Beispiel, wenn der Timer den Prozess alle x=10 ms unterbricht, dann muss die Ausführungsfenstergröße ein Vielfaches von 10 sein und entweder 10, 20 oder x*10 betragen.

Betrachten wir ein Beispiel: Die Aufgaben ABC kommen gleichzeitig im System an und jede von ihnen möchte 5 Sekunden lang arbeiten. Der SJF-Algorithmus würde jede Aufgabe bis zum Ende ausführen, bevor er die nächste startet. Im Gegensatz dazu würde der RR-Algorithmus mit einem Zeitfenster von 1 Sekunde die Aufgaben wie folgt abarbeiten (siehe Abb. 4.3):

(SJF Wieder (Schlecht für die Reaktionszeit)

(Round Robin (Gut für die Reaktionszeit)

Die durchschnittliche Reaktionszeit für den RR-Algorithmus beträgt (0+1+2)/3=1, während sie für SJF (0+5+10)/3=5 beträgt.

Es ist logisch anzunehmen, dass das Zeitfenster ein sehr wichtiger Parameter für RR ist; je kleiner es ist, desto höher ist die Antwortzeit. Man kann es jedoch auch nicht zu klein wählen, da die Zeit für den Kontextwechsel ebenfalls eine Rolle für die Gesamtleistung spielt. Daher wird die Wahl der Ausführungszeitfenster vom OS-Architekten festgelegt und hängt von den Aufgaben ab, die darin ausgeführt werden sollen. Der Kontextwechsel ist nicht die einzige Dienstleistung, die Zeit kostet – das laufende Programm interagiert mit vielen anderen, beispielsweise verschiedenen Caches, und bei jedem Wechsel muss diese Umgebung gespeichert und wiederhergestellt werden, was ebenfalls viel Zeit in Anspruch nehmen kann.

RR ist ein hervorragender Planer, wenn es nur um die Metrik der Antwortzeit geht. Aber wie verhält sich die Metrik der Durchlaufzeit bei diesem Algorithmus? Betrachten wir das obige Beispiel, bei dem die Ausführungszeiten A, B, C = 5s sind und gleichzeitig eintreffen. Aufgabe A wird um 13 Uhr, B um 14 Uhr und C um 15 Uhr abgeschlossen und die durchschnittliche Durchlaufzeit beträgt 14s. Somit ist RR der schlechteste Algorithmus für die Durchlaufzeit-Metrik.

Im Allgemeinen ist jeder Algorithmus vom Typ RR fair, da er die CPU-Bearbeitungszeit gleichmäßig zwischen allen Prozessen verteilt. Daher stehen diese Metriken ständig im Konflikt miteinander.

Damit haben wir mehrere gegensätzliche Algorithmen und es bleiben einige Annahmen – dass die Zeit der Aufgabe bekannt ist und dass die Aufgabe nur die CPU nutzt.

Mischung mit I/O

Zunächst entfernen wir die Annahme 4, dass der Prozess nur die CPU nutzt, das ist natürlich nicht der Fall und Prozesse können auch auf andere Hardware zugreifen.

In dem Moment, in dem ein Prozess eine Ein- oder Ausgabeoperation anfordert, wechselt der Prozess in den Zustand 'blocked', in Erwartung des Abschlusses der I/O. Wenn die I/O an die Festplatte gesendet wird, kann eine solche Operation mehrere Millisekunden oder länger in Anspruch nehmen, und der Prozessor wird in dieser Zeit untätig sein. In dieser Zeit kann der Scheduler die CPU von einem anderen Prozess nutzen. Die nächste Entscheidung, die der Scheduler treffen muss, besteht darin, wann der Prozess seine I/O abgeschlossen hat. Wenn dies geschieht, tritt eine Unterbrechung auf und das Betriebssystem versetzt den den I/O anfordernden Prozess in den Zustand 'ready'.

Betrachten wir ein Beispiel aus mehreren Aufgaben. Jede davon benötigt 50 ms Prozessorzeit. Die erste wird jedoch alle 10 ms auf I/O zugreifen (das ebenfalls alle 10 ms ausgeführt wird). Der Prozess B hingegen verwendet einfach 50 ms Prozessor ohne I/O.

In diesem Beispiel verwenden wir den STCF-Planer. Wie wird sich der Planer verhalten, wenn wir einen Prozess wie A darauf starten? Er wird folgendermaßen vorgehen – zuerst wird er den Prozess A vollständig abarbeiten und dann den Prozess B.

Der herkömmliche Ansatz zur Lösung dieses Problems besteht darin, jede 10-ms-Unteraufgabe von Prozess A als separate Aufgabe zu interpretieren. So wird bei Start mit dem Algorithmus STJF die Wahl zwischen der 50-ms-Aufgabe und der 10-ms-Aufgabe offensichtlich. Wenn die Unteraufgabe A abgeschlossen ist, wird Prozess B und I/O gestartet. Nach Abschluss des I/O wird beschlossen, den 10-ms-Prozess A erneut zu starten, anstatt Prozess B. Dadurch ist es möglich, Überlappungen zu realisieren, bei denen die CPU von einem anderen Prozess genutzt wird, während der erste auf I/O wartet. Das Ergebnis ist eine bessere Auslastung des Systems – während interaktive Prozesse auf I/O warten, können andere Prozesse auf der CPU ausgeführt werden.

Der Oracle ist weg.

Jetzt versuchen wir, die Annahme aufzugeben, dass die Laufzeit einer Aufgabe bekannt ist. Dies ist im Allgemeinen die schlechteste und unrealistischste Annahme aus der gesamten Liste. Tatsächlich weiß das Betriebssystem in gängigen, durchschnittlichen Systemen normalerweise sehr wenig über die Ausführungszeit von Aufgaben, wie würde man also einen Planer ohne das Wissen über die Dauer der Aufgabe erstellen? Vielleicht könnten wir einige Prinzipien des RR verwenden, um dieses Problem zu lösen?

Fazit

Wir haben die grundlegenden Ideen der Aufgabenplanung betrachtet und zwei Familien von Planern betrachtet. Der erste startet die kürzeste Aufgabe zuerst und erhöht so die Durchlaufzeit, während der zweite gleichmäßig zwischen allen Aufgaben wechselt und die Reaktionszeit erhöht. Beide Algorithmen sind dort schlecht, wo die Algorithmen der anderen Familie gut sind. Außerdem haben wir gesehen, wie die parallele Nutzung von CPU und I/O die Leistung verbessern kann, aber das Problem mit dem Hellsehen des Betriebssystems nicht gelöst. Im nächsten Kurs werden wir einen Planer betrachten, der in die nahen Vergangenheit schaut und versucht, die Zukunft vorherzusagen. Er heißt Multi-Level-Feedback-Queue.

Quelle: habr.com