Einführung in Betriebssysteme

Hey Habr! Ich möchte Sie auf eine Reihe von Artikeln und Übersetzungen einer meiner Meinung nach interessanten Literatur aufmerksam machen – OSTEP. In diesem Material wird ausführlich auf die Arbeit unixähnlicher Betriebssysteme eingegangen, nämlich auf die Arbeit mit Prozessen, verschiedenen Schedulern, Speicher und anderen ähnlichen Komponenten, aus denen ein modernes Betriebssystem besteht. Das Original aller Materialien können Sie hier einsehen hier. Bitte beachten Sie, dass die Übersetzung unprofessionell (ziemlich frei) angefertigt wurde, aber ich hoffe, dass ich die allgemeine Bedeutung beibehalten habe.

Laborarbeiten zu diesem Thema finden Sie hier:

Andere teile:

Sie können auch auf meinem Kanal vorbeischauen Telegramm =)

Einführung in den Scheduler

Der Kern des Problems: Wie entwickelt man eine Scheduler-Richtlinie?
Wie sollten die zugrunde liegenden Scheduler-Richtlinien-Frameworks gestaltet sein? Was sollten die wichtigsten Annahmen sein? Welche Kennzahlen sind wichtig? Welche grundlegenden Techniken wurden in frühen Computersystemen verwendet?

Annahmen zur Arbeitslast

Bevor wir auf mögliche Richtlinien eingehen, machen wir zunächst ein paar vereinfachende Exkurse über die im System ablaufenden Prozesse, die zusammenfassend genannt werden Arbeitsbelastung. Das Definieren der Arbeitslast ist ein wichtiger Teil der Erstellung von Richtlinien. Je mehr Sie über die Arbeitslast wissen, desto bessere Richtlinien können Sie erstellen.

Machen wir die folgenden Annahmen über die im System laufenden Prozesse, manchmal auch genannt Jobs & Karriere (Aufgaben). Fast alle dieser Annahmen sind nicht realistisch, aber für die Entwicklung des Denkens notwendig.

Jede Aufgabe wird gleich lange ausgeführt.
Alle Aufgaben werden gleichzeitig gestellt,
Die zugewiesene Aufgabe funktioniert bis zu ihrer Fertigstellung,
Alle Aufgaben verbrauchen nur CPU,
Die Laufzeit jeder Aufgabe ist bekannt.

Planer-Metriken

Zusätzlich zu einigen Annahmen über die Auslastung wird ein weiteres Tool zum Vergleich verschiedener Planungsrichtlinien benötigt: Scheduler-Metriken. Eine Metrik ist nur ein Maß für etwas. Es gibt eine Reihe von Metriken, die zum Vergleich von Planern verwendet werden können.

Zum Beispiel verwenden wir eine Metrik namens Seitenwechsel (Seitenwechsel). Die Aufgabendurchlaufzeit ist definiert als die Differenz zwischen der Aufgabenerledigungszeit und der Aufgabenankunftszeit im System.

Tturnaround=Tcompletion−Tarrival

Da wir davon ausgegangen sind, dass alle Aufgaben gleichzeitig eintreffen, ist Ta=0 und somit Tt=Tc. Dieser Wert wird sich natürlich ändern, wenn wir die oben genannten Annahmen ändern.

Eine weitere Metrik – Fairness (Fairness, Ehrlichkeit). Produktivität und Fairness sind in der Planung oft gegensätzliche Eigenschaften. Beispielsweise kann der Planer die Leistung optimieren, jedoch auf Kosten der Ausführung anderer Aufgaben, wodurch die Fairness verringert wird.

FIRST IN FIRST OUT (FIFO)

Der grundlegendste Algorithmus, den wir implementieren können, heißt FIFO oder Wer zuerst kommt (rein), mahlt zuerst (raus). Dieser Algorithmus hat mehrere Vorteile: Er ist sehr einfach zu implementieren, erfüllt alle unsere Annahmen und erledigt seine Aufgabe recht gut.

Schauen wir uns ein einfaches Beispiel an. Nehmen wir an, es wurden 3 Aufgaben gleichzeitig gestellt. Nehmen wir jedoch an, dass Aufgabe A etwas früher angekommen ist als alle anderen, sodass sie in der Ausführungsliste früher als die anderen erscheint, genau wie B relativ zu C. Nehmen wir an, dass jede von ihnen 10 Sekunden lang ausgeführt wird. Wie lange dauert es in diesem Fall durchschnittlich, diese Aufgaben zu erledigen?

