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

Planung: Multi-Level Feedback Queue

In dieser Vorlesung werden wir die Herausforderungen der Entwicklung eines der bekanntesten Ansätze zur
Planung besprechen, der als Multi-Level Feedback Queue (MLFQ) bezeichnet wird. Der MLFQ-Planer wurde erstmals 1962 von Fernando J. Corbató im System beschrieben, das
Compatible Time-Sharing System (CTSS). Diese Arbeiten (einschließlich der späteren Arbeiten an
Multics) wurden später für den Turing Award nominiert. Der Scheduler wurde
anschließend verbessert und nahm eine Form an, die man bereits in
einigen modernen Systemen finden kann.

Der MLFQ-Algorithmus versucht, zwei grundlegende überlappend Probleme zu lösen.
Erstens, versucht er, die Durchlaufzeit zu optimieren, die, wie wir in der vorherigen Vorlesung behandelt haben, durch das Starten der kürzesten Aufgaben zu Beginn der Warteschlange optimiert wird. Allerdings weiß das OS nicht, wie lange ein bestimmter Prozess laufen wird, was
das erforderliche Wissen für die Funktionsweise der SJF- und STCF-Algorithmen ist.
Zweitens , versucht der MLFQdas System für die Benutzer (zum Beispiel für diejenigen, die vor dem Bildschirm sitzen und
auf den Abschluss einer Aufgabe warten) reaktionsschnell zu gestalten und somit die
Antwortzeit zu minimieren. Leider reduzieren Algorithmen wie RR die Antwortzeit, haben aber extrem
negative Auswirkungen auf die Durchlaufzeit-Metrik. Daraus ergibt sich unser Problem: Wie entwerfen
wir einen Scheduler, der unseren Anforderungen entspricht und dabei nichts über
ein Scheduler, der unseren Anforderungen gerecht wird und gleichzeitig nichts über
Was ist der allgemeine Charakter des Prozesses? Wie kann ein Planer die Eigenschaften der Aufgaben,
die er ausführt, untersuchen und dadurch bessere Entscheidungen für die Planung treffen?

Das Problem im Kern: Wie plant man die Aufgabenzuweisung ohne perfekte Kenntnisse?
Wie entwickelt man einen Planer, der gleichzeitig die Reaktionszeit
für interaktive Aufgaben minimiert und zugleich die Bearbeitungszeit ohne vorhergehende
Kenntnis der Ausführungszeit der Aufgabe reduziert?

Hinweis: Lernen aus früheren Ereignissen

Die MLFQ-Warteschlange ist ein ausgezeichnetes Beispiel für ein System, das auf
vergangenen Ereignissen lernt, um die Zukunft zu prognostizieren. Solche Ansätze sind häufig
in Betriebssystemen (und vielen anderen Bereichen der Informatik anzutreffen, einschließlich der Vorhersagezweige
in Hardware und Caching-Algorithmen). Solche Vorgehensweisen
funktionieren, wenn Aufgaben Verhaltensphasen haben und daher vorhersehbar sind.
Allerdings sollte man mit dieser Technik vorsichtig sein, da Vorhersagen sehr schnell
falsch sein können und das System zu schlechteren Entscheidungen führen als
es ohne jegliches Wissen der Fall wäre.

MLFQ: Grundregeln

Betrachten wir die grundlegenden Regeln des MLFQ-Algorithmus. Obwohl es mehrere Implementierungen dieses Algorithmus gibt, sind die grundlegenden Ansätze ähnlich.
In der Implementierung, die wir betrachten werden, gibt es im MLFQ mehrere
getrennte Warteschlangen, von denen jede eine andere Priorität hat. Zu jedem Zeitpunkt
befindet sich eine aufrufbereite Aufgabe in einer Warteschlange. MLFQ verwendet Prioritäten,
um zu bestimmen, welche Aufgabe zur Ausführung kommt, d.h. die Aufgabe mit höherer
Priorität (die Aufgabe aus der Warteschlange mit der höchsten Priorität) wird als erste
ausgeführt.
Es ist unbestreitbar, dass in einer bestimmten Warteschlange mehr als eine Aufgabe sein kann, sodass
diese den gleichen Prioritätsgrad haben. In diesem Fall wird ein RR-Mechanismus verwendet,
um die Ausführung unter diesen Aufgaben zu planen.
Somit gelangen wir zu zwei grundlegenden Regeln 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.
Aus dem oben Genannten ergibt sich, dass die Schlüsselfaktoren für die Planung von MLFQ

