mikrocontroller.net

Forum: Compiler & IDEs Wie implementiert man eine Speicherverwaltung?


Autor: TheMason (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo leuts,

ich nochmal. Und wieder mit einer abstrakten (und theoretischen) Frage.
Welche ansätze gibt es eine Speicherverwaltung zu implementieren ?
Ich weiß das das ein Thema ist das in die Betriebssystemprogrammierung 
gehört und auch einiges an Mathematik erfordert (wenn man denn alle nur 
erdenklichen fälle optimalst abdecken möchte), aber kann doch 
prinzipiell nicht so schwierig sein, zumal ja fast jeder c-compiler ein 
malloc unterstützt.
nun ist mir schon klar das man erstmal den zu verwaltenden 
speicherbereich definieren muß. in c würde/könnte man ja einfach ein 
byte-array über (fast) den gesamten speicherbereich definieren, und dann 
ein malloc nachbilden.
aber wie sieht so ein malloc aus ? ich kann mir zwar immer ein stückchen 
vom speicher wegnehmen und auch wieder freigeben (verkettete liste), 
aber wie löst man am einfachsten das problem der fragmentierung (sprich 
: man hat effektiv noch 1024 bytes frei, aber eben nicht 
zusammenhängend). ich weiß das es da 1001 ansätze gibt, aber wie löst 
man sowas am einfachsten ? einfach den speicherbereich umkopieren, und 
dann beim zugriff auf den speicher (mittels dedizierter funktionen) 
dafür sorgen das der nicht in ein loch bzw. auf den falschen speicher 
zugreift ?
wenn ich das problem der fragmentierung mit einem malloc auf einem 
mikrocontroller habe, wie wird das da denn gelöst (wenn es denn gelöst 
wird, oder sagt mir malloc dann einfach : nö, kein speicher mehr frei)

gruß
rene

ps. will ja nicht nerven, bin nur neugierig :-) und möchte etwas mehr 
basiswissen für ein paar zukünftige projekte haben.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: TheMason (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@jörg

erstmal danke für den schnellen link. bin schon am lesen :-)

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

besser nicht, sonst könnte ich wahrscheinlich glatt nochmal informatik 
studieren, bevor ich das kapiere :-)), mal ganz abgesehen davon das ich 
es wahrscheinlich eh nicht verstehen werde.

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> aber wie löst man am einfachsten das problem der fragmentierung (sprich
> : man hat effektiv noch 1024 bytes frei, aber eben nicht
> zusammenhängend).

Kann man nicht.

> einfach den speicherbereich umkopieren, und dann beim zugriff auf den
> speicher (mittels dedizierter funktionen) dafür sorgen das der nicht in
> ein loch bzw. auf den falschen speicher zugreift ?

Das ginge natürlich, aber dann kann man eben wirklich nur noch über 
diese Funktionen auf den Speicher zugreifen. Einfach wie bei malloc 
einen Zeiger dereferenzieren geht dann nicht mehr, weil jeder Zeiger auf 
den Speicherblock beim Herumschieben ungültig wird. Hier wäre dann ein 
"Garbage Collector" im Vorteil. Der kennt alle Zeiger (bzw. kann sie 
ermitteln) und kann sie daher anpassen.

> wenn ich das problem der fragmentierung mit einem malloc auf einem
> mikrocontroller habe, wie wird das da denn gelöst (wenn es denn gelöst
> wird, oder sagt mir malloc dann einfach : nö, kein speicher mehr frei)

Letzteres.

Autor: Bobby (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Letzteres.

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

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Bobby (Gast)
Datum:

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

Garnicht !
Wer sowas braucht darf natürlich gerne mallocen solange er will.

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

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.