Was ist ein guter Speicherzuordner C für Embedded-Systeme? [geschlossen]

StackOverflow https://stackoverflow.com/questions/177209

Frage

Ich habe eine Single-Threaded, eingebettete Anwendung, die viele, viele kleine Blöcke zuordnet und freigibt (32-64b). Das perfekte Szenario für einen Cache-basierten Allocator. Und obwohl ich versuchen könnte einen zu schreiben, es wird wahrscheinlich eine Verschwendung von Zeit, und nicht so gut getestet und abgestimmt als eine Lösung, die an der Front schon gewesen ist.

So würde, was das beste allocator sein, die ich für dieses Szenario verwenden könnte?

. Hinweis: Ich verwende eine Lua Virtual Machine im System (das ist der Täter von 80 +% der Zuweisungen ist), so kann ich meinen Code zu verwenden Stapelzuordnungen zu erhöhen Zuteilung Leistung nicht trivialen Refactoring

War es hilfreich?

Lösung

Ich habe einige der Forschung auf diesem Thema vor kurzem, als wir ein Problem mit der Speicherfragmentierung hatte. Am Ende haben wir beschlossen, mit GNU libc-Implementierung, und fügen Sie einige Anwendungsebene Speicherpools, wo notwendig zu bleiben. Es gab noch andere Verteilern, die eine bessere Fragmentierungsverhalten hatte, aber wir waren nicht genug bequem mit ihnen malloc global ersetzen. GNU hat den Vorteil einer langen Geschichte dahinter.

In Ihrem Fall erscheint es gerechtfertigt; vorausgesetzt, Sie die VM nicht beheben können, sind diese winzigen Zuweisungen sehr verschwenderisch. Ich weiß nicht, was Ihre ganze Umgebung ist, aber Sie sollten erwägen, die Anrufe zu malloc Einwickeln / realloc / Frei nur auf die VM, so dass Sie es aus, um einen Handler für kleine Pools passieren können.

Andere Tipps

In einem früheren Projekt in C arbeitete ich an, ging hinunter wir den Weg unserer eigenen Speicherverwaltungsroutinen der Implementierung für eine Bibliothek auf einer Vielzahl von Plattformen, darunter Embedded-Systemen lief. Die Bibliothek auch eine große Anzahl von kleinen Puffern zugewiesen und befreit. Es lief relativ gut und nicht eine große Menge an Code zu implementieren nehmen. Ich kann Ihnen ein wenig Hintergrund auf dieser Implementierung, falls Sie etwas selbst entwickeln wollen.

Die grundlegende Implementierung enthalten einen Satz von Routinen, die Puffer einer festgelegten Größe verwaltet. Die Routinen wurden als Wrapper um malloc () verwendet und free (). Wir nutzten diese Routinen Zuordnung von Strukturen zu verwalten, die wir häufig verwenden und auch generische Puffer von Set-Größen zu verwalten. Eine Struktur wurde verwendet, um jede Art von Puffer zu beschreiben, verwaltet wird. Wenn ein Puffer eines bestimmten Typs zugeordnet wurde, sollten wir malloc () den Speicher in Blöcken (falls eine Liste der freien Puffer leer war). IE, wenn wir 10 Byte Puffer verwalten, könnten wir eine einzige malloc () machen, die Platz für 100 dieser Puffer enthalten benötigt Fragmentierung und die Anzahl der zugrunde liegenden mallocs zu reduzieren.

An der Vorderseite jeden Puffers würde ein Zeiger sein, der die Puffer in einer freien Liste Kette verwendet werden würde. Wenn die 100-Puffer zugewiesen wurden, würde jeder Puffer zusammen in der freien Liste verkettet werden. Wenn der Puffer in Gebrauch ist, würde der Zeiger auf null gesetzt werden. Wir erhielten auch eine Liste der „Blöcke“ von Puffern, so dass wir durch den Aufruf free () auf jedem des tatsächlichen malloc'd Puffers eine einfache Bereinigung tun könnten.

Für die Verwaltung von dynamischen Puffergrößen, fügten wir auch eine size_t Variable am Anfang jeden Puffers die Größe des Puffers zu erzählen. Dies wurde dann verwendet, um festzustellen, welcher Pufferblock die Puffer wieder in setzen, wenn es freigegeben wurde. Wir hatten Ersatz-Routinen für malloc () und free (), die Pointer-Arithmetik hat die Puffergröße zu bekommen und dann den Puffer in die freie Liste zu setzen. Wir hatten auch eine Grenze, wie groß der Puffer uns gelungen. Puffer größer als diese Grenze waren einfach malloc'd und an den Benutzer übergeben. Für Strukturen, die wir es geschafft haben wir Wrapper-Routinen für die Zuteilung und Freigabe der spezifischen Strukturen.

Schließlich entwickelte wir auch das System Garbage Collection enthalten, wenn vom Benutzer angeforderten ungenutzten Speicher aufzuräumen. Da wir die Kontrolle über das gesamte System hatten, gab es verschiedene Optimierungen konnten wir im Laufe der Zeit machen, die Leistung des Systems zu erhöhen. Wie bereits erwähnt, hat es ganz gut funktionieren.

Ich bin ein bisschen spät zur Party, aber ich mag nur für eingebettete Systeme sehr effizient Speicherzuordner teilen habe ich vor kurzem gefunden und getestet: https://github.com/dimonomid/umm_malloc

