In C können wir Variablen wie folgt definieren:
// Eine innerhalb einer Funktion deklarierte Variable wird üblicherweise auf dem Stack gespeichert.
int a = 42;
// Eine mit `static` oder auf Dateiebene deklarierte Variable wird üblicherweise in `.data`
// oder `.rodata` gespeichert.
static int b = 2026;
Der Speicherplatz für diese Variablen wird von der Sprache selbst verwaltet. Manchmal müssen wir den Speicher jedoch manuell verwalten. In solchen Fällen können wir mit Funktionen wie malloc(), calloc() und realloc() dynamisch zugewiesenen Speicher anfordern.
// Dynamisch zugewiesener Speicher stammt üblicherweise vom Heap.
int *c = malloc(sizeof *c);
*c = 42;
Wenn der Speicher nicht mehr benötigt wird, geben wir ihn mit free() frei.
free(c);
Dadurch können wir Speicher flexibel zuweisen und freigeben. So können wir alle möglichen komplexen Datenstrukturen implementieren und folglich viele Dinge realisieren, die mit ausschliesslich statisch zugewiesenem Speicher schwierig oder unmöglich wären.
Dieser Ansatz bringt jedoch auch ein Problem mit sich.
Betrachten wir das folgende Szenario:
int *a = malloc(sizeof *a);
int *b = a;
Wer ist dafür verantwortlich, den Speicher freizugeben?
Es liegt auf der Hand, dass es keine Lösung ist, die Speicherzuweisung überhaupt nicht freizugeben, da dies zu einem Speicherleck führen würde. Ebenso wenig ist es eine Lösung, sie über beide Zeiger freizugeben, denn das würde gemäss ISO/IEC 9899 undefiniertes Verhalten verursachen und wird üblicherweise als doppeltes Freigeben bezeichnet.
Wir sollten den Speicher nur über einen dieser Zeiger freigeben. Doch wie entscheiden wir, welcher dafür zuständig ist? Damit kommen wir zu einem wichtigen Konzept der Speicherverwaltung und allgemein der Ressourcenverwaltung: Besitz.
Besitz, Ausleihen und Übertragung
Besitz ist eine Vereinbarung, die festlegt, welcher Teil eines Programms für die Verwaltung einer Ressource und deren Freigabe verantwortlich ist, sobald sie nicht mehr benötigt wird. Wir sagen, dass eine Zeigervariable den Speicher besitzt, wenn sie vertraglich dafür verantwortlich ist, die entsprechende Speicherzuweisung mit free() freizugeben.
Um zu erklären, wie uns das Besitzkonzept bei der korrekten Verwaltung von Ressourcen hilft, implementieren wir eine verkettete Liste. Definieren wir zunächst die folgende Struktur:
typedef struct N
{
int data;
struct N *previous;
struct N *next;
} Node;
Wir verwenden previous == NULL, um einen Wächterknoten zu kennzeichnen (dessen Mitglied data keine Bedeutung hat), und next == NULL, um das letzte Element der verketteten Liste zu kennzeichnen.
Nehmen wir an, dass wir eine auf Dateiebene definierte Variable vom Typ Node haben und sie als unseren Wächterknoten verwenden:
Node l = {0, NULL, NULL};
Wir benötigen einige Funktionen, um diese verkettete Liste zu bearbeiten.
Definieren wir die folgenden Funktionen:
Node *getNode(Node *guard, int index)
{
if (index < 0)
return NULL; // Der Index ist negativ.
else if (index > 0 && guard->next == NULL)
return NULL; // Der Index liegt ausserhalb des gültigen Bereichs.
else if (index == 0)
return guard->next;
else return getNode(guard->next, index - 1);
}
void setData(Node *x, int data)
{
x->data = data;
}
int getData(Node *x)
{
return x->data;
}
Hier sind einige Anweisungen aus unserer Funktion main():
/* ... */
Node *a = malloc(sizeof *a);
a->previous = NULL;
a->next = NULL;
setData(a, 42);
printf("%d\n", getData(a));
/* ... */
Wer ist dafür verantwortlich, den von a adressierten Speicher freizugeben, nachdem setData() und getData() aufgerufen wurden? Offensichtlich ist weiterhin a dafür verantwortlich. setData() und getData() lesen oder verändern lediglich den Speicher, der ihnen über ihre Parameter übergeben wird; sie weisen keinen Speicher zu und geben auch keinen frei. Sie geben die Zeiger auch nicht an andere Funktionen oder globale Variablen weiter, die den Speicher ebenfalls verwalten würden. Deshalb sagen wir, dass diese Funktionen den Speicher ausleihen, statt den Besitz daran zu übernehmen.
Ausleihen bedeutet, dass eine Funktion Zugriff auf eine Ressource erhält, ohne die Verantwortung für deren Lebensdauer zu übernehmen. Je nach Schnittstellenvertrag darf die Funktion die Ressource lesen oder verändern, sie darf sie jedoch nicht eigenständig freigeben.
Dasselbe gilt für getNode(): Die Funktion durchläuft die verkettete Liste und ruft anhand eines Indexes einen Knoten ab. Sie weist keinen Speicher zu, gibt keinen Speicher frei und überträgt auch keinen Besitz.
Das ist jedoch nicht immer der Fall. Betrachten wir die folgenden Funktionen:
Node *createNode(int data)
{
Node *ans = malloc(sizeof *ans);
if (! ans)
exit(EXIT_FAILURE);
ans->data = data;
ans->previous = NULL;
ans->next = NULL;
return ans;
}
int insertNode(Node *guard, Node *n, int index)
{
if (index < 0)
return 1; // Der Index ist negativ.
else if (index > 0 && guard->next == NULL)
return 2; // Der Index liegt ausserhalb des gültigen Bereichs.
else if (index == 0)
{
if (guard->next)
{
n->next = guard->next;
guard->next->previous = n;
}
n->previous = guard;
guard->next = n;
return 0;
}
else return insertNode(guard->next, n, index - 1);
}
Wir können nun a an insertNode() übergeben, um den von uns zugewiesenen Knoten in die verkettete Liste einzufügen:
/* ... */
insertNode(&l, a, 0);
/* ... */
Was passiert nun?
Natürlich sollten wir free() nach einem erfolgreichen Aufruf von insertNode() nicht mehr für a aufrufen, da dies die verkettete Liste beschädigen würde. Stattdessen sollte der Knoten freigegeben werden, wenn wir die verkettete Liste zerstören:
void destroyExceptGuard(Node *guard)
{
if (guard == NULL)
return;
Node *current = guard->next;
guard->next = NULL;
while (current != NULL)
{
Node *next = current->next;
free(current);
current = next;
}
}
Wenn insertNode() einen Knoten erfolgreich einfügt, wird der Besitz an diesem Knoten vom Aufrufer auf die verkettete Liste übertragen. Die Funktion führt diese Übertragung durch, aber nach dem Einfügen ist die verkettete Liste für den Knoten verantwortlich.
Die Funktion createNode() bewirkt das Gegenteil: Sie weist Speicher zu und gibt einen Zeiger darauf zurück. Nach ihrer Rückkehr ist die Funktion nicht mehr für die Freigabe des Speichers verantwortlich. Stattdessen geht diese Verantwortung auf den Aufrufer über, der den zurückgegebenen Zeiger erhält. Wir sagen, dass die Funktion den Besitz an den Aufrufer überträgt.
Lebensdauern — Wie lange sollte eine Ressource bestehen?
Besitz zu haben bedeutet, dass der Besitzer nicht nur für die Freigabe des Speichers verantwortlich ist, sondern auch dafür, zu entscheiden, wann er freigegeben wird. Mit anderen Worten: Der Besitzer bestimmt die Lebensdauer der Ressource.
Allgemeiner gesagt ist Besitz eine Programmiervereinbarung, die festlegt, welcher Teil eines Programms für die Verwaltung der Lebensdauer einer Ressource und insbesondere für ihre Freigabe verantwortlich ist, sobald sie nicht mehr benötigt wird. Ein Zeiger kann auf eine Ressource verweisen, ohne sie zu besitzen, und mehrere Zeiger können auf dieselbe Ressource verweisen.
In C wird die Lebensdauer eines Objekts im dynamisch zugewiesenen Speicher mit free() und anderen Funktionen verwaltet, die die Speicherzuweisung verändern können. Das Objekt existiert ab dem Zeitpunkt seiner Zuweisung, bis eine dieser Funktionen auf die Speicherzuweisung angewendet wird.
Betrachten wir unseren Knoten der verketteten Liste noch einmal:
typedef struct N
{
int data;
struct N *previous;
struct N *next;
} Node;
Eine vollständige, korrekt aufgebaute verkettete Liste sollte einen Wächterknoten und einige Elementknoten enthalten, die über ihre Zeiger ordnungsgemäss miteinander verknüpft sind. Wird ein Knoten freigegeben, ohne zuvor die entsprechenden Zeiger zu aktualisieren, können die benachbarten Knoten Zeigerwerte behalten, die auf ein Objekt verweisen, dessen Lebensdauer bereits beendet ist. Diese Zeiger dürfen nicht verwendet werden. Folglich kann das Durchlaufen der verketteten Liste anhand dieser Verknüpfungen zu undefiniertem Verhalten führen. Darüber hinaus können die auf den zerstörten Knoten folgenden Knoten beim Durchlaufen der Liste vom Wächterknoten aus unerreichbar werden.
Wenn wir über die Lebensdauer eines Zeigers sprechen, meinen wir normalerweise die Lebensdauer des Objekts, auf das er verweist, und nicht die Lebensdauer der Zeigervariable selbst. Die Zeigervariable hat ebenfalls eine eigene Lebensdauer, diese ist jedoch davon unabhängig und bestimmt nicht die Lebensdauer des referenzierten Objekts.
Probleme mit Lebensdauern betreffen nicht nur dynamisch zugewiesenen Speicher, dessen Lebensdauer wir selbst verwalten. Nehmen wir beispielsweise an, wir ersetzen createNode() durch die folgende Implementierung:
Node *createNode(int data)
{
Node ans;
ans.data = data;
ans.previous = NULL;
ans.next = NULL;
return &ans;
}
Diese Implementierung ist ungültig, da die Lebensdauer von ans auf die Ausführungszeit der Funktion beschränkt ist. Sie endet, sobald die Funktion zurückkehrt. Zu diesem Zeitpunkt verweist der zurückgegebene Zeiger nicht mehr auf ein existierendes Objekt.
static zu Node ans hinzuzufügen, würde das Problem nicht lösen. Dadurch hätte ans eine Lebensdauer, die sich über die gesamte Ausführung des Programms erstreckt. Allerdings würde jeder Funktionsaufruf auf dasselbe Objekt verweisen, anstatt ein neues Objekt zu erzeugen.
Besitz und Lebensdauern in verschiedenen Programmiersprachen
In C wird Besitz nicht von der Sprache selbst erzwungen. Stattdessen handelt es sich um eine Vereinbarung, die Programmierer festlegen und einhalten, um Abstürze und unerwartetes Verhalten zu vermeiden. Die Lebensdauern von Objekten werden hingegen von der Sprache selbst definiert.
In einigen anderen Programmiersprachen wird Besitz durch die Sprache selbst erzwungen. Rust ist ein bekanntes Beispiel: Es verfügt über ein Besitzsystem, das von seinem Compiler durchgesetzt wird. Jeder Wert hat einen Besitzer, und der Besitz kann durch Verschiebesemantik zwischen Variablen übertragen werden. Referenzen (&T und &mut T) ermöglichen es anderen Teilen des Programms, Werte auszuleihen, ohne deren Besitz zu übernehmen. Die Lebensdauerregeln von Rust stellen sicher, dass ausgeliehene Referenzen die Lebensdauer der Werte, auf die sie verweisen, nicht überschreiten können. Beispielsweise ist String ein besitzender Typ, der einen dynamisch zugewiesenen Speicherbereich für seine Zeichenkettendaten verwaltet, während &str eine ausgeliehene Zeichenkettensicht ist. Rust stellt ausserdem Typen wie Rc<T> und Arc<T> für gemeinsamen Besitz bereit.
C++ verwendet RAII und kombiniert automatische Ressourcenverwaltung mit Möglichkeiten zur manuellen Verwaltung. Wir können Speicher manuell mit new und delete verwalten oder intelligente Zeiger wie std::unique_ptr<T> und std::shared_ptr<T> verwenden, die von der C++-Standardbibliothek bereitgestellt werden. Diese Objekte kapseln Informationen über den Besitz dynamisch zugewiesenen Speichers und ermöglichen es der Sprache, Ressourcen automatisch zu verwalten. Wir können auch eigene intelligente Zeiger implementieren. std::unique_ptr<T> erzwingt exklusiven Besitz. Es verhält sich ähnlich wie Verträge über exklusiven Besitz in C, verwaltet die Ressource jedoch automatisch. std::shared_ptr<T> verwendet einen Zähler, um zu verfolgen, wie viele Variablen den Besitz einer Ressource gemeinsam teilen. Es gibt die Ressource automatisch frei, sobald keine Variable mehr gemeinsamen Besitz daran hat.
Sprachen wie Python verwenden im Allgemeinen automatische Speicherverwaltung, sodass Programmierer Speicher nicht ausdrücklich zuweisen und freigeben müssen. CPython verwendet beispielsweise Referenzzählung in Verbindung mit einem zyklischen Garbage Collector.