Durch Zählen der Werte – 10+20+30 und Teilen durch 3 erhalten wir die durchschnittliche Programmausführungszeit von 20 Sekunden.
Versuchen wir nun, unsere Annahmen zu ändern. Insbesondere Annahme 1 und daher gehen wir nicht mehr davon aus, dass die Ausführung jeder Aufgabe gleich lange dauert. Wie wird sich FIFO dieses Mal verhalten?

Wie sich herausstellt, wirken sich unterschiedliche Aufgabenausführungszeiten äußerst negativ auf die Produktivität des FIFO-Algorithmus aus. Nehmen wir an, dass Aufgabe A 100 Sekunden dauert, während B und C immer noch jeweils 10 Sekunden dauern.

Wie aus der Abbildung ersichtlich ist, beträgt die durchschnittliche Zeit für das System (100+110+120)/3=110. Dieser Effekt wird aufgerufen Konvoi-Effekt, wenn einige kurzfristige Verbraucher einer Ressource nach einem starken Verbraucher anstehen. Es ist wie in der Warteschlange im Supermarkt, wenn ein Kunde mit vollem Einkaufswagen vor einem steht. Die beste Lösung für das Problem besteht darin, zu versuchen, die Kasse zu wechseln oder sich zu entspannen und tief durchzuatmen.

Kürzester Job zuerst

Ist es möglich, eine ähnliche Situation mit schwergewichtigen Prozessen irgendwie zu lösen? Sicherlich. Eine andere Art der Planung heißtKürzester Job zuerst (SJF). Sein Algorithmus ist auch recht primitiv – wie der Name schon sagt, werden die kürzesten Aufgaben nacheinander zuerst gestartet.

In diesem Beispiel wird das Ergebnis der Ausführung derselben Prozesse eine Verbesserung der durchschnittlichen Programmdurchlaufzeit sein, und zwar gleich 50 statt 110, was fast zweimal besser ist.

Unter der gegebenen Annahme, dass alle Aufgaben gleichzeitig ankommen, scheint der SJF-Algorithmus der optimalste Algorithmus zu sein. Allerdings erscheinen unsere Annahmen immer noch nicht realistisch. Dieses Mal ändern wir Annahme 2 und stellen uns dieses Mal vor, dass Aufgaben jederzeit vorhanden sein können und nicht alle gleichzeitig. Zu welchen Problemen kann dies führen?

Stellen wir uns vor, dass Aufgabe A (100c) zuerst eintrifft und mit der Ausführung beginnt. Bei t=10 treffen die Aufgaben B und C ein, die jeweils 10 Sekunden dauern. Die durchschnittliche Ausführungszeit beträgt also (100+(110-10)+(120-10))3 = 103. Was könnte der Scheduler tun, um dies zu verbessern?

Kürzeste Time-to-Completion First (STCF)

Um die Situation zu verbessern, verzichten wir auf die Annahme 3, dass das Programm gestartet wird und bis zur Fertigstellung läuft. Darüber hinaus benötigen wir Hardware-Unterstützung und werden diese, wie Sie sich vorstellen können, verwenden Timer eine laufende Aufgabe unterbrechen und Kontextwechsel. Somit kann der Scheduler in dem Moment, in dem die Aufgaben B, C eintreffen, etwas tun – die Ausführung von Aufgabe A stoppen und die Aufgaben B und C in die Verarbeitung versetzen und nach deren Abschluss mit der Ausführung von Prozess A fortfahren. Ein solcher Scheduler wird aufgerufen STCFoder Präventiver Job zuerst.

Das Ergebnis dieses Planers ist das folgende Ergebnis: ((120-0)+(20-10)+(30-10))/3=50. Somit wird ein solcher Scheduler für unsere Aufgaben noch optimaler.

Metrische Reaktionszeit

Wenn wir also die Laufzeit der Aufgaben kennen und wissen, dass diese Aufgaben nur CPU beanspruchen, ist STCF die beste Lösung. Und früher einmal funktionierten diese Algorithmen recht gut. Mittlerweile verbringt der Nutzer jedoch die meiste Zeit am Terminal und erwartet ein produktives interaktives Erlebnis. So wurde eine neue Metrik geboren – Reaktionszeit (Antwort).

