Ein Angebot von

Dynamische Speicherzuweisung und -fragmentierung in C und C++

| Autor / Redakteur: Colin Walls * / Sebastian Gerstl

Speicherzuweisung: Durch die engen Ressourcenvorgaben und hohen Echtzeitansprüche in Embedded Systemen muss die Speicherzuweisung möglichst exakt erfolgen. In C und C++ kann ein fragmentierter Speicherpool allerdings unerwartete Allokationsfehler hervorrufen, die es dringend zu vermeiden gilt.
Speicherzuweisung: Durch die engen Ressourcenvorgaben und hohen Echtzeitansprüche in Embedded Systemen muss die Speicherzuweisung möglichst exakt erfolgen. In C und C++ kann ein fragmentierter Speicherpool allerdings unerwartete Allokationsfehler hervorrufen, die es dringend zu vermeiden gilt. (Bild: Clipdealer)

In C und C++ kann es sehr komfortabel sein, Speicherblöcke nach Bedarf zu allokieren und wieder freizugeben. Der Umgang mit einem dynamischen Speicher kann jedoch problematisch und ineffizient sein. Bei Desktop-Anwendungen mit ihrem frei verfügbaren Speicher können diese Probleme ignoriert werden. Für Embedded-Anwendungen – meist Echtzeitapplikationen – ist das aber keine Option.

Bei Desktop-Anwendungen mit ihrem frei verfügbaren Speicher können Probleme mit ineffizienter dynamischer Speicherzuweisung in der Regel ignoriert werden. Für Embedded-Anwendungen – meist Echtzeitapplikationen – ist das allerdings keine Option. Dynamische Speicherzuweisung ist in der Regel nicht deterministisch. Die Zeit für die Speicherzuweisung ist möglicherweise nicht vorhersehbar und der Speicherpool möglicherweise fragmentiert. Dies kann zu unerwarteten Allokationsfehlern führen.

In diesem Beitrag werden die Probleme im Detail skizziert. Zudem wird ein Ansatz zur deterministischen dynamischen Speicherzuweisung beschrieben.

Die drei Speicherbereiche in C und C++

Der Datenspeicher in C und C++ ist in drei getrennte Bereiche unterteilt:

Statischer Speicher: Hier befinden sich Variablen, die außerhalb von Funktionen definiert sind. Das Schlüsselwort „statisch“ hat im Allgemeinen keinen Einfluss darauf, wo sich solche Variablen befinden; es spezifiziert ihren lokalen Umfang für das aktuelle Modul. Variablen, die innerhalb einer Funktion definiert und explizit als statisch deklariert sind, werden ebenfalls im statischen Speicher abgelegt. Der statische Speicher befindet sich am Anfang des RAM-Bereichs. Die eigentliche Zuweisung von Adressen zu Variablen erfolgt über das Embedded-Software-Development-Toolkit im Zusammenspiel zwischen Compiler und Linker. Normalerweise kontrollieren Programmteile die Platzierung. Fortschrittlichere Techniken wie Fine-Grain-Allocation erlauben jedoch eine bessere Kontrolle. Im Allgemeinen dient der verbleibende Speicher, der nicht für die statische Speicherung verwendet wird, zur Bildung des dynamischen Speicherbereichs. Dieser enthält die beiden anderen Speicherbereiche.

Automatische Variablen: Variablen, die innerhalb einer Funktion definiert und nicht als statisch deklariert werden, sind automatische Variablen. Es gibt zwar ein Schlüsselwort, um eine solche Variable explizit zu deklarieren – auto – dieses wird aber fast nie verwendet. Automatische Variablen (und Funktionsparameter) werden in der Regel im Stack gespeichert. Dieser Stack wird meist mit Hilfe eines Linkers lokalisiert. Das Ende des dynamischen Speicherbereichs wird typischerweise für den Stack verwendet. Compiler-Optimierungen können dazu führen, dass Variablen für eine bestimmte Zeit oder die gesamte Lebensdauer in Registern gespeichert werden; dies kann auch durch die Verwendung des Keyword-Registers vorgeschlagen werden.

