Dynamische Speicherverwaltung
1. Einleitung - Wozu dynamische Speicherverwaltung?
Bisher haben wir verschiedenste Datenstrukturen kennengelernt:
· Basistypen wie int , float, char usw.
· Arrays von Basistypen
· Strukturen
· Arrays von Strukturen
Diese Strukturen sind grundlegend, weil sie Bausteine für komplexere Strukturen darstellen und auch in der Praxis vorkommen. Der Sinn der Deklaration (Eigenschaften festlegen) eines Datentyps und der Definition einer Variablen von diesem Typ ist die Festlegung des Wertebereichs dieser Variablen und damit auch ihres Speicherschemas. So vereinbarte Strukturen (Typen) heißen daher statisch.
Es gibt viele Probleme, die weit kompliziertere Datenstrukturen erfordern. Wesentlich für diese Probleme ist die Veränderbarkeit ihrer Strukturen während der Ausführung. Solche veränderbaren Strukturen heißen dynamisch. Natürlich sind die Komponenten dieser Strukturen in irgend einer Form statisch.
Dynamische Strukturen werden z.B. bei Erstellung von Indices benötigt. Ein Index ist eine sortierte Liste von Worten eines Dokuments mit dazugrhörigen Seitennummern. Es ist von vornherein nicht klar, wieviele Wörter in diesem Index vorkommen werden und vor allem nicht, an wieviel Stellen ein Wort (Seitennummern) vorkommt.
2. Prinzip der Speicherverwaltung
2.1. Implementierung einer einfachen Speicherverwaltung
Wir verwenden als "Reservoir" einen Zeichenvektor, von dem man Teile mit der Funktion alloc allozieren kann und mit afree wieder freigeben kann. alloc liefert einfach Zeiger auf Abschnitte in allocbuf .
Die Funktionen arbeiten mit Zeigern. Der Vektor wird mit static definiert (wird an anderer Stelle erklärt). Wir müssen auch noch wissen, wieviel von allocbuf schon verteilt wurde. Wir benutzen dazu den Zeiger allocp .
Werden n Zeichen mit alloc angefordert, so wird zunächst überprüft, ob noch genug Speicher vorhanden ist. Ist nicht genug da, so wird NULL zurückgeliefert andernfalls wird allocp um n inkrementiert, damit allocp auf den nächsten freien Bereich zeigt.
afree( p ) setzt einfach allocp auf p , wenn p auf eine Position in allocbuf zeigt.
Vor Aufruf von alloc :
Nach Aufruf von alloc :
#define ALLOCSIZE 10000 /* verfügbarer Platz */
static char allocbuf[ALLOCSIZE]; /* Speicher für alloc */
static char *allocp = allocbuf; /* nächste freie Position */
char * alloc( int n ) /* liefert Zeiger auf Platz für n */
{ /* Zeichen */
if ( allocbuf + ALLOCSIZE - allocp >= n ) /* passt */
{
allocp += n;
return( allocp - n ); /* alter Zeiger */
}
else /* nicht genug Platz */
return( NULL );
}
void afree( char *p ) /* Speicher ab p wieder freigeben */
{
if ( p >= allocbuf && p < allocbuf + ALLOCSIZE )
allocp = p;
}
Diese Implementierung hat den großen Nachteil, daß reservierter Speicher in umgekehrter Reihenfolge (des Reservierens) wieder freigegeben werden muß, da sonst neu angeforderter Speicher einen bereits belegten überschreiben könnte.
Folgendes Programm zeigt eine Verwendung von alloc und afree.
int main( int argc, char *argv[] )
{
char buf[80];
char *s1;
char *s2;
printf( "%s, geben Sie einen String ein> ", argv[0] );
fflush( stdout );
gets( buf );
s1 = alloc( strlen( buf ) + 1 ); /* Speicher allozieren,*/
/* '\0'!!! */
strcpy( s1, buf );
printf( "%s, geben Sie noch einen String ein> ", argv[0]);
fflush( stdout );
gets( buf );
s2 = alloc( strlen( buf ) + 1 ); /* Speicher allozieren,*/
/* '\0'!!! */
strcpy( s2, buf );
printf( "s1 = %p\n", s1 );
printf( "s2 = %p\n", s2 );
printf( "Inhalt \"Buffer\" s1: %s\n", s1 );
printf( "Inhalt \"Buffer\" s2: %s\n", s2 );
afree( s2 ); /* freigeben von s2 */
afree( s1 ); /* freigeben von s1 */
}
2.2. Eine Verbesserung
Eine bessere (reelle) Speicherverwaltung sollte es auch ermöglichen, allozierten Speicher in beliebiger Reihenfolge wieder freizugeben. Dabei entstehen nun "Löcher" in allocbuf . Diese könnten bei den nächsten alloc -Aufrufen wieder verwendet werden.
Man benötigt also eine Liste von freien Speicherbereichen und eine Liste für belegte Bereiche.
Man könnte folgende Struktur verwenden:
typedef struct
{
unsigned char belegt; /* 0...frei, 1...belegt */
unsigned int size; /* Länge des Blocks */
} alloc_t;
Initialisiert wird nun wie folgt:
#define ALLOCSIZE 10000 /* verfügbarer Platz */ static char allocbuf[ALLOCSIZE];/* Speicher für alloc */ alloc_t *allocp = (alloc_t *)allocbuf; /* nächste freie Position*/
allocbuf hat dann folgenden Aufbau:
returnp enthält jene Adresse, die beim ersten alloc zurückgeliefert wurde.
Generell wird so alloziert (alloc( n )):
Beginnend mit der Adresse von allocbuf
wird immer geprüft, ob
allocp->belegt == 0
Wenn dies der Fall ist, dann muß noch geprüft werden, ob
n < allocp->size
Trifft dies zu, dann muß
allocp->belegt = 1;
allocp->size = n;
gesetzt werden, sowie an der Stelle allocp
+ n wieder eine neue Struktur vom Typ alloc_t eingefügt
werden, wo
belegt = 0;
size = RestlicherBereich;
ist.
Ist allocp->belegt == 1
, dann muß
allocp = (alloc_t *)((char *)allocp + sizeof(alloc_t) + allocp->size)
gesetzt werden. Mit diesem Zeiger wird obige Überprüfung neuerlich durchgeführt.
Wird auf diese Weise kein freier Bereich gefunden, so liefert alloc( n ) den Wert NULL .
Freigegeben wird so (afree( p ) ):
Es muß geprüft werden, ob p
innerhalb von
allocbuf und (char *)allocbuf +
ALLOCSIZE - 1
liegt, wenn ja, dann muß noch geprüft werden, ob an der Stelle
(char *)p - sizeof( alloc_t ) "
belegt" eingetragen ist. Ist dies der Fall, so kann dieser Block
freigegeben werden. Sind die Nachbarblöcke ebenfalls "frei
" markiert, sollten sie zu einem Block zusammengefaßt werden.
Achtung: obige Prüfung stellt natürlich nicht sicher, daß p wirklich ein gültiger Zeiger ist. Es könnte zufällig sein, daß bei einem ungültigen Zeiger, der aber innerhalb der Grenzen liegt, die Daten an der Stelle zufällig "richtige" Werte darstellen (also "frei" + eine mögliche Größe).
Der interessierte Leser möge als Übung diese Speicherverwaltung implementieren und damit experimentieren.
3. ANSI-C Funktionen zur Speicherveraltung
Natürlich ist es nicht nötig, eine Speicherverwaltung selbst zu implementieren. Es gibt Bibliotheksfunktionen, die eine dynamische Speicherverwaltung zur Verfügung stellen. Diese Library-Funktionen fordern vom Betriebssystem den nötigen Speicher in größeren Blöcken an und geben dann die geforderten Speicherbereiche an die Applikation weiter.
Die Funktionen zur dynamischen Speicherverwaltung sind in der Standardlibrary enthalten:
#include <stdlib.h>
void *malloc( size_t n );
liefert einen Zeiger auf einen (uninitialisierten) Speicherbereich von n Bytes, oder NULL, falls nicht genügend Speicher vorhanden ist.
void *calloc( size_t n, size_t size );
liefert einen Zeiger auf genügend Speicher für einen Vektor von n Objekten der angegebenen Größe size . Ist nicht genügend Speicher vorhanden, so ist der Resultatwert NULL. Der Speicher wird mit 0 initialisiert .
Der Zeiger, den malloc oder calloc liefert, hat die korrekte Ausrichtung für das gewünschte Objekt, muß aber noch mit einer Umwandlungsoperation (cast) in den richtigen Datentyp umgewandelt werden, z.B.
int *ip;
ip = (int *) calloc( n, sizeof( int ) );
void free( void *p );
free( p ) stellt den Speicher wieder zur Verfügung (für neuerliches malloc ), auf den p zeigt. Dabei stammt p ursprünglich von einem Aufruf von malloc oder calloc. Speicher kann zwar in beliebiger Reihenfolge freigegeben werden, es ist jedoch ein entsetzlicher Fehler, wenn etwas freigegeben wird, was nicht von calloc oder malloc stammt (vgl. weiter oben).
Natürlich ist es auch falsch, etwas zu verwenden, das schon freigegeben wurde.
void *realloc(void *ptr, size_t size);
realloc ändert die Größe des Speicherblocks, auf den ptr zeigt auf die Größe size Bytes. Der Inhalt wird nicht verändert bis zum Minimum der Größe des alten und des neuen Wertes. Ist ptr NULL, so verhält sich der Aufruf von realloc wie der von malloc . Ist size 0, dann ist der Aufruf äquivalent zu free( ptr ) .
malloc liefert NULL, wenn nicht genügend Speicher alloziert werden konnte. Der originale Speicher von ptr bleibt dabei aber unverändert.