die Prioritäten sind. Anstatt jeder Aufgabe eine feste Priorität zuzuweisen,
Prioritäten ist. Anstatt jedem eine feste Priorität zuzuweisen,
Im Rahmen der Aufgabe passt MLFQ die Priorität je nach beobachtetem Verhalten an.
Wenn zum Beispiel eine Aufgabe ständig CPU-Ressourcen zur Eingabe von der Tastatur anfordert,
wird MLFQ die Priorität des Prozesses hoch halten, da dies dem entspricht, wie
ein interaktiver Prozess funktionieren sollte. Im Gegensatz dazu, wenn eine Aufgabe konstant und
intensiv CPU für längere Zeit nutzt, wird MLFQ dessen Priorität verringern.
Auf diese Weise wird MLFQ das Verhalten der Prozesse während ihrer Ausführung
studieren und diese Beobachtungen nutzen.
Lassen Sie uns ein Beispiel skizzieren, wie die Warteschlangen zu einem bestimmten Zeitpunkt
aussehen könnten, und dann würde es etwa so aussehen:

In diesem Diagramm befinden sich die Prozesse A und B in der Warteschlange mit der höchsten Priorität. Der Prozess
C befindet sich irgendwo in der Mitte, während der Prozess D ganz hinten in der Warteschlange steht. Gemäß der oben
geschilderten Beschreibung des MLFQ-Algorithmus wird der Scheduler nur die Aufgaben mit der höchsten
Priorität gemäß RR ausführen, während die Aufgaben C und D inaktiv bleiben.
Ein statisches Snapshot gibt natürlich nicht das volle Bild darüber, wie MLFQ funktioniert.
Es ist wichtig zu verstehen, wie sich das Bild im Laufe der Zeit verändert.

Versuch 1: Wie man die Priorität ändert

An diesem Punkt muss entschieden werden, wie MLFQ die Priorität der Aufgaben
ändert (und damit die Position der Aufgabe in der Warteschlange) im Verlauf ihres Lebenszyklus. Um
dies zu erreichen, muss der Arbeitsablauf im Kopf behalten werden: eine bestimmte Anzahl
interaktiver Aufgaben mit kurzer Laufzeit (und damit häufige Freigabe der
CPU) und mehrere langanhaltende Aufgaben, die die CPU während ihrer gesamten Arbeitszeit nutzen, wobei
die Reaktionszeit für solche Aufgaben unwichtig ist. So kann ein erster Versuch gemacht werden,
den MLFQ-Algorithmus mit den folgenden Regeln zu implementieren:

Regel 3: Wenn eine Aufgabe ins System kommt, wird sie in die Warteschlange mit der höchsten
Priorität eingestellt.
Regel 4a: Wenn eine Aufgabe das ihr zugewiesene Zeitfenster vollständig ausnutzt, wird ihre
Priorität gesenkt.
Regel 4b: Wenn eine Aufgabe die CPU vor Ablauf ihres Zeitfensters freigibt, bleibt sie
mit der gleichen Priorität.

Beispiel 1: Einzelne langlaufende Aufgabe

Wie in diesem Beispiel zu sehen ist, wird die Aufgabe bei ihrem Eintreffen mit der höchsten
Priorität gesetzt. Nach dem Zeitfenster von 10 ms wird die Priorität der Aufgabe durch
den Scheduler gesenkt. Nach dem nächsten Zeitfenster wird die Aufgabe schließlich herabgestuft bis
niedriger Priorität im System, wo sie bleibt.

Beispiel 2: Eine kurze Aufgabe wurde angezeigt.

