Wie implementiert man eine Speicherverwaltung?

Guck dir doch einfach ein existierendes malloc() an.  Die avr-libc hat
eins, und es ist einigermaßen dokumentiert.

Im K&R steht auch eine einfache Variante drin.

In den Opensource-Unixen kannst du dir dann die Hohe Schule derartiger
Systeme angucken...

Bobby wrote:
>> Letzteres.
>
> Das ist (für mich) der Grund, auf den malloc-Kram
> komplett zu verzichten, und zwar nicht nur bei
> Mikrocontrollern...

Super. Und wie lädst du im PC dann z.B. eine Grafikdatei mit zur 
Compilezeit unbekannten Größe?

uint8_t bigArray[MAYBEMAXFILESIZE];

Matthias

> Hier wäre dann ein
> "Garbage Collector" im Vorteil.

Das braucht aber ein "handle based"-System.  Du bekommst also keinen
reinen Zeiger, sondern ein "handle", und musst zum Dereferenzieren
dir über dieses Handle einen Zeiger zurückgeben lassen.  Damit kann
die Speicherverwaltung beim Verstopfung im Hintergrund den Speicher
umorganisieren.

Gibt's dafür eigentlich einen de-facto-API-Standard?  Klingt ja
eigentlich wie eine nette Ergänzung für die avr-libc.

Jörg Wunsch wrote:
>> Hier wäre dann ein
>> "Garbage Collector" im Vorteil.
>
> Das braucht aber ein "handle based"-System.  Du bekommst also keinen
> reinen Zeiger, sondern ein "handle", und musst zum Dereferenzieren
> dir über dieses Handle einen Zeiger zurückgeben lassen.  Damit kann
> die Speicherverwaltung beim Verstopfung im Hintergrund den Speicher
> umorganisieren.
>
> Gibt's dafür eigentlich einen de-facto-API-Standard?

Nicht das ich wüsste.

>  Klingt ja
> eigentlich wie eine nette Ergänzung für die avr-libc.

Ist so wie die Speicherverwaltung in Windows ganz am Anfang
funktioniert hat. Ist ein 'pain in the ass'.
Du brauchst nämlich auch noch Lock und Unlock Funktionen, damit
du der Speicherverwaltung klar machen kannst, dass es einen
bestimmten Speicherbereich jetzt gerade nicht verschieben darf,
weil du zugreifen willst.

Bobby wrote:

> BTW: Ich erstelle Visualisierungen für industrielle Anwendungen.
> Diese sollen wenn möglich nicht nur ein paar Wochen am Stück laufen.

Ja, und?

Andere Leute schreiben ganze Betriebssysteme, die Jahre am Stück
laufen, und sie können trotzdem malloc() benutzen.

Das Fragmentierungsproblem existiert vor allem auf kleinen Maschinen,
auf VM-Architekturen ist das bei vernünftiger Programmierung kein
ernsthaftes Problem.  Bei einer langleben Applikation mit viel
malloc()/free() wird es sich statistisch ohnehin auf einem bestimmten
Niveau einpegeln, statt ohne jede Grenze nach oben zu wachsen.

Rolf Magnus wrote:
> Das braucht er aber auch nur, wenn er nebenher in einem eigenen Thread
> läuft. Das ist eh ungünstig, weil das Verhalten dann nicht
> deterministisch ist. Der Collector räumt halt auf, wenn er grad Lust
> dazu hat. Man könnte aber eine Garbage Collection auch so machen, daß
> sie explizit angestoßen wird. Dann kann man einerseits aufräumen lassen,
> wenn man gerade Zeit hat (oder auch erst, wenn man mal neuen Speicher
> braucht, für den kein Platz mehr ist), andererseits geht das ganze auch
> synchron, und man braucht kein Locking.

Das Problem ist, dass du die Garbage Collection dann maximal
im main() aufrufen darfst, wenn sonst nichts anderes im
System läuft. Und dann darfst du natürlich nicht vergessen, dass
alle Pointer die du bereits hast ungültig sind und neu aus
den Handles generiert werden muessen.

> oder auch erst, wenn man mal neuen Speicher
> braucht,

Genau dieser Fall artet dann in ein Nightmare aus.
Stell dir vor du hast eine Funktion, in der mehrere
mallocs involviert sind. Nach jedem malloc kann u.U
der GC aufgerufen werden. Das heist aber auch, dass
alle bisherigen Pointer in der Funktion ungültig sind
und neu generiert werden muessen. Das gilt auch für den
Aufrufer dieser Funktion:

void foo()
{
  char* pPtr = malloc( 10 );

  if( pPtr == NULL ) {
    GC();
    pPtr = malloc( 10 );   // ich spar mir hier die Fehlerbehandlung
  }

  *pPtr = 5;        // mach was damit

  // soweit so gut. Jetzt ruft die Funktion eine andere Funktion auf
  foo2();

  // an dieser Stelle: ist pPtr noch gültig? Oder hat ein Aufruf
  // von GC() in foo2() den Pointer ungütlig gemacht

  *pPtr = 8;
}

void foo2()
{
  char* pPtr1 = malloc(20);

  if( pPtr1 == NULL ) {
    GC();
    pPtr1 = malloc( 20 );   // wieder: Fehlerbehandlung gespart
  }

  char* pPtr2 = malloc( 100 );

  if( pPtr2 == NULL ) {
    GC();                  // pPtr1 ist damit ungültig geworden
    pPtr1 = malloc( 20 );  // der kann aber immer noch schief gehen
    pPtr2 = malloc( 100 );
  }

}


Die entsprechenden free() hab ich mir jetzt gespart.
Aber man sieht auch so schon: Das artet in Chaos aus.
Im Grunde weist du nach einem Funktionsaufruf nie, ob alle
deine Pointer überhaupt noch gültig sind.
Im Grunde hast du bei mehreren Allokierungen in einer Funktion
enorme Allokierungs-Probleme.


In C++ könnte man dafür eine schöne Klasse schreiben, die einen
Handle kapselt und bei jeder Dereferenzierung den Handle in
einen Pointer umwandelt. Aus Gründen der Laufzeit: Will man das?

Wenn malloc anders arbeiten würde, ginge es:

bool malloc(void** ptr, size_t size);

Nur löst das nicht die Probleme, die auftreten, wenn der Pointer 
irgendwo anders verwendet werden soll (dann müsste man wieder mit einem 
Handle arbeiten und sich daran halten...).
Das Problem der Fragmentierung kann man z.B. abmildern, indem man 
"größere" Blöcke direkt belegt und "kleinere" Blöcke separat (z.B. 
innerhalb eines größeren) verwaltet.