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 =)

Planung: Mehrstufige Feedback-Warteschlange

In dieser Vorlesung werden wir über die Probleme bei der Entwicklung eines der bekanntesten Ansätze sprechen
Planung, die man nennt Mehrstufige Feedback-Warteschlange (MLFQ). Der MLFQ-Scheduler wurde erstmals 1962 von Fernando J. Corbató in einem System namens beschrieben
Kompatibles Time-Sharing-System (CTSS). Diese Werke (einschließlich späterer Arbeiten an
Multics) wurden anschließend für den Turing Award nominiert. Der Planer war
anschließend verbessert und erhielt das Aussehen, das bereits in zu finden ist
einige moderne Systeme.

Der MLFQ-Algorithmus versucht, zwei grundlegende überlappende Probleme zu lösen.
Erstens, wird versucht, die Durchlaufzeit zu optimieren, die, wie wir in der vorherigen Vorlesung besprochen haben, durch die Methode optimiert wird, am meisten am Anfang der Warteschlange zu beginnen
kurze Aufgaben. Das Betriebssystem weiß jedoch nicht, wie lange ein bestimmter Prozess ausgeführt wird
notwendige Kenntnisse für den Betrieb der SJF- und STCF-Algorithmen. Zweitens, MLFQ versucht es
Machen Sie das System für Benutzer reaktionsfähig (z. B. für diejenigen, die sitzen und
auf den Bildschirm starren und darauf warten, dass die Aufgabe abgeschlossen ist) und so die Zeit minimieren
Antwort. Leider verbessern Algorithmen wie RR die Reaktionszeit, aber extrem
haben einen negativen Einfluss auf die Durchlaufzeitmetrik. Daher unser Problem: Wie man gestaltet
ein Planer, der unsere Anforderungen erfüllt, ohne etwas darüber zu wissen
die Art des Prozesses im Allgemeinen? Wie kann der Planer die Eigenschaften von Aufgaben lernen,
was es startet und so bessere Planungsentscheidungen treffen kann?

Der Kern des Problems: Wie kann man die Aufgabenstellung ohne perfekte Kenntnisse planen?
So entwerfen Sie einen Scheduler, der gleichzeitig die Antwortzeit minimiert
für interaktive Aufgaben und minimiert gleichzeitig die Bearbeitungszeit ohne Wissen
Wissen über die Ausführungszeit einer Aufgabe?

Hinweis: Wir lernen aus früheren Ereignissen

Die MLFQ-Warteschlange ist ein hervorragendes Beispiel für ein System, das daraus lernt
vergangene Ereignisse, um die Zukunft vorherzusagen. Ähnliche Ansätze gibt es oft
gefunden in OS (und vielen anderen Zweigen der Informatik, einschließlich Zweigen
Hardwarevorhersagen und Caching-Algorithmen). Ähnliche Reisen
werden ausgelöst, wenn Aufgaben Verhaltensphasen haben und somit vorhersehbar sind.
Allerdings sollten Sie bei dieser Technik vorsichtig sein, da Vorhersagen sehr einfach sind
kann sich als falsch erweisen und dazu führen, dass das System schlechtere Entscheidungen trifft als
wäre überhaupt ohne Wissen.

MLFQ: Grundregeln

Schauen wir uns die Grundregeln des MLFQ-Algorithmus an. Und zwar Implementierungen dieses Algorithmus
Es gibt mehrere, die grundsätzlichen Ansätze sind ähnlich.
In der Implementierung, die wir uns ansehen werden, wird MLFQ mehrere haben
separate Warteschlangen, von denen jede eine andere Priorität hat. Jederzeit,
Eine zur Ausführung bereite Aufgabe befindet sich in einer Warteschlange. MLFQ verwendet Prioritäten,
um zu entscheiden, welche Aufgabe zur Ausführung ausgeführt werden soll, d. h. Aufgabe mit höher
Priorität (Aufgabe aus der Warteschlange mit der höchsten Priorität) wird zuerst gestartet
Warteschlange.
Natürlich kann es in einer bestimmten Warteschlange auch mehr als eine Aufgabe geben
Sie haben also die gleiche Priorität. In diesem Fall wird der Mechanismus verwendet
RR, um einen Lauf zwischen diesen Aufgaben zu planen.
Somit kommen wir zu zwei Grundregeln für MLFQ:

