Gibt es Müllsammler, die Paging berücksichtigen?

12

Garbage Collections müssen alle Objekte besuchen, die noch leben, um den Speicher zu finden, der wiederhergestellt werden kann. (Mit vielen Generationen verzögert sich das nur ein bisschen)

Wenn alle Dinge gleich sind, ist es eindeutig besser, zuerst das Objekt zu besuchen, das bereits in den RAM ausgelagert ist, bevor ein anderer Block eingelagert und daher ein Objekt ausgelagert wird.

Eine weitere Möglichkeit besteht darin, dass, wenn das Betriebssystem eine Seite RAM aus dem Prozess entfernen möchte, der GC zuerst gefragt wird, ob eine Seite vorhanden ist, die aufgegeben werden kann, ohne dass sie ausgelagert werden muss. Der GC kann meistens mit dem Verschieben von Objekten von einer Seite durchgeführt werden, sodass diese Seite innerhalb des Zeitlimits gelöscht werden kann, innerhalb dessen das Betriebssystem eine Seite benötigt.

Ich kann mich jedoch nicht an einen Garbage Collector erinnern, der in das Betriebssystem-Paging-System integriert ist und die Reihenfolge bestimmt, in der der GC arbeitet.

Ian Ringrose
quelle
Nicht gerade Paging, sondern die Ruby Enterprise Edition gc wurde neu geschrieben, um die Auswirkungen der gc auf das Kopieren auf Schreibseiten zu verringern, indem Objekt-Metadaten auf separate Seiten verschoben werden.
user1937198
überraschenderweise, afaik / afaict, scheint fast die gesamte (?) gc-Literatur OS-Paging nur abstrakt zu analysieren. Idee: Ein Speicherzuweisungssystem, das die Verfolgung von Zeigern zwischen Objekten in einer Struktur getrennt von den Objekten selbst verfolgt, ist möglicherweise lokaler / paging-freundlicher, da nur die Zeiger selbst (während gc) in einem eng komprimierten Raum statt aller Objekte von gc durchlaufen werden verschiedene Größen, die im Speicher verteilt sein können (und einige, auf die selten zugegriffen wird und die so ausgelagert sind). Je nach Implementierung kann es zu geringfügigen Kosteneinsparungen kommen.
VZN
Flash-Laufwerke müssen eine Form des Kopierens von Garbage Collection verwenden, die die Anordnung des Speichers in Blöcken berücksichtigt, obwohl ich nicht weiß, wie gut solche Dinge in der akademischen Literatur diskutiert werden. Die dort zu lösenden Probleme sind sehr unterschiedlich (Flash-Laufwerke benötigen GC, da der Speicherplatz nur in sehr großen Blöcken wiederverwendet werden kann. Wenn ein Block also einige Live-Seiten und viele tote Seiten enthält, müssen die Live-Daten vor der Seite an eine andere Stelle kopiert werden kann recycelt werden), aber die Grundsätze der Datenkonsolidierung könnten hilfreich sein.
Supercat
Ein Muster, das ich in Fällen verwendet habe, in denen Datenelemente im Verhältnis zu meiner Speicherblockgröße alle klein waren, bestand darin, dass jedes Datenelement aus einem Header mit fester Größe, der von vorne nach hinten zugewiesen wurde, und Daten mit variabler Größe bestand von hinten nach vorne zugewiesen werden. In einer Tabelle wurden logische Blockadressen den physischen Adressen und dem freien Speicherplatz in jedem Block zugeordnet. Nach jedem Scan wird auch festgestellt, wie viel Speicherplatz tot ist. Verweise wurden in Flash gespeichert, und jeder Verweis hatte die Form "Element # 3 des logischen Blocks # 7". Ein GC-Zyklus würde alle Live-Daten von einem Block in einen neuen kopieren und ...
supercat

Antworten:

8

Wie ich mich erinnere, sollten Kopiersammler paging-freundlich sein, da das Verfolgen durch Kopieren dazu neigt, die Lokalität von Zeigerreferenzen zu verbessern. Dies wirkt sich positiv auf das Programm (Mutator) aus, das beim Verfolgen von Links weniger Seitenfehler verursacht und auch den nächsten Erfassungszyklus verbessert, da die Ablaufverfolgung auch weniger Seitenfehler verursacht. Die Ablaufverfolgungsagenda (welche Zeiger zuerst verarbeitet werden sollten) kann sich auf die Wirksamkeit zur Verbesserung der Datenlokalität auswirken. Dies kann verbessert werden, indem Statistiken über die Anzahl der Zugriffe auf verschiedene Zeiger in verschiedenen Zelltypen erstellt werden.