Lassen Sie uns nun ein Beispiel ansehen, wie MLFQ versucht, SJF zu approximieren. In diesem
Beispiel gibt es zwei Aufgaben: A, die eine langlaufende Aufgabe ist und ständig
CPU verwendet, und B, die eine kurze interaktive Aufgabe darstellt. Nehmen wir an,
dass A bereits einige Zeit gearbeitet hat, als Aufgabe B eintrifft.

In diesem Diagramm sind die Ergebnisse des Szenarios sichtbar. Aufgabe A, wie jede andere
Aufgabe, die CPU verwendet, befindet sich ganz unten. Aufgabe B wird zu einem Zeitpunkt T=100
eingereicht und erhält den höchsten Prioritätsplatz in der Warteschlange. Da ihre Ausführungszeit kurz
ist, wird sie abgeschlossen, bevor sie die letzte Warteschlange erreicht.

Aus diesem Beispiel sollte die Hauptzielsetzung des Algorithmus deutlich werden: Da der Algorithmus nicht
weiss, ob eine Aufgabe lang oder kurz ist, geht er zunächst davon aus, dass die Aufgabe
kurz ist und gibt ihr die höchste Priorität. Wenn es sich tatsächlich um eine kurze Aufgabe handelt,
wird sie schnell ausgeführt, andernfalls, wenn es sich um eine lange Aufgabe handelt, wird sie langsam
in der Priorität nach unten wandern und bald beweisen, dass es sich um eine tatsächlich lange Aufgabe handelt, die nicht
erfordert eine Antwort.

Beispiel 3: Was ist mit der Ein- und Ausgabe?

Schauen wir uns nun ein Beispiel zur Ein- und Ausgabe an. Wie in Regel 4b erwähnt,
wenn ein Prozess die CPU freigibt, ohne ihre gesamte Zeit zu nutzen,
bleibt er auf der gleichen Prioritätsstufe. Die Absicht dieser Regel ist ziemlich einfach,
wenn eine interaktive Aufgabe viele Ein- und Ausgabeoperationen ausführt, indem sie beispielsweise
auf Tasteneingaben oder Mausklicks des Benutzers wartet, gibt diese Aufgabe die CPU
früher als zugewiesen frei. Wir möchten solch eine Aufgabe nicht herabstufen,
und daher bleibt sie auf der gleichen Stufe.

Dieses Beispiel zeigt, wie der Algorithmus mit solchen Prozessen arbeitet – interaktive Aufgabe B, die nur 1 ms CPU benötigt, bevor sie
einen Ein- und Ausgabeprozess ausführt, und die lang laufende Aufgabe A, die die gesamte CPU-Zeit nutzt.
MLFQ hält Prozess B auf der höchsten Prioritätsstufe, da er die CPU ständig freigibt.
Wenn B eine interaktive Aufgabe ist, hat der Algorithmus in diesem Fall sein Ziel erreicht,
interaktive Aufgaben schnell zu starten.

Probleme mit dem aktuellen MLFQ-Algorithmus

In den vorherigen Beispielen haben wir eine grundlegende Version von MLFQ erstellt. Es scheint, dass sie
gut funktioniert und die Prozessorzeit fair zwischen
langwierigen Aufgaben verteilt, während sie kürzeren Aufgaben oder solchen, die intensiv
auf Eingaben-Ausgaben zugreifen, schnell die Möglichkeit gibt, verarbeitet zu werden. Leider hat dieser Ansatz einige
ernsthafte Probleme.
Erstens, das Hungerproblem: Wenn es im System viele interaktive
Aufgaben gibt, verbrauchen diese die gesamte Prozessorzeit, sodass keine langwierige
Aufgabe die Möglichkeit erhält, ausgeführt zu werden (sie verhungern).

