RW-SystemarchitekturKap. 8 1 Kapitel 8 Speicherverwaltung

  • Published on
    05-Apr-2015

  • View
    104

  • Download
    1

Embed Size (px)

Transcript

  • Folie 1
  • RW-SystemarchitekturKap. 8 1 Kapitel 8 Speicherverwaltung
  • Folie 2
  • RW-SystemarchitekturKap. 8 2 berblick Betriebssysteme 6 Einfhrung 7 Prozesse, Fden (threads), Scheduling 8. Speicherverwaltung 8.1 Anforderungen an die Speicherverwaltung 8.2 Grundlegende Methoden der Speicherverwaltung 8.2.1 Partitionierung 8.2.2 Verlagerung 8.2.3 Seitenadressierung und Seitenaustausch 8.2.4 Segmentierung 8.2.5 Seiten und Segmente 9. Dateisysteme 10. Ein- und Ausgabe Nebenlufigkeit und wechselseitiger Ausschluss Inhalt der Vorlesung Nebenlufige Programmierung Deadlocks - dito
  • Folie 3
  • RW-SystemarchitekturKap. 8 3 8 Speicherverwaltung Speicherverwaltung: Aufteilung des verfgbaren Hauptspeichers zwischen Betriebssystem verschiedenen Prozessen Speicherverwaltung erfordert enges Zusammenspiel von Hardware und Betriebssystem. Hardwareaspekte (virtueller Speicher): kurz in Kapitel 4 behandelt Jetzt: Betriebssystemaspekte Ausfhrliche Behandlung des Zusammenspiels Hardware / Betriebssystem
  • Folie 4
  • RW-SystemarchitekturKap. 8 4 Speicher Funktion Aufbewahrung fr Programme und Daten Organisation meist eine Hierarchie CPU-Register Speicher Befehle/Adressen/./Operanden Programm 1-8 Bytes Blcke Cache Controller 8-128 Bytes oben unten schnell, klein langsam, gro Cache Festplatte Seiten Betriebssystem 512-4K bytes Band Dateien Bnutzer/Operator Mbytes Inhalte/Struktur Besitzer/Verwalter Gre
  • Folie 5
  • RW-SystemarchitekturKap. 8 5 8.1 Anforderungen an die Speicherverwaltung Anforderungen an die Speicherverwaltung von der Betriebssystemseite Bereitstellung von Speicher fr Betriebssystem und Prozesse Ziel wg. Mehrprogrammbetrieb (Multiprogramming): Mglichst viele Prozesse im Speicher vorhanden Anforderungen nach Lister/Eager: Fundamentals of Operating Systems 1.Verlagerbarkeit (relocatability) 2.Schutz (protection) 3.Gemeinsame Nutzung (sharing) 4.Logische Organisation 5.Physikalische Organisation
  • Folie 6
  • RW-SystemarchitekturKap. 8 6 Verlagerung (relocation) Motivation: Mehrere Prozesse gleichzeitig im System Auslagern und Wiedereinlagern ganzer Prozesse aus dem Hauptspeicher ermglichen Ort der Einlagerung zum Zeitpunkt der Programmentwicklung / Programmbersetzung unbekannt! Bindung an alten Ort beim Wiedereinlagern sehr ungnstig! ) Problem: Speicherreferenzen innerhalb des Programms: Absolute Sprungbefehle Datenzugriffsbefehle
  • Folie 7
  • RW-SystemarchitekturKap. 8 7 Verlagerung (relocation) bersetzung der Speicherreferenzen im Programmcode in physikalische Speicheradressen durch Prozessorhardware Betriebssystemsoftware Ausnahme: Paging mit virtuellem Speicher (einfacher Fall ohne dynamisch gebundene Module) Prozesskontrollblock Programm Daten Beginn Prozesskontrollinformationen Einsprungstelle ins Programm Zunehmende Adresswerte Programmende Sprung- befehl Referenz auf Daten
  • Folie 8
  • RW-SystemarchitekturKap. 8 8 Schutz (Protection) Schutz von Prozessen gegen beabsichtigte oder unbeabsichtigte Strungen durch andere Prozesse berprfung aller Speicherzugriffe Schwierigkeit: Effektive Adresse (berechnet aus Registerinhalten und Offsets z.B. d(A n, I x ) ) nicht zur bersetzungszeit eines Programms berprfbar. Grund: effektive Adressen werden erst zur Ausfhrungszeit berechnet (dynamische) Verlagerung ) Dynamische berprfung ntig, braucht Hardwareuntersttzung, wird zusammen mit Verlagerung gelst.
  • Folie 9
  • RW-SystemarchitekturKap. 8 9 Gemeinsame Nutzung (Sharing) Gemeinsame Nutzung = kontrollierter Zugriff mehrerer Prozesse auf gemeinsam genutzte Bereiche des Speichers Anwendungsbeispiele: Ausfhrung des gleichen Programms durch eine Reihe von Prozessen ) Code nur einmal im Speicher Benutzung gemeinsamer Module (z.B. dynamisch gelinkte Bibliotheken) Kooperation von Prozessen ber gemeinsam genutzten Datenspeicher (shared memory)
  • Folie 10
  • RW-SystemarchitekturKap. 8 10 Logische Organisation Hauptspeicher ist lineares Feld von Bytes (Wrtern) Dagegen: Logischer Aufbau groer Programme: Sammlung verschiedener Module Unabhngig bersetzt; Referenzen erst zur Laufzeit aufgelst Verschiedene Module mit verschiedenem Schutz (z. B. nur lesen / ausfhren) Gemeinsame Nutzung von Modulen durch verschiedene Prozesse Z.B. auch dynamisch gebundene Bibliotheken Betriebssystem muss mit Modulen umgehen knnen. Programm A Programm B Code Daten schreib- geschtzt
  • Folie 11
  • RW-SystemarchitekturKap. 8 11 Physikalische Organisation Hier betrachtet: 2 Ebenen: Hauptspeicher (schnell, teuer, flchtig) Hintergrundspeicher (langsam, billig, nicht flchtig) Grundproblem: Organisation des Informationsflusses zwischen Haupt- und Sekundrspeicher Prinzipiell mglich: in Verantwortung des Programmierers Aufwndig, erschwert durch Mehrprogrammbetrieb (multiprogramming) Deshalb: Verwaltung durch das Betriebssystem Hauptspeicher Sekundrspeicher - Festplatte
  • Folie 12
  • RW-SystemarchitekturKap. 8 12 8.2 Grundlegende Methoden der Speicherverwaltung Partitionierung Fr Speicheraufteilung zwischen verschiedenen Prozessen eher veraltetes Konzept Betriebssysteminterne Nutzung von Partitionierung Paging Aufteilung des Adressraums in Seiten und virtuelle Adressen Kombiniert mit Seitenaustausch Segmentierung Einfache Segmentierung Kombiniert mit Konzept des virtuellen Speichers
  • Folie 13
  • RW-SystemarchitekturKap. 8 13 8.2.1 Partitionierung Partitionierung: Aufteilung des Speichers in Bereiche mit festen Grenzen Fester, zusammenhngender Teil des Hauptspeichers fr Betriebssystem Pro Prozess ein zusammenhngender Teil des Speichers Verschiedene Varianten: Statische Partitionierung Dynamische Partitionierung Buddy-Verfahren Probleme: Speicherverschnitt/Fragmentierung interne Fragmentierung innerhalb der zugeteilten Speicherbereiche externe Fragmentierung auerhalb der zugeteilten Speicherbereiche
  • Folie 14
  • RW-SystemarchitekturKap. 8 14 Statische Partitionierung (1) Einteilung des Speichers in feste Anzahl von Partitionen 2 Varianten: Alle Partitionen mit gleicher Lnge Partitionen mit unterschiedlicher Lnge Betriebssystem 8 Mbyte 8 Mbyte Betriebssystem 8 Mbyte 2 Mbyte 4 Mbyte 8 Mbyte 12 Mbyte 16 Mbyte 2 Mbyte
  • Folie 15
  • RW-SystemarchitekturKap. 8 15 Statische Partitionierung (2) Probleme: Programm zu gro fr Partition ) Programmerstellung mit Overlays ntig (aufwndig und fehleranfllig!) Interne Fragmentierung: Platzverschwendung, wenn Programm kleiner als Gre der zugeordneten Partition Fest vorgegebene Anzahl von Prozessen im Speicher Bei Laden von Prozessen in den Speicher: evtl. Auslagern von anderen Prozessen Zuweisung von Partitionen an Prozesse: Bei Bereichen mit gleicher Lnge: trivial Bei Bereichen mit variabler Lnge: Kleinste verfgbare Partition die gerade noch ausreicht? Wenn Speicherbedarf nicht feststellbar, dann helfen nur Overlays oder virtueller Speicher!
  • Folie 16
  • RW-SystemarchitekturKap. 8 16 Dynamische Partitionierung (1) Einteilung des Speichers in Partitionen variabler Lnge und variabler Anzahl Prozesse erhalten exakt passende Speicherbereiche Ein- und Auslagern fhrt zu externer Fragmentierung! (vgl. auch Kapitel Dateisysteme)
  • Folie 17
  • RW-SystemarchitekturKap. 8 17 Dynamische Partitionierung (2) BS, 8 MB 56 MB Prozess1 20 MB 36 MB BS, 8 MB Prozess1 20 MB 22 MB Prozess 2 14 MB Prozess 3 18 MB BS, 8 MB Prozess1 20 MB 4 MB Prozess 2 14 MB Prozess 3 18 MB BS, 8 MB Prozess1 20 MB 4 MB Prozess 3 18 MB BS, 8 MB Prozess1 20 MB 4 MB P. 4, 8 MB Prozess 3 18 MB BS, 8 MB 4 MB P. 4, 8 MB 20 MB Prozess 3 18 MB BS, 8 MB 4 MB P. 4, 8 MB Prozess 2 14 MB 6 MB
  • Folie 18
  • RW-SystemarchitekturKap. 8 18 Dynamische Partitionierung (3) Defragmentierung erforderlich! Aufwndig Speicherverdichtung nur erfolgreich, wenn dynamische Verlagerung mglich (Speicherreferenzen werden nicht ungtig!) Speicherzuteilungsalgorithmen: Best Fit: Suche kleinsten Block, der ausreicht First Fit: Suche beginnend mit Speicheranfang bis ausreichender Block gefunden Next Fit: Suche beginnend mit der Stelle der letzten Blockzuweisung
  • Folie 19
  • RW-SystemarchitekturKap. 8 19 Dynamische Partitionierung (4) Analyse von Speicherzuteilungsalgorithmen: Im Schnitt ist First Fit am besten! Next Fit: Etwas schlechter Typischer Effekt: Schnelle Fragmentierung des grten freien Speicherblocks am Ende des Speichers Best Fit: Am schlechtesten Produziert schnell eine Reihe von sehr kleinen Fragmenten, die ohne Defragmentierung nie mehr benutzt werden knnen Zudem: langsames Verfahren
  • Folie 20
  • RW-SystemarchitekturKap. 8 20 Buddy-System (1) Nachteil statische Partitionierung: Beschrnkte Anzahl nicht-ausgelagerter Prozesse Interne Fragmentierung Nachteil dynamische Partitionierung: Defragmentierung ntig wegen externer Fragmentierung Buddy-System (Halbierungsverfahren): Kompromiss zwischen statischer und dynamischer Partitionierung Eigenschaften: Anzahl nicht-ausgelagerter Prozesse dynamisch Interne Fragmentierung beschrnkt Keine explizite Defragmentierung
  • Folie 21
  • RW-SystemarchitekturKap. 8 21 Buddy-System (2) Prinzip: Verwalte Speicherblcke der Gre 2 K, L K U, ausgerichtet an nx 2 K -Grenzen 2 L = Gre des kleinsten zuteilbaren Blocks 2 U = Gre des grten zuteilbaren Blocks (z.B. Gesamtgre des Speichers) Zu Beginn: Es existiert genau ein Block der Gre 2 U. Anforderung eines Blocks der Gre s: Bei 2 U-1 < s 2 U : Weise gesamten Speicher zu Sonst: Teile auf in 2 Blcke der Gre 2 U-1 Bei 2 U-2 < s 2 U-1 : Weise einen der beiden Blcke zu Sonst: Whle einen der beiden Blcke aus und teile Fahre fort bis zu Block der Gre 2 K mit 2 K-1 < s 2 K Bei resultierendem Block ist der Verschnitt kleiner als die halbe Blockgre
  • Folie 22
  • RW-SystemarchitekturKap. 8 22 Buddy-System (3) Verwalte f.a. L K U Listen mit freien Blcken der Gre 2 K Allgemeiner Fall: Anforderung eines Blocks der Gre 2 i-1 < s 2 i : Vergebe Block aus Liste i, wenn vorhanden Sonst: Whle Block aus nchst grerer nichtleerer Liste Teile rekursiv auf, bis ein Block der Gre 2 i vorhanden Wenn nach Freigabe eines Blocks der Gre 2 K der entsprechende Partnerblock der Gre 2 K ebenfalls frei war: Verschmelze die Blcke zu einem Block der Gre 2 K+1 Mache rekursiv mit Verschmelzen weiter
  • Folie 23
  • RW-SystemarchitekturKap. 8 23 Buddy-System (4) Beispiel: Speicher der Gre 1 GB Folge von Anforderungen und Freigaben: A fordert 100 MB an. B fordert 240 MB an. C fordert 64 MB an. D fordert 256 MB an. Freigabe B Freigabe A E fordert 75 MB an. Freigabe C Freigabe E Freigabe D 1 GB
  • Folie 24
  • RW-SystemarchitekturKap. 8 24 Buddy-System (5) 1 GB
  • Folie 25
  • RW-SystemarchitekturKap. 8 25 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 1 256 MB: 1 128 MB: 1 64 MB: 0 Es folgt Anforderung B: 240 MB, d.h. Block der Gre 256 MB. A:128MB Nach Anforderung A: 100 MB, d.h. Block der Gre 128 MB:
  • Folie 26
  • RW-SystemarchitekturKap. 8 26 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 1 256 MB: 0 128 MB: 1 64 MB: 0 Nach Anforderung B: 240 MB, d.h. Block der Gre 256 MB. Es folgt Anforderung C: 64 MB, d.h. Block der Gre 64 MB. A:128MB B:256MB
  • Folie 27
  • RW-SystemarchitekturKap. 8 27 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 1 256 MB: 0 128 MB: 0 64 MB: 1 Nach Anforderung C: 64 MB, d.h. Block der Gre 64 MB. Es folgt Anforderung D: 256 MB, d.h. Block der Gre 256 MB. A:128MB B:256MB C:64MB
  • Folie 28
  • RW-SystemarchitekturKap. 8 28 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 0 256 MB: 1 128 MB: 0 64 MB: 1 Nach Anforderung D: 256 MB, d.h. Block der Gre 256 MB. Es folgt Freigabe B. A:128MB B:256MB C:64MB D:256MB
  • Folie 29
  • RW-SystemarchitekturKap. 8 29 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 0 256 MB: 2 128 MB: 0 64 MB: 1 Nach Freigabe B : Es folgt Freigabe A. A:128MB C:64MB D:256MB
  • Folie 30
  • RW-SystemarchitekturKap. 8 30 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 0 256 MB: 2 128 MB: 1 64 MB: 1 Nach Freigabe A: Es folgt Anforderung E: 75 MB, d.h. Block der Gre 128 MB.. C:64MB D:256MB
  • Folie 31
  • RW-SystemarchitekturKap. 8 31 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 0 256 MB: 2 128 MB: 0 64 MB: 1 Nach Anforderung E: 75 MB, d.h. Block der Gre 128 MB: Es folgt Freigabe C.. C:64MB D:256MB E:128MB
  • Folie 32
  • RW-SystemarchitekturKap. 8 32 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 0 256 MB: 2 128 MB: 0 64 MB: 2 Bei Freigabe C: D:256MB E:128MB Buddies
  • Folie 33
  • RW-SystemarchitekturKap. 8 33 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 0 256 MB: 2 128 MB: 1 64 MB: 0 Nach Freigabe C : Es folgt Freigabe E.. D:256MB E:128MB
  • Folie 34
  • RW-SystemarchitekturKap. 8 34 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 0 256 MB: 2 128 MB: 2 64 MB: 0 Bei Freigabe E : D:256MB Buddies
  • Folie 35
  • RW-SystemarchitekturKap. 8 35 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 0 256 MB: 3 128 MB: 0 64 MB: 0 Bei Freigabe E : D:256MB Buddies
  • Folie 36
  • RW-SystemarchitekturKap. 8 36 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 1 256 MB: 1 128 MB: 0 64 MB: 0 Nach Freigabe E : D:256MB Es folgt Freigabe D..
  • Folie 37
  • RW-SystemarchitekturKap. 8 37 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 1 256 MB: 2 128 MB: 0 64 MB: 0 Bei Freigabe D : Buddies
  • Folie 38
  • RW-SystemarchitekturKap. 8 38 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 0 512 MB: 2 256 MB: 0 128 MB: 0 64 MB: 0 Bei Freigabe D : Buddies
  • Folie 39
  • RW-SystemarchitekturKap. 8 39 Buddy-System (5) 1 GB Freie Blcke: 1 GB: 1 512 MB: 0 256 MB: 0 128 MB: 0 64 MB: 0 Nach Freigabe D : Gesamter Speicher wieder als 1 Block verfgbar.
  • Folie 40
  • RW-SystemarchitekturKap. 8 40 8.2.2 Verlagerung (1) Nach Aus- und Wiedereinlagern von Prozessen liegen Programmcode bzw. Daten an anderer Stelle. Absolute Sprungbefehle und Datenzugriffsbefehle sollen weiterhin funktionieren. Unterscheidung: Logische Adresse: Bezug auf eine Speicherstelle unabhngig von der aktuellen Zuteilung von Daten im Speicher Relative Adresse: Spezialfall einer logischen Adresse Adresse relativ zu einem bekannten Punkt (meist Programmanfang) ausgedrckt Physikalische bzw. absolute Adresse: konkrete Stelle im Hauptspeicher
  • Folie 41
  • RW-SystemarchitekturKap. 8 41 Verlagerung (2) Berechnung von absoluten Adressen aus relativen Adressen durch Hardware. Beim Einlagern eines Prozesses: Adresse des Programmanfangs in Basisregister. Zustzlich: Zur Realisierung von Speicherschutz enthlt Grenzregister die hchste erlaubte Speicheradresse eine Schtzmanahme gegen Pufferberlauf (buffer overflow)
  • Folie 42
  • RW-Sy...

Recommended

View more >