Teil 23 „When the computer gets full“

Der C-Kurs
Antworten
Benutzeravatar
bodo
User
Beiträge: 319
Registriert: 14.02.2007, 17:21
Kontaktdaten:

Teil 23 „When the computer gets full“

Beitrag von bodo » 02.01.2011, 15:18

C für BASIC-Programmierer

Arbeiten mit dem z88dk Cross-Compiler

von Jens Sommerfeld und Bodo Wenzel

Teil 23

Im BASIC-Buch von Steven Vickers heißt das Kapitel 23 „When the computer gets full“, und deshalb werden wir uns in diesem Teil des C-Kurses mit dem Thema „Speicher“ befassen.

Kein Computer hat (lokal) unendlich viel Speicherplatz zur Verfügung. Daher ist es kein Problem, selbst mit einem kleinen Programm schnell an die Grenzen zu stoßen. Wir werden heute verschiedene Szenarien untersuchen...

Zuviel Platz angefordert für lokale Variablen

Viele C-Programmierer sind sich dessen nicht bewusst, aber lokale Variablen werden üblicherweise auf dem Stack des Prozessors angelegt. Zu den lokalen Variablen zählen übrigens auch die an Funktionen übergebenen Parameter. Bei unserem Z80 wächst der Stack von Ende des RAMs in Richtung auf niedrige Adressen, an denen aber das BASIC-Programm und auch unser C-Programm liegen.

Wir können relativ einfach abschätzen, wieviel Platz wir zur Verfügung haben. Das folgende Testprogramm bietet dazu einen Ansatz, bei dem aus Platzgründen der BASIC-Speicher nicht berücksichtigt ist. Dabei wird nur die Startadresse der Hauptfunktion „main“ und die Adresse der lokalen Variablen „x“ ausgegeben:

Code: Alles auswählen

#include <stdio.h>

int main(void) {
    char x;

    printf("MAIN BEI %04x, STACK BEI %04x\n", main, &x);

    return 0;
}
Mit einem weiteren Versuch zeigen wir, dass der Compiler des z88dk keine Tests während des Programmlaufs durchführt, ob der Stack nicht beim Wachsen in den BASIC-Bereich hineinstößt. Dazu rufen wir rekursiv immer wieder dieselbe Funktion auf, bis der Stack irgendwann das Programm zerstört:

Code: Alles auswählen

#include <stdio.h>

static void rekursion(int tiefe) {
    char speicher_verbrauch[100];

    printf("AUFRUF %d\n", tiefe);
    rekursion(tiefe + 1);
}

int main(void) {
    rekursion(1);

    return 0;
}
Bei einem BASIC-Programm prüft der Interpreter im ROM dagegen stets, ob er noch Platz hat. Allerdings kann man trefflich darüber streiten, ob der Laufzeitfehler „4“ für einen Anwender so hilfreich ist. Programmierer dagegen freuen sich, weil ihr Programm dann (meistens) noch da ist...

Zuviel Platz angefordert für statische Variablen

Ebenso wie wir zuviel Speicher durch lokale Variablen belegen können, tritt auch bei statischen Variablen das Problem auf. Das folgende Programm lässt sich ohne Fehler compilieren:

Code: Alles auswählen

#include <stdio.h>

static char speicher_verbrauch[16000];

int main(void) {
    return 0;
}
Allerdings wollte der ZX81 (in seiner emulierten 16K-Form) das fertige Programm nicht laden, er kam mit einem Reset zurück. Durch die zusätzliche Option „-m“ kann der Compiler übrigens veranlasst werden, eine sogenannte Map-Datei zu erzeugen, die alle Adressen einmal alphabetisch nach Namen und einmal numerisch nach Adressen sortiert auflistet. Diese Map (englisch, auf deutsch „Karte“) ist hilfreich beim Abschätzen der Größe eines Programms.

Selbst wenn wir ein Programm mit einer großen Speichermenge an statischen Variablen (oder an Maschinencode) geladen kriegen, wird uns eventuell zur Laufzeit der Stack zu groß: aber dieses Problem hat das erste Kapitel dieses Teils behandelt.

Dynamische Speicherverwaltung

So, nachdem wir erstmal Probleme gewälzt haben, kommen wir jetzt zu Problemlösungen!

Manchmal wissen wir nicht, wieviel Speicher wir für Daten brauchen. Dann ist es nicht sinnvoll, Arrays mit der maximalen Größe vorzusehen, denn damit begrenzen wir ja die Anwender je nach Speicherausbau. Außerdem kann es auch sein, dass je nach Programmablauf mal die eine oder mal die andere Variable wachsen muss.

Dies kann z.B. eine Namensverwaltung sein, die verschieden lange Namen und verschieden große Anzahlen von Namen beherrschen soll. Der eine Anwender kennt lauter Evas, Udos, Tims und Mayas, aber davon sehr viele. Der andere Anwender hat dafür eine noble Bekanntschaft aus lauter Grafen „von und zu“, die dafür aber in der Anzahl beschränkt ist.