, versucht der MLFQ, versierte Benutzer könnten ihre Programme so schreiben, dass sie
den Scheduler überlisten. Der Trick besteht darin, etwas zu tun, das den
Scheduler dazu bringt, der Aufgabe mehr Prozessorzeit zuzuweisen. Der oben beschriebene
Algorithmus ist durchaus anfällig für solche Angriffe: Bevor das Zeitfenster praktisch
abgelaufen ist, muss eine Eingabe-Ausgabe-Operation (bei einer beliebigen, egal welcher Datei) durchgeführt werden,
um somit die CPU freizugeben. Ein solches Verhalten erlaubt es, im gleichen
um die CPU-Zeit in der Warteschlange zu maximieren. Wenn dies richtig durchgeführt wird,
zum Beispiel, indem sie 99% der Zeit im Vordergrund läuft, bevor die CPU freigegeben wird,
kann eine solche Aufgabe einfach die gesamte Prozessorzeit monopolisiert.

Schließlich kann ein Programm im Laufe der Zeit sein Verhalten ändern. Aufgaben,
die zuerst CPU-intensive waren, könnten interaktiv werden. In unserem Beispiel
würden solche Aufgaben nicht die dringend benötigte Aufmerksamkeit vom Scheduler erhalten,
weil sie anderen (ursprünglichen) interaktiven Aufgaben vorgezogen werden würden.

Frage an die Runde: Welche Angriffe auf den Scheduler könnten in der heutigen Welt ausgeführt werden?

Versuch 2: Prioritätserhöhung

Versuchen wir, die Regeln zu ändern und zu sehen, ob wir das Problem der
Hungersnot umgehen können. Was könnten wir tun, um sicherzustellen, dass CPU-gebundene
Aufgaben ihre Zeit erhalten (auch wenn nicht lange)?
Als einfache Lösung für dieses Problem könnte man vorschlagen,
regelmäßig die Priorität aller solchen Aufgaben im System zu erhöhen. Es gibt viele Möglichkeiten,
dies zu erreichen, lassen Sie uns ein einfaches Beispiel umsetzen: eine Übersetzung.
Alle Aufgaben sofort in höchste Priorität setzen, daher die neue Regel:

Regel5: Nach einer gewissen Zeit S alle Aufgaben im System in die höchste Warteschlange versetzen.

Unsere neue Regel löst sofort zwei Probleme. Erstens, die Prozesse
sind garantiert nicht unterversorgt: Aufgaben in der höchsten Warteschlange erhalten
die Prozesszeit gemäß dem RR-Algorithmus und dadurch erhält jeder Prozess
Prozesszeit. Zweitens, wenn ein Prozess, der zuvor nur CPU-Ressourcen genutzt hat, interaktiv wird,
bleibt er in der Warteschlange mit der höchsten Priorität, nachdem er einmal die Priorität auf die höchste
erhoben hat.
Betrachten wir ein Beispiel. In diesem Szenario betrachten wir einen Prozess, der verwendet

CPU und zwei interaktive, kurze Prozesse. Auf der linken Seite zeigt die Abbildung das Verhalten ohne Priorisierungserhöhung, wodurch eine langwierige Aufgabe hungert, nachdem zwei interaktive Aufgaben ins System eintreten. Auf der rechten Seite wird alle 50 ms eine Prioritätserhöhung durchgeführt, sodass alle Prozesse garantiert CPU-Zeit erhalten und regelmäßig ausgeführt werden. 50 ms dienen hier als Beispiel; in der Realität ist diese Zahl etwas höher.
Es ist offensichtlich, dass die Hinzufügung von periodischer Erhöhungszeit S zu
der zwangsläufigen Frage führt: Welcher Wert sollte festgelegt werden? Einer der angesehenen
Systemingenieure, John Ousterhout, nannte derartige Größen in Systemen voo-doo
Konstanten, da sie irgendwie schwarze Magie zur korrekten
Einstellung erforderten. Und leider hat S einen ähnlichen Geschmack. Wenn der Wert zu hoch eingestellt wird,
beginnen langwierige Aufgaben zu hungern. Wenn der Wert jedoch zu niedrig eingestellt wird,
erhalten die interaktiven Aufgaben nicht die erforderliche CPU-Zeit.

Versuch 3: Bessere Berücksichtigung

