Der Seitenverwaltungs-Algorithmus (System-Working-Set-Verfahren, SYS-WS) verwaltet die Hauptspeicher-Seiten global, wobei die Einteilung entsprechend ihrem „Zugriffsalter“ in fünf Gruppen erfolgt:
Gruppe 1 | Seiten, die gerade den Frame zugewiesen bekommen haben | Aktive Gruppen: System-Working-Set |
Gruppe 2 | Seiten, bei denen eine Referenz vorlag, deren CPU-Zeit noch nicht abgelaufen war oder die eine zweite Chance verdient haben | |
Gruppe 3 | Seiten, die zur Überprüfung des Referenz-Indikators anstehen | |
Gruppe 4 | Seiten, die bei der periodischen Working-Set-Überprüfung als Kandidaten zur Verdrängung aus dem System-Working-Set ermittelt worden sind | |
Gruppe 5 | Read Write Queue: Seiten, die noch auf die Paging-Area gesichert werden müssen Read Only Queue: Seiten, die ein Abbild auf der Paging-Area haben Empty Queue: Freie Frames | Inaktive Gruppe: Free-Pool |
Die Seiten jeder Gruppe - genauer gesagt die Hardware-Frames auf denen die Seiten liegen - sind miteinander verkettet.
Prinzipieller Ablauf
Grundsätzlich wird versucht, möglichst viele Seiten aktiv zu halten. Der Free-Pool ist daher relativ klein. Eine gewisse Minimalgröße zur Befriedigung schnell aufeinander folgender Seitenanforderungen ist jedoch notwendig. Bei Erreichen der Minimalgröße wird daher eine Free-Pool-Regulierung mit dem Ziel durchgeführt, immer genügend freie Frames in der Empty Queue vorrätig zu haben.
Das System-Working-Set-Verfahren wählt nach dem LRU(Least Recently Used)-Verfahren die Seiten aus, die zugreifbar im Hauptspeicher bleiben, und die Seiten, die aus dem System-Working-Set in den Free-Pool verdrängt werden:
- Modifizierte Seiten kommen dabei an das Ende der Read Write Queue, da der Seiteninhalt noch auf die Paging-Area gesichert werden muss. Die Paging-Routine sorgt durch Zurückschreiben von Seiten aus der Read Write Queue und anschließendem Umhängen in die Read Only Queue dafür, dass die Read Only Queue im Normalfall nie leer wird.
- Nicht-modifizierte Seiten kommen an das Ende der Read Only Queue, da bereits ein Abbild der Seite auf der Paging-Area existiert.
Bei der Freigabe einer Hauptspeicherseite kommt der zugehörige Frame in die Empty Queue.
Wird eine Hauptspeicherseite angefordert, dann entnimmt das System einen Frame aus der Gruppe 5, füllt ihn bei Bedarf mit dem aktuellen Seiteninhalt aus der Paging-Area oder - bei neu angeforderten Seiten - mit Nullen und bringt ihn dann in die Gruppe 1. Danach ist die Seite zugreifbar und der Referenz-Indikator ist gesetzt.
Außer bei einem Reclaim, bei dem der Eigentümer auf eine bereits deaktivierte Seite im Free-Pool neu zugreift, bedient das System Seitenanforderungen immer aus der Empty Queue, die die unbenutzten Frames enthält. Wird die Empty Queue dadurch zu klein, wird sie aufgefüllt mit Seiten aus der Read Only Queue. Diese enthält Seiten, die überschrieben werden dürfen, weil ihr Inhalt bereits auf der Paging-Area gesichert ist. Beim Übergang in die Empty Queue "verlieren" die Seiten ihren Eigentümer und danach ist kein Reclaim mehr möglich.
Die Empty Queue und die Read Only Queue bilden den Vorrat, aus dem das System Speicheranforderungen unmittelbar befriedigen kann. Wird dieser Vorrat zu klein, schreibt das System Seiten aus der Read Write Queue, die Seiten mit neuem/geändertem Inhalt enthält, auf die Paging-Area. Mit Ende des Schreibvorgangs können die Seiten im Speicher überschrieben werden und gelangen in die Read Only Queue.
Zur Ermittlung, ob eine Seite referenziert wurde, wird von der Hardware (auf x86-Servern von X2000 nachgebildet) beim Zugriff auf die Seite der zugehörige Referenz-Indikator gesetzt.
Beim System-Working-Set-Verfahren gilt:
- Referenzierte Seiten bleiben immer im System-Working-Set.
- Task-lokale Seiten bleiben auch bei Nicht-Referenz im System-Working-Set, wenn die Task seit dem letzten Zugriff eine bestimmte CPU-Zeit noch nicht verbraucht hat.
- Globale Seiten bleiben bei Nicht-Referenz noch einmal im System-Working-Set, d.h. sie bekommen eine zweite Chance und werden erst bei der nachfolgenden Prüfung verdrängt, wenn bis dahin keine Referenz vorliegt.
- Fixierte Seiten bleiben immer im System-Working-Set.
Das System-Working-Set-Verfahren wird sowohl On-Demand bei Engpässen im Free-Pool als auch periodisch in bestimmten Zeitabständen durchgeführt bzw. wenn eine Logische Maschine in den Zustand 'IDLE' geht.
Der einfache Algorithmus des SYS-WS-Verfahrens führt zu einer Aufwandsreduzierung im Paging-Management, aber auch zu einer „gröberen“ Bestimmung des Working-Set-Bedarfs der einzelnen Tasks. Die Aufwandsreduzierung macht sich besonders bei großem Hauptspeicher bemerkbar.
Wird eine Task deaktiviert, so behält sie auch im inaktiven Zustand ihren Working-Set. Wird die Task erneut aktiviert, sind keine Page-Reclaims zur Wiederbeschaffung ihres Working-Sets notwendig.
Das SYS-WS-Verfahren kennt zwar den UPG-Wert (Used-Pages) jeder Task, hat jedoch keine Möglichkeit festzustellen, in welcher Phase sich die Task befindet (auch inaktive Tasks haben einen UPG-Wert != 0).
Die Bestimmung des PPC-Wertes (Planned Page Count) erfolgt daher näherungsweise durch einen Vergleich des UPG-Wertes mit einem angenommenen, vom Kategorietyp abhängigen, mittleren Working-Set-Wert.
Da möglichst viele Seiten aktiv gehalten werden, liegt der Summen-UPG-Wert praktisch immer in der Größenordnung des verfügbaren seitenwechselbaren Hauptspeichers und hat nur begrenzte Aussagekraft. Der Working-Set-Bedarf wird ausschließlich durch den PPC-Wert ausgedrückt. Der Wert ist eine grobe Schätzung. Bei den heute üblichen großen Speicherausbauten ergeben sich Vorteile dadurch, dass die Aufwände für die ohnehin nicht benötigte genaue Abschätzung des Speicherbedarfs unterbleiben.