Einführung in Betriebssysteme

Hallo, Habr! Ich möchte euch eine Serie von Übersetzungen einer interessanten Literatur vorstellen — OSTEP. In diesem Material wird die Funktionsweise von unixähnlichen Betriebssystemen recht tiefgehend behandelt, insbesondere die Arbeit mit Prozessen, verschiedenen Planern, Speicher und anderen ähnlichen Komponenten, die ein modernes Betriebssystem ausmachen. Das Original aller Materialien könnt ihr hier ansehen hier. Bitte beachtet, dass die Übersetzung nicht professionell (recht frei) durchgeführt wurde, aber ich hoffe, dass ich die allgemeine Bedeutung erhalten habe.

Die Laborarbeiten zu diesem Thema findet ihr hier:

Weitere Teile:

Ihr könnt auch mal auf meinen Kanal in Telegram =)

Einführung in den Scheduler

Das Problem im Kern: Wie entwickelt man eine Scheduler-Politik?
Wie sollten grundlegende Frameworks für Scheduler-Politiken entwickelt werden? Was sind die wesentlichen Annahmen? Welche Metriken sind wichtig? Welche grundlegenden Techniken wurden in früheren Rechensystemen verwendet?

Annahmen zur Arbeitslast

Bevor wir mögliche Politiken diskutieren, lassen Sie uns zunächst einige vereinfachende Überlegungen zu den Prozessen anstellen, die im System laufen und zusammen als Arbeitslastbezeichnet werden. Eine klare Definition der Arbeitslast ist entscheidend für die Entwicklung von Politiken, und je mehr Sie über die Arbeitslast wissen, desto besser können Sie eine qualitativ hochwertige Politik formulieren.

Lassen Sie uns folgende Annahmen über die im System laufenden Prozesse treffen, die manchmal auch als jobs (Tasks) bezeichnet werden. Praktisch alle diese Annahmen sind unrealistisch, aber sie sind notwendig, um den Gedankengang zu fördern.

Jeder Task läuft die gleiche Zeit lang,
Alle Tasks werden gleichzeitig gestartet,
Ein gestarteter Task läuft bis zu seinem Abschluss,
Alle Tasks nutzen nur die CPU,
Die Bearbeitungszeit jeder Aufgabe ist bekannt.

Scheduler-Metriken

Neben einigen Annahmen zur Last benötigen wir auch ein Werkzeug zum Vergleich verschiedener Scheduling-Politiken: die Scheduler-Metriken. Eine Metrik ist lediglich ein Maß für etwas. Es gibt eine Reihe von Metriken, die verwendet werden können, um Scheduler zu vergleichen.

Als Beispiel verwenden wir eine Metrik, die genannt wird Bearbeitungszeit (turnaround time). Die Bearbeitungszeit einer Aufgabe wird als Differenz zwischen dem Abschlusszeitpunkt der Aufgabe und dem Zeitpunkt, an dem die Aufgabe im System ankommt, definiert.

Tturnaround = Tcompletion − Tarrival

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

Eine andere Metrik ist Fairness (Fairness, Gerechtigkeit). Leistung und Fairness sind oft gegensätzliche Eigenschaften im Scheduling. Ein Scheduler kann die Leistung optimieren, jedoch auf Kosten der Wartezeit anderer Aufgaben, wodurch die Fairness verringert wird.

FIRST IN FIRST OUT (FIFO)

Der grundlegendste Algorithmus, den wir umsetzen können, wird 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, während er die Aufgabe ziemlich gut erfüllt.

Betrachten wir ein einfaches Beispiel. Angenommen, 3 Aufgaben wurden gleichzeitig eingereicht. Nehmen wir an, dass Aufgabe A etwas früher als die anderen eingetroffen ist, sodass sie im Ausführungsreihenfolge vor den anderen steht, 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 — 10 + 20 + 30 zusammenzählen und durch 3 teilen, erhalten wir eine durchschnittliche Ausführungszeit des Programms von 20 Sekunden.
Jetzt versuchen wir, unsere Annahmen zu ändern. Insbesondere Annahme 1, weshalb wir nicht mehr davon ausgehen, dass jede Aufgabe die gleiche Zeit benötigt. Wie wird sich FIFO diesmal schlagen?

Es zeigt sich, dass unterschiedliche Ausführungszeiten von Aufgaben die Produktivität des FIFO-Algorithmus negativ beeinflussen. Angenommen, Aufgabe A benötigt 100 Sekunden, während B und C jeweils 10 Sekunden benötigen.

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

Shortest Job First

Kann man eine solche Situation mit schweren Prozessen irgendwie lösen? Natürlich. Ein anderer Planungstyp wird genanntShortest Job First (SJF). Sein Algorithmus ist ebenfalls recht primitiv – wie der Name schon sagt, werden zuerst die kürzesten Aufgaben nacheinander ausgeführt.

In diesem Beispiel führt das Starten der gleichen Prozesse zu einer Verbesserung der durchschnittlichen Bearbeitungszeit, die dann 50 anstelle von 110 beträgt, was praktisch doppelt so gut ist.

