Kapitel 6 SPEICHERVERWALTUNG [KMS] Sommer 2015 Speicherverwaltung 1 Ziele dieses Kapitels ² Neben der CPU ist der Speicher das wichCgste BetriebsmiEel eines Prozesses ² Dieses BM muss verwaltet werden – wir lernen in diesem Kapitel die für Speicher spezialisierten Verwaltungsmöglichkeiten kennen ª ª ² Hierzu werden geeignete Adressierungsarten benöCgt WichCg: Trennen der Mechanismen von Strategien Zusätzlich: Weiteres Beispiel für Virtualisierung – transparentes Ersetzen eines BetriebsmiEels durch ein anderes [KMS] Sommer 2015 Speicherverwaltung 2 Überblick ² Speicher und Prozess ª ª ª ² ² ² ² Außensicht: Speicher als BetriebsmiEel Reale vs. logische Adressen, Virtualisierung Innensicht eines Prozesses Speicherverwaltung Virtueller Speicher Speicherhierarchie Anhang: Laden und Binden eines Programms [KMS] Sommer 2015 Speicherverwaltung 3 Wiederholung Prozess (aus Kapitel 2) ² Prozess ist definiert durch ª ª ª ² Verarbeitungsvorschri_ (Programm) AkCvitätsträger Hier behandelt! Adressraum Prozess: LOAD X STORE Y LOAD Z Adressraum (AR) eines Prozesses: ª Eine Menge gül8ger Adressen, auf die der Prozess lesend/schreibend zugreifen darf § Bei Zugriff auf andere Adressen: Fehler ª ² Adressraum (AR) eines Rechners: ª ² O_, aber nicht notwendigerweise, zusammenhängend CPU Menge der vorhandenen, eindeuCg adressierbaren Speicherstellen Zusammenhang dieser beiden Sichtweisen?? Speicher 0 [KMS] Sommer 2015 Speicherverwaltung n-1 4 Zuordnung AR Prozess ↔ AR Rechner: OpOon ² Einfachste Möglichkeit: 1:1 Zuordnung ª ª ² Jede Prozess-‐Adresse entspricht direkt einer Maschinen-‐Adresse Und umgekehrt Akzeptabel, wenn Nur genau ein Prozess exisCert, und ª Prozess in den Speicher passt, also keine Adressen ansprechen will, die außerhalb des realen Speichers liegen ª ² ProblemaCsch, wenn ª ª Mehrere Prozesse exisCeren, oder Prozesse passen nicht in realen Speicher [KMS] Sommer 2015 Speicherverwaltung 5 1:1 Zuordnung, mehrere Prozesse? ² Bei einer 1:1 Zuordnung: Wie unterstützt man mehrere Prozesse, die den Speicher benutzen wollen? ² Idee 1: Analog zu Scheduling, Speicher als 1-‐Exemplar-‐ BetriebsmiEel auffassen und zeitweise an unterschiedliche Prozesse zuteilen Prozess 1 bekommt für besCmmte Zeit gesamten Speicher zugeteilt, danach entzogen und an Prozess 2 zugeteilt, etc. ª Problem: Was passiert mit Speicherinhalt von Prozess 1, während Prozess 2 realen Speicher nutzt? ª Muss anderswo aujewahrt werden – z.B. Hintergrundspeicher ª § Analog zu CPU Registern bei Prozesswechsel! à Swapping [KMS] Sommer 2015 Speicherverwaltung 6 1:1 Zuordnung, mehrere Prozesse? ² à Idee 2: Eigentlich ist Speicher doch ein Mehrexemplar-‐BetriebsmiEel (Speicherstellen!) Also auch als solches verwalten! ª ª ª Unterschiedlichen Prozessen werden unterschiedliche Bereiche des Speichers zugeteilt BenöCgt Auswahlstrategie, welcher Prozess welchen Speicher bekommt – siehe später Annahme: Prozesse passen alle gleichzeiCg in Speicher Adressen der Prozesse Reale 0 Adressen [KMS] Sommer 2015 Woher? 17 18 19 4711 4712 4713 Prozess 1 Prozess 2 17 18 19 4711 4712 4713 Speicherverwaltung n-1 7 Absolute reale Adressen in Prozessen? ² Woher weiß ein Prozess, welche absoluten Werte der realen Adressen er verwenden soll? ª ² Ein Prozess wird immer an der gleichen Stelle gestartet? ! Kaum prakCkabel, nimmt der BM-‐Verwaltung viel Freiraum Lösung: Programm umschreiben Programm wird aufgeschrieben, als würde es ab Adresse 0 ausgeführt ª Beim Start eines Programms – also beim Erzeugen des Prozesses – werden die im Programm benutzten, logischen Adressen auf die tatsächlichen realen Adressen umgeschrieben ª § Reloka8on, benutzt ein Reloka8onswörterbuch Programm: LOAD 0 STORE 1 LOAD 2 [KMS] Sommer 2015 Umschreiben Speicherverwaltung Prozess: LOAD 17 STORE 18 LOAD 19 8 Zusammenfassung: reale/logische Adressen 1:1 ² Zusammenfassung: Gleichsetzen von realen Adressen und durch Prozesse benutzte Adressen prinzipiell möglich Erfordert Swapping und/oder RelokaCon für Mehrprozessbetrieb ª Prozess muss beim Start eine geeignete Par88on finden ª RelokaCon beim Programmstart verhindert (z.B.) Umlagern von Prozessen im Speicher, wenn Platz knapp wird ª Prozess 1 Prozess 2 P3 ² Prozess 1 Prozess 2 ? AlternaCve: Trennen der Werte dieser unterschiedlichen Adressen! ª Unterscheide zwischen realen und logischen Adressen [KMS] Sommer 2015 Speicherverwaltung 9 Trennen realer und logischer Adressen ² Idee: Erlaube beliebige Werte für logische Adressen, unabhängig von Werten der zugehörigen realen Adressen Logisch! Logische Adressen Reale Adressen 0 ² ² 0 1 2 0 1 2 Prozess 1 Prozess 2 17 18 19 4711 4712 4713 n-1 Vorteil: Keine RelokaCon beim Programmstart notwendig Realisierung: Umrechnen von logischen in reale Adressen ª ª Indirek8on Zur Laufzeit, bei jedem Speicherzugriff [KMS] Sommer 2015 Speicherverwaltung 10 Speichersicht eines Prozesses ² Damit: Prozessen sind nur die logischen Adressen bekannt ª ² Kennt (normalerweise) keine physikalischen Adressen Prozess hat Vorstellung, ihm „gehört“ der gesamte Speicher ª ª Es gibt keine anderen Prozesse, die ebenfalls Speicher belegen Speicher wurde virtualisiert Logische Adressen eines Prozesses 0L maxL ª Nicht immer sind alle möglichen logischen Adressen auch legaler logischer Adressraum à siehe später [KMS] Sommer 2015 Speicherverwaltung 11 Speichersicht des Betriebssystems ² Damit: Betriebssystem sieht realen Speicher als durch einzelne Prozesse belegt Realer Speicher Belegt durch Prozess P1 ² Belegt durch Prozess P2 Muss ein Prozess in einem Stück im realen Speicher liegen? Kann man in mehrere Teile au_eilen? Realer Speicher Belegt durch Prozess P1 [KMS] Sommer 2015 Speicherverwaltung Belegt durch Prozess P2 12 „Gestreute Speicherung“ eines Prozesses ² Es ist möglich und sinnvoll, einen Prozess auch „gestreut“ im realen Speicher (nicht nur im zusammenhängenden Block) abzulegen Sinnvoll: Erhöhte Flexibilität bei der Verwaltung des BetriebsmiEels „Speicher“, feinere Granularität ª Aus Effizienzgründen: Nicht für logische Adresse einzeln, sondern in ganzen Gruppen/Blöcken/Seiten/… ª Einheit der Speicherverwaltung von fester / flexibler Länge ª § Feste Länge: Seiten § Flexible Länge: Segmente ² Zuordnung logische à reale Adresse wird komplizierter Festhalten, welche logische Adresse in welchen realen Teil abgebildet wird ª Beispiel hier: Seiten mit Seitentabellen ª [KMS] Sommer 2015 Speicherverwaltung 13 Abbildung logische à reale Adressen: Seiten ² ª ² 0 1 2 0 1 : The image part with relationship ID rId3 was not found in the file. Wenn Prozess auf logische Seitentabelle [Seitennummer] Adresse zugrei_, wird Prozess 2 zunächst in reale Adresse umgerechnet 0 Seitentabelle: Gibt reale Anfangsadresse für jeden Seitenanfang an ª ² Prozess 1 Jeder logischen Adresse wird eine reale Adresse zugeordnet Für jeden Prozess separat 1 Seitentabelle Speicherverwaltung organisiert Einträge Offset Seitennummer Bitmuster der logischen Adresse max-1 Logische Adresse Seitentabelle [Seitennummer] [KMS] Sommer 2015 Reale Adresse Speicherverwaltung Offset 14 0 1 2 : Abbildung logische à reale Adressen: Seiten, formal ² Gegeben: ª ª ª ² Maximale realer Speichergröße 2k Einheiten Maximale logisch Speichergröße 2n Einheiten (z.B. Bytes) Seiten der Größe 2m Einheiten Daraus folgt: ª ª ª ª Länge der realen Adressen: 2k Bits 2n Bits Länge der logisch Adressen: Maximale Anzahl Einträge in Seitentabelle: 2 n/2m = 2n-‐m Rechenvorschri_ logisch à real: § Seitennummer = LogAdr % 2m • (Die ersten Bits bis auf die letzten m) § Offset = LogAdr mod 2m • (Die letzten m Bits) § R = Seitentabelle[Seitennummer] * 2m + Offset [KMS] Sommer 2015 Speicherverwaltung 15 Abbildung logische à reale Adressen: MMU ² Umrechnung logischer in reale Adressen (typischerweise) durch eine eigene FunkConseinheit verwirklicht Memory Management Unit (MMU) ª Überwachung von Zugriffsrechten – darf auf eine besCmmte logische Adresse der gewünschte Zugriff (lesen, schreiben, ausführen) überhaupt erfolgen? ª Melden von Zugriffsverletzungen an den Prozessor ª CPU Logische Reale ArbeitsMMU Adressen Adressen speicher Prozess-ID [KMS] Sommer 2015 Speicherverwaltung Seitentabelle des zugreifenden Prozesses 16 Zusammenfassung: Seitenzugriff bei Paging Copyright © 2009 by Jerome H. Saltzer and M. Frans Kaashoek. Fig. 5.20 in Principles of Computer System Design [KMS] Sommer 2015 Speicherverwaltung 17 Speicherschutz Prozesse sollen wechselseitigen Schutz vor Speicherzugriffen sicherstellen. Ist dies gegeben bei a) Relozierender Prozessausführung b) Speicherzugriff mit Seitentabellen? Wie kann man Seitentabellen nutzen/manipulieren, um Speicherschutz zu umgehen? [KMS] Sommer 2015 Speicherverwaltung 18 Größe der Seitentabellen ² Beispiel: Typische PC-‐Systeme ª ª ª ª ª Realer Hauptspeicher: 4 GB Virtueller Speicher eines Prozesses = 2 GB = 2 x 230 Bytes Größe einer Seite: 4 kB = 4 x 210 Bytes Anzahl Einträge = 231 Bytes / 212 Bytes = 219 Größe eines Eintrages in Seitentabelle: § § § § 19 bits pro logische Adresse 20 bits pro physikalische Adresse ein paar Bits für Verwaltung => Insgesamt: 6 Bytes Gesamtgröße Speichertabelle PRO PROZESS: 6 x 219 = 3 MB! ª Typisch 50 – 100 Prozesse => 150 – 300 MB nur für Speichertabellen! ª [KMS] Sommer 2015 Speicherverwaltung 19 Verkleinerung Seitentabellen ² Idee 1: Nur tatsächlich benutzte Seiten bekommen Eintrag in Tabelle ª ² Möglich, aber Verwaltung der Tabelle kompliziert – wie speichern für schnellen Zugriff? Idee 2: Hierarchie von Seitentabellen einführen (Standardidee für InformaCker J) ª Unterteile logische Adresse in zwei Teile ª Erster Teil grei_ auf eine „root page table“ zu ª Darin steht Adresse einer kleineren Page Table; zweiter Teil der logischen Adresse ist Offset in dieser zweiten Tabelle ª Eigentliche Adresse wird aus dieser zweiten Tabelle entnommen, mit offset der logischen Adresse wie üblich ª [KMS] Sommer 2015 Speicherverwaltung 20 Verkleinerung Seitentabellen ² Idee 3: InverCerte Seitentabelle Ansätze bisher: Größe der Seitentabelle proporConal zur Anzahl Seiten im virtuellem Adressraum und Anzahl Prozessen ª AlternaCve: Ein Eintrag in Seitentabelle pro Kachel (Seite im realen Adressraum) ª Problem: wie findet man von logischer Adresse zur zugehörigen Kachel? ª Idee: Hash-‐FunkCon! Die Kachel einer Seite wird als Hash-‐Wert der Seitennummer ausgerechnet ª § Schließlich ist eine Seitentabelle ja nur eine AbbildungsfunkCon, also kann man auch gleich eine Abbildung nehmen... ª Verbleibendes Problem: Was ist mit Hash-‐Kollisionen? § Die muss man in inver3erter Seitentabelle auflösen § Dort muss jetzt auch die Prozessnummer stehen; es gibt ja nur noch eine Tabelle! [KMS] Sommer 2015 Speicherverwaltung 21 InverOerte Seitentabelle Stallings, Operating Systems, 6. Auflage [KMS] Sommer 2015 Speicherverwaltung 22 Überblick ² Speicher und Prozess ª ª ª ² ² ² ² Außensicht: Speicher als BetriebsmiEel Reale vs. logische Adressen, Virtualisierung Innensicht: Von Programm zu Prozesses Speicherverwaltung Virtueller Speicher Speicherhierarchie Anhang: Laden und Binden eines Programms [KMS] Sommer 2015 Speicherverwaltung 23 Von Programm zu Prozess ² Ein ausführbares Programm muss enthalten ª ª ² Programmcode an sich Daten zur IniCalisierung Prozess enthält ª ª ª Programmcode und Daten zur IniCalisierung Heap und Stack ProzesskontrollinformaCon (oder auch im Kernel abgelegt) Prozesskontrollblock (PCB) [KMS] Sommer 2015 Programm Statische Daten Programm Statische Daten Speicherverwaltung Prozess erzeugen Dynamische Daten (Heap) Laufzeitkeller (Stack) 24 OrganisaOon von Adressräumen aus Prozesssicht ² Im Adressraum stehen alle für die Prozessausführung benöCgten Daten in einer typischen Anordnung ª ª Programmcode: Alle Maschinenbefehle Datenbereich: Alle notwendigen Variablen und Konstanten § StaCscher Bereich: Zur Startzeit bekannte und iniCalisierte Daten § Dynamischer Bereich (Heap): Datenstrukturen, die während der Laufzeit angelegt werden, z.B. durch malloc() in C, new() in C++ oder allgemein allocate_mem() PCB ª Laufzeitkeller (Stapel, Stack): AutomaCsche Variablen, die beim Aufruf von Prozeduren/Unterprogrammen zur Parameterübergabe und Ergebnisrückgabe angelegt werden Programm Niedrige logische Adresse [KMS] Sommer 2015 Statische Daten Dynamische Daten Nicht vorhandener Speicherverwaltung logischer Adressbereich Laufzeitkeller Hohe logische Adresse 25 Wachstum von Heap und Stapel ² ² Größe von Code/staCschen Daten konstant während Ausführung Größe des dynamischen Bereichs ändert sich zur Laufzeit Heap: Zusätzliche Variablen/Datenstrukturen werden angelegt ª Stapel: Größe abhängig von Verschachtelung bei FunkConsaufrufen, Anzahl/Art von Eingabeparametern, … ª ² Geeignete BesCmmung des Abstands zwischen Heap und Stapel sehr schwierig, o_ gar unmöglich ª ª Noch schwieriger bei mehreren Threads (Ein Stapel pro Thread) PCB ² Abstand möglichst groß, damit keine Überscheidung vorkommt Vorhandenen Speicherplatz möglichst effizient nutzen [KMS] Sommer 2015 Programm Statische Daten Speicherverwaltung Dynamische Daten Keller 1 Keller n 26 Wie bekommt ein Prozess mehr logischen Speicher? PCB ² Wenn dynamischer Speicher angefordert wird, müssen zuvor illegale logische Adressen in legale logische Adressen umgewandelt werden Programm PCB Anfrage Statische Daten ² Dynamische Daten Programm Statische Daten Laufzeitkeller Dynamische Daten Laufzeitkeller Prozess fragt Speicherverwaltung nach zusätzlichem Speicher – diese klinkt zusätzliche Adresse ein, macht dies der MMU bekannt [KMS] Sommer 2015 Speicherverwaltung 27 Gefundenen Speicher Prozess zur Verfügung stellen ² ² SituaCon: Speicherverwaltung hat auf Speicheranfrage eines Prozesses freien realen Speicher gefunden Dieser muss dem Prozess zur Verfügung gestellt werden ª In die Seitentabelle eintragen The image part with relationship ID rId3 was not found in the file. maxL maxL 0L Anfrage Bestätigung Speicherverwaltung ² Freigabe von Speicher analog [KMS] Sommer 2015 Speicherverwaltung Prozess 1 0 1 2 3 Seitentabelle max-1 28 Physikalischer Speicher Logische Adressen Prozesses Neu ? Logische Adressen eineseines Prozesses 0 1 : Offene Fragen ² Wie funkConiert die Speicherverwaltung an sich? ª ª ² Wie wird freier Speicher gefunden, wenn angefordert? Wie wird Speicher freigegeben? Was passiert, wenn bei einer solchen Speicher-‐ anforderung der physikalische Speicher belegt ist? [KMS] Sommer 2015 Speicherverwaltung 29 Überblick ² ² Speicher und Prozess Speicherverwaltung ª ª ª ª ² ² ² Aufgabe Datenstrukturen VerschniE Auswahlstrategien Virtueller Speicher Speicherhierarchie Anhang: Laden und Binden eines Programms [KMS] Sommer 2015 Speicherverwaltung 30 Speicherverwaltung ² Speicherverwaltung ª ª Teil eines Betriebssystems Physikalischer Speicher als BetriebsmiEel aufgefasst, verwaltet § Mehrexemplar, wiederverwendbar, begrenzt, real ª ² OperaConen ª ª ª ² Nicht nur Arbeitsspeicher, z.B. auch Sektoren auf PlaEen, Teile von Bändern (Backup-‐Systeme) etc. werden ähnlich verwaltet Belegen von freiem Speicher durch einen Prozess Freigeben belegten Speichers durch einen Prozess „VermiElung“ zwischen logischem und physikalischem Speicher Notwendig ª ª ª Datenstrukturen zur Darstellung der BelegungssituaCon Algorithmen zur Belegung/Freigabe IntegraCon mit Prozessbeschreibung [KMS] Sommer 2015 Speicherverwaltung 31 Datenstruktur zur Belegungsdarstellung ² Wie werden Speicherkacheln/-‐segmente als frei/belegt markiert? ª Bit signalisiert Status frei 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 ª belegt Tabellendarstellung § Freie SpeicherabschniEe werden in einer Tabelle zusammengefasst § SorCerung etwa nach Adresse oder Länge der freien AbschniEe Adresse Länge 9 7 19 3 24 1 [KMS] Sommer 2015 Speicherverwaltung Länge Adresse 1 24 3 19 7 9 32 Verkeaete Darstellung ² Jedes freie Segment enthält folgende Angaben ª ª ª ² Länge des Segments selbst Verweis auf das nächste freie Segment Freier Speicher enthält VerwaltungsinformaCon über sich selbst SorCerung nach Adresse 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ² SorCerung nach Länge 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [KMS] Sommer 2015 Speicherverwaltung 33 SpeicherfragmenOerung ² Zerstückelung des Speichers (FragmenCerung, VerschniL) ist ein allgemeines Problem der Speicherverwaltung ª ª Interner VerschniL: Nicht benutzter Speicher innerhalb einem Prozess zugeteilter Speicherbereiche Externer VerschniL: Zu kleine Segmente können für die aktuelle Anforderung nicht belegt werden. Insgesamt (Summe aller freien Segmente) ist jedoch genug Speicher für die Anforderung vorhanden Physikalischer Speicher Neue Anfrage Frei, aber nicht belegbar (externer Verschnitt) Belegt, aber ungenutzt durch P1 (interner Verschnitt) Belegt und benutzt Speicherplatz belegt durch den Prozess P1 [KMS] Sommer 2015 Speicherverwaltung 34 DefiniOonen zum Verschnia ² Absoluter interner VerschniE f int −abs = Größe des belegten, aber nicht genutzten Speichers ² Verhältnisgrößen ª Interner VerschniE Größe des belegten, aber nicht genutzten Speichers f int = Größe des belegten Speichers § Kann ein konkreter Wert oder ein Erwartungswert sein ª Externer VerschniE Größe des freien, aber nicht belegbaren Speichers f ext = Größe des belegten Speichers ª Auslastung η= [KMS] Sommer 2015 Größe des belegten Speichers Größe des gesamten Speichers Speicherverwaltung 35 Überblick ² ² Speicher und Prozess Speicherverwaltung ª ª ª Aufgabe Datenstrukturen VerschniE Auswahlstrategien Virtueller Speicher Speicherhierarchie Anhang: Laden und Binden eines Programms ª ² ² ² [KMS] Sommer 2015 Speicherverwaltung 36 Auswahlstrategien ² Gegeben ª ª ² Gesucht ª ª ² Freier Speicherplatz, der diese Anfrage erfüllt Oder: Antwort, dass nicht möglich OpCmierungsziele ª ª ² Anfrage nach Speicher Aktuelle BelegungssituaCon des realen Speichers Geringer VerschniE (intern? extern?) Geringer Aufwand des Algorithmus (Laufzeit) Beispiel für BetriebsmiEelverwaltung! ª Ähnliche Strategien einsetzbar [KMS] Sommer 2015 Speicherverwaltung 37 Auswahlstrategien – einfache Beispiele ² First Fit: Durchlaufe die nach Adressen sorCerte Liste mit freien Segmenten und belege das erste Segment ausreichender Größe ª ª ² Next Fit, RotaOng First Fit: Analog zu First-‐Fit, die Suche beginnt allerdings beim letzten belegten Segment ª ª ª ² Geringer Suchaufwand, aber hoher externer VerschniE KonzentraCon belegter Segmente am Anfang ⇒ Hoher Suchaufwand durch viele unpassende, kleine Segmente am Anfang Zyklisches Durchlaufen der Liste Keine KonzentraCon der belegten Segmente am Listenanfang Verkürzung der Suchzeiten Nearest Fit: Eine gewünschte Adresse für die Belegung wird übergeben ⇒ Von da aus First-‐Fit-‐Suche ª ª Minimierung der Armbewegungen bei FestplaEen GünsCge PosiConierung o_ benöCgter Daten, wie z.B. Dateikataloge [KMS] Sommer 2015 Speicherverwaltung 38 Auswahlstrategien (2) ² Best Fit: Belege das kleinste, aber hinreichend große Stück ² Worst Fit: Suche und belege das größte freie Speicherstück ⇒ Möglichst großes Reststück noch vorhanden ² Quick Fit: Extraliste für häufig vorkommende Belegungen ⇒ schnelleres Auffinden passender Freistellen ª ª ² Werden z.B. regelmäßig Nachrichten der Länge 1 KB verschickt, wird eine Extraliste für 1-‐KB-‐Belegungen geführt Solche Anfragen werden schnell und ohne VerschniE erfüllt Buddy Systeme (Erweiterung von QuickFit) ª ª Für mehrere Belegungsgrößen – Speicher in den Größen von Zweierpotenzen – wird eine eigene Liste angelegt Paarweise BesCmmung von Segmenten ⇒ Schnelle/einfache Verschmelzung freier Bereiche [KMS] Sommer 2015 Speicherverwaltung 39 Auswahlstrategien: Beispiel Gegeben Speicherbelegung (1-1-2-1-3-1-5-1-8-1): Letzte zugeteilte Anforderung Folge von Speicheranforderungen: 2, 3, 5, 7 Zeigen Sie die zugeteilten Speicherbereiche für Next Fit: Best Fit: [KMS] Sommer 2015 Speicherverwaltung 40 Halbierungsverfahren (Buddy-‐System) ² ² Speicherverwaltung in früheren Versionen von Linux Speicher besteht aus 2max Einheiten Vergabe von Speicherstücken der Größe 20, 21,…,2max ª Aufrundung aller Anforderungen auf die nächste Zweierpotenz ª Ist kein freier Block der Größe 2k vorhanden, so wird ein freies Speicherstück der Größe 2k+1 in zwei Stücke von je 2k Byte aufgeteilt ª Die beiden Stücke heißen Partner (buddy) und sind genau gekennzeichnet ª § Die Anfangsadressen sind idenCsch bis auf das k-‐te Bit in ihrer Adresse, das inverCert ist § Dadurch schnelle Überprüfung möglich: ExisCert zu einem freien Block ein ebenfalls freier Buddy. Falls ja ⇒ Verschmelzung [KMS] Sommer 2015 Speicherverwaltung 41 Ablauf Anforderung/Freigabe (im Buddy-‐System) ² Ablauf Anforderung ª ª ª Aufrunden auf nächste Zweierpotenz Zugriff auf erstes freies Stück der Liste Falls Liste leer (rekursiv) § § § § ² Zugriff auf Liste der nächsten Größe Stück en‚ernen Stück halbieren Hintere Häl_e an entsprechende Liste anhängen Ablauf Freigabe ª ª ª Buddy besCmmen Falls Buddy belegt, freigewordenes Stück an die Liste anhängen Falls Buddy frei § Vereinigung mit Buddy § IteraCon, bis Buddy belegt oder maximale Größe erreicht [KMS] Sommer 2015 Speicherverwaltung 42 Beispiel zu Buddy-‐System ² Gegeben ª ª ª Speichergröße 64 Einheiten Anforderungen: A1:7 (Aufrundung 8) A2:6 (8) A3:3 (4) Freigabe: A2, A1 32 32 32 32 64 32 [KMS] Sommer 2015 32 32 32 8 8 8 16 16 16 16 8 8 8 8 8 8 A1 A2 A3 Speicherverwaltung 4 4 8 8 4 4 4 4 16 43 Interner Verschnia beim Buddy-‐Verfahren ² Vorteile des Buddy-‐Verfahrens ª ª ª ² ² Schnelle OperaConen Anpassung an das Anforderungsprofil Nach Einschwingen wenig Teilungs-‐ und Vereinigungsvorgänge Nachteil: RelaCv hoher interner VerschniE Verdeutlichung am Beispiel (Herleitung siehe folgende Folien) ª ª ª ª Anforderungsgröße a: 1 2 3 4 5 6 7 8 9 10 … Größe des belegten Stücks b(a): 1 2 4 4 8 8 8 8 16 16 … pa: Wahrscheinlichkeit, dass eine Anforderung Größe a besitzt a max Interner VerschniE fint ∑ p a (b (a ) − a ) f int = a =1a = 0.25, d .h . 25% max ∑ p a b (a ) a =1 [KMS] Sommer 2015 Speicherverwaltung 44 Interner Verschnia beim Buddy-‐Verfahren ² InterpretaCon a max ª S b : = p a b ∑ a =1 a max ª S : = p a ª ² ² ∑ a =1 a (a ) a Erwartungswert für Belegungsgröße b Erwartungswert für Anforderungsgröße a VerschniE: fint = 1 –Sa/Sb Annahme einer Gleichverteilung im Intervall [1,2n] ⇒ jede Anforderung hat gleiche Wahrscheinlichkeit pa=1/2n ApproximaCve Berechnung miElerer Anforderungsgröße 1 Sa = n 2 [KMS] Sommer 2015 2n ( ) 1 2n 2n + 1 1 n −1 n −1 i = = 2 + ≈ 2 ∑ 2 2 2n i =1 Speicherverwaltung 45 Interner Verschnia beim Buddy-‐Verfahren ² VerschniE durch Aufrundung 1 Sb = n 2 ⎛ ⎞ ⎜1 + 2 + 4 + 4 + 8 + 8 + 8 + 8 + … + 2n + … + 2n ⎟ = 1 1 + 1 ⋅ 2 + … + 2n −12n $!# ! !" ! ⎟ 2n ⎜ n −1 2 mal ⎝ ⎠ n −1 1 ⎛ 1 ⎛ 22n − 1 ⎞ 1 22n +1 + 1 2n +1 2i ⎞ ⎟⎟ = n = n ⎜⎜1 + 2∑ 2 ⎟⎟ = n ⎜⎜1 + 2 2 ≈ 3 3 2 ⎝ 2 − 1 ⎠ 2 i =0 ⎠ 2 ⎝ ² ² ( Ergebnis: S a S b = 2n −1 Folgerung ( 1 3 ) 2n +1 = 3 4 Zugeteilte Stücke sind im MiEel um ein Viertel größer als angefordert ª Belegte Stücke werden im MiEel nur zu 3/4 genutzt ª Interner VerschniE beträgt fint = 25% ª [KMS] Sommer 2015 Speicherverwaltung 46 ) Überblick ² ² ² Speicher und Prozess Speicherverwaltung Virtueller Speicher ª ª ª ² ² Grundidee Nachschubstrategien Verdrängungsstrategien Speicherhierarchie Anhang: Laden und Binden eines Programms [KMS] Sommer 2015 Speicherverwaltung 47 Virtueller Speicher (durch Paging) ² Noch offen: Was passiert, wenn bei Speicheranforderung kein physikalischer Speicher mehr zur Verfügung steht? ² Idee: Nutze sekundären Speicher, um primären realen Speicher zu „erweitern“ – Virtueller Speicher ª ª Typischer (hier besprochener) Fall: Virtueller Speicher für Paging Prinzipien auch auf ParConierung, SegmenCerung anwendbar [KMS] Sommer 2015 Speicherverwaltung 48 Virtueller Speicher – Speicherhierarchie ² Primärer physikalischer Speicher (RAM) durch sekundären Speicher erweitert ª I.d.R.: größer, billiger, langsamer – z.B. FestplaEe Physikalischer Arbeitsspeicher – Kacheln [KMS] Sommer 2015 Speicherverwaltung Sekundärer Speicher – Kacheln 49 Speicherbelegung in primärem und sekundärem Speicher ² Prozess belegt damit nicht nur Speicher im primären Arbeitsspeicher sondern auch im sekundären Speicher Primärer Speicher Sekundärer Speicher [KMS] Sommer 2015 Speicherverwaltung 50 Speicherzugriff auf Adresse nicht im primären Speicher? ² Logische Adressen werden auf reale Adressen abgebildet ª ª ² Egal ob auf primären oder sekundären Speicher Hierzu: Seitentabelle erweitert, um InformaCon aufzunehmen Was passiert bei Zugriff auf logische Adresse, die auf reale Adresse im sekundären Speicher abgebildet wird? Im Prinzip: Speicherzugriff durchführen durchaus möglich ª Aber: nicht prakCkabel ª StaEdessen: Verschiebe die entsprechende Kachel vom sekundären in den primären Speicher – Einlagern ª Ausgelöst durch Interrupt – Seitenfehler ª Physikalischer Arbeitsspeicher – Kacheln [KMS] Sommer 2015 ZugriffSpeicherverwaltung Sekundärer Speicher – Kacheln 51 Kachel verschieben wenn primärer Speicher voll? ² Aber Ausgangsproblem: Primärer Speicher ist voll! ª ² Also auf welche Kachel die einzulagernde Seite packen? Eine belegte Kachel des primären Speichers muss frei geräumt werden ª ª ª Seiteninhalt darf aber nicht verloren gehen! Muss ggf. auf sekundären ausgelagert – verdrängt – werden Verdrängung notwendig wenn Seite modifiziert § Oder noch keine Kachel im sekundären Speicher vorhanden Physikalischer Arbeitsspeicher Auswahl [KMS] Sommer 2015 Sekundärer Speicher Zugriff Speicherverwaltung 52 Zusätzliche InformaOonen der Seitentabelle ² maxL Adresse im physikalischen Speicher – primär oder sekundär! ª Seite im Hauptspeicher vorhanden? Präsenzbit (presence/valid bit) ª Wurde auf die Seite bereits zugegriffen? Referenzbit (reference bit) ª Wurde die Seite modifiziert? Modifika8onsbit (dirty bit) ª Seitentabelle 0 1 2 3 Physikalische Adresse Präsenzbit Referenzbit [KMS] Sommer 2015 Sekundärer realer Speicher Prozess 1 Speicherverwaltung Modifikationsbit Primärer realer Speicher Neben der physikalischen Adresse enthält jeder Eintrag noch InformaConen über (z.B.) The image part with relationship ID rId3 was not found in the file. 53 Zusätzliche InformaOon in Seitentabelle: Beispiel UNIX SVR4 Table 8.6 UNIX SVR4 Memory Management Parameters (page 1 of 2) Page Table Entry Page frame number Refers to frame in real memory. Age Indicates how long the page has been in memory without being referenced. The length and contents of this field are processor dependent. Copy on write Set when more than one process shares a page. If one of the processes writes into the page, a separate copy of the page must first be made for all other processes that share the page. This feature allows the copy operation to be deferred until necessary and avoided in cases where it turns out not to be necessary. Table 8.6 UNIX SVR4 Memory Management Parameters (page 2 of 2) Page Frame Data Table Entry Page State Indicates whether this frame is available or has an associated page. In the latter case, the status of the page is specified: on swap device, in executable file, or DMA in progress. Modify Indicates page has been modified. Reference Indicates page has been referenced. This bit is set to zero when the page is first loaded and may be periodically reset by the page replacement algorithm. Reference count Number of processes that reference the page. Valid Logical device Logical device that contains a copy of the page. Indicates page is in main memory. Block number Block location of the page copy on the logical device. Protect Indicates whether write operation is allowed. Disk Block Descriptor Swap device number Logical device number of the secondary device that holds the corresponding page. This allows more than one device to be used for swapping. Device block number Block location of page on swap device. Type of storage Storage may be swap unit or executable file. In the latter case, there is an indication as to whether the virtual memory to be allocated should be cleared first. [KMS] Sommer 2015 Speicherverwaltung Pfdata pointer Pointer to other pfdata table entries on a list of free pages and on a hash queue of pages. Swap-Use Table Entry Reference count Number of page table entries that point to a page on the swap device. Page/storage unit number Page identifier on storage unit. 54 Detaillierter Ablauf – Virtueller Speicher (VS) Belegen des VS Ersatzspeicher belegen Initialisierung Freigabe des VS Leere Kachel verfügbar? [KMS] Sommer 2015 Speicherverwaltung Kachelinhalt modifiziert? Nein Seite auslagern auf Ersatzspeicher Neue Seite vom Ersatzspeicher einlagern Ersetzen Belegte Kacheln freigeben Ersatzspeicher freigeben Zeitintensive Verarbeitungsschritte Ja Freizuräumende Kachel wählen Verdrängen Speicherzugriff Seite präsent? Nein: Seitenfehler aktivieren Ja: Setze Verarbeitung fort Ablauf bei Seitenfehler Eintrag Kacheltabelle Eintrag Seitentabelle 55 Offene Frage: Verdrängung & Nachschub ² Wenn Seite einzulagern ist und keine freie Kachel verfügbar: Welche Seite soll verdrängt werden? à Verdrängungsstrategien notwendig ² Und: Wann werden Seiten überhaupt eingelagert? Wie viele Seiten? ª Bis jetzt: Nur eine einzelne Seite bei Seitenfehler, aber ist das geschickt? à Nachschubstrategien notwendig [KMS] Sommer 2015 Speicherverwaltung 56 Nachschubstrategien (Fetch Policies) ² Auf Verlangen (Demand paging) ª ª ª ² Die Seite wird erst bei aktuellem Bedarf nachgeladen Interrupt Seitenfehler (page fault) akCviert die AllokaCon Diese Strategie wird üblicherweise angewendet Vorgeplant (Pre-‐paging) Voraussetzung: Prozessverhalten im Voraus bekannt ª Transport einer Seite in den Arbeitsspeicher so, dass die Seite zum Referenzierungszeitpunkt zur Verfügung steht ª Die notwendige Kenntnis über das exakte Programmverhalten steht meist nicht zur Verfügung ª ² Kombinierte Ansätze (meist in Praxis verwendet) Beim Start Pre-‐paging, z.B. Anfang des Programmcodes, staCsche Daten, Seiten für Heap und Stapel, … ª Während Laufzeit: Demand paging ª [KMS] Sommer 2015 Speicherverwaltung 57 Verdrängungsstrategien (Replacement Policies) ² AusgangssituaCon ª ª ² ² Eine Seite soll in den Arbeitsspeicher geladen werden Keine Kachel ist zu dem Zeitpunkt frei Welche Kachel soll geleert und der Inhalt ausgelagert werden? Unterscheidung ª Lokale Verdrängungsstrategie § Es wird eine Kachel geleert, welche dem Seitenfehler verursachenden Prozess zugeordnet ist ª Globale Verdrängungsstrategie § Eine beliebige Kachel – auch von fremden Prozessen – darf geleert werden [KMS] Sommer 2015 Speicherverwaltung 58 Modellierung der Seitenzugriffe ² Für den Vergleich verschiedener Verdrängungsstrategien wird eine so genannte Seitenreferenzfolge benutzt Seitenreferenzfolge R = r1, r2, r3, … : Folge der Seiten, auf die zugegriffen werden ª Details, z.B. auf welche Adresse zugegriffen, uninteressant ª Aufeinander folgende Referenzen auf dieselbe Seite werden zusammengefasst, d.h. ∀i : ri ≠ri+1 ª ² ² Bei lokaler Strategie: Referenzfolge pro Prozess Bei globaler Strategie Referenzfolge als Mischung der Referenzfolgen der Prozesse ª Prozessnummer des referenzierenden Prozesses wird hinzugefügt, d.h. ein Seitenzugriff wird durch (PID, ri) beschrieben ª ² Hier: Prozessnummern weggelassen [KMS] Sommer 2015 Speicherverwaltung 59 Verdrängungsstrategien – Überblick Denken Sie sich ein paar Verdrängungsstrategien aus. Überlegen Sie sich, welche Information jede Strategie braucht und ob sie (in welchem Sinne) optimal ist. [KMS] Sommer 2015 Speicherverwaltung 60 OpOmale Verdrängungsstrategie ² Verdränge diejenige Seite, die am längsten nicht mehr benöCgt werden wird J OpCmal: Minimierung der Seitenfehleranzahl bei gegebener Speichergröße ª Nicht realisierbar (Wie könnte man auch in die Zukun_ sehen?) ⇒ Wird als MesslaEe für realisierbare Strategien eingesetzt, d.h. wie weit ist eine Strategie vom opCmalen Ergebnis noch en‚ernt ª ² Beispiel: Speicher mit 3 Kacheln, vorgegebene Seitenreferenzfolge Zeit 1 2 3 4 5 6 7 8 9 10 11 12 Referenz 0 2 4 3 2 3 0 1 0 3 0 2 Kachel 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 1 1 1 1 1 4 3 3 3 3 3 3 3 3 3 Kachel 2 Kachel 3 Ergebnis: 3 Fehler (ohne Initialseitenfehler) [KMS] Sommer 2015 Speicherverwaltung Verdrängung 61 Zufällige Verdrängungsstrategie (RANDom) ² ² Strategie: Wähle zufällig eine auszutauschende Seite Voraussetzung/Annahme ª ª Lokalitätsprinzip triƒ nicht zu Zugriffe gleich verteilt und unabhängig voneinander Zeit 1 2 3 4 5 6 7 8 9 10 11 12 Referenz 0 2 4 3 2 3 0 1 0 3 0 2 Kachel 1 0 0 0 0 2 2 2 2 2 2 0 0 2 2 3 3 3 0 0 0 3 3 3 4 4 4 4 4 1 1 1 1 2 Kachel 2 Kachel 3 Ergebnis: 7 Fehler (ohne Initialseitenfehler) [KMS] Sommer 2015 Speicherverwaltung 62 Realisierbare Strategien ² Idee: Vorhersage zukün_iger Zugriffe aufgrund vergangener Referenzen ª ² Auswahl basiert auf ª ª ² Rech‚erCgung: Lokalitätsprinzip – Zugriffsverhalten in unmiEelbarer Vergangenheit ist eine gute Schätzung für das Verhalten in nächster Zukun_ Häufigkeit der Zugriffe auf eine Seite Zeitpunkt der Zugriffe Strategien: Verdrängung der Seite, die Am längsten im Speicher war (First In – First Out, FIFO) ª Am längsten nicht benutzt wurde (Least Recently Used, LRU) ª Am wenigsten häufig benutzt wurde (Least Frequently Used, LFU) ª Innerhalb eines vorgegebenen Zeitraums nicht mehr referenziert wurde (Recently Not Used, RNU) ª [KMS] Sommer 2015 Speicherverwaltung 63 FIFO-‐Strategie ² ² FIFO: 4 Seitenfehler für die betrachtete Referenzfolge Anomalie der FIFO-‐Strategie ª ª Bei steigender Anzahl von Kacheln steigt die Anzahl von Seitenfehlern Beispiel: Bei 4 Kacheln ⇒ 7 Fehler, bei 5 Kacheln ⇒ 8 Fehler !?!?! Zeit 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Referenz 0 1 2 3 4 0 1 5 6 0 1 2 3 5 6 Kachel 1 0 0 0 0 4 4 4 4 6 6 6 6 6 6 6 1 1 1 1 0 0 0 0 0 0 2 2 2 2 2 2 2 2 1 1 1 1 1 1 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 Kachel 2 Kachel 3 Kachel 4 ² Aber eigentlich erwünscht: ª à Weniger Seitenfehler, wenn mehr Speicher zur Verfügung steht Monoton fallende Seitenfehlerrate bei steigender Kachelrate [KMS] Sommer 2015 Speicherverwaltung 64 LFU-‐Strategie ² Verdränge Seite, die am wenigsten häufig benutzt wurde ª ª ª Annahme: Eine kaum verwendete Seite wird auch zukün_ig selten benöCgt Ein Zähler pro Seite ⇒ InkremenCerung bei jedem Zugriff Bei gleicher Frequenz: 2. Strategie (Ce breaker), z.B. FIFO Zeit 1 2 3 4 5 6 7 8 9 10 11 12 Referenz 0 2 4 3 2 3 0 1 0 3 0 2 Kachel 1 0 0 0 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 1 1 1 1 2 4 4 4 4 0 0 0 0 0 0 2 2 2 1 (2) 3 1 (2) 3 1 (2) 4 1 (2) 4 (1) 3 2 (1) 2 (1) 2 (1) 3 (1) 3 (1) 3 (1) Kachel 2 Kachel 3 0 1 Zähler 2 1 - 1 1 1 1 (1) 1 3 4 - - 1 1 1 [KMS] Sommer 2015 Speicherverwaltung (1) (1) 2 2 1 1 2 1 65 LRU-‐Strategie ² Verdränge Seite, die am längsten nicht mehr referenziert wurde ª ª ª „Modifizierter“ Stapel: die Seite, auf die zuletzt zugegriffen wurde, wird auf oberste StapelposiCon gelegt ⇒ Oberste k Seiten aktuell im Speicher Falls Seite schon im Speicher, wird sie von der alten StapelposiCon gelöscht Bei Auslagerung: k-‐te Seite wird ausgetauscht, die neu referenzierte Seite auf die oberste PosiCon gelegt ⇒ Vorhandene Seiten „rutschen“ im Stapel nach unten (die Kacheln bleiben natürlich, wo sie sind…) Zeit 1 2 3 4 5 6 7 8 9 10 11 12 Referenz 0 2 4 3 2 3 0 1 0 3 0 2 Kachel 1 0 0 0 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 1 1 1 1 2 2 0 - 4 4 2 0 4 3 4 2 4 2 3 4 4 3 2 4 0 0 3 2 0 1 0 3 0 0 1 3 0 3 0 1 0 0 3 1 0 2 0 3 Kachel 2 Kachel 3 top Stapel 1 2 [KMS] Sommer 2015 0 - Speicherverwaltung 66 RNU-‐Strategie ² Verdränge Seite, die innerhalb eines Zeitraums nicht mehr referenziert wurde ª ª ª ª DefiniCon des Zeitraums über ein Fenster, das k zuletzt referenzierte Elemente umfasst Für eine Verdrängung kommen alle Seiten in Frage, die nicht innerhalb des Fensters referenziert wurden KriCsche Größe: Fensterbreite k>0, aber k klein Beispielreferenzfolge: 4 Seitenfehler, bei k=2 Zeit 1 2 3 4 5 6 7 8 9 10 11 12 Referenz 0 2 4 3 2 3 0 1 0 3 0 2 Kachel 1 0 0 0 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 1 1 1 1 2 4 4 4 4 0 0 0 0 0 0 Kachel 2 Kachel 3 [KMS] Sommer 2015 Speicherverwaltung 67 Vergleich der Strategien ² Von den diskuCerten Strategien zeigt LRU im DurchschniE die beste Leistung, d.h. geringste Seitenfehlerrate ª ² Interessant: LRU ist symmetrisch zur opCmalen Strategie: Vom aktuellen Zeitpunkt aus betrachtet ª ª ² Häufige Anwendung in realer Systemso_ware LRU die Vergangenheit die opCmale Strategie die Zukun_ Probleme bei der Realisierung Alle realisierbaren Strategien erfordern bei jedem Zugriff gewisse DatenoperaConen (StapeloperaConen, ZählerinkremenCerung, …) ª Durchführung dieser OperaConen (vollständig in So_ware, mit Unterstützung von Hardware) ist zu aufwändig ª Daher werden hauptsächlich Annäherungsverfahren realisiert ª [KMS] Sommer 2015 Speicherverwaltung 68 Angenäherte LRU/RNU-‐Strategie ² Hardwareunterstützung beim Seitenzugriff ª ª ª ² Jeder Seite wird ein Referenzbit zugeordnet Das Referenzbit einer Seite wird bei jedem Zugriff gesetzt Keine InformaCon über dem Zeitpunkt eines Zugriffs Fehlende ZeiCnformaCon wird durch eine periodische Rücksetzung der Referenzbits simuliert Variante 1: Bei jeder Rücksetzung wird ein Zähler inkremenCert, wenn die Seite in der Zeit nicht referenziert wurde ⇒ Verdrängung der Seite mit dem höchsten Zähler ª Variante 2: Second-‐Chance (siehe nächste Folie) ª [KMS] Sommer 2015 Speicherverwaltung 69 Second-‐Chance-‐Algorithmus (auch: Clock-‐Algorithmus) ² Ziel: Approximiere LRU ª Annäherung durch: Durchlaufe zyklisch den Referenzbits-‐Vektor § Falls das Referenzbit der aktuellen Seite =1 • Setze das Referenzbit auf 0 • Betrachte die nächste Seite § Falls das Referenzbit der aktuellen Seite =0 • Verdränge die Seite • Setze die Suche (für die nächste Verdrängung) mit der nächsten Seite fort ² Rücksetzung von Teilmengen von Referenzbits (alte bis neue PosiCon). Alle anderen Seiten mit Referenzbit 0 haben eine zweite Chance, referenziert zu werden ª Anmerkung: Second-‐Chance und Clock-‐Algorithmus sind ImplemenCerungsvarianten mit einigen Detailunterschieden [KMS] Sommer 2015 Speicherverwaltung 70 Second-‐Chance-‐Algorithmus ² BeispielsituaCon (Bi‚olgen = Referenzindikatoren) Auswahlzeiger 0 0 1 1 1 1 1 1 1 0 1 0 AuswahlAuswahlzeiger Auswahlzeiger Auswahlzeiger Auswahlzeiger Auswahlzeiger zeiger Vor Auswahl [KMS] Sommer 2015 0 0 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 2. Chance genutzt Auswahlzeiger Nach Auswahl Speicherverwaltung 1 0 1 1 1 0 1 1 0 1 1 1 Auswahlzeiger Bei nächster Aufforderung 0 0 1 1 1 0 1 1 0 1 0 0 Zu verdrängende Seite 71 Überblick ² ² ² ² ² Speicher und Prozess Speicherverwaltung Virtueller Speicher Speicherhierarchie Anhang: Laden und Binden eines Programms [KMS] Sommer 2015 Speicherverwaltung 72 Speicherhierarchien und Lokalität ² à Notwendig: Verallgemeinerung von primärem/sekundärem physikalischem Speicher Speicherhierarchie ª ª ² Kompromiss zwischen Kapazität, Preis und Zugriffsgeschwindigkeit Verarbeitung nur mit Daten im Speicher/Cache/Register möglich Ziel: Effiziente und transparente Übertragung von ª ª BenöCgten Daten in höhere Ebenen der Speicherhierarchie Auszulagernden Daten in niedrigere Ebenen der Speicherhierarchie Verarbeitung schneller, teurer, kleiner Register L1/L2 Cache Arbeitsspeicher Festplatte langsamer, billiger, größer [KMS] Sommer 2015 Speicherverwaltung Bandspeicher, CD-ROMs, DVDs ... 73 Prinzipielle Vorgehensweise ² Nachladen von Daten ª ª ª Zugriff auf Datenobjekt gewünscht Schicht 1 Auffindung des Objektes Erstelle stufenweise Kopien auf Schicht n-1 höhere Ebenen, bis die Verarbeitungsebene erreicht ist Schicht n ² Verdrängen von Daten ª ª Schicht 1 Nach einer DatenmodifikaCon werden die veränderten Elemente schriEweise, teilweise verzögert Schicht n-1 nach unten propagiert Dieser SchriE en‚ällt bei einem Lesezugriff Schicht n [KMS] Sommer 2015 Speicherverwaltung Kopie Kopie Original Mod. Kopie Mod. Kopie Mod. Original 74 Gestaltungsaspekte einer Speicherhierarchie ² ² ² Ziel: BenöCgte Daten und Programme sollen möglichst weit oben in der Speicherhierarchie verfügbar sein Problem: Kapazitäten werden nach oben hin sehr knapp Fragen Auf welche Daten wird als nächstes zugegriffen? Kenntnis des Programmverhaltens? ª Zuständigkeit für den Datentransport? Benutzer/Programmierer, Übersetzer, Betriebssystem, Hardware? ª In welchen Einheiten werden die Daten transporCert? Bytes, Speicherworte, Blöcke, Dateien? ª ² Zielsetzung ª ª Beschleunigung des Zugriffs auf die aktuelle Schicht (Caching)? Erweiterung der Kapazität (Virtualisierung)? [KMS] Sommer 2015 Speicherverwaltung 75 Lokalitätsprinzip (Principle of Locality) ² Ein Prozess grei_ im kurzen Zeitraum Δt nur auf einen kleinen Teil seines Adressraums ΔA ⊂ A zu ª ª ² Warum? ª ª ª ª ª ² Meist sequenCelle Ausführung von Anweisungen O_ vorkommende Schleifen (zeitliche Lokalität) Zusammenhängende Datenstrukturen (Arrays, räumliche Lokalität) Ausführung besCmmter Programmteile nur in Ausnahmefällen 90/10-‐Regel: Prozesse verbringen 90% der Zeit in 10% des Adressraums Konsequenz ª ª ² Räumliche Lokalität: Nach einem Zugriff auf Adresse a ist ein Zugriff auf eine Adresse in der Nähe von a sehr wahrscheinlich Zeitliche Lokalität: Nach einem Zugriff auf Adresse a ist (in Kürze) ein erneuter Zugriff auf a sehr wahrscheinlich Nur kleine Teile des Adressraums werden gleichzeiCg benöCgt Auslagerung des Rests auf untere Ebenen der Speicherhierarchie Lokalitätsprinzip dient als Approxima3on des Programmverhaltens! [KMS] Sommer 2015 Speicherverwaltung 76 Zugriff auf Seitennummer [KMS] Sommer 2015 Ausführungszeit Speicherverwaltung 77 Zuständigkeiten für Transport, Transfereinheit ² Welche Einheiten sind für die DatenmigraCon zwischen den Schichten zuständig? ª ª ª Zuständigkeit Transport von Daten/Befehlen zwischen Speicher, Cache und Prozessor ⇒ Hardware Ein-‐/Auslagerung von Daten auf sekundäre Speicher, z.B. FestplaEe ⇒ Systemso_ware KommunikaCon mit terCärem Speicher, z.B. Bandlaufwerk § Expliziter Aufruf durch Benutzer § Systemso_ware (Dateisystem) Register Transfereinheit Speicherwort (z.B. 8 Byte) HW Cache Cache-Line (z.B. 64 Byte) HW Hauptspeicher Plattenblöcke (z.B. 4 KByte) Systemsoftware Festplatte Datei (variable Größe) Systemsoftware, Benutzer Bandlaufwerk [KMS] Sommer 2015 Speicherverwaltung 78 Unterschied Caching ↔ Virtualisierung ² Der Benutzer einer Speicherhierarchie ª ª ª ² ² Sieht in der Regel nicht alle Schichten der Hierarchie Muss nicht wissen, auf welcher Speicherschicht die aktuell benöCgten Daten liegen Hat den Eindruck, alle seine Zugriffe beziehen sich auf Schicht k Liegen die benöCgten Daten in einer höheren Schicht ⇒ Beschleunigter Zugriff durch Caching Liegen die benöCgten Daten auf einer niedrigeren Schicht und werden nur bei Bedarf eingelagert ⇒ Vergrößerung der Speicherkapazität von Schicht k durch Virtualisierung Schicht k-1 (transparent) Caching Schicht k (sichtbar) Virtualisierung Schicht k+1 (transparent) [KMS] Sommer 2015 Speicherverwaltung 79 Verzweigende Speicherhierarchien ² Beispiele für Verzweigungen ª ª ² Verzweigung nach unten ª ª ² Prozessoren im Parallelrechner haben eigenen Cache Mehrere Bandlaufwerke vorhanden UnkriCsch, da nur eine Kopie eines Datensatzes exisCert „Wegbeschreibung“ muss z.B. die Nummer des Laufwerks umfassen Verzweigung nach oben ª ª ª Cache 1 Cache 2 Hauptspeicher Festplatte Bandlaufwerk 1 Bandlaufwerk 2 Existenz mehrerer Kopien eines Datensatzes auf derselben Ebene Unabhängige ModifikaCon möglich Welcher Datensatz ist aktuell? ⇒ Cachekohärenzproblem [KMS] Sommer 2015 Speicherverwaltung 80 Cachekohärenzproblem ² Problem durch nach oben verzweigte Speicherhierarchien ª Cachekohärenz bedeutet, dass zu keinem Zeitpunkt unterschiedliche Inhalte derselben Speicherzelle in verschiedenen Caches gespeichert werden § Genauer: … unterschiedliche Antworten auf Anfragen geliefert werden ª Client Client Lokale Kopie 2 Lokale Kopie 1 Netz Wo treten solche Probleme z.B. auf? § MulCprozessorsysteme § Verteilte Dateien im Netz: Greifen mehrere Clients lesend und schreibend auf dieselbe Datei zu, so beziehen sich die Schreibzugriffe zunächst auf die lokale Kopie ⇒ unterschiedliche Inhalte derselben Datei [KMS] Sommer 2015 Speicherverwaltung Fileserver Original 81 Cachekohärenzproblem – Lösungsansätze ² SituaCon: ª ª Ein Datenobjekt in mehreren Caches enthalten Ein Cacheeintrag wird verändert Welche Möglichkeiten haben Sie, auf die Veränderung eines Cache-Eintrages zu reagieren? [KMS] Sommer 2015 Speicherverwaltung 82 Cachekohärenzproblem – Lösungsansätze ² SituaCon: ª ª ² Ein Datenobjekt in mehreren Caches enthalten Ein Cacheeintrag wird verändert Möglichkeiten Nichts tun à Caches nicht mehr kohärent da unterschiedliche Werte ª Bzgl. Original-‐Datenobjekt (auch bei nur einem Cache) ª § Original sofort mit Cache-‐Eintrag ändern (write-‐through cache) § Original erst bei Gelegenheit aktualisieren (write-‐back cache) ª Bzgl. anderer Caches § Andere Caches „entwerten“ (cache invalidate) – MiEeilen, dass alter Cacheeintrag nicht gülCg ist § Andere Caches mit neuem Wert versorgen (cache update) – Neuen Wert explizit übermiEeln [KMS] Sommer 2015 Speicherverwaltung 83 Welche KombinaOon funkOoniert? Cache Kohärenz Verhalten zu Hauptspeicher Write back Verhalten zu anderen Caches [KMS] Sommer 2015 Write through Cache invalidate Problematisch, wenn Datum nicht Ja in allen Caches zum Zeitpunkt des Updates vorhanden oder wenn andere CPU auf Datum nach update/vor write-back zugreift Cache update Problematisch, wenn Datum nicht Ja in allen Caches zum Zeitpunkt des Updates vorhanden Speicherverwaltung 84 Beispiel: Caching im World Wide Web ² Auch das Zugriffsverhalten im WWW zeigt Lokalität ª ª ª ª ª O_ besuchte Websites sind evtl. für mehrere Benutzer interessant Regelmäßiges Aufrufen der Seiten Allgemein benöCgte Downloads, z.B. Patches, Updates, … Webseiten/Programme werden im Cache zwischengespeichert Beschleunigung des Zugriffs und Entlastung des Netzwerks Wie lösen Sie hier das CacheKohärenzproblem? [KMS] Sommer 2015 Speicherverwaltung Web Client Intranet Web Client Web Client Web Cache Internet Web Server Web Server Web Server 85 Überblick ² ² ² ² ² Speicher und Prozess Speicherverwaltung Virtueller Speicher Speicherhierarchie Anhang: Laden und Binden eines Programms [KMS] Sommer 2015 Speicherverwaltung 86 Anhang: Laden und Binden eines Programms ² Offene Fragen: Was passiert eigentlich beim Start eines Prozesses? ª Wie kommt man überhaupt zu einem ausführbaren Programm (das dann als Prozess gestartet werden kann) ª Wie sieht ein ausführbares Programm überhaupt aus? ª [KMS] Sommer 2015 Speicherverwaltung 87 Welche Adressen stehen im Programm? ² ² Adressen z.B. für Sprungbefehle, Daten, … Bei Systemen mit logischen Adressen ª ² Einfach: logische Adressen! Programm kann einen Adressraum von 0 bis Lmax nutzen Bei Systemen ohne logische Adressen ª Angenommen, es stünden direkt feste Adressen im Programm à Mehrprogrammbetrieb schwierig § Lader muss diese festen Adressen auf die aktuellen Adressen umschreiben (relozierbares Laden) ª Oder: relaCve Adressen im Programm (z.B. relaCv zum Programmstart) § Dann RelokaCon einfach – nur tatsächliche Startadressen zu Adressen hinzufügen ª In beiden Fällen: Lader muss wissen, wo im Programm Adressen benutzt werden (Reloka8onswörterbuch) [KMS] Sommer 2015 Speicherverwaltung 88 Erzeugung eines ausführbaren Programms ² Typisches Programm: „eigener“ Quelltext + Benutzung von Bibliotheken ª ² In einzelnen Modulen Wie wird daraus ein ausführbares Programm? à Binden © Stallings, Betriebssysteme [KMS] Sommer 2015 Speicherverwaltung 89 OpOon für Binder ² Binden durch Compiler: Bibliotheken im Quellcode vorhanden, alles gemeinsam übersetzt, ferCg ª ² Binden beim Erstellen des ausführbaren Programms ª ² Binder monCert Objektmodule zusammen, löst Referenzen (z.B. Sprünge) auf und ersetzt durch sinnvolle Adressen Binden beim Start des Prozesses (dynamisches Binden) ª ª ª ² Nicht typisch, Bibliotheken meist übersetzt vorhanden Referenzen zu Bibliotheksmodulen werden erst beim Start des Prozesses aufgelöst BenöCgt Beschreibung der benöCgten Bibliotheken im (unvollständigen!) Programmcode Erleichtert gemeinsame Benutzung von Bibliotheken – Betriebssystem weiß, welche Bibliotheken schon geladen wurden und muss nicht doppelt laden Binden bei Ausführung ª Ähnlich wie Binden beim Start, aber Auflösung erst, wenn FunkCon tatsächlich ausgeführt werden soll [KMS] Sommer 2015 Speicherverwaltung 90 Start eines Programms ² Beim Start eines Programms ª ª ª ProzesskontrollinformaCon iniCalisieren Realen Speicher bereitstellen (wie viel?) Programm laden und ggf. binden § Wie viel des Programms? Gesamten Code und Daten? § Einfachste OpCon: Nur die erste Seite des Codes laden, Programm wird, wenn es auf nicht vorhandene Seiten zugreifen will, Seitenfehler verursachen § Paging-‐Mechanismus wird die fehlenden Seiten nachladen (vgl. Diskussion über Nachschubstrategien) In ProzesskontrollinformaCon: Die vereinbarte StarCnstrukCon des Prozesses als nächste auszuführende InstrukCon eintragen ª Prozess im Scheduler als „bereit“ eintragen ª [KMS] Sommer 2015 Speicherverwaltung 91 Zusammenfassung ² Speicherverwaltung sorgt dafür, dass ein Prozess Speicher benutzen kann – auf Anforderung ª ² Effiziente Datenstrukturen und Auswahlalgorithmen nöCg Speicherverwaltung wird meist mit virtuellem Speicher kombiniert Erweitert den physikalisch vorhandenen Speicher durch Speicher anderen Typs ª Führt zu mehrstufigen Speicherhierarchien ª Erfordert Austauschverfahren ª § Nachschub: Wann werden wie viele Seiten eingelagert? § Verdrängung: Welche Seiten werden ausgelagert, wenn kein Platz mehr da ist ª Ermöglicht Prozess größer realem (1-‐Stufen) Speicher; viele Prozesse die gemeinsam größer sind als realer (1-‐Stufen) Speicher [KMS] Sommer 2015 Speicherverwaltung 92
© Copyright 2024 ExpyDoc
