Lernzettel Betriebssysteme PDF

Preview

Summary

Zusammenfassung aus dem Bereich Aufbau Betriebssysteme...

Description

Warum waren zu Anfang der EDV keine Betriebssysteme notwendig? Es wurde damals systemnah programmiert (sehr hardwarenahe Maschinensprache) Programme lagen als Lochkarten vor Wozu ist ein Betriebssystem überhaupt notwendig? Verwaltung sämtlicher Betriebsmittel (Hardware und Software-Ressourcen) [Prozessor, Speicher, Dateien und Geräte] Hardware soll benutzerfreundlich [Nutzer soll von komplexen Einzelheiten abgeschirmt werden] effizient [Minimierung des Betriebsmittelverbrauchs Lauf- u. Antwortzeiten, Speicherbedarf] und sicher [Schutz vor Störungen / Vermeidung von Störungen, Was passiert beim Fehler] zu steuern und zu kontrollieren.

Mikroprogrammbefehle Testbefehle, Sprungbefehle (BRANCH), (Add) und logische Befehle (CMP, SHIFT)

Transportbefehle (MOV),

arithmeitische

Welche zwei Sichtweisen gibt Prof. Tanenbaum bei der Betrachtung der Funktion eines BS? Top Down: Eine erweiterte Maschine (Extended machine) Versteckt die technischen Details vor dem Nutzer Einfache Sicht, Rechner als virtuelle Maschine Bottom Up: Betriebsmittelverwalter (Ressource Manager) Jeder Prozess/ Programm bekommt Nutzungszeit für eine Ressource zugewiesen Und er bekommt Arbeitsplatz innerhalb der Ressource. Von Neumann-Architektur Struktur des Rechners ist unabhängig vom bearbeiteten Problem Programme und Daten stehen im selben Speicher Arbeitsweise

Programm als Folge von Befehlen (Instruktionen) nacheinander (sequentielle Abfolge) Æ Durch bedingte / unbedingte Sprungbefehle können Programmfortsetzungen aus späteren Zellen bewirkt werden Nutzung des Binärcodes (Dualzahlen) Alles muss geeignet kodiert werden Bitfolgen sind nicht selbstidentifizierend Æ Rechner entscheidet nach dem zeitlichen Kontext ob Bitfolge ein Befehl, eine Adresse ein Datum ist Befehlsausführung

CPU

Interner Speicher

Ein- und Ausgabewerk

System Bus