Dies ist eine Bibliothek Speicherverwaltung speziell mit dem ARM7 entworfen zu arbeiten, persönlich verwende ich es auf PIC32-Gerät, aber es sollte auf jedem arbeiten 16- und 8-Bit-Gerät (Ich habe Pläne auf 16-Bit PIC24 zu testen , aber ich habe es getestet noch nicht)

wurde ich ernsthaft durch Fragmentierung mit Standard-Allocator geschlagen: mein Projekt oft Blöcke verschiedener Größe zuordnet, aus mehreren Bytes bis zu mehreren hundert Bytes, und manchmal stand ich ‚out of memory‘ Fehler. My PIC32 Vorrichtung hat insgesamt 32K RAM und 8192 Bytes für die Halde verwendet. Am bestimmten Moment gibt es mehr als 5 K freien Speicher, aber standardmäßig allocator maximalen nicht-fragmentierten Speicherblock nur von etwa 700 Bytes hat, wegen der Fragmentierung. Das ist zu schlecht, so dass ich für eine effizientere Lösung zu suchen, entschieden.

Ich war schon von einigen Verteilern bewusst, aber alle von ihnen hat einige Einschränkungen (wie Blockgröße eine Leistung oder 2 sein sollte, und nicht an den Start von zwei, sondern von, sagen wir, 128 Bytes), oder war nur Buggy. Jedes Mal, bevor ich hatte auf den Standard allocator zu wechseln.

Aber dieses Mal, ich habe Glück: ich diese gefunden habe: http: // hempeldesigngroup .com / embedded / stories / memorymanager /

Wenn ich diese Speicherzuordner versucht, in genau der gleichen Situation mit 5K des freien Speichers, es hat mehr als 3800 Bytes blockieren! Es war so unglaublich, mir (bis 700 Bytes zu vergleichen), und ich durchgeführt harte Probe: Gerät stark mehr als 30 Stunden gearbeitet. Keine Speicherlecks, alles funktioniert, wie es funktionieren soll. Ich fand auch dieses allocator im FreeRTOS Repository: http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg=1041# , und diese Tatsache ist ein weiterer Beweis für die Stabilität von umm_malloc. Also habe ich komplett auf umm_malloc, und ich bin ganz zufrieden damit.

Ich musste es einfach ändern, um ein bisschen: Konfiguration war ein bisschen buggy, wenn Makro UMM_TEST_MAIN nicht definiert ist, so habe ich die GitHub-Repository erstellt haben (der Link am Anfang der Post ist). Nun benutzerabhängig Konfiguration wird gespeichert in separater Datei umm_malloc_cfg.h

Ich habe nicht tief noch in den Algorithmen in diesem allocator angewendet bekam, aber es hat sehr detaillierte Erklärung der Algorithmen, so dass jeder, der interessiert ist an der Spitze der Datei umm_malloc.c aussehen kann. Zumindest Ansatz „Binning“ sollte großen Vorteil in weniger Fragmentierung geben: http: // g .oswego.edu / dl / html / malloc.html

Ich glaube, dass jeder, der für Mikrocontroller für eine effizienten Speicherzuordner benötigt, soll diese eine zumindest versuchen.

Obwohl die einige Zeit her, dass ich das fragte, war meine endgültige Lösung Lokis SmallObjectAllocator es große Arbeit zu verwenden. Got alle OS Anrufe gereinigt weg und die Leistung meiner Lua Engine für Embedded-Geräte verbessert. Sehr schön und einfach, und nur etwa 5 Minuten im Wert von Arbeit!

Ich möchte nur auch dies noch hinzuzufügen, obwohl es ist ein alter Thread. In einer eingebetteten Anwendung, wenn Sie können Ihre Speichernutzung für Ihre Anwendung und kommen mit einer max Anzahl der Speicherbelegung der verschiedenen Größen in der Regel die schnellste Art von allocator analysieren einen Speicherpool verwenden ist. In unseren Embedded-Anwendungen können wir alle Zuordnungsgrößen bestimmen, die jemals während der Laufzeit benötigt werden. Wenn Sie dies tun können, können Sie völlig Heapfragmentierung und haben sehr schnell Zuweisungen beseitigen. Die meisten diese Implementierungen haben einen Überlaufpool, der eine regelmäßige malloc für die Sonderfälle tun, die hoffentlich weit und wenige zwischen sein wird, wenn Sie Ihre Analyse richtig gemacht haben.

Ich habe die ‚binäre Buddy‘ -System für eine gute Wirkung unter VxWorks verwendet. Grundsätzlich Sie Teil aus Ihren Haufen von Blöcken halbiert die kleinste Zweierpotenz großen Block, um Ihre Anfrage zu halten, und wenn Blöcke frei sind, können Sie eine der Baum passieren, machen den Blöcken verschmelzen wieder zusammen Fragmentierung zu mildern. Eine Google-Suche sollte alle Informationen aufdrehen Sie benötigen.

Ich bin ein C Speicherzuordner genannt tinymem zu schreiben, soll der Lage sein, den Haufen zu defragmentieren, und wiederverwenden Speicher. Check it out:

https://github.com/vitiral/tinymem

Hinweis: Dieses Projekt ist nicht mehr auf dem Rost Umsetzung zu arbeiten:

https://github.com/vitiral/defrag-rs

Auch hatte ich nicht vor der umm_malloc gehört. Leider scheint es nicht in der Lage zu sein, mit der Fragmentierung zu behandeln, aber es sieht auf jeden Fall nützlich. Ich werde es überprüfen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top