Mammut: Eine Verteilte Speicherverwaltung Für Symbolische Manipulation

ISBN-13: 9783519021988 / Niemiecki / Miękka / 1997 / 120 str.

Holger Naundorf; Holger Naundorf

Opis

Viele moderne Programmiersprachen und insbesondere alle Computeralgebra-Systeme enthe ben den Programmierer von der Aufgabe der Deallokation nicht mehr benotigten Speichers. Dies erleichtert die Benutzung erheblich und hilft, eine groBe Anzahl von Fehlern zu vermei den. Entscheidender allerdings ist noch, daB es fUr den Programmierer unmoglich ist zu wissen, wann ein Speicherbereich wirklich freigegeben werden muB, wenn dieser von verschiedenen Stellen aus benotigt wird und sich die Anzahl dieser Stellen w?hrend des Programms andern kann. Beim Programmieren ist deshalb eine Schnittstelle unverzichtbar, die dem Benutzer die Auf gabe abnimmt zu entscheiden, wann ein Speicherbereich wirklich freigegeben werden kann. Eine solche Schnittstelle nennt man Garbage Kollektor oder einfach Kollektor. Obwohl die existierende Hardware in sehr kurzen Zyklen verbessert wird, gibt es viele An wendungen, bei denen die Rechenleistung oder der vorhandene Speicherplatz fur eine LOsung in angemessener Zeit nicht ausreichen. Unabhangig von der Entwicklung der Hardware wird es solche Probleme immer geben. Eine naturliche Methode, sowohl die Rechenleistung als auch den zur Verfugung stehenden Speicher zu erhohen, ist die Benutzung von parallelen und verteilten Rechnern. Insbesondere verteilte Rechner haben den Vorteil, daB sich ihre Rechenleistung und der benutzbare Speicher beinahe beliebig skalieren I?flt. Bei der Losung sehr speicherplatzintensiver Probleme sollte moglichst das mehrmalige Spei chern von Daten auch auf verteilten Rechnern vermieden werden. Dies bedeutet, daB von allen verteilten Rechnern eine Art gemeinsamer Speicher benutzt werden muB.

Spis treści

