Verkettete Liste für ASURO

[Spacy Bar]

Du schaffst dir ein 'komplexes' Problem, weil eine einfache Lösung witzlos ist?!
Dann bekommst du es nicht gelöst, es endet in einem Gewirr! Jetzt soll das Forum ran?

Der war gut...

Tut mir leid, das ist von dir falsch verstanden worden. Deswegen habe ich den Zwinker-Smiley dahinter gesetzt, damit es als Witz verstanden wird, das gilt in meinem Umfeld als absolute Entschuldigung.


- - - Aktualisiert - - -

Davon abgesehen: malloc zu verwenden ist auf so kleinen Plattformen wie dem AVR in der Regel keine gute Idee. Zum sind malloc und free "teuer" und zum anderen kannst du es früher oder später mit Speicherfragmentierung zu tun bekommen. In der Regel reicht eine statische Speicherreservierung aus, ist dabei einfacher und im Zweifelsfall auch zuverlässiger.[...]

Das kann ich zum einen nachvollziehen, da der µC nur 1 kb RAM hat, zum anderen Funktionierte das Programm als Zahlenspeicher für den PC ebenfalls nur im Bereich unter einem KB (solange man keinen Zahlenwald darein gepflanzt hat).

LG
Spacy Bar

[markusj]

Das kann ich zum einen nachvollziehen, da der µC nur 1 kb RAM hat, zum anderen Funktionierte das Programm als Zahlenspeicher für den PC ebenfalls nur im Bereich unter einem KB (solange man keinen Zahlenwald darein gepflanzt hat).

Das Problem der Speicherfragmentierung hat erst einmal nichts mit dem verfügbaren Speicher zu tun. Speicherfragmentierung entsteht, wenn im Adressraum einzelne Bereiche belegt sind und andere dazwischen frei. Wenn von den 1kB rechnerisch 50% frei sind kann es so trotzdem passieren, dass selbst ein malloc für 100 Bytes fehlschlagen kann, wenn kein zusammenhängender freier Speicherbereich >=100 Byte vorhanden ist. Ein solcher Flickenteppich im RAM entsteht dann, wenn du unterschiedlich große Speicherblöcke anforderst und der allozierte Speicher dann sehr unterschiedliche "Lebensdauern" hat.
Ein Beispiel (Je Zeichen 64 Byte, + entspricht belegtem Speicher, _ entspricht freiem Speicher) bei dem nur noch Speicheranforderungen bis zu zwei Einheiten (128 Byte) möglich sind - Und wenn man das ganze auf Byte-Ebene betrachtet kann die Fragmentierung noch viel schlimmer werden:
_+++__+__+_++_+_

mfG
Markus

[Spacy Bar]

Das Problem der Speicherfragmentierung hat erst einmal nichts mit dem verfügbaren Speicher zu tun. Speicherfragmentierung entsteht, wenn im Adressraum einzelne Bereiche belegt sind und andere dazwischen frei. Wenn von den 1kB rechnerisch 50% frei sind kann es so trotzdem passieren, dass selbst ein malloc für 100 Bytes fehlschlagen kann, wenn kein zusammenhängender freier Speicherbereich >=100 Byte vorhanden ist. Ein solcher Flickenteppich im RAM entsteht dann, wenn du unterschiedlich große Speicherblöcke anforderst und der allozierte Speicher dann sehr unterschiedliche "Lebensdauern" hat.
Ein Beispiel (Je Zeichen 64 Byte, + entspricht belegtem Speicher, _ entspricht freiem Speicher) bei dem nur noch Speicheranforderungen bis zu zwei Einheiten (128 Byte) möglich sind - Und wenn man das ganze auf Byte-Ebene betrachtet kann die Fragmentierung noch viel schlimmer werden:
_+++__+__+_++_+_

Erstmal Danke für die Erklärung, von den Grundsätzen der Heap-Fragmentierung hatte ich zwar im C-Grundkurs von Jürgen Wolf schon gelesen, aber offensichtlich nicht richtig verstanden. Da stand etwas von Heap-Defragmentierung per Funktionsimplimentierung, allerdings kein Beispiel. Wenn du davon was verstehst, würde ich mich sehr über eine Erklärung freuen.
Außerdem wurde die alternative Funktion alloca() erwähnt, mit der Speicher vom Stack angefordert wird. Wird sie genauso verwendet und macht sie in meinem Fall Sinn?
Ich freue mich über jegliche erklärenden Antworten.

LG
Spacy Bar

[shedepe]

Auf einem Mikrocontroller ist es viel sinnvoller sich einen Ringbuffer zu bauen als eine verkettete Liste. Dessen speicher kann man statisch allokieren. Problematisch wird es nur wenn man zwischen drin Daten einfügen will.

