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.
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...
@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.
> 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.
> Letzteres.
Das ist (für mich) der Grund, auf den malloc-Kram
komplett zu verzichten, und zwar nicht nur bei
Mikrocontrollern...
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.
> 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.
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.
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.