Regel 1: Wenn Priorität (A) > Priorität (B), wird Aufgabe A gestartet (B nicht).
Regel 2: Wenn Priorität (A) = Priorität (B), werden A und B mit RR gestartet

Basierend auf dem oben Gesagten sind dies die Schlüsselelemente für die Planung von MLFQ
sind Prioritäten. Anstatt jedem eine feste Priorität zu geben
Task ändert MLFQ seine Priorität abhängig vom beobachteten Verhalten.
Wenn beispielsweise eine Aufgabe der CPU ständig Arbeit abverlangt, während sie auf Tastatureingaben wartet,
MLFQ wird die Prozesspriorität hoch halten, weil das so ist
Ein interaktiver Prozess sollte funktionieren. Wenn im Gegenteil die Aufgabe ständig und
Wenn die CPU über einen längeren Zeitraum stark beansprucht wird, verringert MLFQ diese
eine Priorität. Daher wird MLFQ das Verhalten von Prozessen während ihrer Ausführung untersuchen
und Nutzungsverhalten.
Lassen Sie uns ein Beispiel zeichnen, wie die Warteschlangen irgendwann aussehen könnten
Zeit und dann bekommst du so etwas:

In diesem Schema befinden sich zwei Prozesse A und B in der Warteschlange mit der höchsten Priorität. Verfahren
C befindet sich irgendwo in der Mitte und Prozess D befindet sich ganz am Ende der Warteschlange. Gemäß dem oben Gesagten
Gemäß den Beschreibungen des MLFQ-Algorithmus führt der Scheduler Aufgaben nur mit der höchsten aus
Priorität gemäß RR, und die Aufgaben C, D werden arbeitslos sein.
Natürlich gibt ein statischer Schnappschuss kein vollständiges Bild der Funktionsweise von MLFQ.
Es ist wichtig, genau zu verstehen, wie sich das Bild im Laufe der Zeit verändert.

Versuch 1: So ändern Sie die Priorität

An diesem Punkt müssen Sie entscheiden, wie MLFQ die Prioritätsstufe ändern wird
Aufgaben (und damit die Position der Aufgabe in der Warteschlange), während sie ihren Lebenszyklus durchläuft. Für
Dies ist notwendig, um den Arbeitsablauf im Auge zu behalten: eine bestimmte Menge
interaktive Aufgaben mit kurzen Laufzeiten (und damit häufiger Freigabe).
CPU) und mehrere lang laufende Aufgaben, die die CPU während ihrer gesamten Arbeitszeit beanspruchen
Bei solchen Aufgaben kommt es nicht auf die Reaktionszeit an. Und so können Sie Ihren ersten Versuch wagen
Implementieren Sie den MLFQ-Algorithmus mit den folgenden Regeln:

Regel 3: Wenn eine Aufgabe das System betritt, wird sie in die höchste Warteschlange gestellt
Priorität.
Regel4a: Wenn eine Aufgabe das gesamte ihr zugeteilte Zeitfenster nutzt, dann ist sie
Die Priorität wird reduziert.
Regel 4b: Wenn eine Task die CPU freigibt, bevor ihr Zeitfenster abläuft, dann wird sie ausgeführt
bleibt bei gleicher Priorität.

Beispiel 1: Einzelne Aufgabe mit langer Laufzeit

Wie in diesem Beispiel zu sehen ist, wird die Zulassungsaufgabe mit der höchsten gesetzt
Priorität. Nach einem Zeitfenster von 10 ms wird der Prozess in der Priorität herabgestuft
Planer. Nach dem nächsten Zeitfenster wird die Aufgabe endgültig herabgestuft
niedrigste Priorität im System, wo es verbleibt.

Beispiel 2: Eine kurze Aufgabe geliefert

