Einführung in Betriebssysteme

Hallo Habr! Ich möchte Sie auf eine Reihe von Artikelübersetzungen einer meiner Meinung nach interessanten Literatur aufmerksam machen - OSTEP. Dieser Artikel beschreibt ziemlich ausführlich die Arbeit von Unix-ähnlichen Betriebssystemen, nämlich die Arbeit mit Prozessen, verschiedenen Schedulern, Speicher und anderen ähnlichen Komponenten, aus denen das moderne Betriebssystem besteht. Das Original aller Materialien können Sie hier sehen . Bitte beachten Sie, dass die Übersetzung unprofessionell (ziemlich frei) durchgeführt wurde, aber ich hoffe, dass ich die allgemeine Bedeutung beibehalten habe.

Laborarbeiten zu diesem Thema finden Sie hier:

Andere Teile:

Und du kannst meinen Kanal im Telegramm ansehen =)

Planung: Mehrstufige Feedback-Warteschlange

In diesem Vortrag werden wir über die Probleme bei der Entwicklung eines der bekanntesten Ansätze sprechen
Planung namens Multi-Level Feedback Queue (MLFQ). Der MLFQ-Scheduler wurde erstmals 1962 von Fernando J. Corbató in einem System namens Compatible Time-Sharing System (CTSS) beschrieben. Diese Arbeiten (einschließlich späterer Arbeiten zu Multics) wurden anschließend beim Turing Award eingereicht. Der Scheduler wurde anschließend verbessert und erhielt ein Aussehen, das bereits in einigen modernen Systemen zu finden ist.

Der MLFQ-Algorithmus versucht, zwei grundlegende Querschnittsprobleme zu lösen.
Zunächst versucht er, die Bearbeitungszeit zu optimieren, die, wie wir in der vorherigen Vorlesung untersucht haben, optimiert wird, indem am Anfang der Warteschlange der kürzesten Aufgaben begonnen wird. Das Betriebssystem weiß jedoch nicht, wie lange dieser oder jener Prozess funktionieren wird, und dies ist das notwendige Wissen für den Betrieb der SJF- und STCF-Algorithmen. Zweitens versucht MLFQ, das System auf Benutzer (z. B. diejenigen, die auf dem Bildschirm sitzen und starren, während sie auf den Abschluss der Aufgabe warten) zu reagieren und so die Antwortzeit zu minimieren. Leider reduzieren Algorithmen wie RR die Antwortzeit, haben jedoch einen sehr schlechten Einfluss auf die Durchlaufzeitmetriken. Daher unser Problem: Wie kann man einen Scheduler entwerfen, der unseren Anforderungen entspricht und gleichzeitig nichts über die Art des Prozesses im Allgemeinen weiß? Wie kann der Planer die Merkmale der von ihm gestarteten Aufgaben kennenlernen und so bessere Planungsentscheidungen treffen?

Das Wesentliche des Problems: Wie kann man die Formulierung von Aufgaben ohne perfektes Wissen planen? Wie kann ein Scheduler entwickelt werden, der gleichzeitig die Antwortzeit für interaktive Aufgaben minimiert und gleichzeitig die Bearbeitungszeit minimiert, ohne die Zeit für die Ausführung der Aufgabe zu kennen?

Hinweis: Aus früheren Ereignissen lernen

Die MLFQ-Aufstellung ist ein großartiges Beispiel für ein System, das aus vergangenen Ereignissen lernt, um die Zukunft vorherzusagen. Ähnliche Ansätze finden sich häufig im Betriebssystem (und in vielen anderen Bereichen der Informatik, einschließlich Hardware-Vorhersagezweigen und Caching-Algorithmen). Ähnliche Reisen funktionieren, wenn Aufgaben Verhaltensphasen haben und daher vorhersehbar sind.

Bei einer solchen Technik sollte man jedoch vorsichtig sein, da sich Vorhersagen sehr leicht als falsch herausstellen und das System dazu veranlassen können, schlechtere Entscheidungen zu treffen, als dies ohne Wissen überhaupt der Fall wäre.

MLFQ: Grundregeln

Beachten Sie die Grundregeln des MLFQ-Algorithmus. Obwohl es mehrere Implementierungen dieses Algorithmus gibt, sind die grundlegenden Ansätze ähnlich.