[markusj]

Da stand etwas von Heap-Defragmentierung per Funktionsimplimentierung, allerdings kein Beispiel. Wenn du davon was verstehst, würde ich mich sehr über eine Erklärung freuen.
Außerdem wurde die alternative Funktion alloca() erwähnt, mit der Speicher vom Stack angefordert wird. Wird sie genauso verwendet und macht sie in meinem Fall Sinn?

Heap-Defragmentierung über Funktionen: Keine Ahnung was damit gemeint ist, ich vermute das geht Hand in Hand mit alloca und der Nutzung des Stacks.
Grundsätzlich: Wenn alle Speicheranforderungen bis zum Ende einer Funktion wieder vollständig freigegeben wurden, bekommst du kein Problem mit der Fragmentierung des Speichers - Weil es keine "überlebenden" Speicherblöcke gibt die den Adressraum fragmentieren können.
Für solche "kurzlebigen" Speicherobjekte kannst du dann aber auch den Stack verwenden (die beiden Varianten unterschieden sich dann nicht) - Speicher vom Stack wird mit alloca() angefordert. Vorteil: Bei verlassen der Funktion wird er automatisch freigegeben. Vorteil für alloca(): Die Funktion ist deutlich schneller/performanter als malloc/free.

Nochmal zur Defragmentierung: Das wird ohne größere Klimmzüge nicht funktionieren. Dazu würdest du eine zusätzliche Ebene zusätzlicher Indirektion benötigen die es dir erlaubt, Speicherbereiche im Hintergrund zu verschieben ohne die Verweise darauf ungültig zu machen. Direkte Pointer können das nicht leisten, du müsstest also mit Referenzen arbeiten.

mfG
Markus

[Spacy Bar]

Heap-Defragmentierung über Funktionen: Keine Ahnung was damit gemeint ist, ich vermute das geht Hand in Hand mit alloca und der Nutzung des Stacks.
Grundsätzlich: Wenn alle Speicheranforderungen bis zum Ende einer Funktion wieder vollständig freigegeben wurden, bekommst du kein Problem mit der Fragmentierung des Speichers - Weil es keine "überlebenden" Speicherblöcke gibt die den Adressraum fragmentieren können.
Für solche "kurzlebigen" Speicherobjekte kannst du dann aber auch den Stack verwenden (die beiden Varianten unterschieden sich dann nicht) - Speicher vom Stack wird mit alloca() angefordert. Vorteil: Bei verlassen der Funktion wird er automatisch freigegeben. Vorteil für alloca(): Die Funktion ist deutlich schneller/performanter als malloc/free.

Nochmal zur Defragmentierung: Das wird ohne größere Klimmzüge nicht funktionieren. Dazu würdest du eine zusätzliche Ebene zusätzlicher Indirektion benötigen die es dir erlaubt, Speicherbereiche im Hintergrund zu verschieben ohne die Verweise darauf ungültig zu machen. Direkte Pointer können das nicht leisten, du müsstest also mit Referenzen arbeiten.[...]

Danke, gut dass das geklärt ist. Ich meinte allerdings mit der Verwendung von alloca() hauptsächlich die Syntax. Ist das 1 zu 1 mit malloc() austauschbar und macht das das free() überflüssig?
Bitte um baldige Antwort.

LG
Spacy Bar

[Wsk8]

http://bit.ly/1n8j23N

mfg

[markusj]

Danke, gut dass das geklärt ist. Ich meinte allerdings mit der Verwendung von alloca() hauptsächlich die Syntax. Ist das 1 zu 1 mit malloc() austauschbar und macht das das free() überflüssig?

http://www.nongnu.org/avr-libc/user-...p__alloca.html
http://www.nongnu.org/avr-libc/user-...78e5251dfd3ebd

mfG
Markus

[Spacy Bar]

@shedepe Ich habe mir soeben ein Beispiel eines Ringbuffers angesehen, aber ihn nicht wirklich verstanden. Könntest du vielleicht ein gut kommentiertes Beispiel posten?

Problematisch wird es nur wenn man zwischen drin Daten einfügen will.

Das habe ich nicht vor, nur notfalls bereits gespeicherte Daten löschen, ohne die gesamte Liste/den gesamten Ringbuffer zu leeren.

LG
Spacy Bar

[shedepe]

Schau mal hier:
https://www.mikrocontroller.net/articles/FIFO

http://rn-wissen.de/wiki/index.php/FIFO_mit_avr-gcc

Prinzip ist wie eine queu (Also First in First out).