Sehen wir uns nun ein Beispiel dafür an, wie MLFQ versuchen wird, sich SJF zu nähern. Darin
Beispiel zwei Aufgaben: A, bei der es sich um eine ständig laufende Aufgabe handelt
Belegung von CPU und B, was eine kurze interaktive Aufgabe ist. Vermuten
dass A bereits einige Zeit gearbeitet hatte, als Aufgabe B eintraf.

Diese Grafik zeigt die Ergebnisse des Szenarios. Aufgabe A, wie jede Aufgabe,
Die CPU-Auslastung war ganz unten. Aufgabe B wird zum Zeitpunkt T=100 eintreffen und dies tun
in die Warteschlange mit der höchsten Priorität gestellt. Da seine Betriebszeit also kurz ist
Der Vorgang wird abgeschlossen, bevor die letzte Warteschlange erreicht wird.

Anhand dieses Beispiels sollte das Hauptziel des Algorithmus verstanden werden: Da der Algorithmus dies nicht tut
Weiß, ob eine Aufgabe lang oder kurz ist, dann geht er zunächst davon aus, dass die Aufgabe
kurz und gibt ihm die höchste Priorität. Wenn das eine wirklich kurze Aufgabe ist, dann
Es wird schnell erledigt sein, andernfalls wird es, wenn es sich um eine lange Aufgabe handelt, langsam voranschreiten
Priorität nach unten und wird bald beweisen, dass sie tatsächlich eine lange Aufgabe ist, die das nicht tut
erfordert eine Antwort.

Beispiel 3: Was ist mit I/O?

Schauen wir uns nun ein I/O-Beispiel an. Wie in Regel 4b angegeben,
wenn ein Prozess den Prozessor freigibt, ohne seine gesamte Prozessorzeit zu nutzen,
dann bleibt es auf der gleichen Prioritätsstufe. Der Zweck dieser Regel ist recht einfach
- wenn der interaktive Job viele I/O-Vorgänge ausführt, beispielsweise wartet
Durch Drücken der Benutzertaste oder der Maus wird durch eine solche Aufgabe der Prozessor entlastet
vor dem vorgesehenen Fenster. Wir möchten die Priorität einer solchen Aufgabe nicht herabsetzen,
und somit bleibt es auf dem gleichen Niveau.

Dieses Beispiel zeigt, wie der Algorithmus mit solchen Prozessen funktioniert – interaktiver Job B, der vor der Ausführung nur 1 ms lang CPU benötigt
I/O-Prozess und Job A mit langer Laufzeit, der die gesamte Zeit mit der CPU verbringt.
MLFQ behält Prozess B die höchste Priorität, da er fortgesetzt wird
Geben Sie die CPU frei. Wenn B eine interaktive Aufgabe ist, hat der Algorithmus die Aufgabe erfüllt
Ihr Ziel ist es, interaktive Aufgaben schnell auszuführen.

Probleme mit dem aktuellen MLFQ-Algorithmus

In den vorherigen Beispielen haben wir eine Basisversion von MLFQ erstellt. Und es scheint, dass er
erledigt seine Arbeit gut und ehrlich und verteilt die CPU-Zeit fair zwischen den Benutzern
lange Aufgaben und ermöglicht kurze oder großvolumige Aufgaben
Arbeiten Sie schnell an E/A. Leider enthält dieser Ansatz mehrere
ernsthafte Probleme.
Erstens, das Problem des Hungers: Wenn das System viele interaktive hat
Aufgaben, dann verbrauchen sie die gesamte Prozessorzeit und somit für längere Zeit keine einzige
Die Aufgabe kann nicht ausgeführt werden (sie hungern).