Die Reaktionszeit berechnet sich wie folgt:

Tresponse=Tfirstrun−Tarrival

Für das vorherige Beispiel beträgt die Antwortzeit also: A=0, B=0, C=10 (abg=3,33).

Und es stellt sich heraus, dass der STCF-Algorithmus in einer Situation, in der drei Aufgaben gleichzeitig eintreffen, nicht so gut ist – er muss warten, bis die kleinen Aufgaben vollständig erledigt sind. Der Algorithmus ist also 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 einzugeben, und müssen mehr als 3 Sekunden warten, weil eine andere Aufgabe die CPU beansprucht. Es ist nicht sehr angenehm.

Wir stehen also vor einem weiteren Problem: Wie können wir einen Scheduler erstellen, der auf die Antwortzeit reagiert?

Round Robin

Zur Lösung dieses Problems wurde ein Algorithmus entwickelt Round Robin (RR). Die Grundidee ist ganz einfach: Anstatt Aufgaben so lange auszuführen, bis sie abgeschlossen sind, führen wir die Aufgabe für einen bestimmten Zeitraum (Zeitscheibe genannt) aus und wechseln dann zu einer anderen Aufgabe aus der Warteschlange. Der Algorithmus wiederholt seine Arbeit, bis alle Aufgaben abgeschlossen sind. In diesem Fall muss die Laufzeit des Programms ein Vielfaches der Zeit betragen, nach der der Timer den Vorgang unterbricht. Wenn beispielsweise ein Timer einen Prozess alle x=10 ms unterbricht, sollte die Größe des Prozessausführungsfensters ein Vielfaches von 10 sein und 10,20 oder x*10 betragen.

Schauen wir uns ein Beispiel an: ABC-Aufgaben treffen gleichzeitig im System ein und jede von ihnen möchte 5 Sekunden lang ausgeführt werden. Der SJF-Algorithmus erledigt jede Aufgabe, bevor er mit der nächsten beginnt. Im Gegensatz dazu wird der RR-Algorithmus mit einem Startfenster = 1s die Aufgaben wie folgt durchlaufen (Abb. 4.3):