Der Heap: Der Rest des dynamischen Speicherbereichs wird in der Regel dem Heap zugewiesen, aus dem Anwendungsprogramme bei Bedarf dynamisch Speicher allokieren können.

Praktische Umsetzung: Dynamischer Speicher in C

In C wird der dynamische Speicher aus dem Heap mit Hilfe einiger Standard-Bibliotheksfunktionen zugewiesen. Die beiden wichtigsten dynamischen Speicherfunktionen sind malloc() und free(). Die malloc()-Funktion nimmt einen einzelnen Parameter, der der Größe des angeforderten Speicherbereichs in Bytes entspricht und weist einen Zeiger auf den allokierten Speicher zurück. Wenn die Zuweisung fehlschlägt, weist sie NULL zurück. Der Prototyp für die Standardbibliotheksfunktion ist wie folgt:

void *malloc(size_t size);

Die free()-Funktion nimmt den von malloc() zurückgewiesenen Zeiger und gibt den Speicher frei. Es wird kein Hinweis auf Erfolg oder Misserfolg zurückgemeldet. Der Funktionsprototyp ist wie folgt:

void free(void *pointer);

Die Verwendung dieser Funktionen lässt sich mit folgendem Code zeigen, mit dem sich ein Array statisch definiert und der Wert des vierten Elements festgelegen lässt:

int my_array[10];​my_array[3] = 99;

Der folgende Code erledigt die gleiche Aufgabe mit dynamischer Speicherzuweisung:

int *pointer;
pointer = malloc(10 * sizeof(int));
*(pointer+3) = 99;

Die Syntax zur Dereferenzierung des Zeigers ist schwer zu lesen. Daher kann man die normale Syntax zur Referenzierung des Arrays verwenden; [ und ] sind nur Operatoren:

pointer[3] = 99;

Wird das Array nicht mehr benötigt, lässt sich der Speicher wie folgt freigegeben:

free(pointer);
pointer = NULL;

Die Zuweisung von NULL an den Zeiger ist nicht zwingend erforderlich, aber eine bewährte Praxis. Sie führt zu einem Fehler, wenn der Zeiger nach der Freigabe des Speichers falsch verwendet wird. Die Menge des tatsächlich von malloc() zugewiesenen Heap-Speicherbereichs ist normalerweise ein Wort größer als das angeforderte. Das zusätzliche Wort dient dazu, die Größe der Zuordnung beizubehalten. Es kann später von free() verwendet werden. Dieses „Größenwort“ befindet sich vor dem Datenbereich, auf den malloc() einen Zeiger zurückweist.

Es gibt zwei weitere Varianten des malloc()-Funktion: calloc() und realloc(). Die calloc()-Funktion erledigt im Grunde genommen die gleiche Aufgabe wie malloc(). calloc() benötigt jedoch zwei Parameter – die Anzahl der Array-Elemente und die Größe jedes Elements – anstelle eines einzigen Parameters. Der zugewiesene Speicher wird ebenfalls auf Null initialisiert: void *calloc(size_t nelements, size_t elementSize);

Die realloc()-Funktion ändert die Größe einer zuvor von malloc() vorgenommenen Speicherzuweisung. Sie verwendet als Parameter einen Zeiger auf den Speicherbereich und die erforderliche neue Größe. Falls die Größe reduziert wird, können Daten verloren gehen. Wenn die Größe erhöht wird und die Funktion nicht in der Lage ist, die bestehende Zuordnung zu erweitern, weist sie automatisch einen neuen Speicherbereich zu und kopiert Daten hinein. So weist sie einen Zeiger auf den zugewiesenen Speicher zurück:

void *realloc(void *pointer, size_t size);

Praxisbeispiele: Dynamischer Speicher in C++

Die Verwaltung des dynamischen Speichers in C++ ähnelt C in vielerlei Hinsicht. Obwohl die Bibliotheksfunktionen vermutlich verfügbar sein werden, bietet C++ zwei zusätzliche Operatoren – new und delete. Damit kann Code klarer, prägnanter, flexibler und mit geringerer Fehlerwahrscheinlichkeit geschrieben werden. Der new-Operator ist auf drei Arten verwendbar:

p_var = new typename;
p_var = new type(initializer);
p_array = new type [size];

In den ersten beiden Fällen wird Speicherbereich für ein einzelnes Objekt zugewiesen; der zweite beinhaltet die Initialisierung. Der dritte Fall ist der Mechanismus, um einer Reihe von Objekten Speicherbereiche zuzuweisen.

Der delete-Operator lässt sich auf zwei Arten aufrufen:

delete p_var;
delete[] p_array;

Die erste ist für ein einzelnes Objekt, die zweite gibt den von einem Array belegten Speicherplatz frei. Es ist sehr wichtig, in jedem Fall die richtige Freigabe zu verwenden.

Es gibt keinen Operator, der die Funktionalität der in C vorhandenen realloc() Funktion bereitstellt. Aber mit folgendem Code kann man ein Array dynamisch zuweisen und das vierte Element initialisieren:

int* pointer;
pointer = new int[10];
pointer[3] = 99;

Die Verwendung der Array-Zugriffs-Notation ist natürlich. Die Freigabe wird folgendermaßen durchgeführt:

delete[] pointer;
pointer = NULL;

Eine weitere Möglichkeit zur Verwaltung des dynamischen Speichers in C++ ist die Verwendung der Standard Template Library. Dies ist jedoch für Embedded-Echtzeit-Systeme nicht empfehlenswert.

Häufig auftretende Fragen und Probleme

In der Regel ist dynamisches Verhalten in Embedded-Echtzeit-Systemen heikel. Die zentralen Anliegen sind die Festlegung der Maßnahmen, die bei Ressourcenerschöpfung zu ergreifen sind, und die nicht deterministische Ausführung.

Bei der dynamischen Speicherzuweisung in einem Echtzeitsystem gibt es eine Reihe von Problemen.

Die Standardbibliotheksfunktionen (malloc() und free()) sind normalerweise nicht reentrant, denn das wäre in einer Multithreading-Anwendung problematisch. Wenn der Quellcode verfügbar ist, sollte dies einfach zu beheben sein, indem Ressourcen mit Echtzeit-Betriebsfunktionen (wie eine Semaphore) gesperrt werden.

Ein hartnäckigeres Problem ist mit der Performance von malloc() verbunden. Das Verhalten dieser Funktion ist nicht vorhersehbar, weil die Zeit, die für die Speicherzuweisung benötigt wird, extrem variabel ist. Ein solches nicht-deterministisches Verhalten ist in Echtzeitsystemen nicht tolerierbar.

Ohne große Sorgfalt entstehen leicht Speicherlecks in Anwendungscode, der mit malloc() und free() implementiert wurde. Die Ursache hierfür ist Speicher, der allokiert und nie wieder freigegeben wird. Solche Fehler führen zu einer allmählichen Leistungsabnahme und verursachen möglicherweise einen Ausfall. Diese Art von Fehler ist sehr schwer zu finden.

Das Fehlschlagen einer Speicherzuweisung ist ein Problem. Im Gegensatz zu Desktop-Anwendungen haben die meisten Embedded-Systeme nicht die Möglichkeit, einen Dialog zu öffnen und Optionen mit dem Benutzer zu diskutieren. Oft ist das Zurücksetzen die einzige Option, diese ist jedoch unattraktiv. Treten während der Prüfung Allokationsfehler auf, muss die Ursache sorgfältig diagnostiziert werden. Es kann sein, dass einfach nicht genügend Speicher zur Verfügung steht – das deutet auf verschiedene Vorgehensweisen hin. Es kann jedoch auch sein, dass genügend Speicher vorhanden ist, dieser aber nicht in einem zusammenhängenden Block zur Verfügung steht, um die Zuordnungsanforderung zu erfüllen. Dies wird als Speicherfragmentierung bezeichnet.

Die Problematik der Speicherfragmentierung