In der Implementierung, die wir betrachten werden, wird es in MLFQ mehrere separate Warteschlangen geben, von denen jede eine andere Priorität hat. Eine zur Ausführung bereitstehende Aufgabe befindet sich jederzeit in einer Warteschlange. MLFQ verwendet Prioritäten, um zu entscheiden, welche Aufgabe ausgeführt werden soll, d. H. Eine Aufgabe mit einer höheren Priorität (eine Aufgabe aus der Warteschlange mit einer höheren Priorität) wird zuerst gestartet.

Zweifellos kann sich mehr als eine Aufgabe in einer bestimmten Warteschlange befinden, sodass sie dieselbe Priorität haben. In diesem Fall wird die RR-Engine verwendet, um den Start unter 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 & B mit RR gestartet

Auf dieser Grundlage sind die Schlüsselelemente für die MLFQ-Planung Prioritäten. Anstatt für jede Aufgabe eine feste Priorität festzulegen, ändert MLFQ seine Priorität abhängig vom beobachteten Verhalten.

Wenn beispielsweise eine Aufgabe die Arbeit an der CPU ständig beendet, während sie auf Tastatureingaben wartet, behält MLFQ die Priorität des Prozesses auf einem hohen Niveau bei, da der interaktive Prozess auf diese Weise funktionieren sollte. Wenn im Gegenteil die Aufgabe die CPU über einen langen Zeitraum ständig und intensiv nutzt, verringert MLFQ ihre Priorität. Daher wird MLFQ das Verhalten von Prozessen zum Zeitpunkt ihres Betriebs untersuchen und das Verhalten verwenden.

Lassen Sie uns ein Beispiel zeichnen, wie die Warteschlangen zu einem bestimmten Zeitpunkt aussehen könnten, und dann erhalten wir so etwas:

Bild

In diesem Schema befinden sich 2 Prozesse A und B in der Warteschlange mit der höchsten Priorität. Prozess C befindet sich irgendwo in der Mitte und Prozess D befindet sich ganz am Ende der Warteschlange. Gemäß den obigen Beschreibungen des MLFQ-Algorithmus führt der Scheduler Aufgaben nur mit der höchsten Priorität gemäß RR aus, und die Aufgaben C, D sind arbeitslos.

Ein statischer Schnappschuss liefert natürlich kein vollständiges Bild der Funktionsweise von MLFQ.
Es ist wichtig, genau zu verstehen, wie sich das Bild im Laufe der Zeit ändert.

Versuch 1: So ändern Sie die Priorität

Zu diesem Zeitpunkt müssen Sie entscheiden, wie MLFQ die Prioritätsstufe der Aufgabe (und damit die Position der Aufgabe in der Warteschlange) während ihres Lebenszyklus ändert. Dazu müssen Sie den Workflow berücksichtigen: eine Reihe interaktiver Aufgaben mit einer kurzen Laufzeit (und damit häufigen CPU-Freigabe) und mehreren langen Aufgaben, die die CPU während ihrer gesamten Arbeitszeit nutzen, während die Antwortzeit für solche Aufgaben nicht wichtig ist. Und so können Sie den ersten Versuch unternehmen, den MLFQ-Algorithmus mit den folgenden Regeln zu implementieren:

Regel 3: Wenn eine Aufgabe in das System eingeht, wird sie mit der höchsten in die Warteschlange gestellt
Priorität.
Regel 4a: Wenn eine Aufgabe das gesamte ihr zugewiesene Zeitfenster verwendet, ist es
Priorität sinkt.
Regel 4b: Wenn die Task die CPU vor Ablauf ihres Zeitfensters freigibt, dann sie
bleibt mit der gleichen Priorität.

Beispiel 1: Eine einzelne Aufgabe mit langer Laufzeit

Wie Sie in diesem Beispiel sehen können, hat die Aufgabe bei der Zulassung die höchste Priorität. Nach einem Zeitfenster von 10 ms wird der Prozess vom Scheduler vorrangig abgesenkt. Nach dem nächsten Zeitfenster fällt die Aufgabe schließlich auf die niedrigste Priorität im System, wo sie verbleibt.

Beispiel 2: Sie haben eine kurze Aufgabe angesprochen

Schauen wir uns nun ein Beispiel an, wie MLFQ versuchen wird, SJF näher zu kommen. In diesem Beispiel gibt es zwei Aufgaben: A, eine lang laufende Aufgabe, die ständig die CPU beansprucht, und B, eine kurze interaktive Aufgabe. Angenommen, A hat bereits einige Zeit gearbeitet, als Aufgabe B eintrifft.