Cache Erweiterung für Rechnerarchitekturen Schneller Pufferspeicher / Zwischenspeicher für oft benötigte Daten Speicherung von Daten oder Codeteile zur Zugriffsoptimierung L1-Cache (in der CPU~16-64 kByte) häufig benötigte Befehle und Daten L2-Cache ( Speicherverdichtung / Kompaktifizierung

Fragmentierung

Virtual Memory Sofern Programm größer als Hauptspeicher dann lade nur notwendige Teile davon, die anderen nach Bedarf Jedoch die Frage (Welcher Teil ist notwendig und muss im Speicher sein, Was kann ausgelagert werden)

Paging: Beispiel

MMU Memory Management UNI MMU = Teil der CPU Jede durch einen Prozess angeforderte virtuelle Adresse wird zuerst durch MMU in physikalische Adresse umgesetzt, bevor auf Adressbus geschrieben wird Page Table (Innenleben der MMU) Index gibt die Nummer der virtuellen Seite an Seiteneintrag gibt physikalische Seite an z.B. 16 mögliche virtuelle Seiten werden auf 8 vorhandene physikalische Kacheln abgebildet Present / Absent Bit zeigt an ob die virtuelle Seite vorhanden ist

12 Virtuelle Adresse 8196 Binär 0010000000000100

13 Seitentabelleneintrag (Page Tables (in der MMU)

14 Virtual Memory Größe des Arbeitsspeichers

Eigenschaften vom Paging Keine externe Fragmentierung (letzte Seite eines logischen Adressraums wird nicht genutzt) Æ Intern Fragmentierung Lineare Speicheradressierung (keine Fragmentierung aus Pogrammiersicht) Speicherschutz durch Schutzbits (Zusatz Bits zeigen ob Kachel gültig oder modifiziert ist) Adressraum eines Prozesses muss nicht vollständig im Speicher sein zur Ausführung Zugriffe auf nicht geladene Seiten Æ Seit enfehler (Pagefault) Æ BS behebt Seitenfeher in dem Seite in freie Kachel geladen wird und Befehl erneut ausgeführt wird (Neustart Zeitverlust)

anschließend

15 a 32 Bit-Adresse mit zwei 10 Bit Feldern für Seitennummern b Zweistufige Seitentabellen Seitentabellen werden ausgelagert in andere Tabellen Î Nicht mehr alle müssen im RAM sein

Tabellen

Zweistufige Seitentabellen (statt einer einstufigen Tabelle in der ein 20 Bit Feld über 1 Mio Einträge aufweist) AMD Opteron (64 Bit) hat z.B. 4 stufige Tabellen

16 Translation Lookaside Buffers = Assoziativspeicher (HW, Teil der MMU)

In der MMU spezieller Cache der die letzten Adressübersetzungen als Tabelle abspeichert Æ Beschleunigung des Paging Direkte Abbildung der virtuellen auf Physische Adressen (Ohne Seitentabellen) MMU hat spezielle schneller Register für Basisadressen und Offset ÆUm Adressberechnung so effizient wie möglich zu machen Lokalitätsprinzip Zeitlich: Daten / Code der gerade benutzt wird, wird mit hoher Wahrscheinlichkeit gleich wieder benötigt Örtlich: Nächster Daten / Code-Zugriff ist mit hoher WS in der Nähe der vorherigen Zugriffe

Faustregel: Ein Programm verbringt 90 % seiner Abarbeitungszeit in 10 % des gesamten Codes. Die Befehle ändern sich oft nicht, nur die Adressen der jeweils benötigten Daten (Operanden)

Inverted Page Tables

Abbildung von virtueller Seite auf physische viel aufwendiger: gesamte Seitentabelle muss nach Eintrag durchsucht werden, nicht nur bei Seitenfehlern Æ Nur sinnvoll mit Translation Lookaside Buffers TLB

17 Behandlung von Seitenfehlern

Speicherverwaltung (Memory Management) Teil des Betriebssystems, der für die Verwaltung des Speichers zuständig ist Speicherzuteilung für Prozesse Anschließende Freigabe des Speichers Platzierungsstrategien First Fit

Einfachstes Verfahren / nicht ineffizient Plat zierung in das erste hinreichend große Loch Ziel: Speicherlöcher gleichmäßig im Speicher verteilen

Best Fit

Langsam Gesamter Speicher wird durchsucht nach kleinstem Loch Æ Langsam Große Löcher bleiben lange bestehen Æ starke Fragmentierung

Worst Fit

Schlechte Idee Auswahl des größten verfügbaren Lochs Das einzelne Loch kann zu klein sein zu Aufnahme eines neuen Segments

Quick Fit

Schlechte Idee (Schnell sehr aufwendig) Erstellung einer Liste der Größen der Löcher (4KB, 8KB, 12KB, 20KB…)

Rotating First Fit / Next Fit

hohe Geschwindigkeit / einfache Implementierung

Einführung eines zusätzlichen Zeigers der auf den zuletzt verkleinerten Frei-Bereich oder auf den Nachfolger eines aufgelösten Frei-Bereich Funktionsweise wie First-Fit ab der Zeigerposition 18 Grafische Übersicht der Platzierungsstrategien

Ersetzungsstrategien Seitenfehler entstehen, wenn Seite entfernt werden muss oder Platz geschaffen werden muss für neue Seiten Veränderte Daten müssen zunächst gespeichert werden / Unveränderte Seiten können überschrieben werden Für Seitenauslagerung sinnvoll die selten genutzten Seiten zu nutzen / häufig genutzte müssen bald wieder eingelagert werden Optimaler Algorithmus

Theoretisches Modell nach Belady

Ersetze Seite wird nach unendlicher Zeit erst wieder benötigt Æ Nur die „richtigen Seiten“ werden ausgelagert (kann vom BS nicht vorhergesehen / gesteuert werden) Not-Recently-Used NRU

First in First out FiFo Jede Seite erhält beim Laden in Hauptspeicher einen Zeitstempel Neue Seiten an den Anfang / Älteste Seiten werden am Ende gelöscht + Geringer Aufwand und leicht zu implementieren / - Die Seite, die am längsten im Speicher ist, wird of am meisten genutzt

Second Chance

Abwandlung von FiFo

Überprüfung des Reference Bit der ältesten Seite Wenn das Bit alt ist (FiFo) und unbenutzt ist (Reference-Bit / R-Bit = 0), dann Seite ersetzen Sucht möglichst alte Seiten die im letzten Timerintervall nicht zugegriffen wurde Clock-Algorithmus Ringförmige Liste der Seiten Wenn Seitenfehler auftritt, wird auf die Seite referenziert, auf die der Pfeil zeigt (Abhängig vom R-Bit) R = 0 Seite auslagern R = 1 Lösche R und gehe eine Position weiter

Least-Recently-Used LRU

sehr aufwendig recht selten mit Spezialhardware

Seite die von den letzten Befehlen häufig genutzt wurde wird auch in den nächsten Befehlen genutzt Æ Ausgelagerte Seiten bleiben lange unbenutzt. Seiten die am längsten nicht mehr genutzt wurde, wird ausgelagert Vorhaltung einer verketteten Liste aller Seiten im Hauptspeicher. Zuletzt genutzte Seite am Anfang am wenigsten Genutzte am Ende Æ Aktualisierung bei jedem Speicherzugriff LRU verlangt, dass jede Seite Zeitangabe hat

19 LRU durch Hardware realisieren

Working Set Arbeitsbereich nach Denning (bei hoher Lokalität wirkungsvoll) Menge von Seiten, die von einem Prozess zu einem bestimmten Zeitpunkt benutzt wird Wenn ein zusammenhängender Arbeitsbereich im Speicher ist ÆVerarbeitung fast keine Fehler Vorausschauendes Paging (Arbeitsvorgang eines Prozesses wird vom BS bei Auslagerung registriert und bei erneutem Aufruf schon im Vorhinein geladen) Die Letzten d Referenzen werden betrachtet um daraus sinnvolles Working-Set zu bestimmen Beispiel Distanzkette d = 10

Å

Anordnung

der

Seiten

Referenzhäufigkeit Referenzhäufigkeit pi der Seite i

nach

20 Working Set Algorithmus 21 Working Set Clock Verbesserung des WS-Algorithmus

Gute Leistung einfach zu implementieren Æ A und b zeigen was bei R = 1 passiert C und D geben ein Beispiel für R = 0

Sperrung von Seiten im Speicher Virtueller Speicher und E/A interagieren Prozess startet Systemaufruf um Daten in Puffer seines Adressraumes einzulesen Wenn Prozess auf E/A wartet wird er suspendiert anderer Prozess bekommt CPU-Zeit ÆSeitenfehler werden erzeugt Seite die den Puffer enthält wird ev. Zur Auslagerung gewählt LösungÆ Sperrung der Seiten die mit E/A Zugriffen zu tun haben (pinning) Æ Seiten werden nicht mehr ausgelagert Ladestrategien fetch strategies wann wollen neue Daten in Hauptspeicher geladen werden Demand Paging Seiten nur auf Verlangen laden Pro:

Keine überflüssigen Seiten werden geladen

Con:

Prozess muss warten bis notwendige Seite geladen

Prepaging

Anticipatory Paging

Seiten vorausschauend laden Mehr Hauptspeicher notwendig, dann werden Auswirkungen von falschen Entscheidungen kleiner Pro:

Verringerung der Ausführungszeit bei richtigen Entscheidungen

Con:

Falsche Entscheidungen erhöhen Ausführungszeit

Freigabe Strategien Paging Daemon (Hintergrundprozess) Überprüft regelmäßig Zustand des Speichers und hält Mindestanzahl von Kacheln frei Aus dem Vorrat werden Seitenfehler schnell bedient und neue Adressräume angelegt Wenn nicht genügende Seitenrahmen frei werden mittels Seitenersetzungsalgorithmus Seiten ausgewählt die ausgelagert werden

24 Beladys Anomalie

Modellierung von Ersetzungsstrategien

23 Paging in Linux Buddy Algorithmus

Halbierung des Speichers bis ausreichende Größe erreicht Dynamische Zusammenfassung leerer Bereiche 25 Clock Algorithmus mit 2 Zeiger

22 Design Kriterien für Paging

Lokale vs. Globale Seitenersetzung Anzahl der Seitenrahmen eines Prozesses ist veränderlich Æ globale Strategie flexibler Einige Algorithmen können mit Globalen und Lokalen Paging Strategien arbeiten FIFO: älteste Seite aus dem Speicher (global) auslagern und durch älteste Seite des aktuellen Prozesses (lokal) ersetzen. LRU auch Nur lokale Strategie sinnvoll bei Working Set / WS Clock 26 Lokale vs Globale Seitenersetzung

Seitenfehlerrate (Page Fault Frequency PFF) in Abhängigkeit von Anzahl der zugewiesenen Seitenrahmen

Thrashing Problem Laststeuerung Trotz gutem Design, kann System zu viele Seitenfehler erzeugen, wenn PFF zeigt, dass mehrere Prozesse zu wenig Speicher haben aber keiner zu viel Lösung: Einige Prozesse zeitweise komplett aus Speicher entfernen Auslagerung auf Festplatte und Seiten freigeben (Swapping, wenn beim Paging Gefahr des Trashing besteht) oder Anzahl der laufenden Programme begrenzen

Optimale Seitengröße es gibt kein Optimum bei kleiner Seitengröße Pro:

geringe

interne

Fragmentierung,

bessere Anpassung an verschiedene Daten-Strukturen Weniger ungenutzte Daten im Speicher Con:

Programme belegen viele Seiten und benötigen große Seitentabellen Æ Langsamer werden muss

weil

mehr

durchsucht

Dynamische Speicherzuteilung Segmentierung (Speicherzuteilungsstrategien notwendig) Segmente sind zusammenhängende Speicherbereiche die aufeinanderfolgende Adressen haben Sind deutlich größer als Pages Es werden Segmente allokiert (angefordert) und freigegeben Anwendungsprogramme werden beispielsweise in Codesegment, Datensegment und Stacksegment (für Verwaltungsinformationen) eingeteilt 27 Eindimensionaler Adressraum

28 Vergleich Paging und Segmentierung

29 Umsetzung Logische in physikalische Adresse

Bei Segmentierung wird die Memory Management Unit MMU benötigt Prozessumschaltung

durch

Austausch

der

Segmentbasis

Æ

jeder

Prozess

hat

eigene

Übersetzungstabelle Ein- und Auslagerung wird vereinfacht Æ nach Einlagerung muss nur Übersetzungstabelle angepasst werden

Unterbrechung zeigt Speicherplatzverletzung an >

30 Schutz vor Segmentübertretung

Programme und BS voreinander geschützt > Zugriffsschutz einfach zu integrieren Rechte für Lesen/Schreiben/Ausführen werden von MMU geprüft Speicher

wird

bei

häufigem

Ein-Auslagern

fragmentiert (kleine nicht nutzbare Lücken) Segmente werden verschoben um Lücken zu schließen Æ Kompaktifizierung Lange E/A Zeiten für die Ein- und Auslagerung da nicht alle Teiles eines Segments gleich häufig genutzt werden 31 externe Fragmentierung

Vorteile der Segmentierung Gemeinsame

Segmente

möglich

(global) Befehlssegmente, Datensegmente (Shared Memory), Umfangreiche Gafikbibliotheken Gemeinsam benutzte Adressbereiche (global) Windows: DLL dynamik link library UNIX: Shared library Belegt nur eine Ressource Variable Größe der Segmente Auch in Kombination mit Paging nutzbar

32 Zusammenfassung Logische virtuelle Adressen

Garbage

Collection

Æ

automatische

Speicherverwaltung

die

den

Speicherbedarf

eines

Computerprogramms minimiert. Zur Laufzeit werden nicht länger benötigte Speicherbereiche automatisch identifiziert und dann freigegeben. Manchmal werden diese Bereiche zusammengefasst (Defragmentierung) Æ Ziel:

Vermeidung von Speicherproblemen

Kernel Panic: BS befindet sich in einem undefinierten Zustand (keine Möglichkeit das System kontrolliert weiter zu betreiben (Fataler Fehler Systemabsturz)

Ein Computer soll für einen Mehrprogrammbetrieb ausgelegt sein. Wovon hängt die maximale Größe der quasi gleichzeitig ablaufenden Programme ab?

Æ Die Größe vom Hauptspeicher

Wozu braucht man Speicherverwaltung? Was leistet sie?

Æ

Effiziente

Verwaltung

des

Hauptspeichers (flüchtiger Speicher RAM) Aufbereitung des Prozessscheduler Ein System hat maximal 4 Programme im Hauptspeicher. Diese Programme haben eine E/A-Wartezeit von 50%. Welcher Anteil der Prozessorzeit wird verschwendet? Um welchen Wert verbessert sich hier die Auslastung zum Monoprogramming? Æ 1 – 0,5^4 = 93,75% ausgenutzt ÆMonoprogramming 4 * 50%

In einem Swapping System sind folgende Löcher im Speicher, nach aufsteigenden Adressen geordnet: 10 KB, 4 KB, 20 KB, 18 KB, 7 KB, 9 KB, 12 KB und 15 KB. Welche Löcher wählten die bekannten vier Platzierungs- Modelle / Algorithmen, wenn nacheinander Segmente von 12 KB, 10 KB und 9 KB angefordert würden? (kurze Erklärung!)

Wodurch wird die virtuelle Adresse in eine physische (Speicher-) Adresse umgerechnet? Î Durch die Memory Management Unit und der Page Table Nennen Sie verschiedene Ansätze / Techniken, wie der Hauptspeicher verwaltet werden kann und beschreiben Sie diese. Î Fest, Dynamisch, Swapping, Paging, Segmentierung Woran erkennt das Betriebssystem, ob sich eine Speicherseite eines Prozesses im Hauptspeicher befindet oder nicht? Î An dem Present / Absent Bit Ein Prozessor besitzt virtuelle Adressen mit 32 Bits, physisch mit 28 Bits und Seiten mit 2 Kb. Wie viele Bits werden für die virtuelle und physische Seitennummern benötigt? Æ 17 Bit ? 2kb = 2048 B = 2^11

28 Bit- 11 = 17 Bit

Wie funktioniert Speicherverwaltung in eingebetteten Systemen? Æ Warum ist der Least-Recently-Used-Algorithmus für die Seitenverdrängung nicht praktikabel? Æ zu viele Verwaltungsinformationen, weil alles perfekt passen soll Was macht ein Page Daemon Æ automatischer Hintergrundprozess der Dienste vom System anstößt Ein Rechner hat einen 32-bit Adressraum und eine Seitengröße von 8 KB. Wieviele Einträge hat die Seitentabelle der MMU? 32 Bit -8192 (2^13) = 19 Bit 2^19 = 524.288 Einträge Was versteht man unter einem „Working Set“ eines Programms? Welche Informationen werden benötigt? Rechtfertigt der zusätzliche Aufwand das Ergebnis? Æ Menge von Seiten (Vorausschauendes Paging)

Was ist die Ursache von Thrashing? Wie kann das BS darauf reagieren? Wie kann dieser Zustand verhindert werden?

Æ Thrashing sucht nach freiem Speicher ist aber alles voll

Ein virtueller Adressraum wird mit 32 Bit langen virtuellen Adressen adressiert. Eine virtuelle Adresse enthält jeweils 10 Bit für den Index in der Top-Level- Seitentabelle und 10 Bit für den Index in der Second-Level-Seitentabelle. • Wieviele Second-Level-Seitentabelle gibt es pro Prozess? • Wie groß sind

die

Seitenrahmen

im

Hauptspeicher? Wie

groß

gesamte Adressraum

•

ist

der

virtuelle eines

Prozesses? Schildern Sie die Vor- und Nachteile von größeren bzw. kleineren Seiten. Con Klein:

große Paging Tabellen viele Einträge viel Verwaltungsaufwand

Pro Klein:

geringe Fragmentierung

Pro Groß:

Einfachere Auslagerung von Seitenrahmen

Con Groß:

Anzahl an Adressen werden weniger

Dateiverwaltung Teil des BS das sich mit der physischen und logischen Aufteilung & Strukturierung der Datenträger beschäftigt Unterschiedliche oft properitäre Dateisysteme (APFS NTFS…) Dateisystem = Sammlung von Daten auf einem Permanentspeicher (HDD, SSD) Im DS wird definiert, wie Dateien abgelegt werden (Blockgröße, zusammenhängend / fragmentiert) DS definiert Listen, welche Speicherpositionen der Dateien enthält

Essentielle Anforderungen an langfristige Datenhaltung -Möglichkeit, große Mengen von Informationen zu speichern -Informationen

muss

eine gewisse Dauer überleben

(Datenpersistenz) -Mehrere Prozesse müssen gleichzeitig auf die Information zugreifen können Namensgebung ist abhängig vom DS Länge, Dateierweiterung, gültige Zeichen, Case Sensitive

Dateityp Reguläre

Dateien

enthalten

Benutzerinformationen,

ASCII

oder

Binärdaten Verzeichnisse sind Systemdateien zur Strukturierung des Dateisystems Spezielle Dateitypen (UNIX) sind z.B. Zeichendateien die E/A Geräte modellieren (Drucker) oder auch spezielle Blockdateien die gesamte Datenträger abbilden (Diskette, USB-Stick) Dateistruktur

Byte-Sequence Record-Sequence (Lochkarte) Baum

(jeder

Record

mit

einem

Schlüssel)

B-Bäume Dateistruktur als Datenbank

schneller Dateizugriff

kurze

Wiederherstellungszeiten Performance Gewinn werden durch komplexere...