next up previous contents
Next: Garbage Collection Up: Speicherverwaltung Previous: Speicherverwaltung   Inhalt


Allokation

Unter Speicherallokation wird die Zuordnung von Speicherbereichen zu Programmsymbolen verstanden. Der Unterteilung von [Jones and Lins, 1996] folgend unterscheiden wir prinzipiell drei Methoden der Speicherallokation:

1.
Statische Allokation: Der benötigte Speicher wird zur Übersetzungszeit statisch vergeben, d.h. die Symbole im Programmtext werden bereits vom Compiler einer bestimmten (u.U. relativen) Speicheradresse zugeordnet. Sprachen, die allein statische Allokation verwenden, können keine Rekursion unterstützen, da die lokalen Variablen einer Funktion nur einmal angelegt werden. Weiterhin muß die Größe einer Datenstruktur bereits zum Zeitpunkt der Übersetzung bekannt sein, d.h. dynamische Datenstrukturen können mit dieser Form der Allokation nicht implementiert werden. Ausschließlich statische Allokation wird z.B. von Fortran 77 [Nyhoff and Leestma, 1995] verwendet - modernere imperative Sprachen wie Pascal und C verwenden sie lediglich für die Allokation von globalen Variablen.
2.
Stack-Allokation: Bei der Stack-Allokation werden Parameter und lokale Variablen beim Aufruf einer Funktion auf einem Stack abgelegt. Der auf dem Stack hierdurch belegte Bereich wird Rahmen (frame) genannt. Nach Beendigung der Funktion wird der Rahmen wieder abgebaut, d.h. der Speicherbereich steht der nächsten gerufenen Funktion zur Verfügung. Diese Form der Allokation eignet sich besonders gut für prozedurale Sprachen. Ihre Vorteile gegenüber der statischen Allokation sind im Wesentlichen: Eine weitere Konsequenze von Stack-Allokation ist, daß eine gerufenen Aktivierung niemals länger als die aufrufende existieren kann. Dies ist die Grundannahme, die zwar blockstrukturierten Sprachen zugrundeliegt, in (meist funktionalen) Sprachen mit Funktionsabschlüssen (closures) jedoch nicht mehr gilt. Weiterhin stellt die Tatsache, daß die Größe des Rückgabewertes zur Übersetzungszeit feststehen muß, und damit für eine bestimmte Funktion konstant ist, eine erhebliche Begrenzung im Programmiermodell dar.
3.
Heap-Allokation: Der Hauptnachteil der Stack-Allokation ist die Tatsache, daß dynamische Datenstrukturen nicht als Rückgabewert einer Funktion dienen können. Dieses Problem wird durch Heap-Allokation (oftmals als ,,dynamische Speicherverwaltung`` bezeichnet) behoben. Hier werden mit Hilfe einer Bibliotheksfunktion, die das Laufzeitsystem der verwendeten Sprache bereitstellt (in Pascal z.B. new), Objekte beliebiger Größe und unbegrenzter Lebenszeit in einem ausgezeichnetem Speicherbereich, dem Heap, angelegt. Dadurch können dynamische Datenstrukturen angelegt werden und auch als Rückgabewert einer Funktion dienen.

Heap-Allokation wirft jedoch neue Probleme auf: da die Verwendung des Speichers nicht mehr statisch vom Compiler ermittelt werden kann, muß die Speicherfreigabe ebenso wie die Allokation unter Programmkontrolle erfolgen. Dabei ist zu ermitteln, welche Speicherbereiche freigegeben werden dürfen und welche vom laufenden Programm noch benötigt werden. Klassische imperative Sprachen wie Pascal und C überlassen diese Entscheidung dem Programmierer, indem sie explizite Bibliotheksfunktionen bereitstellen, mit deren Hilfe ein Speicherbereich als unbenutzt markiert und somit dem Laufzeitsystem ,,zurückgegeben`` wird (in Pascal z.B. dispose). Das Programmiermodell der prozeduralen, imperativen Programmierung baut ohnehin hauptsächlich auf Stack-Allokation auf, so daß diese ,,Unannehmlichkeit`` akzeptiert wird.

Mit der Verwendung von abstrakten Datentypen in modularen, funktionalen und objektorientierten Sprachen führt diese ,,manuelle Speicherverwaltung`` jedoch zu erheblichen Problemen, da die Zuständigkeit für die Freigabe eines Speicherbereiches nicht mehr eindeutig festzulegen ist. Funktionale und objektorientierte Sprachen wie Lisp, Smalltalk und Java sind daher mit automatischer Speicherverwaltung ausgestattet, die selbst ermittelt, welche Programmobjekte nicht mehr verwendet werden können, und diese daraufhin dem vorhandene Freispeicher hinzufügt.


next up previous contents
Next: Garbage Collection Up: Speicherverwaltung Previous: Speicherverwaltung   Inhalt

2001-02-28