Zweitens, könnten kluge Benutzer ihre Programme so schreiben
täuschen Sie den Planer. Täuschung liegt darin, etwas zu erzwingen
Der Scheduler gibt dem Prozess mehr CPU-Zeit. Algorithmus das
Wie oben beschrieben ist es ziemlich anfällig für ähnliche Angriffe: praktisch vor Ablauf des Zeitfensters
Wenn es beendet ist, müssen Sie einen E/A-Vorgang ausführen (für einige, egal welche Datei).
und somit die CPU entlasten. Ein solches Verhalten ermöglicht es Ihnen, im Gleichen zu bleiben
die Warteschlange selbst und erhalten wiederum einen größeren Prozentsatz der CPU-Zeit. Wenn Sie tun
Dies ist korrekt (führen Sie beispielsweise 99 % der Fensterzeit aus, bevor Sie die CPU freigeben).
Eine solche Aufgabe kann den Prozessor einfach monopolisieren.

Schließlich kann ein Programm sein Verhalten im Laufe der Zeit ändern. Diese Aufgaben
welche CPU verwendet wird, kann interaktiv werden. In unserem Beispiel ähnlich
Aufgaben erhalten vom Planer nicht die Behandlung, die sie verdienen, wie andere es tun würden
(erste) interaktive Aufgaben.

Frage an das Publikum: Welche Angriffe auf den Terminplaner könnten in der modernen Welt durchgeführt werden?

Versuch 2: Priorität erhöhen

Versuchen wir, die Regeln zu ändern und zu sehen, ob wir Probleme damit vermeiden können
Fasten. Was können wir tun, um dies sicherzustellen?
CPU-Aufgaben bekommen ihre Zeit (wenn auch nicht lange).
Als einfache Lösung für das Problem können Sie regelmäßig Vorschläge machen
Erhöhen Sie die Priorität aller dieser Aufgaben im System. Es gibt viele Wege
Um dies zu erreichen, versuchen wir als Beispiel etwas Einfaches umzusetzen: Übersetzen
Alle Aufgaben erhalten sofort die höchste Priorität, daher die neue Regel:

Regel5: Verschieben Sie nach einer bestimmten Zeit S alle Aufgaben im System in die höchste Warteschlange.

Unsere neue Regel löst gleich zwei Probleme. Erstens die Prozesse
verhungern garantiert nicht: Aufgaben mit höchster Priorität werden aufgeteilt
CPU-Zeit entsprechend dem RR-Algorithmus und damit alle Prozesse erhalten
CPU-Zeit. Zweitens, wenn ein Prozess verwendet wird, der zuvor verwendet wurde
nur der Prozessor wird interaktiv, er bleibt in der Warteschlange mit dem höchsten Wert
Priorität nach Erhalt einer einmaligen Erhöhung der Priorität auf die höchste Priorität.
Schauen wir uns ein Beispiel an. Betrachten Sie in diesem Szenario einen Prozess mit

CPU und zwei interaktive, kurze Prozesse. Auf der linken Seite der Abbildung wird das Verhalten ohne Prioritätserhöhung dargestellt. Daher beginnt die lang laufende Aufgabe zu verhungern, nachdem zwei interaktive Aufgaben im System angekommen sind. In der Abbildung rechts wird alle 50 ms eine Prioritätserhöhung durchgeführt, sodass alle Prozesse garantiert CPU-Zeit erhalten und regelmäßig gestartet werden. Als Beispiel dienen hier 50ms, in der Realität liegt diese Zahl etwas höher.
Offensichtlich führt die Addition der periodischen Anstiegszeit S zu
eine logische Frage: Welcher Wert sollte eingestellt werden? Einer der Geehrten
Der Systemingenieur John Ousterhout nannte solche Größen in Systemen Voo-Doo
konstant, da sie in gewisser Weise schwarze Magie zur Korrektur benötigten
ausstellen. Und leider hat S so einen Duft. Wenn Sie den Wert auch festlegen
groß – lange Aufgaben beginnen zu verhungern. Und wenn Sie den Wert zu niedrig einstellen,
Interaktive Aufgaben erhalten nicht die richtige CPU-Zeit.

Versuch 3: Bessere Buchhaltung