In diesem Diagramm sind die Ergebnisse des Skripts sichtbar. Aufgabe A befindet sich wie jede Aufgabe, die eine CPU verwendet, ganz unten. Aufgabe B erreicht T = 100 und wird mit der höchsten Priorität in die Warteschlange gestellt. Da die Zeit ihrer Arbeit kurz ist, endet sie, bevor sie die letzte Stufe erreicht.

Anhand dieses Beispiels sollte man das Hauptziel des Algorithmus verstehen: Da der Algorithmus keine lange oder kurze Aufgabe kennt, geht er zunächst davon aus, dass die Aufgabe kurz ist, und gibt ihr die höchste Priorität. Wenn es sich um eine wirklich kurze Aufgabe handelt, wird sie schnell erledigt. Wenn es sich um eine lange Aufgabe handelt, wird sie sich langsam in der Priorität nach unten bewegen und bald beweisen, dass es sich um eine wirklich lange Aufgabe handelt, für die keine Antwort erforderlich ist.

Beispiel 3: Was ist mit E / A?

Schauen Sie sich nun das E / A-Beispiel an. Wie in Regel 4b angegeben, bleibt ein Prozess auf derselben Prioritätsstufe, wenn er einen Prozessor freigibt, ohne seine Prozessorzeit vollständig zu nutzen. Die Absicht dieser Regel ist recht einfach: Wenn eine interaktive Aufgabe viele E / A-Vorgänge ausführt, z. B. darauf wartet, dass ein Benutzer eine Taste oder eine Maus drückt, gibt eine solche Aufgabe den Prozessor vor dem zugewiesenen Fenster frei. Wir möchten eine solche Aufgabe nicht vorrangig weglassen, und daher bleibt sie auf dem gleichen Niveau.

Dieses Beispiel zeigt, wie der Algorithmus mit solchen Prozessen arbeitet - eine interaktive Aufgabe B, die vor dem Ausführen des E / A-Prozesses nur 1 ms lang eine CPU benötigt, und eine lange Aufgabe A, die die CPU ständig nutzt.

MLFQ hält Prozess B mit der höchsten Priorität, da er die ganze Zeit fortgesetzt wird.
Geben Sie die CPU frei. Wenn B eine interaktive Aufgabe ist, hat der Algorithmus sein Ziel erreicht, interaktive Aufgaben schnell zu starten.

Probleme mit dem aktuellen MLFQ-Algorithmus

In den vorherigen Beispielen haben wir die Basisversion von MLFQ erstellt. Und es scheint, dass er seine Arbeit gut und ehrlich macht, indem er die Prozessorzeit ehrlich auf lange Aufgaben verteilt und es kurzen Aufgaben oder Aufgaben, die intensiv auf E / A zugreifen, ermöglicht, schnell zu arbeiten. Leider enthält dieser Ansatz mehrere schwerwiegende Probleme.

Erstens das Problem des Hungers: Wenn es viele interaktive Aufgaben im System gibt, verbrauchen sie die gesamte Prozessorzeit und somit kann keine einzige lange Aufgabe ausgeführt werden (sie hungern).

Zweitens könnten intelligente Benutzer ihre Programme so schreiben
Trick den Planer. Der Trick besteht darin, etwas zu tun
Scheduler, um dem Prozess mehr Prozessorzeit zu geben. Algorithmus das
oben beschrieben ist ziemlich anfällig für solche Angriffe: bevor das Zeitfenster praktisch ist
beendet müssen Sie eine E / A-Operation ausführen (für einige, egal welche Datei)
und damit die CPU freigeben. Dieses Verhalten ermöglicht es Ihnen, im selben zu bleiben
die Warteschlange selbst und wieder einen größeren Prozentsatz der CPU-Zeit erhalten. Wenn fertig
Dies ist korrekt (z. B. 99% der Fensterzeit vor dem Freigeben der CPU).
Eine solche Aufgabe kann den Prozessor einfach monopolisieren.

Schließlich kann ein Programm sein Verhalten im Laufe der Zeit ändern. Diese Aufgaben
Wer die CPU benutzt hat, kann interaktiv werden. In unserem Beispiel ähnlich
Aufgaben werden vom Planer nicht richtig behandelt, wie andere es tun würden
(anfängliche) interaktive Aufgaben.

Frage an das Publikum: Welche Angriffe auf den Planer könnten in der modernen Welt erfolgen?

Versuch 2: Priorität erhöhen