Wenn Sie nun generell einen Tracing-Collector in Betracht ziehen, müssen Sie normalerweise eine Struktur pflegen, die die noch nicht verfolgten Zeiger verfolgt. Es kann möglich sein, diese Struktur so zu organisieren, dass alle auf dieselbe Seite zeigenden Wartezeiger zusammengehalten werden (obwohl dies in einigen Fällen mehr Platz in Anspruch nimmt, abhängig von den verfügbaren Techniken, um die Liste solcher Zeiger zu führen). Eine mögliche Richtlinie besteht darin, immer zuerst den größten Satz von Wartezeigern zu verfolgen, die auf dieselbe Seite zeigen, wenn kein Wartezeiger mehr auf die Seiten im Speicher vorhanden ist.

In Bezug auf die Frage im dritten Absatz, die hinzugefügt wurde, nachdem ich geantwortet habe, ist das Sammeln von Kopien erneut eine Antwort. Das Betriebssystem kann die Anzahl der zugewiesenen physischen Seiten zur Erfassungszeit reduzieren, da die Seiten vollständig freigegeben werden. Bei einem Mark-and-Sweep-Sammler ist das Ereignis, dass eine ganze Seite frei ist, wahrscheinlich viel seltener und daher keinen bestimmten zu berücksichtigenden Mechanismus wert.

Diese Art von Ideen ist natürlich und wird wahrscheinlich in einigen Veröffentlichungen beschrieben. Aber ich kann mich nicht sofort daran erinnern. Ich denke, die frühen Veröffentlichungen zu Lisp GC enthalten einige dieser Ideen (z. B .: Sollte zuerst Auto oder CDR befolgt werden?).

Die gute Nachricht bei dieser Rolle der Kopiersammlung ist auch, dass das Paging die Kopiersammlung erleichtert, da der verfügbare Speicherplatz vergrößert wird. Erinnern Sie sich daran, dass der Kopiersammler im Prinzip doppelt so viel Speicherplatz benötigt wie für die eigentliche Datenspeicherung. Die Auswirkung von Paging hängt nun auch vom Adressraum des Computers und dem verfügbaren physischen Speicher ab. In älteren Computern war der physische Speicher viel kleiner als der verfügbare Adressraum, so dass Paging wirklich ein Platzbonus war, der Richtlinien wie das Kopieren von GCs ermöglichte. Selbst wenn der physische Raum so groß ist wie der Adressraum, kann es sinnvoll sein, ihn gemeinsam zu nutzen, damit der Prozess, der einen GC verwendet, ohne Paging weniger Adressraum hat (siehe Paging)). Diese Ausführungen werden durch den Einsatz von Generationssammlern etwas überholt. In der Regel nutzen sie das Sammeln von Kopien gerade wegen dieser Eigenschaften für die junge Generation, und weil die junge Generation meist nur von kurzer Dauer ist.

Dann haben Sie alle Interaktionen von Generations-GC mit dem Cache-System, die in einer vorherigen Frage behandelt wurden: Sind Generations-Garbage-Collectors von Natur aus Cache-freundlich?

Für weitere Informationen zu diesem Thema würde ich das Web beispielsweise mit den Stichwörtern Garbage Collection und Locality durchsuchen .