Jetzt müssen wir ein weiteres Problem lösen: wie es nicht geht
zulassen, dass sich unser Planer täuschen lässt? Die Schuldigen an dieser Möglichkeit sind:
Regeln 4a, 4b, die es einem Job ermöglichen, die Priorität zu behalten, wodurch der Prozessor entlastet wird
bevor die vorgegebene Zeit abgelaufen ist. Wie gehe ich damit um?
Die Lösung in diesem Fall kann in einer besseren Abrechnung der CPU-Zeit für jeden betrachtet werden
MLFQ-Ebene. Anstatt die Zeit zu vergessen, die das Programm verbraucht hat
Für den vorgesehenen Zeitraum sollten die Daten des Prozessors berücksichtigt und gespeichert werden. Nachdem
Wenn der Prozess seine zugewiesene Zeit aufgebraucht hat, sollte er auf den nächsten herabgestuft werden
Prioritätsstufe. Jetzt kommt es nicht mehr darauf an, wie der Prozess seine Zeit nutzen wird – wie
ständiges Rechnen auf dem Prozessor oder als Anzahl von Aufrufen. Auf diese Weise,
Regel 4 sollte wie folgt umgeschrieben werden:

Regel4: Nachdem eine Aufgabe ihre zugewiesene Zeit in der aktuellen Warteschlange aufgebraucht hat (unabhängig davon, wie oft sie die CPU freigegeben hat), wird die Priorität dieser Aufgabe verringert (sie wird in der Warteschlange nach unten verschoben).

Schauen wir uns ein Beispiel an:
»

Die Abbildung zeigt, was passiert, wenn Sie versuchen, den Planer zu täuschen
Wenn es mit den vorherigen Regeln 4a, 4b wäre, würde das Ergebnis auf der linken Seite erhalten. Frohes neues
Die Regel ist das Ergebnis auf der rechten Seite. Vor dem Schutz könnte jeder Prozess E/A vor Abschluss aufrufen und
dominieren somit die CPU, nachdem der Schutz aktiviert wurde, unabhängig vom Verhalten
I/O, er wird immer noch in der Warteschlange nach unten verschoben und kann daher nicht unehrlich sein
CPU-Ressourcen übernehmen.

Verbesserung des MLFQ und anderer Probleme

Mit den oben genannten Verbesserungen gehen neue Probleme einher: eines der Hauptprobleme
Fragen: Wie parametriert man einen solchen Scheduler? Diese. Wie viel sollte es sein
Warteschlangen? Wie groß sollte das Programmfenster innerhalb der Warteschlange sein? Wie
Die Programmpriorität sollte häufig erhöht werden, um Hungersnöte zu vermeiden
Berücksichtigen Sie die Änderung des Programmverhaltens? Auf diese Fragen gibt es keine einfache Antwort
Antwort und nur Experimente mit Lasten und anschließender Konfiguration
Der Planer kann zu einem zufriedenstellenden Gleichgewicht führen.

Beispielsweise können Sie bei den meisten MLFQ-Implementierungen unterschiedliche Zuweisungen vornehmen
Zeitintervalle für verschiedene Warteschlangen. Normalerweise Warteschlangen mit hoher Priorität
Es sind kurze Intervalle vorgeschrieben. Diese Warteschlangen bestehen aus interaktiven Aufgaben,
Das Umschalten ist sehr empfindlich und sollte höchstens 10 Minuten dauern
MS. Im Gegensatz dazu bestehen Warteschlangen mit niedriger Priorität aus lang laufenden Aufgaben, die verwendet werden
CPU. Und in diesem Fall passen lange Zeitintervalle sehr gut (100ms).

In diesem Beispiel gibt es zwei Aufgaben, die in der Warteschlange 2 mit hoher Priorität ausgeführt wurden
ms, aufgeteilt in 10-ms-Fenster. 40 ms in der mittleren Warteschlange (20 ms-Fenster) und in der niedrigen Priorität
Das Zeitfenster für die Warteschlange wurde auf 40 ms erhöht, in dem die Aufgaben ihre Arbeit erledigten.