(SJF schon wieder (schlecht für die Reaktionszeit)

(Round Robin (gut für Reaktionszeit)

Die durchschnittliche Antwortzeit für den RR-Algorithmus beträgt (0+1+2)/3=1, während sie für den 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 Reaktionszeit. Sie sollten es jedoch nicht zu klein machen, da die Kontextwechselzeit auch eine Rolle für die Gesamtleistung spielt. Daher wird die Wahl der Ausführungsfensterzeit vom Betriebssystemarchitekten festgelegt und hängt von den Aufgaben ab, die darin ausgeführt werden sollen. Das Wechseln des Kontexts ist nicht der einzige Dienstvorgang, der Zeit verschwendet – das laufende Programm arbeitet mit vielen anderen Dingen, zum Beispiel verschiedenen Caches, und bei jedem Wechsel ist es notwendig, diese Umgebung zu speichern und wiederherzustellen, was ebenfalls viel Zeit in Anspruch nehmen kann Zeit.

RR ist ein großartiger Planer, wenn wir nur über die Reaktionszeitmetrik sprechen würden. Aber wie verhält sich die Metrik der Aufgabendurchlaufzeit mit diesem Algorithmus? Betrachten Sie das obige Beispiel, wenn die Betriebszeit von A, B, C = 5 Sekunden beträgt und sie gleichzeitig ankommen. Aufgabe A endet um 13, B um 14, C um 15 Sekunden und die durchschnittliche Bearbeitungszeit beträgt 14 Sekunden. Somit ist RR der schlechteste Algorithmus für die Umsatzmetrik.

Allgemeiner ausgedrückt ist jeder RR-Algorithmus fair; er teilt die CPU-Zeit gleichmäßig auf alle Prozesse auf. Und daher stehen diese Kennzahlen ständig im Konflikt miteinander.

Somit haben wir mehrere gegensätzliche Algorithmen und gleichzeitig bleiben noch einige Annahmen übrig – dass die Task-Zeit bekannt ist und die Task nur die CPU beansprucht.

Mischen mit I/O

Entfernen wir zunächst Annahme 4, dass der Prozess nur die CPU nutzt; das ist natürlich nicht der Fall und Prozesse können auf andere Geräte zugreifen.

Sobald ein Prozess eine E/A-Operation anfordert, wechselt der Prozess in den blockierten Zustand und wartet auf den Abschluss der E/A. Wenn E/A an die Festplatte gesendet werden, kann ein solcher Vorgang mehrere ms oder länger dauern und der Prozessor befindet sich in diesem Moment im Leerlauf. Während dieser Zeit kann der Scheduler den Prozessor mit jedem anderen Prozess belegen. Die nächste Entscheidung, die der Scheduler treffen muss, ist, wann der Prozess seine E/A abschließen wird. In diesem Fall kommt es zu einem Interrupt und das Betriebssystem versetzt den Prozess, der die E/A aufgerufen hat, in den Bereitschaftszustand.

Schauen wir uns ein Beispiel für mehrere Probleme an. Jeder von ihnen benötigt 50 ms CPU-Zeit. Der erste greift jedoch alle 10 ms auf E/A zu (was auch alle 10 ms ausgeführt wird). Und Prozess B verwendet einfach einen 50-ms-Prozessor ohne E/A.

In diesem Beispiel verwenden wir den STCF-Scheduler. Wie verhält sich der Scheduler, wenn ein Prozess wie A darauf gestartet wird? Er wird Folgendes tun: Zuerst wird er Prozess A vollständig ausarbeiten und dann Prozess B.

Der traditionelle Ansatz zur Lösung dieses Problems besteht darin, jede 10-ms-Unteraufgabe von Prozess A als separate Aufgabe zu behandeln. Wenn man also mit dem STJF-Algorithmus beginnt, liegt die Wahl zwischen einer 50-ms-Aufgabe und einer 10-ms-Aufgabe auf der Hand. Wenn dann Unteraufgabe A abgeschlossen ist, werden Prozess B und E/A gestartet. Nach Abschluss der E/A ist es üblich, den 10-ms-Prozess A anstelle von Prozess B erneut zu starten. Auf diese Weise ist es möglich, eine Überlappung zu implementieren, bei der die CPU von einem anderen Prozess verwendet wird, während der erste auf den Prozess wartet E/A. Und dadurch wird das System besser ausgelastet – in dem Moment, in dem interaktive Prozesse auf I/O warten, können andere Prozesse auf dem Prozessor ausgeführt werden.

Das Orakel gibt es nicht mehr

Versuchen wir nun, die Annahme loszuwerden, dass die Laufzeit der Aufgabe bekannt ist. Dies ist im Allgemeinen die schlechteste und unrealistischste Annahme auf der gesamten Liste. Tatsächlich weiß das Betriebssystem selbst in einem durchschnittlichen normalen Betriebssystem normalerweise nur sehr wenig über die Ausführungszeit von Aufgaben. Wie kann man also einen Scheduler erstellen, ohne zu wissen, wie lange die Ausführung der Aufgabe dauern wird? Vielleicht könnten wir einige RR-Prinzipien nutzen, um dieses Problem zu lösen?

Ergebnis

Wir haben uns die Grundideen der Aufgabenplanung angesehen und uns zwei Familien von Planern angesehen. Der erste startet die kürzeste Aufgabe zuerst und erhöht so die Bearbeitungszeit, während der zweite gleichmäßig zwischen allen Aufgaben hin- und hergerissen wird, was die Reaktionszeit erhöht. Beide Algorithmen sind schlecht, während die Algorithmen der anderen Familie gut sind. Wir haben auch untersucht, wie die parallele Nutzung von CPU und I/O die Leistung verbessern kann, haben das Problem mit der Hellsichtigkeit des Betriebssystems jedoch nicht gelöst. Und in der nächsten Lektion schauen wir uns einen Planer an, der in die unmittelbare Vergangenheit blickt und versucht, die Zukunft vorherzusagen. Und es wird als mehrstufige Feedback-Warteschlange bezeichnet.

Source: habr.com

Betriebssysteme: Drei einfache Teile. Teil 4: Einführung in den Scheduler (Übersetzung)