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:
- Rekursion: Da die lokalen Variablen nicht direkt der Funktion
sondern einer Aktivierung zugeordnet sind, können Funktionen auch
rekursiv verwendet werden. Der Code einer Funktion wird so von
ihren Daten getrennt und erlaubt so mehr als eine Aktivierung zur
Zeit.
- Datenstrukturen dynamischer Größe: da ein Rahmen eine
dynamische Größe hat, ist es möglich, den Speicherbedarf der
enthaltenen lokalen Variablen erst zur Laufzeit festzulegen. Somit
könnte also die Größe eines Arrays, das auf dem Stack angelegt
wird, erst zur Laufzeit festgelegt werden.
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: Garbage Collection
Up: Speicherverwaltung
Previous: Speicherverwaltung
  Inhalt
2001-02-28