Die Speicherfragmentierung lässt sich durch folgendes Beispiel am besten verstehen. Es wird ein 10K großer Heap angenommen. Zuerst wird ein Bereich von 3K angefordert:

#define K (1024)
char *p1;
p1 = malloc(3*K);

Dann werden weitere 4K angefordert:

p2 = malloc(4*K);

Nun sind 3K Speicherplatz frei. Einige Zeit später wird die erste Speicherzuweisung, auf die p1 zeigt, aufgehoben:

free(p1);

Dadurch bleiben 6K Speicherplatz in zwei 3K-Blöcken frei. Es wird nun eine weitere Anforderung für eine 4K-Zuordnung gestellt:

p1 = malloc(4*K);

Das führt zu einem Fehler – NULL wird an p1 zurückgegeben – denn obwohl 6K Speicherplatz verfügbar sind, gibt es keinen zusammenhängenden 4K großen Block. Das ist Speicherfragmentierung.

Eine naheliegende Lösung besteht darin, den Speicher zu defragmentieren und die beiden 3K-Blöcke zu einem einzigen mit 6K zusammenzuführen. Das ist jedoch nicht möglich, weil dadurch der 4K-Block zum p2-Punkt verschoben werden würde. Das Verschieben ändert seine Adresse. Dadurch wird jeder Code beschädigt, der eine Kopie des Zeigers erstellt hat. In anderen Sprachen (z.B. Visual Basic, Java und C#) gibt es Wege zur Defragmentierung (oder „Garbage Collection“). Das ist möglich, weil diese Sprachen keine direkten Zeiger unterstützen, so dass das Verschieben der Daten keine negativen Auswirkungen auf den Anwendungscode hat. Diese Defragmentierung tritt auf, wenn eine Speicherzuweisung fehlschlägt oder ein periodischer Garbage-Collection-Prozess ausgeführt wird. In beiden Fällen werden die Echtzeitleistung und den Determinismus erheblich beeinträchtigen.

Speicher mit einem Echtzeit-Betriebssytem

Ein Echtzeit-Betriebssystem kann einen Dienst bereitstellen, der tatsächlich eine reentrante Form von malloc() ist. Es ist jedoch unwahrscheinlich, dass diese Möglichkeit deterministisch wäre.

In der Regel werden Speicherverwaltungseinrichtungen bereitgestellt, die mit den Echtzeitanforderungen kompatibel, das heißt, deterministisch sind. Dies ist in der Regel ein Schema, das Blöcke – oder „Partitionen“ – des Speichers unter der Kontrolle des Betriebssystems zuweist.

Speicherzuweisung bei Blöcken/Partitionen

Typischerweise erfolgt die Speicherzuweisung bei Blöcken unter Verwendung eines „Partitionspools“. Dieser ist statisch oder dynamisch definiert und konfiguriert und enthält eine festgelegte Anzahl von Blöcken einer bestimmten festen Größe. Für das Nucleus-Betriebssystem hat der API-Aufruf zur Definition eines Partitionspools den folgenden Prototyp:

STATUS NU_Create_Partition_Pool(NU_PARTITION_POOL *pool,
CHAR *name, VOID *start_address, UNSIGNED pool_size,
UNSIGNED partition_size, OPTION suspend_type);

Dies verdeutlicht ein Beispiel:

status = NU_Create_Partition_Pool(&MyPool, "any name",
(VOID *) 0xB000, 2000, 40, NU_FIFO);

Mit dem Deskriptor MyPool wird ein Partitionspool erstellt. Dieser enthält einen 2000 Byte großen Speicher, der mit Partitionen mit einer Größe von 40 Byte gefüllt ist (d.h. es gibt 50 Partitionen). Der Pool befindet sich bei der Adresse 0xB000 und ist folgendermaßen konfiguriert: Wenn eine Task versucht, einen nicht verfügbaren Block zuzuweisen und beim Aufruf der Zuweisungs-API unterbrochen werden soll, dann werden die unterbrochenen Aufgaben in einer First-In-First-Out-Reihenfolge aktiviert. Die andere Option wäre eine Reihenfolge nach Prioritäten der Tasks.

Um die Zuordnung einer Partition anzufordern, steht ein weiterer API-Aufruf zur Verfügung. Hier ein Beispiel für die Verwendung des Nucleus-Betriebssystems:

status = NU_Allocate_Partition(&MyPool, &ptr, NU_SUSPEND);

Dieses erfordert die Zuweisung einer Partition von MyPool. Wenn erfolgreich, wird ein Zeiger auf den allokierten Block in ptr zurückgegeben. Wenn kein Speicher verfügbar ist, wird die Task unterbrochen, weil NU_SUSPEND angegeben wurde. Eine andere Möglichkeit bestünde darin, mit einem Timeout auszusetzen oder einfach mit einem Fehler zurückzukehren.

Wird die Partition nicht mehr benötigt, kann sie folgendermaßen freigegeben werden:

status = NU_Deallocate_Partition(ptr);

Wenn eine Task mit höherer Priorität ausgesetzt wurde, bis eine Partition verfügbar ist, dann wird sie nun ausgeführt.

Eine Fragmentierung ist nicht möglich, da nur Blöcke mit fester Größe verfügbar sind. Der einzige Fehlermodus ist die echte Ressourcenerschöpfung, die, wie dargestellt, durch Unterbrechung einer Task gesteuert und eingedämmt werden kann.

Es stehen zusätzliche API-Aufrufe zur Verfügung, die dem Anwendungscode Informationen über den Status des Partitionspools liefern können, zum Beispiel, wie viele freie Partitionen derzeit verfügbar sind.

Bei der Zuweisung und Freigabe von Partitionen ist Vorsicht geboten, da die Einführung von Speicherlecks weiterhin möglich ist.

Erkennen von Speicherlecks

Die Anbieter von Echtzeit-Betriebssystemen haben das Potenzial für Programmierfehler erkannt, die bei der Verwendung von Partitionspools zu einem Speicherleck führen. Üblicherweise gibt es ein Profiler-Tool zum Auffinden und Beheben solcher Fehler.

Echtzeit-Speicherlösungen

Nachdem eine Reihe von Problemen mit dem Verhalten von dynamischen Speichern in Echtzeitsystemen identifiziert wurde, kann man einen besseren Ansatz vorschlagen.

Dynamischer Speicher

Mit Hilfe der Partitionsspeicherzuweisung lässt sich malloc() auf eine robuste und deterministische Weise implementieren. Die Idee ist, eine Reihe von Partitionspools mit Blockgrößen von beispielsweise 32, 64, 128, 256 Byte in einer geometrischen Progression zu definieren. Eine malloc()-Funktion kann geschrieben werden, um deterministisch den richtigen Pool auszuwählen und genügend Speicherplatz für eine gegebene Zuordnungsanforderung bereitzustellen. Dieser Ansatz nutzt das deterministische Verhalten des API-Aufrufs für die Partitionszuordnung, robuste Fehlerbehandlung (z.B. Task-Suspension) und Fragmentierungsfreiheit des Blockspeichers.

Schlussbetrachtungen zur unterschiedlichen Speichernutzung in C und C++

C und C++ nutzen den Speicher auf unterschiedliche Weise, sowohl statisch als auch dynamisch. Dynamischer Speicher beinhaltet einen Stack und Heap.

Dynamisches Verhalten in Embedded-Echtzeitsystemen bietet im Allgemeinen Anlass zur Sorge, da es tendenziell nicht deterministisch und ein Ausfall schwer einzudämmen ist.

Die meisten Echtzeit-Betriebssysteme haben jedoch Möglichkeiten zur Implementierung eines dynamischen Speichers, der deterministisch, fragmentierungsfrei und mit guter Fehlerbehandlung ist.

* Colin Walls ist Embedded-Software-Technologist bei Mentor, a Siemens business, in Reading, Großbritannien.

Kommentar zu diesem Artikel abgeben
Sehr schöne Übersicht und Zusammenfassung! Danke!  lesen
posted am 25.11.2018 um 20:25 von Unregistriert


Mitdiskutieren
copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45583621 / Implementierung)