1. Einleitung.- 2 Grundlagen der Garbage Collection.- 2.1 Grundkonzept.- 2.2 Zwei-Phasen-Abstraktion.- 2.3 Zellen-Repräsentation.- 2.4 Verschieben von Zellen.- 2.4.1 Vorteile.- 2.4.2 Nachteile.- 2.5 Referenzzähl-Kollektor.- 2.6 Mark-Sweep-Kollektor.- 2.7 Mark-Compact-Kollektor.- 2.7.1 Einfache Implementation.- 2.7.2 Verbesserte Implementation.- 2.8 Copying Kollektor.- 2.9 Mostly-copying Kollektoren.- 2.10 Non-Copying Implicit Kollektor.- 2.11 Generational Kollektor.- 2.11.1 Subheaps mit unterschiedlicher Collection-Frequenz.- 2.11.2 Erkennen von Zeigern zwischen den Generationen.- 2.12 Inkrementelle und nebenläufige Kollektoren.- 2.12.1 Dreifarbmarkierung.- 2.12.2 Read- und Write-Barriers.- 2.12.3 Implementation von Barriers.- 2.12.4 Replication-basierter Kollektor.- 2.13 Kollektoren für multi-threaded Mutatoren.- 2.13.1 Referenzzähl-Kollektoren.- 2.13.2 Stop-and-Copy Kollektor.- 2.13.3 Inkrementeller Copying Kollektor.- 2.13.4 Kollektor für speziellen Parallelismus.- 2.14 Verteilte Kollektoren.- 2.14.1 Referenzzähl-Kollektoren.- 2.14.2 Referenzlisten.- 2.14.3 Tracing-basierte Kollektoren.- 2.15 Finalization.- 3 Die MAMMUT-Schnittstelle intuitiv.- 3.1 Einführung.- 3.1.1 Motivation.- 3.1.2 Überblick.- 3.2 MAMMUT-Zellen.- 3.3 Initialisierung von MAMMUT.- 3.4 Allokation.- 3.5 Freigabe.- 3.6 Größenveränderung.- 3.7 Vergleichen und Kopieren.- 3.8 Zugriff auf den Inhalt.- 3.8.1 Veränderung ohne Seiteneffekte.- 3.8.2 Zugriff auf den Mem-Teil.- 3.8.3 Zugriff auf den Point-Teil.- 3.8.4 Zeiger in eine Zelle.- 3.8.5 Ende eines Zugriffs.- 3.9 Zugriff auf Statusinformationen.- 3.9.1 Größe einer Zelle.- 3.9.2 Typinformation.- 3.9.3 Signatur.- 3.9.4 Lock.- 3.9.5 Unverschiebbarkeit.- 3.10 Kommunikation mit anderen Prozessen.- 3.10.1 Globale C-Variablen.- 3.11 Definition des Root Sets.- 4 Programmbeispiele.- 4.1 Initialisierung eines Strings.- 4.1.1 Implementation 1.- 4.1.2 Implementation 2.- 4.2 Ersetzen in einem Baum.- 4.2.1 Implementation 1.- 4.2.2 Implementation 2.- 4.3 Ausführen einer Task.- 5 Die Speicherverwaltung MAMMUT.- 5.1 Formalisierung eines Zustandes.- 5.2 Die Variablen der Speicherverwaltung.- 5.3 Invarianten.- 5.4 Funktionen in alphabetischer Reihenfolge.- A Tabellen der Funktionen.- B Existierende Implementationen.- B.1 Gemeinsamkeiten der Referenzzähl-Versionen.- B.2 Debug-Version.- B.2.1 Verwendete Filenamen.- B.2.2 Die Option MMMDACTIV.- B.2.3 Die Option MMMMOVE.- B.2.4 Die Option MMMDEBUG.- B.3 Parallele Version.- B.3.1 Zugrundeliegendes Modell.- B.3.2 Verwendete Filenamen.- B.3.3 Implementation als Makro.- B.3.4 Implementation der S-Zeiger.- B.3.5 Allokieren und Freigeben.- B.3.6 Schnittstelle nach unten.- B.3.7 Portierung der Speicherverwaltung.- B.3.8 Probleme mit Referenzzählern.- B.3.9 Das Initialisierungsfile.- B.4 Automatische Version.- B.4.1 Implementation der S-Zeiger.- B.4.2 Allokation von S-Zeigern.- B.4.3 Kopieren und Freigeben von S-Zeigern.- B.4.4 Verändern von S-Zeigern.- B.4.5 Zugriff auf S-Zeiger.- B.4.6 Unverschiebbare Zellen.- B.4.7 Generational Garbage Kollektoren.- B.5 Verteilte Version.- B.5.1 Zugrundeliegende Funktionalität.- B.5.2 Implementation von S-Zeigern.- B.5.3 Anforderung und Freigabe von S-Zeigern.- B.5.4 Zugriff auf S-Zeiger.- B.5.5 Inaktivieren von S-Zeigern.- B.5.6 Test auf Gleichheit.- B.6 Implemenation gemeinsamer Variablen.

Blurb

Viele moderne Programmiersprachen und insbesondere alle Computeralgebra-Systeme entheben den Programmierer von der Aufgabe der Deallokation nicht mehr benötigten Speichers. Für den Programmierer ist es auch unmöglich zu wissen, wann ein Speicherbereich wirklich freigegeben werden muß, wenn dieser von verschiedenen, sich dynamisch ändernden Stellen aus benötigt wird. Beim Programmieren ist deshalb eine Schnittstelle unverzichtbar, die dem Benutzer die Aufgabe abnimmt zu entscheiden, wann ein Speicherbereich wirklich freigegeben werden kann. Eine solche Schnittstelle nennt man Garbage Kollektor oder einfach Kollektor. Es wird immer Probleme geben, für die die Leistung eines einzelnen Rechners nicht ausreicht. Eine natürliche Methode, sowohl die Rechenleistung als auch den zur Verfügung stehenden Speicher zu erhöhen, ist die Benutzung von parallelen und verteilten Rechnern. Insbesondere verteilte Rechner haben den Vorteil, daß sich ihre Rechenleistung und der benutzbare Speicher beinahe beliebig skalieren läßt. Bei der Lösung sehr speicherplatzintensiver Probleme sollte möglichst das mehrmalige Speichern von Daten auch auf verteilten Rechnern vermieden werden. Dies bedeutet, daß von allen verteilten Rechnern eine Art gemeinsamer Speicher benutzt werden muß. In diesem Buch wird eine Schnittstelle vorgestellt, die sowohl für die Freigabe von Speicher als auch für den Zugriff auf einen möglicherweise virtuellen gemeinsamen Speicher benutzt werden kann. Diese Schnittstelle ist Grundlage des Computeralgebra-Systems MuPAD. Inhalt Einleitung - Grundlagen der Garbage Collection - Die MAMMUT-Schnittstelle intuitiv - Porgrammbeispiele - Die Speicherverwaltung MAMMUT - Tabellen der Funktionen - Existierende Implementationen - Literaturverzeichnis - Index