babou
quelle
Ich bin mir nicht sicher, ob die Sammler von Kopien tatsächlich "lokaler" sind als die Verfolgung. Kopiersammler scheinen konzeptionell in der Dynamik des Speicherzugriffs (möglicherweise kaum zu unterscheiden) der Verfolgung des "alten Raums" sehr ähnlich zu sein. denke, das braucht eine Referenz. das heißt, es gibt eine Möglichkeit, dass der Kopiermechanismus die Kontiguität in dem neuen Raum verbessert. Der neue Raum beginnt vollkommen zusammenhängend, aber dann nimmt diese "Lokalität" mit der Zeit ab oder verschlechtert sich.
VZN
Nun, Sie haben den größten Teil der Antwort gefunden. Sei also nicht zweifelhaft. Es handelt sich bei den Basisreferenzen um das Thema. Lokalität aufgrund der Tatsache, dass der Speicher komprimiert wird, und aufgrund des Kopiervorgangs, bei dem Datenzellen, die gemäß der Zeigerstruktur logisch nahe beieinander liegen (die sich möglicherweise bei einer Zeigerneuzuweisung entwickeln), dicht beieinander ersetzt werden.
Babou
bin immer noch skeptisch / zweifelhaft. es scheint intuitiv, dass der alte Raum eine schlechte Lokalität und / oder Kontiguität aufweist, wenn der Kopier- / Gc-Zyklus initiiert wird. Die Lokalität bezieht sich auf das Lesen (aus dem alten Raum) und Schreiben (in den neuen Raum). um es zu analysieren, muss das gestalt- / emergente verhalten untersucht werden. Möglicherweise kann vieles davon nur effektiv / genau / realistisch empirisch und nicht viel theoretisch untersucht werden.
VZN
Ich sage es ist in der Literatur, wie viele andere Dinge. Aber ich habe keine Zeit, danach zu suchen, und ich denke, meine Antwort ist lang und voller Informationen. Tut mir leid, dass ich knapp bin, ich muss einen Zug erwischen.
Babou
Sorry ... verwechsle diese Frage mit einer anderen ... die mehr hat.
Babou
7

Emery Berger, Matthew Hertz und Yi Feng haben daran gearbeitet.

Die Garbage Collection bietet zahlreiche Vorteile bei der Softwareentwicklung, interagiert jedoch schlecht mit virtuellen Speichermanagern. Bestehende Garbage Collectors erfordern weitaus mehr Seiten als die Arbeitsseiten und Kontaktseiten der Anwendung, unabhängig davon, welche sich im Speicher befinden, insbesondere während der Garbage Collection mit vollem Heap. Das resultierende Paging kann dazu führen, dass der Durchsatz sinkt und die Pausenzeiten auf Sekunden oder sogar Minuten ansteigen.

Ich stelle einen Müllsammler vor, der Paging vermeidet. Dieser Lesezeichensammler arbeitet mit dem virtuellen Speichermanager zusammen, um seine Räumungsentscheidungen zu steuern.

Dies ist ein Video von Emerys Vortrag darüber, und er schrieb eine Zeitung Garbage Collection Without Paging

Aus einigen Gründen scheint es nicht viel spätere Arbeiten zu geben oder eine Verwendung in der „realen Welt“. Am Ende des Artikels heißt es: „Wir entwickeln eine parallele Variante des Algorithmus für die Erfassung von Lesezeichen“ , aber ich kann sie nicht aufspüren.

CRAMM: Die Unterstützung des virtuellen Speichers für Garbage-Collected-Anwendungen versucht, das Betriebssystem so zu ändern, dass GC weniger Paging erstellt.

Verwenden von Page Residency, um die Kompromisse bei der Verfolgung der Garbage Collection auszugleichen

Wir führen eine Erweiterung der meist kopierenden Sammlung ein, die die Seitenresidenz verwendet, um zu bestimmen, wann Objekte verschoben werden sollen. Unser Sammler wirbt für Seiten mit hoher Präsenz, um unnötige Arbeit und Platzverschwendung zu vermeiden. Es wird der Speicherort jeder Seite vorhergesagt. Wenn sich die Vorhersagen jedoch als ungenau herausstellen, verwendet unser Collector nicht belegten Speicherplatz, um Zuordnungsanforderungen zu erfüllen. Mithilfe von Residency kann unser Collector die Kompromisse zwischen Kopieren und Nicht-Kopieren von Sammlungen dynamisch ausgleichen. Unsere Technik benötigt weniger Platz als ein reiner Kopiersammler und unterstützt das Fixieren von Objekten, ohne die Fähigkeit zum Verschieben von Objekten zu beeinträchtigen. Im Gegensatz zu anderen Hybriden ist unser Sammler nicht von der anwendungsspezifischen Konfiguration abhängig und kann schnell auf sich änderndes Anwendungsverhalten reagieren. Unsere Messungen zeigen, dass unser Hybrid unter verschiedenen Bedingungen gute Leistungen erbringt. Es bevorzugt das Kopieren von Sammlungen, wenn genügend Speicherplatz vorhanden ist, greift jedoch auf nicht kopierende Sammlungen zurück, wenn der Speicherplatz begrenzt wird.

Ian Ringrose
quelle