sysprog6.pdf

6. Speicher- und Adressraumverwaltung Überblick 6.1 Speicherverwaltung im Betriebssystem 6.2 Speicherzuweisung und Auslagerung 6.3 Verdrängungsstrategien Systemprogrammierung 1  6.1...

6. Speicher- und Adressraumverwaltung Überblick 6.1 Speicherverwaltung im Betriebssystem 6.2 Speicherzuweisung und Auslagerung 6.3 Verdrängungsstrategien Systemprogrammierung 1  6.1 Speicherverwaltung im Betriebssystem Speicher ist ein „spezielles“ Betriebsmittel, das vom BS besonders verwaltet werden muss Speicherallokation = Zuordnung von Speicher Zwecke, für die Speicher benötigt wird: Ø Prozesse § Stack § Heap § Programm-Code und -Daten Ø Das BS selbst! § BS-Code § BS-Daten § Dynamisch erzeugte Verwaltungsstrukturen (PCBs etc.) Systemprogrammierung 2  Statische und dynamische Speicherallokation Statische Speicherallokation: Feste Einteilung des Speichers in mehrere Bereiche Ø Nehmen einen Prozess vollständig auf Ø Prozess blockiert Þ Verdrängung aus aktuellem Laufbereich und Auslagerung auf den externen Speicher Ø Wiedereinlagerung nach Wechsel blockiert ® bereit Ø Nachteil: Nur ganze Prozesse werden verdrängt Þ ineffizient Dynamische Speicherallokation: Prozessteile werden – transparent für den Benutzer – zur Laufzeit und erst bei Bedarf ein- und ausgelagert Ø Grundlage: Virtuelle Adressierung so, dass Prozesse verdrängt und ohne zusätzlichen Programmieraufwand in anderem Speicherbereich ausgeführt werden können Þ Realokierbare Prozesse Ø Beim Zugriff auf fehlenden Inhalt wird ein Interrupt (Seitenfehler, Page Fault) ausgelöst, der das Nachladen des Inhalts initiiert Systemprogrammierung 3  Datenstruktur zur Adressraumverwaltung Gedankenexperiment: wir erstellen einen Adressraum Benötigte Struktur dafür muss für jede virtuelle Adresse V die folgenden Dinge liefern: Ø Gültigkeit (ist V eine gültige Adresse in diesem Adressraum, oder löst ein Zugriff auf V einen Speicherfehler aus?) Ø Wenn gültig: § Zugehörige Physische Adresse P § Lesen, Schreiben, Ausführen von dieser Adresse erlaubt? § Zugriff für unprivilegierte Instruktionen erlaubt? § Þ je Eintrag brauchen wir mind. ein Maschinenwort… (wir müssen ja P speichern plus ein paar Bits extra) Systemprogrammierung 4  Datenstruktur zur Adressraumverwaltung (2) Frage: wie granular wollen wir V zuordnen können? Ø Extrem 1: ultrafein, d.h. jedes Byte einzeln Þ dann brauchen wir mehr Speicher für die Verwaltungs-struktur als das System überhaupt Speicher hat Ø Extrem 2: ultragrob, z.B. 64MB Þ dann belegt jeder Prozess mind. 64MB Speicher, da wir kleinere Einheiten nicht verwalten können Trade-Off zwischen Effizienz des Lookups, Größe der Verwaltungsstruktur und anderen Überlegungen Ø Resultat für die meisten Architekturen: 4kB Þ virtuelle Verwaltungseinheit ist eine Seite (page) Þ physisches Pendant heißt Kachel (page frame) Þ Seitentabelle oder Seite-Kachel-Tabelle (page table) Systemprogrammierung 5  Seitenadressierung Bei Seitenadressierung (paging) werden der virtuelle und der physikalische Speicher in Stücke fester Länge eingeteilt Ø Stücke im logischen Adressraum heißen Seiten (pages) Ø Stücke im physikalischen Speicher heißen Kacheln (page frames) Ø Seiten und Kacheln sind gleich groß Programmadressraum Speicher Seite 1 Kachel 1 (frei) Seite 2 Kachel 2 (Seite 3) Seite 3 Kachel 3 (Seite 2) Seite 4 Kachel 4 (frei) Seite 5 Kachel 5 (frei) Seite 6 Kachel 6 (Seite 4) Kachel 7 (Seite 5) Kachel 8 (frei) Kachel 9 (Seite 1) Systemprogrammierung 6  Verbindung durch Seitentabelle Neben der physikalischen Adresse enthält jeder Eintrag der Seitentabelle noch Informationen über Ø Seite im Hauptspeicher vorhanden? Präsenzbit (presence bit P) Ø Wurde auf die Seite bereits zugegriffen? Referenzbit (reference bit R oder access bit A) Ø Wurde die Seite modifiziert? Modifikationsbit (dirty bit D oder modification bit M) Kachel Speicher Seitentabelle oder Seiten Seiten-Kachel -Tabelle 1 1 1 1 0 0 0 0 0 1 1 0 0 1 0 Modifikation Referenzierung Präsenz Systemprogrammierung 7  Adressübersetzung mit Seitentabelle Seitenbasierte Speicherbelegung ist Standard in Betriebssystemen Notwendige Angaben Ø Wo befindet sich die Seitentabelle Þ Tabellenbasisregister Ø Welche Seite wird angesprochen Þ Seitennummer Ø Adresse innerhalb der Seite Þ Wortadresse (offset, displacement ) Tabellenbasisadresse (Im Prozessor) Seitentabelle Speicher + Seite Wortadresse K K = Konkatenation (Zusammenfügen) Systemprogrammierung 8  Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der Übersetzungstabelle (nur privilegiert, also vom BS, konfigurierbar) Schritt 1: zerlege V in Seitennummer und Offset Verwaltungsstruktur Physischer Speicher Tabellenbasisadressregister („Seitentabelle“) Seitennummer Offset Virtuelle Adresse V Systemprogrammierung 9  Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der Übersetzungstabelle (nur privilegiert, also vom BS, konfigurierbar) Schritt 2: verwende Seitennummer als Index in Seitentabelle Verwaltungsstruktur Physischer Speicher Tabellenbasisadressregister („Seitentabelle“) Seitennummer Offset Virtuelle Adresse V Systemprogrammierung 10  Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der Übersetzungstabelle (nur privilegiert, also vom BS, konfigurierbar) Schritt 3: prüfe Gültigkeit und Zugriffsrechte in den Metadaten des Eintrags („Bits“), lese Kachelnummer Verwaltungsstruktur Tabellenbasisadressregister („Seitentabelle“) Kachelnummer Bits Seitennummer Offset Virtuelle Adresse V Systemprogrammierung 11  Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der Übersetzungstabelle (nur privilegiert, also vom BS, konfigurierbar) Schritt 4: bilde aus Kachelnummer und Offset das Ergebnis, die physische Adresse P Verwaltungsstruktur Physischer Speicher Tabellenbasisadressregister („Seitentabelle“) Kachelnummer Bits Seitennummer Offset Kachelnummer Offset Virtuelle Adresse V Physische Adresse P Systemprogrammierung 12  Datenstruktur zur Adressraumverwaltung (3) Annahme: 32-Bit-Architektur, d.h. 4GB Adressraum, Verwaltungseinheit 4kB Þ es gibt 4GB/4kB=220 Seiten pro virtuellem Adressraum Wenn die Verwaltungsstruktur eine einfache Tabelle ist, wäre sie 220 Einträge lang (wovon häufig die allermeisten ungültig sein werden) [Wie ein 2000-seitiges Telefonbuch, wo hinter 99,9% der Namen keine Rufnummer steht…] Für 64-Bit-Architekturen erst recht nicht handhabbar (252!) Systemprogrammierung 13  Datenstruktur zur Adressraumverwaltung (4) Abhilfe-Idee 1: invertierte Tabelle Ø Ein Eintrag pro Kachel, nicht pro Seite Ø Größe der Tabelle skaliert mit dem tatsächlich vorhandenen Speicher, nicht mit der virtuellen Adressraum-Größe Problem: wenn das eine Kachel-Tabelle ist, wie löst man die Aufgabe „gegeben V, suche P“? Ø [Wer in diesem Telefonbuch hat die Rufnummer 33344499?] Ø Naiv: lineare Suche durch die gesamte Tabelle Ø Etwas trickreicher: durch Einsatz von Hash-Verfahren muss nur ein Teil der Einträge durchsucht werden… Þ letztlich dennoch ineffizient Systemprogrammierung 14  Datenstruktur zur Adressraumverwaltung (5) Abhilfe-Idee 2: mehrstufige Tabelle Ø Anstatt alle 20 Bits mit einer einzigen 220-Tabelle zu übersetzen, mache zwei Schritte à 10 Bits Ø Erste Tabelle enthält 210 Einträge Ø Nur an Stellen, wo virtuelle Adressen tatsächlich übersetzt werden sollen, verweist die erste Tabelle auf eine zweite Tabelle zur Übersetzung der übrigen Bits dieses Adressbereichs Þ für den üblichen Fall des spärlich besetzten Adressraums: sehr effiziente Darstellung § Leerer Adressraum: eine Tabelle à 210 § Adressraum mit fünf Seiten: max. sechs Tabellen à 210 § Voll besetzter Adressraum: 210+1 Tabellen à 210 (auch nicht schlimmer als eine einzige große Tabelle) Systemprogrammierung 15 Mehrstufige Seitentabellen Second Level 10 10 12 PT1 PT2 Offset Top Level Grau = derzeit nicht genutzt Systemprogrammierung 16  Mehrstufiges Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der ersten Ebene der hierarchischen Übersetzungstabelle (nur privilegiert, also vom BS, konfigurierbar) Schritt 1: zerlege V in Tabellen-Indices und Offset Seitentabelle, Tabellenbasisadressregister erste Ebene Index #1 Index #2 Offset Virtuelle Adresse V Systemprogrammierung 17  Mehrstufiges Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der ersten Ebene der hierarchischen Übersetzungstabelle (nur privilegiert, also vom BS, konfigurierbar) Schritt 2: benutze Tabellenbasisadressregister und Index #1 für Lookup in der ersten Tabellenstufe Seitentabelle, Tabellenbasisadressregister erste Ebene Index #1 Index #2 Offset Virtuelle Adresse V Systemprogrammierung 18  Mehrstufiges Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der ersten Ebene der hierarchischen Übersetzungstabelle (nur privilegiert, vom BS konfigurierbar) Schritt 3a: wenn gültig, enthält Eintrag Basisadresse einer Tabelle der zweiten Ebene für die Übersetzung der restlichen Bits Seitentabelle, Tabellenbasisadressregister erste Ebene Tab.Basis #2 Bits Index #1 Index #2 Offset Virtuelle Adresse V Systemprogrammierung 19  Mehrstufiges Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der ersten Ebene der hierarchischen Übersetzungstabelle (nur privilegiert, vom BS konfigurierbar) Schritt 3b: benutze diese zweite Basisadresse und Index #2 für einen weiteren Tabellen-Lookup Seitentabelle, Seitentabelle, Tabellenbasisadressregister erste Ebene zweite Ebene Kachelnummer Bits Tab.Basis #2 Bits Index #1 Index #2 Offset Virtuelle Adresse V Systemprogrammierung 20  Mehrstufiges Adressübersetzungsverfahren Prozessor enthält spezielles Kontrollregister für Basisadresse der ersten Ebene der hierarchischen Übersetzungstabelle (nur privilegiert, vom BS konfigurierbar) Schritt 4: wenn auch dieser Eintrag gültig, füge wieder Kachelnummer und Offset zu P zusammen Seitentabelle, Tabellenbasisadressregister zweite Ebene Kachelnummer Bits Tab.Basis #2 Bits Index #1 Index #2 Offset Kachelnummer Offset Virtuelle Adresse V Physische Adresse P Systemprogrammierung 21  Metadaten in der Seitentabelle Je ein Bit für (nur eine Auswahl, es gibt noch mehr): Ø Seite-Kachel-Eintrag ist gültig (Present) Ø Seite darf gelesen werden (Read) Ø Seite darf beschrieben werden (Write) Ø Seite darf ausgeführt werden (eXecute) Ø Seite darf von unprivilegiertem Code benutzt werden (User); manchmal auch mit umgekehrter Logik als (Supervisor) Ø Auf die Seite wurde bereits lesend zugegriffen (Accessed) Ø Auf die Seite wurde bereits schreibend zugegriffen (Dirty) A und D werden von der CPU aktualisiert(!) Systemprogrammierung 22  6.2 Speicherzuweisung und Auslagerung BS verwaltet sowohl die Kacheln selbst (frei/belegt, und womit?) als auch die Adressräume (welche Kachel ist an welcher virtuellen Adresse in welchen Adressräumen verfügbar?) Wir unterscheiden zwei Fälle, in denen etwas zu tun ist (Speicher zuweisen bzw. wieder entziehen) und wir eine Strategie benötigen: Ø Nachschub: ein neuer Prozess startet oder ein bestehender fordert zusätzlichen Speicher an Ø Verdrängung: es besteht Speicherknappheit, so dass durch Auslagerung Platz geschaffen werden muss Systemprogrammierung 23  Nachschubstrategien (Fetch Policies) Auf Verlangen (Demand Paging): Seiten werden erst bei Bedarf nachgeladen Ø Bedarf äußert sich durch Zugriff auf ungültige virtuelle Adresse (Þ Seitenfehler tritt auf, BS „löst das Problem“) Vorgeplant (Pre-Paging) Transport einer Seite in den Arbeitsspeicher so, dass die Seite zum Referenzierungszeitpunkt zur Verfügung steht Ø Voraussetzung: exaktes Prozessverhalten im Voraus bekannt, meist nicht erfüllt Kombinierte Ansätze Ø Beim Prozess-Start Pre-Paging: Programm laden, mind. eine Seite für je Heap und Stack bereitstellen, usw. Ø Während Laufzeit: Demand Paging Systemprogrammierung 24  Verdrängung Speicherknappheit erfordert Verdrängung, d.h. Auslagerung von Speicherinhalten auf andere Medien (z.B. Festplatte) Möglichkeit 1: Prozesse vollständig ein- und auslagern Ø Prozess blockiert Þ Auslagerung Ø Prozess wieder bereit Þ Wiedereinlagerung Ø Aber: zu viel Arbeit, insb. bei kurzen Blockierungen Þ ineffizient Möglichkeit 2: Prozessteile (Seiten!) werden – transparent für den Benutzer – zur Laufzeit und erst bei Bedarf ein- und ausgelagert Ø Ausgelagerte Seiten werden in der Seitentabelle als „ungültig“ markiert, beim Zugriff darauf wird ein Seitenfehler ausgelöst Þ BS kann Seite wieder einlagern, ohne dass der Prozess merkt, dass sie weg war Systemprogrammierung 25  Verdrängung Auslagerung von Seiten nutzt die Seitentabelle „kreativ“: Ø Gültiger Eintrag in der Seitentabelle enthält: § Gültig-Bit P = 1 § Virtuelle Adresse V § Zugriffsrechtebits R,W,X,U § Zugriffsprotokollbits A,D Ø Für einen ungültigen Eintrag muss nur gelten: Gültig-Bit P = 0 Ø Die übrigen Felder werden von der MMU dann ignoriert Ø Diese können also z.B. dazu genutzt werden, die Blocknummer auf der Festplatte zu speichern, wohin der Seiteninhalt ausgelagert wurde! Wenn das D-Bit in der Seitentabelle nicht gesetzt ist, kann das Schreiben auf die Festplatte u.U. unterbleiben! Systemprogrammierung 26  Detaillierter Ablauf Belegen des VS Ablauf bei Seitenfehler Ersatzspeicher belegen Initialisierung Ja Leere Kachel verfügbar? Verdrängen Zugriff Freizuräumende Kachel wählen Seite vorhanden? Nein Nein: Seitenfehler aktivieren Kachelinhalt modifiziert? Ja: Setze Verarbeitung fort Seite auslagern auf Ersatzspeicher Freigabe des VS Belegte Kacheln freigeben Neue Seite vom Ersatzspeicher einlagern Ersetzung Ersatzspeicher freigeben Zeitintensive Eintrag Kacheltabelle Verarbeitungsschritte Eintrag Seitentabelle Systemprogrammierung 27  Demand Paging SKT = Seite-Kachel-Tabelle (anderer Name für Seitentabelle) Systemprogrammierung 28 Demand Paging (2) Seitenfehler (Page Fault) Systemprogrammierung 29 Demand Paging (3) Systemprogrammierung 30 Demand Paging (4) Systemprogrammierung 31 Demand Paging (5) Systemprogrammierung 32  6.3 Verdrängungsstrategien (Replacement Policies) Leistungsfähigkeit von Demand Paging stark von der Anzahl der Seitenfehler abhängig Þ Seitenfehler durch intelligente Verdrängung minimieren Welche Kachel soll geleert und der Inhalt ausgelagert werden? Ø Lokale Auswahlstrategie: Es wird eine Kachel geleert, welche dem den Seitenfehler verursachenden Prozess zugeordnet ist Ø Globale Auswahlstrategie: Eine beliebige Kachel – auch von fremden Prozessen – darf geleert werden Modellierung der Seitenersetzung Ø Ist ri die Nummer der Seite, auf der zum Zeitpunkt t zugegriffen wird, so heißt R = r1, r2, r3,…, rn Seitenreferenzfolge Systemprogrammierung 33  Optimale Auswahlstrategie Verdränge diejenige Seite, die am längsten nicht mehr benötigt werden wird J Ø Minimierung der Seitenfehleranzahl bei gegebener Speichergröße Ø Nicht realisierbar ohne hellseherische Fähigkeiten Þ wird als Messlatte für realisierbare Strategien eingesetzt, d.h. wie weit ist eine Strategie vom optimalen Ergebnis noch entfernt Zeit 1 2 3 4 5 6 7 8 9 10 11 12 Zugriff Seite A C E D C D A B A D A C Kachel 1 A A A A A A A A A A A C Kachel 2 C C C C C C B B B B B Kachel 3 E D D D D D D D D D Ergebnis: 3 Fehler (ohne Initialseitenfehler) Systemprogrammierung 34  Realisierbare Strategien Lokalitätsprinzip: Zugriffsverhalten in unmittelbarer Vergangenheit = gute Schätzung für das Verhalten in nächster Zukunft Ø Räumliche Lokalität: Nach 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 ein erneuter Zugriff (in Kürze) auf a sehr wahrscheinlich Warum? Ø Sequentielle Ausführung von Anweisungen, Schleifen Ø Ausführung bestimmter Programmteile nur in Ausnahmefällen Ø 90/10-Regel: Prozesse verbringen 90% der Zeit in 10% des Adressraums Systemprogrammierung 35  Realisierbare 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 Zeitraums nicht referenziert (Recently Not Used, RNU) Systemprogrammierung 36  FIFO-Strategie FIFO: 4 Seitenfehler für die betrachtete Referenzfolge Anomalie der FIFO-Strategie Ø Bei steigender Kachelzahl kann die Anzahl von Seitenfehlern steigen(!) Ø Beispiel: 4 Kacheln Þ 7 Fehler, 5 Kacheln Þ 8 F., 6 Kacheln Þ 6 F. Erwünscht Ø Weniger Seitenfehler, wenn mehr Speicher zur Verfügung steht Ø Monoton fallende Seitenfehlerrate bei steigender Kachelrate Zeit 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Zugriff Seite A B C D E A B F G A B C D F G Kachel 1 A A A A E E E E G G G G G G G Kachel 2 B B B B A A A A A A C C C C Kachel 3 C C C C B B B B B B D D D Kachel 4 D D D D F F F F F F F F Systemprogrammierung 37  LFU-Strategie Verdränge Seite, die am wenigsten häufig benutzt wurde Ø Eine kaum verwendete Seite wird auch zukünftig selten benötigt Ø Ein Zähler pro Seite Þ Inkrementierung bei jedem Zugriff Ø Bei gleicher Frequenz: 2. Strategie, z.B. FIFO Zeit 1 2 3 4 5 6 7 8 9 10 11 12 Zugriff Seite A C E D C D A B A D A C Kachel 1 A A A D D D D D D D D D Kachel 2 C C C C C C B B B B C Kachel 3 E E E E A A A A A A A 1 1 1 (1) (1) (1) 2 2 3 3 4 4 B - - - - - - - 1 1 1 1 (1) Zähler C - 1 1 1 2 2 2 (2) (2) (2) (2) 3 D - - - 1 1 2 2 2 2 3 3 3 E - - 1 1 1 1 (1) (1) (1) (1) (1) (1) Systemprogrammierung 38  LRU-Strategie Verdränge Seite, die am längsten nicht mehr referenziert wurde Ø Seitenzugriffs-Stapel: Seite, auf die zuletzt zugegriffen wurde, wird auf oberste Stapelposition gelegt Þ oberste k Seiten im Speicher Ø Falls Seite schon im Speicher: im Stapel wieder nach oben befördern Ø Bei Auslagerung: k-te Seite austauschen; neu referenzierte Seite kommt auf oberste Position Þ vorhandene Seiten rutschen nach unten, k-te Seite rutscht aus dem Stapel Zeit 1 2 3 4 5 6 7 8 9 10 11 12 Zugriff Seite A C E D C D A B A D A C Kachel 1 A A A D D D D D D D D D Kachel 2 C C C C C C B B B B C Kachel 3 E E E E A A A A A A 1 A C E D C D A B A D A C Stapel 2 - A C E D C D A B A D A 3 - - A C E E C D D B B D Systemprogrammierung 39  RNU-Strategie Verdränge Seite, die innerhalb eines Zeitraums nicht mehr referenziert wurde Ø Definition 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 Ø Kritische 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 Zugriff Seite A C E D C D A B A D A C Kachel 1 A A A D D D D D D D D D Kachel 2 C C C C C C B B B B C Kachel 3 E E E E A A A A A A Systemprogrammierung 40  Vergleich der Strategien Von den Strategien zeigt LRU im Durchschnitt die beste Leistung, d.h. geringste Seitenfehlerrate ÞHäufige Anwendung in realer Systemsoftware Probleme bei der Realisierung Ø Alle realisierbaren Strategien erfordern bei jedem Zugriff gewisse Datenoperationen (Stapeloperationen, Zählerinkrementierung, …) Ø Durchführung dieser Operationen (vollständig in Software, mit Unterstützung von Hardware) ist zu aufwendig Ø Daher werden hauptsächlich Annäherungsverfahren realisiert Systemprogrammierung 41  Angenäherte LRU/NRU-Strategie Hardwareunterstützung beim Seitenzugriff Ø Jede Seite besitzt Zugriffsbit (A) in der Seitentabelle Ø Das Zugriffsbit wird beim Lesen der Seite von der CPU gesetzt Ø Keine Information über den Zeitpunkt eines Zugriffs Fehlende Zeitinformation wird durch eine periodische Rücksetzung der Zugriffsbits simuliert Beispiel: Second-Chance-Algorithmus (Clock-Algorithmus) Systemprogrammierung 42  Second-Chance-Algorithmus (Clock-Algorithmus) FIFO-Modifikation durch Berücksichtigung von Referenzen Ø Sortiere die Seiten/Referenzbits gemäß Einlagerungsdauer Ø Durchlaufe zyklisch den Vektor mit Referenzbits § 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 mit der nächsten Seite fort Rücksetzung von Teilmengen von Referenzbits (Alte bis Neue Position). Alle anderen Seiten mit R-Bit 0 haben eine zweite Chance, referenziert zu werden Clock-Algorithmus ist eine Implementierungsvariante Systemprogrammierung 43  Second-Chance-Algorithmus Beispielsituation (Bitfolgen = Referenzindikatoren) 0 0 1 0 2. Chance Auswahl- 0 Auswahl- 0 0 0 genutzt zeiger 1 zeiger 1 1 1 1 1 1 1 1 0 0 Auswahl- 0 1 1 0 0 zeiger 0 1 1 0 Auswahl- 1 1 1 1 0 zeiger 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 Bei nächster Zu verdrängende Vor Auswahl Nach Auswahl Aufforderung Seite Systemprogrammierung 44  Solaris 2: Algorithmus Speicherverwaltung mit dem Prozess pageout Ø Variante des Clockalgorithmus (Zweizeigeralgorithmus, two-handed-clock) Ø Erster Zeiger scannt die Seiten und setzt die Referenzbits auf 0 Ø Später läuft der zweite Zeiger nach und gibt alle Seiten mit Referenzbit immer noch 0 wieder frei Wichtige Parameter Ø Scanrate: Scangeschwindigkeit (Seiten/Sekunde) § Anpassung an aktuellen Systemzustand (slowscan = 100 Seiten/s bis fastscan = Gesamtanzahl von Seiten/2 aber max = 8192) Ø Handspread: Statischer Abstand in Seiten zwischen den Zeigern § Tatsächlicher Abstand ergibt sich durch Kombination von scanrate und handspread, z.B. scanrate = 100 und handspread = 1024 Þ 10s zwischen den beiden Zeigern § Bei höher Belastung Abstände von einigen Tausendstel nicht ungewöhnlich Erweiterung: Überspringe Seiten von Shared Libraries Systemprogrammierung 45  Paging-Daemon Technik zur Sicherung eines ausreichenden Vorrats an freien Kacheln für schnelle Reaktion auf weitere Speicheranforderungen Grundidee Ø Trennung von Seitenverdrängung und Seiteneinlagerung Ø Speicherverwaltung hält eine vorab festgelegte Anzahl an Kacheln frei ÞSeitenfehler können ohne Verdrängung beseitigt und neue Adressräume direkt angelegt werden Realisierung Ø Paging-Daemon wird periodisch aktiviert (Üblicher Wert: alle 250 ms) Ø Überprüfung, ob die a-priori vorgegebene Anzahl freier Kachel unterschritten wurde (Üblicher Wert: ca. 25% der Kachel frei) § Falls ja Þ Auslagerung von Seiten auf die Festplatte gemäß der eingesetzten Verdrängungsstrategie § Falls nein Þ Blockierung des Paging-Daemons bis zum nächsten Sollzeitpunkt Systemprogrammierung 46  Realisierung eines Paging Daemons in Solaris 2 Wichtige Parameter Ø Lotsfree: mindestens 1/4 des Speichers frei, Überprüfung alle 0.25s Ø Desfree: Fällt die Anzahl freier Seite unter diesen Schwellwert (Durchschnitt über 30s) Þ Start Swapping, Überprüfung alle 0.1s Ø Minfree: Nur noch minimale Menge freier Seiten vorhanden Þ Aufruf der Seitenersetzung bei jeder Speicheranforderung Scanrate Anzahl freier Seiten Systemprogrammierung 47  Page-Fault-Frequency-Modell Seitenfehlerrate = Anzahl Seitenfehler / Zeiteinheit Für jeden Prozess wird die Seitenfehlerrate r gemessen Ø Einführung von zwei Schwellwerten r1 (obere Intervallgrenze) und r2 (untere Intervallgrenze) Ø Einstellung der Kachelanzahl S in Abhängigkeit von Seitenfehlerrate § Verringere Anzahl Kacheln, falls r < r1, d.h. S =S -1 § Erhöhe Anzahl Kacheln, falls r > r2, d.h. S = S + 1 Seitenfehler- rate r S erhöhen r2 r1 S verringern Anzahl Kacheln S Systemprogrammierung 48