Versuchen wir, die Regeln zu ändern und herauszufinden, ob wir Probleme mit vermeiden können
Fasten. Was könnten wir tun, um dies sicherzustellen?
CPU-Aufgaben erhalten ihre Zeit (auch wenn nicht lange).
Als einfache Lösung für das Problem können Sie regelmäßig anbieten
Erhöhen Sie die Priorität aller dieser Aufgaben im System. Es gibt viele Möglichkeiten.
Um dies zu erreichen, versuchen wir, als Beispiel etwas Einfaches zu implementieren: übersetzen
Alle Aufgaben gleichzeitig mit höchster Priorität, daher die neue Regel:

Regel 5 : Übertragen Sie nach einer bestimmten Zeitspanne von S alle Aufgaben im System auf die höchste Priorität.

Unsere neue Regel löst zwei Probleme gleichzeitig. Erstens die Prozesse
garantiert nicht verhungern: Aufgaben mit der höchsten Priorität werden geteilt
Prozessorzeit nach dem RR-Algorithmus und damit alle Prozesse empfangen
Prozessorzeit. Zweitens, wenn es einen Prozess gibt, der zuvor verwendet wurde
Nur der Prozessor wird interaktiv, dann bleibt er im Einklang mit dem höheren
Priorität nach einmal erhält eine Prioritätserhöhung auf die höchste.
Betrachten Sie ein Beispiel. Betrachten Sie in diesem Szenario einen Prozess mit

CPU und zwei interaktive, kurze Prozesse. Links in der Abbildung zeigt die Abbildung das Verhalten, ohne die Priorität zu erhöhen, und daher beginnt die lange Aufgabe zu verhungern, nachdem zwei interaktive Aufgaben im System angekommen sind. In der Abbildung rechts wird alle 50 ms die Priorität erhöht, sodass alle Prozesse garantiert Prozessorzeit erhalten und regelmäßig gestartet werden. In diesem Fall werden 50 ms als Beispiel genommen, in Wirklichkeit ist diese Zahl etwas größer.
Offensichtlich führt die Hinzufügung von Zeit für eine periodische Erhöhung von S zu
logische Frage: Welcher Wert sollte gesetzt werden? Einer der Geehrten
Systemingenieure John Ousterhout nannte ähnliche Größen in Systemen wie voo-doo
konstant, weil sie irgendwie schwarze Magie für richtig forderten
ausstellen. Und leider hat S so ein Aroma. Wenn Sie den Wert auch einstellen
große - lange Aufgaben werden anfangen zu verhungern. Und wenn Sie den Wert zu niedrig einstellen,
Interaktive Aufgaben erhalten keine ordnungsgemäße Prozessorzeit.

Versuch 3: Beste Buchhaltung

Jetzt haben wir noch ein Problem, das gelöst werden muss: wie nicht
unseren Planer betrügen lassen? Schuld an dieser Gelegenheit sind
Regeln 4a, 4b, die es der Aufgabe ermöglichen, die Priorität beizubehalten und den Prozessor freizugeben
vor Ablauf der zugewiesenen Zeit. Wie gehe ich damit um?
Die Lösung in diesem Fall kann als die beste Abrechnung der CPU-Zeit auf jedem angesehen werden
MLFQ-Level. Anstatt die Zeit zu vergessen, die das Programm verwendet hat
Prozessor für den zugewiesenen Zeitraum sollten Sie ihn berücksichtigen und speichern. Nachdem
Der Prozess hat Zeit dafür aufgewendet, sollte auf den nächsten reduziert werden
Prioritätsstufe. Egal wie der Prozess seine Zeit nutzt - wie
ständig auf dem Prozessor oder so viele Anrufe rechnen. Auf diese Weise,
Regel 4 sollte wie folgt umgeschrieben werden:

Regel 4 : Nachdem die Aufgabe die ihr in der aktuellen Warteschlange zugewiesene Zeit aufgebraucht hat (unabhängig davon, wie oft sie die CPU freigegeben hat), nimmt die Priorität einer solchen Aufgabe ab (sie bewegt sich in der Warteschlange nach unten).

Schauen wir uns ein Beispiel an:

""

Die Abbildung zeigt, was passiert, wenn Sie versuchen, den Scheduler zu täuschen, wie
Wenn es mit den vorherigen Regeln 4a, 4b wäre, erhalten wir das Ergebnis auf der linken Seite. Frohes neues
Die Regel ist das Ergebnis auf der rechten Seite. Vor dem Schutz kann jeder Prozess E / A bis zum Abschluss aufrufen und
dominieren somit die CPU nach Aktivierung des Schutzes, unabhängig vom Verhalten
I / O, es wird immer noch auf der ganzen Linie fallen und wird daher nicht unehrlich sein
CPU-Ressourcen in Besitz nehmen.