Jetzt haben wir ein weiteres Problem, das gelöst werden muss: Wie verhindern wir,
dass unser Scheduler ausgetrickst wird? Verantwortlich für diese Möglichkeit sind
die Regeln 4a und 4b, die es einer Aufgabe erlauben, ihre Priorität zu behalten und den Prozessor
bis zum Ende der zugewiesenen Zeit zu entlasten. Wie gehen wir damit um?
Eine Lösung in diesem Fall könnte die bessere Zeiterfassung der CPU auf jedem
MLFQ-Level sein. Anstatt die Zeit zu ignorieren, die ein Programm während eines
bestimmten Zeitraums für die CPU verwendet hat, sollte diese berechnet und aufgezeichnet werden. Sobald
der Prozess seine zugewiesene Zeit aufgebraucht hat, sollte er auf die nächste
Prioritätsstufe herabgestuft werden. Es spielt jetzt keine Rolle, wie der Prozess seine Zeit nutzt – ob
er ständig auf der CPU rechnet oder eine Vielzahl von Aufrufen macht. Daher sollte
Regel 4 wie folgt umgeschrieben werden:

Rule4: Sobald eine Aufgabe ihre ihr zugewiesene Zeit in der aktuellen Warteschlange aufgebraucht hat (unabhängig davon, wie oft sie die CPU freigegeben hat), wird die Priorität dieser Aufgabe herabgestuft (sie bewegt sich nach unten in der Warteschlange).

Schauen wir uns ein Beispiel an:
»

Die Abbildung zeigt, was passiert, wenn man versucht, den Scheduler auszutricksen, als
wäre es mit den vorherigen Regeln 4a, 4b auf der linken Seite. Mit der neuen
Regel – das Ergebnis auf der rechten Seite. Vor der Aktivierung des Schutzes konnte jeder Prozess I/O bis zum Abschluss anfordern und
somit die CPU dominieren. Nach der Aktivierung des Schutzes, unabhängig vom Verhalten
von I/O, wird er dennoch in den Warteschlangen nach unten rutschen und somit nicht unrechtmäßig
auf die CPU-Ressourcen zugreifen können.

Verbesserung von MLFQ und anderen Problemen

Mit den oben genannten Verbesserungen tauchen neue Probleme auf: Eine der Hauptfragen ist, wie man einen solchen Scheduler parametrieren sollte. Das heißt, wie viele
Warteschlangen sollten vorhanden sein? Wie groß sollte das Zeitfenster für die Programmausführung innerhalb der Warteschlange sein? Wie
oft sollte die Priorität eines Programms erhöht werden, um Hunger zu vermeiden und
Verhaltensänderungen des Programms zu berücksichtigen? Auf diese Fragen gibt es keine einfache
Antwort und nur Experimente mit Lasten sowie anschließende Konfigurationen
des Schedulers können zu einem gewissen befriedigenden Gleichgewicht führen.
Zum Beispiel erlauben die meisten Implementierungen von MLFQ, verschiedene

beispielsweise erlauben die meisten MLFQ-Implementierungen die Zuordnung unterschiedlicher
Zeitintervalle für verschiedene Warteschlangen. Hochpriorisierte Warteschlangen erhalten in der Regel
kurze Intervalle. Diese Warteschlangen bestehen aus interaktiven Aufgaben,
zwischen denen das Umschalten recht sensibel ist und weniger als 10
ms in Anspruch nehmen sollte. Im Gegensatz dazu bestehen niedrigpriorisierte Warteschlangen aus langen Aufgaben, die CPU
nutzen. Daher sind längere Zeitintervalle hier sehr geeignet (100 ms).

In diesem Beispiel gibt es 2 Aufgaben, die in der Hochprioritätswarteschlange 20
ms gearbeitet haben, aufgeteilt in Fenster von 10 ms. 40 ms in der mittleren Warteschlange (Fenster von 20 ms) und in der niedrigpriorisierten
Warteschlange wurde das Zeitfenster auf 40 ms gesetzt, wo die Aufgaben ihre Arbeit abgeschlossen haben.