Die Standardbibliothek bietet uns zur dynamischen Speicherverwaltung (http://www.z88dk.org/wiki/doku.php/libr ... allocation) zunächst zwei Basisfunktionen an. Mit diesen können wir uns aus dem Heap (englisch, auf deutsch „Haufen“) einen Bereich geben lassen, und diesen auch zurückgeben, wenn wir ihn nicht mehr brauchen.

Code: Alles auswählen

void *malloc(unsigned int size);
Diese Funktion gibt einen Zeiger auf einen Speicherbereich mit mindestens der übergebenen Größe in Bytes zurück. Falls es dafür nicht mehr genug Speicher gibt, wird der Wert NULL zurückgegeben – wir müssen also das Ergebnis immer prüfen!

Code: Alles auswählen

void free(void *address);
Diese Funktion wird verwendet, um den durch malloc() geholten Speicher wieder „zurückzugeben“, damit er wieder für die nächsten Anforderungen durch malloc() zur Verfügung steht. Als Adresse darf übrigens auch NULL übergeben werden, dann passiert natürlich nichts weiter.

Woher weiß nun das C-Programm, an welcher Adresse es wieviel Speicherplatz zur Verfügung hat? In Umgebungen mit „richtigen“ Betriebssystemen wird der Heap vom Betriebssystem geholt. Auf unserem Zeddy müssen wir das vor dem Aufruf von malloc() einmalig selbst in die Hand nehmen:

Code: Alles auswählen

long heap;
Diese globale Variable wird zur Verwaltung benötigt.

Code: Alles auswählen

void mallinit(void);
Mit dieser Funktion initialisieren wir die Verwaltung.

Code: Alles auswählen

void sbrk(void *address, uint size);
Und mit dieser Funktion geben wir der Verwaltung bekannt, ab welcher Adresse wieviele Bytes zur Verfügung stehen. Der Aufruf ist auch mehrfach möglich, wenn wir mehrere freie Bereiche haben.

Probieren wir das doch gleich einmal aus:

Code: Alles auswählen

#include <malloc.h>
#include <stdio.h>

long heap;
static unsigned char freier_platz[1000];

int main(void) {
    void *zeiger;

    mallinit();
    sbrk(freier_platz, sizeof(freier_platz));

    zeiger = malloc(998); /* mehr geht nicht */
    printf("ADRESSE = %04x\n", zeiger);
    free(zeiger);

    return 0;
}
Das Testprogramm übergibt den Speicher, den es mit der statischen Variablen „freier_platz“ angelegt hat, an die Speicherverwaltung. Wenn euer Zeddy irgendwo anders Speicher herumliegen hat, könnt ihr natürlich auch diesen angeben. ;-)

Achtung! Wenn ihr das Programm erzeugen wollt, müsst ihr beim Linken die Option „-lmalloc“ angeben, damit die Funktionen der Standardbibliothek auch hinzugefügt werden können.

Die übliche Standardbibliothek enthält noch zwei weitere nützliche Funktionen, die das Allozieren (So heißt das Anfordern von Speicher bei Profis, vom englischen „to allocate“, deshalb auch malloc =
memory allocate.
) bequemer machen:

Code: Alles auswählen

void *calloc(unsigned int number, unsigned int size)
Diese Funktion alloziert genügend Platz für number Elemente der Größe size. Der Speicher wird dann noch mit Nullbytes initialisiert, was malloc() nämlich nicht macht. Im Fehlerfall gibt auch sie NULL zurück. Leider findet der Linker die Funktion nicht. :-(

Code: Alles auswählen

void *realloc(void *address, unsigned int size)
Ab und zu möchtet ihr den allozierten Speicher in seiner Größe verändern. Genau das macht diese Funktion, aber es kann vorkommen, dass sich dabei die Adresse verändert. Intern ruft die Funktion nämlich zuerst malloc() mit der neuen Größe auf, bei Erfolg wird der alte Inhalt unter Beachtung der Größe umkopiert, und dann wird der alte Bereich mit free() zurückgegeben. So sieht jedenfalls die simple Implementierung aus... Im Fehlerfall gibt sie NULL zurück, dann könnt ihr den alten Speicher unverändert weiternutzen. Leider kann die z88dk-Variante nicht mit einer übergebenen Adresse von NULL umgehen.

Diese Art der Speicherverwaltung neigt zu Fragmentierung, das heißt, dass bei mehrfachem malloc() und free() irgendwann der verwaltete Speicher in kleinen Stückchen vergeben ist. Dann kann es bei einer Anforderung passieren, dass in Summe zwar noch genügend Speicher frei wäre, aber kein zusammenhängendes Stück der gewünschten Größe.

Deshalb haben die z88dk-Macher noch zwei weitere Arten der Speicherverwaltung vorgesehen. Diese sind aber kein Standard, so dass wir auf die Dokumentation (Selber lernen macht schneller schlau! :-P) verweisen.

Hausaufgaben
  1. Schreibt die Speicherfunktionen für die oben erwähnte Namensverwaltung. Testet sie mit einem Testprogramm. Dieses kann z.B. zuerst die maximale Anzahl anlegbarer kurzer Namen ermitteln, und dann die maximale Anzahl anlegbarer langer Namen. Sind die Ergebnisse plausibel?
  2. Überlegt euch, welche Konsequenzen die simple Implementierung von realloc() hat. Wenn ihr nicht darauf kommt, schreibt euch ein kleines Testprogramm, das z.B. den allozierten Speicher immer etwas größer werden lässt, bis es nicht mehr weiter geht. Zur Analyse kann das Programm z.B. die aktuelle Adresse und die Größe ausgeben. Wer hier tiefer einsteigen will, kann sich Verfahren zur Umgehung der unangenehmen Seiten überlegen...
B0D0: Real programmers do it in hex.

Antworten