Für die Annahme, dass alle Aufgaben gleichzeitig ankommen, scheint der SJF-Algorithmus der optimalste zu sein. Unsere Annahmen scheinen jedoch immer noch unrealistisch. Diesmal ändern wir Annahme 2 und stellen uns vor, dass Aufgaben zu beliebigen Zeiten eintreffen können und nicht alle gleichzeitig. Welche Probleme könnte dies verursachen?

Nehmen wir an, Aufgabe A (100s) kommt als erste und beginnt mit der Ausführung. Zu t=10 erreichen Aufgaben B und C, die jeweils 10 Sekunden in Anspruch nehmen. Daher beträgt die durchschnittliche Bearbeitungszeit (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 falleng, dass das Programm läuft und bis zur Fertigstellung arbeitet. Außerdem benötigen wir Hardwareunterstützung und wie Sie vielleicht erraten haben, werden wir einen Timer verwenden, um laufende Aufgaben zu unterbrechen und Kontexte zu wechseln.So kann der Scheduler bei Eintreffen der Aufgaben B und V die Ausführung von Aufgabe A unterbrechen und die Aufgaben B und V zur Bearbeitung annehmen, um danach die Ausführung von Prozess A fortzusetzen. Ein solcher Scheduler wird genannt STCFoder Preemptive Job First.

Das Ergebnis der Arbeit dieses Schedulers wird folgendermaßen sein: ((120-0)+(20-10)+(30-10))/3=50. Somit wird dieser Scheduler noch optimaler für unsere Aufgaben.

Metrik Reaktionszeit (Response Time)

Daher, wenn wir die Laufzeit der Aufgaben kennen und wissen, dass diese Aufgaben nur die CPU nutzen, wird STCF die beste Lösung sein. In früheren Zeiten funktionierten diese Algorithmen ganz gut. Jetzt verbringt der Benutzer jedoch die meiste Zeit am Terminal und erwartet eine leistungsfähige, interaktive Interaktion. So entstand die neue Metrik — Reaktionszeit (Response Time).

Die Reaktionszeit wird folgendermaßen berechnet:

Tresponse=Tfirstrun−Tarrival

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

Es stellt sich heraus, dass der STCF-Algorithmus in Situationen, in denen drei Aufgaben gleichzeitig ankommen, nicht so gut abschneidet – er muss warten, bis die kleinen Aufgaben vollständig abgeschlossen sind. Daher ist der Algorithmus zwar gut für die Durchlaufzeit-Metrik, jedoch nicht geeignet für die Interaktivitätsmetrik. Stellen Sie sich vor, Sie sitzen an einem Terminal und versuchen, Zeichen in einen Editor einzugeben, und müssen dabei mehr als 10 Sekunden warten, weil eine andere Aufgabe die CPU beansprucht. Das ist alles andere als angenehm.

So stehen wir vor einem weiteren Problem: Wie können wir einen Scheduler entwickeln, der zeitempfindlich ist?

Round Robin

Zur Lösung dieses Problems wurde ein Algorithmus entwickelt Round Robin (RR). Die Grundidee ist ziemlich einfach: Anstatt Aufgaben bis zur vollständigen Fertigstellung zu starten, führen wir die Aufgabe für einen bestimmten Zeitraum (genannt Quantenzeit) aus und wechseln dann zur nächsten Aufgabe in der Warteschlange. Der Algorithmus wiederholt diesen Vorgang, bis alle Aufgaben abgeschlossen sind. Dabei muss die Laufzeit 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, muss die Größe des Ausführungsfensters ein Vielfaches von 10 sein und 10, 20 oder x*10 betragen.

Betrachten wir ein Beispiel: Die Aufgaben A, B und C kommen gleichzeitig im System an, und jede möchte 5 Sekunden lang arbeiten. Der SJF-Algorithmus wird jede Aufgabe bis zum Ende ausführen, bevor er eine andere startet. Im Gegensatz dazu wird der RR-Algorithmus mit einem Zeitfenster von 1 Sekunde die Aufgaben folgendermaßen durchlaufen (Abb. 4.3):

(SJF Wiederholung (Schlecht für die Reaktionszeit)

(Round Robin (Gut für die Reaktionszeit)

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

Es liegt nahe, dass das Zeitfenster ein sehr wichtiger Parameter für RR ist: je kleiner es ist, desto höher ist die Antwortzeit. Allerdings sollte es nicht zu klein gewählt werden, da auch die Kontextwechselzeit eine Rolle bei der Gesamtleistung spielt. Somit wird die Wahl der Ausführungszeit durch den OS-Architekten festgelegt und hängt von den Aufgaben ab, die darin geplant sind. Der Kontextwechsel ist nicht die einzige operationale Tätigkeit, die Zeit beansprucht – ein laufendes Programm bearbeitet auch viele andere Aspekte, wie verschiedene Caches, und bei jedem Wechsel muss diese Umgebung gespeichert und wiederhergestellt werden, was ebenfalls viel Zeit in Anspruch nehmen kann.

RR ist ein ausgezeichneter Scheduler, wenn es nur um die Antwortzeit-Metrik geht. Aber wie verhält sich die Metrik der Durchlaufzeit bei diesem Algorithmus? Betrachten wir das oben genannte Beispiel, bei dem die Ausführungszeiten A, B, C=5s sind und sie zur gleichen Zeit eintreffen. Aufgabe A wird um 13s abgeschlossen, B um 14s und C um 15s, was zu einer durchschnittlichen Durchlaufzeit von 14s führt. Daher ist RR der schlechteste Algorithmus für die Durchlaufzeiten-Metrik.

Allgemeiner gesagt ist jeder RR-Algorithmus fair, da er die CPU-Zeit gleichmäßig auf alle Prozesse verteilt. Dadurch können diese Metriken ständig miteinander in Konflikt geraten.

So haben wir mehrere gegensätzliche Algorithmen und es bleiben zudem einige Annahmen, nämlich dass die Zeit für die 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, was natürlich nicht der Fall ist, da Prozesse auch auf andere Hardware zugreifen können.

In dem Moment, in dem ein Prozess eine Ein-/Ausgabeoperation anfordert, wechselt der Prozess in den Blockierungszustand, während er auf den Abschluss der I/O wartet. Wenn die I/O an eine Festplatte gesendet wird, kann diese Operation mehrere Millisekunden oder länger in Anspruch nehmen, während die CPU zu diesem Zeitpunkt untätig bleibt. In dieser Zeit kann der Scheduler die CPU mit einem anderen Prozess belegen. Die nächste Entscheidung, die der Scheduler treffen muss, ist, wann der Prozess seine I/O abgeschlossen hat. Wenn dies passiert, erfolgt eine Unterbrechung, und das Betriebssystem versetzt den den I/O anfordernden Prozess in den Bereitschaftszustand.

Betrachten wir ein Beispiel mit mehreren Aufgaben. Jede benötigt 50 ms CPU-Zeit. Die erste Aufgabe greift jedoch alle 10 ms auf I/O zu (was ebenfalls alle 10 ms ausgeführt wird). Prozess B verwendet einfach die 50 ms CPU ohne I/O.

In diesem Beispiel verwenden wir den STCF-Planer. Wie verhält sich der Planer, wenn wir einen Prozess wie A starten? Er wird folgendermaßen vorgehen – zunächst wird Prozess A vollständig bearbeitet, bevor Prozess B beginnt.

Der traditionelle Ansatz zur Lösung dieses Problems besteht darin, jede 10-ms-Unteraufgabe von Prozess A als separate Aufgabe zu interpretieren. Daher ist bei Verwendung des STJF-Algorithmus die Wahl zwischen der 50-ms-Aufgabe und der 10-ms-Aufgabe offensichtlich. Wenn Unteraufgabe A abgeschlossen ist, wird Prozess B und I/O gestartet. Nach dem Abschluss von I/O wird entschieden, dass der 10-ms-Prozess A erneut gestartet wird, anstatt Prozess B auszuführen. Auf diese Weise kann eine Überlappung realisiert werden, bei der die CPU von einem anderen Prozess verwendet wird, während der erste auf I/O wartet. Das Ergebnis ist eine bessere Auslastung des Systems – in dem Moment, wenn interaktive Prozesse auf I/O warten, können andere Prozesse auf der CPU ausgeführt werden.

Der Oracle ist nicht mehr

Lassen Sie uns nun das Missverständnis beseitigen, dass die Ausführungszeit einer Aufgabe bekannt ist. Dies ist im Grunde die schlechteste und unrealistischste Annahme auf der Liste. In der Tat weiß das durchschnittliche Betriebssystem in der Regel sehr wenig über die Ausführungszeit von Aufgaben. Wie kann man also einen Scheduler bauen, ohne zu wissen, wie lange eine Aufgabe benötigt? Vielleicht könnten wir einige Prinzipien des RR-Algorithmus nutzen, um dieses Problem zu lösen?

Zusammenfassung

Wir haben die grundlegenden Ideen des Task-Schedulings betrachtet und uns zwei Gruppen von Schedulern angesehen. Der erste startet mit der kürzesten Aufgabe und verbessert so die Bearbeitungszeit, während der zweite gleichmäßig zwischen allen Aufgaben aufschlüsselt und die Reaktionszeit erhöht. Beide Algorithmen sind in den Situationen, in denen die jeweiligen anderen Algorithmen gut abschneiden, nicht optimal. Außerdem haben wir uns angeschaut, wie die parallele Nutzung von CPU und I/O die Leistung verbessern kann, ohne jedoch das Problem der Vorhersagbarkeit des Betriebssystems zu lösen. Im nächsten Abschnitt werden wir einen Scheduler betrachten, der in die jüngste Vergangenheit schaut und versucht, die Zukunft vorherzusagen. Dieser wird als Multi-Level-Feedback-Warteschlange bezeichnet.

Quelle: habr.com