Die Implementierung von MLFQ im Solaris-Betriebssystem ist eine Art von Planer, der zeitlich aufteilt.
Der Planer stellt eine Reihe von Tabellen bereit, die genau definieren, wie sich
die Priorität eines Prozesses im Laufe seiner Lebensdauer ändern sollte, wie groß das
zugewiesene Fenster sein sollte und wie oft die Prioritäten der Aufgabe erhöht werden müssen. Der Administrator
des Systems kann mit dieser Tabelle interagieren und den Planer anweisen, sich entsprechend zu verhalten.
anders. Standardmäßig enthält diese Tabelle 60 Warteschlangen mit allmählicher Erhöhung
der Fenstergröße von 20 ms (hohe Priorität) bis zu mehreren hundert ms (geringe Priorität) und
einem Boost aller Aufgaben einmal pro Sekunde.

Andere MLFQ-Planer verwenden keine Tabelle oder spezifischen
Regeln, die in dieser Vorlesung beschrieben sind; stattdessen berechnen sie Prioritäten mit
mathematischen Formeln. So verwendet beispielsweise der Planer in FreeBSD eine Formel zur
Berechnung der aktuellen Priorität einer Aufgabe, basierend darauf, wie viel Prozess
CPU-Ressourcen verbraucht hat. Darüber hinaus verschlechtert sich die CPU-Auslastung
im Laufe der Zeit, sodass die Erhöhung der Priorität etwas anders erfolgt als oben beschrieben. Dies sind die
sogenannten Decay-Algorithmen. Seit Version 7.1 verwendet FreeBSD den ULE-Planer.

Schließlich haben viele Planer andere Eigenschaften. Zum Beispiel reservieren einige
Planer höhere Prioritäten für das Betriebssystem, sodass kein Benutzerprozess die höchste
Priorität im System erreichen kann. Einige Systeme erlauben es, Hinweise zu geben, um zu helfen
Systeme. Einige Systeme bieten Ratschläge, um zu helfen
Es ist wichtig, dass der Scheduler die Prioritäten korrekt festlegt. Zum Beispiel kann mit dem Befehl nice
die Priorität einer Aufgabe erhöht oder verringert werden, um so die Chancen des Programms auf CPU-Zeit zu verbessern oder zu verschlechtern.
die Chancen eines Programms auf CPU-Zeit zu verringern.

MLFQ: Zusammenfassung

Wir haben einen Planungsansatz beschrieben, der MLFQ genannt wird. Der Name basiert auf dem Funktionsprinzip — er verwendet mehrere Warteschlangen und nutzt Rückmeldungen
um die Priorität einer Aufgabe festzulegen.
Die finale Regel sieht wie folgt aus:
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.Regel 3
: Wenn eine Aufgabe in das System kommt, wird sie in die Warteschlange mit der höchsten Priorität eingeordnet.MLFQ ist aus folgendem Grund interessant — anstatt dass er im Voraus Kenntnisse über die Natur der Aufgabe erfordert, lernt der Algorithmus aus dem vergangenen Verhalten der Aufgabe und passt die
Rule4: Sobald eine Aufgabe ihre ihr zugewiesene Zeit in der aktuellen Warteschlange aufgebraucht hat (unabhängig davon, wie oft sie die CPU freigegeben hat), wird die Priorität dieser Aufgabe herabgestuft (sie bewegt sich nach unten in der Warteschlange).
Regel5: Nach einer gewissen Zeit S alle Aufgaben im System in die höchste Warteschlange versetzen.

Prioritäten entsprechend an. So versucht er, gleichzeitig zwei Ziele zu erreichen — Leistung für kleine Aufgaben (SJF, STCF) und die faire Ausführung längerer,
CPU-intensiver Aufträge. Deshalb setzen viele Systeme, einschließlich BSD und deren Abkömmlinge, darauf.
Prioritäten entsprechend. So versucht er, auf zwei Hochzeiten gleichzeitig zu tanzen – die Leistung für kleinere Aufgaben (SJF, STCF) zu maximieren und gleichzeitig längere,
CPU-intensiven Aufgaben gerecht zu werden. Daher nutzen viele Systeme, einschließlich BSD und deren Ableger,
Solaris, Windows und Mac verwenden eine Form von Algorithmus als Scheduler.
MLFQ als grundlegendes Konzept.