Verbesserung des MLFQ und anderer Probleme

Mit den oben genannten Verbesserungen treten neue Probleme auf: eines der Hauptprobleme
Fragen - wie man einen solchen Scheduler parametriert? Das heißt, Wie viel sollte sein
platzt? Wie groß sollte das Programmfenster in der Warteschlange sein? Wie
Die Programmpriorität sollte häufig erhöht werden, um Hunger zu vermeiden
Änderungen im Programmverhalten berücksichtigen? Auf diese Fragen ist es nicht einfach
Antwort und nur Experimente mit Lasten und nachfolgender Konfiguration
Der Planer kann zu einem zufriedenstellenden Gleichgewicht führen.

Bei den meisten MLFQ-Implementierungen können Sie beispielsweise unterschiedliche Zuweisungen vornehmen
Zeitintervalle zu verschiedenen Warteschlangen. Warteschlangen mit hoher Priorität normalerweise
kurze Intervalle werden zugewiesen. Diese Warteschlangen bestehen aus interaktiven Aufgaben.
Das Umschalten ist sehr empfindlich und sollte 10 oder weniger dauern
ms Im Gegensatz dazu bestehen Warteschlangen mit niedriger Priorität aus langen Aufgaben
CPU In diesem Fall passen lange Zeitintervalle sehr gut (100 ms).

In diesem Beispiel gab es zwei Aufgaben, die in der Warteschlange 20 mit hoher Priorität ausgeführt wurden
ms, 10 ms lang durch Windows unterbrochen. 40 ms in der mittleren Warteschlange (Fenster bei 20 ms) und in der niedrigen Priorität
Das Zeitfenster für die Warteschlange betrug 40 ms, in dem die Aufgaben ihre Arbeit erledigten.

Die Solaris OS MLFQ-Implementierung ist eine Klasse von Time-Sharing-Schedulern.
Der Scheduler bietet eine Reihe von Tabellen, die genau bestimmen, wie es sein soll
Ändern Sie die Priorität des Prozesses über seine Lebensdauer, was sollte die Größe sein
das ausgewählte Fenster und wie oft Sie die Prioritäten der Aufgabe erhöhen müssen. Admin
Systeme können mit dieser Tabelle interagieren und den Scheduler verhalten
anders. Standardmäßig enthält diese Tabelle 60 inkrementelle Warteschlangen.
Fenstergröße von 20 ms (hohe Priorität) bis zu mehreren hundert ms (niedrigste Priorität) und
auch mit einem Schub aller Aufgaben einmal pro Sekunde.

Andere MLFQ-Planer verwenden keine Tabelle oder eine bestimmte
die Regeln, die in dieser Vorlesung beschrieben werden, im Gegenteil, sie berechnen Prioritäten mit
mathematische Formeln. So verwendet beispielsweise der Scheduler in FreeBSD die Formel für
Berechnen der aktuellen Priorität einer Aufgabe basierend auf dem Umfang des Prozesses
gebrauchte CPU. Darüber hinaus nimmt die Nutzung der CPU mit der Zeit ab und so weiter
Somit erfolgt die Prioritätserhöhung etwas anders als oben beschrieben. Ist das so
Zerfallsalgorithmen genannt. Seit Version 7.1 verwendet FreeBSD den ULE-Scheduler.

Schließlich haben viele Planer andere Funktionen. Zum Beispiel einige
Planer reservieren die höchsten Ebenen für das Betriebssystem und so weiter
Auf diese Weise kann kein Benutzerprozess die höchste Priorität erhalten
System. Bei einigen Systemen können Sie Tipps geben, um zu helfen.
der Scheduler, um Prioritäten richtig zu setzen. Zum Beispiel mit dem Befehl nice
Sie können die Priorität der Aufgabe erhöhen oder verringern und damit oder erhöhen
Reduzieren Sie die Wahrscheinlichkeit, dass das Programm Prozessorzeit benötigt.

MLFQ: Zusammenfassung

Wir haben einen Planungsansatz namens MLFQ beschrieben. Sein Name
im Prinzip der Arbeit abgeschlossen - es hat mehrere Warteschlangen und verwendet Feedback
.
:

Rule1 : () > (), ( )
Rule2 : () = (), RR
Rule3 : , .
Rule4 : ( CPU) ( ).
Rule5 : S .

MLFQ —
,
. — (SJF, STCF) ,
CPU . , BSD ,
Solaris, Windows, Mac
MLFQ .

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