Die Solaris OS-Implementierung von MLFQ ist eine Klasse von Time-Sharing-Schedulern.
Der Planer stellt eine Reihe von Tabellen bereit, die genau so definieren, wie es sein sollte
Die Priorität des Prozesses ändert sich im Laufe seines Lebens, was sollte die Größe sein
zugewiesenes Fenster und wie oft Sie die Aufgabenprioritäten erhöhen müssen. Administrator
Systeme können mit dieser Tabelle interagieren und ein Verhalten des Schedulers bewirken
anders. Standardmäßig verfügt diese Tabelle über 60 Warteschlangen, die schrittweise erhöht werden
Fenstergröße von 20 ms (hohe Priorität) bis zu mehreren hundert ms (niedrige Priorität) und
auch mit einem Boost aller Aufgaben einmal pro Sekunde.

Andere MLFQ-Planer verwenden keine Tabelle oder andere spezifische Elemente
Regeln, die in dieser Vorlesung beschrieben werden, im Gegenteil, sie berechnen Prioritäten anhand
mathematische Formeln. Beispielsweise verwendet der FreeBSD-Scheduler eine Formel für
Berechnen Sie die aktuelle Priorität einer Aufgabe basierend auf der Dauer des Prozesses
verwendete CPU. Darüber hinaus nimmt die CPU-Auslastung mit der Zeit ab usw
Daher erfolgt die Erhöhung der Priorität etwas anders als oben beschrieben. Ist das so
sogenannte Zerfallsalgorithmen. Seit Version 7.1 verwendet FreeBSD den ULE-Scheduler.

Schließlich verfügen viele Planer über weitere Funktionen. Zum Beispiel einige
Scheduler reservieren die höchsten Ebenen für den Betrieb des Betriebssystems und somit
Somit kann kein Benutzerprozess die höchste Priorität erhalten
System. Bei einigen Systemen können Sie Ratschläge geben, um zu helfen
Der Planer kann Prioritäten richtig setzen. Zum Beispiel mit dem Befehl schön
Sie können die Priorität einer Aufgabe erhöhen oder verringern und somit erhöhen oder
Reduzieren Sie die Wahrscheinlichkeit, dass das Programm CPU-Zeit beansprucht.

MLFQ: Zusammenfassung

Wir haben einen Planungsansatz namens MLFQ beschrieben. Sein Name
im Funktionsprinzip eingeschlossen - es verfügt über mehrere Warteschlangen und nutzt Feedback
um die Aufgabenpriorität zu bestimmen.
Die endgültige Form der Regeln wird wie folgt aussehen:

Regel1: Wenn Priorität (A) > Priorität (B), wird Aufgabe A gestartet (B nicht).
Regel2: Wenn Priorität(A) = Priorität(B), werden A&B mit RR gestartet
Regel3: Wenn eine Aufgabe das System betritt, wird sie in die Warteschlange mit der höchsten Priorität gestellt.
Regel4: Nachdem eine Aufgabe ihre zugewiesene Zeit in der aktuellen Warteschlange aufgebraucht hat (unabhängig davon, wie oft sie die CPU freigegeben hat), wird die Priorität dieser Aufgabe verringert (sie wird in der Warteschlange nach unten verschoben).
Regel5: Verschieben Sie nach einer bestimmten Zeit S alle Aufgaben im System in die höchste Warteschlange.

MLFQ ist aus folgendem Grund interessant – anstatt Kenntnisse darüber zu erfordern
Der Algorithmus untersucht die Art der Aufgabe im Voraus, untersucht das vergangene Verhalten der Aufgabe und stellt sie ein
entsprechend Prioritäten setzen. Daher versucht er, auf zwei Stühlen gleichzeitig zu sitzen – um Produktivität für kleine Aufgaben (SJF, STCF) zu erreichen und ehrlich gesagt lange zu laufen,
CPU-belastende Jobs. Daher sind viele Systeme, einschließlich BSD und seine Derivate,
Solaris, Windows und Mac verwenden eine Art Algorithmus als Scheduler
MLFQ als Basis.

Zusätzliche Materialien:

Source: habr.com

Betriebssysteme: Drei einfache Teile. Teil 5: Planung: Mehrstufige Feedback-Warteschlange (Übersetzung)