Fragmentierung-resistente Microcontroller Heap-Algorithmus

Question

Ich bin auf der Suche nach einem Heap-Allocation-Algorithmus in C für einen Speicher-Constrained-Mikrocontroller zu implementieren. Ich habe meine Suche auf 2 Optionen beschränkt, die mir bekannt sind, aber ich bin sehr offen für Vorschläge, und ich suche Rat oder Kommentare von jemandem mit Erfahrung in diesem Bereich.

Meine Anforderungen:

-Geschwindigkeit zählt auf jeden Fall, aber es ist zweitrangig.

-Timing Determinismus ist nicht wichtig - jeder Teil des Codes, der deterministische Worst-Case-Timing erfordert, hat seine eigene Zuweisungsmethode.

-Die wichtigste Voraussetzung ist Fragmentierung Immunität. Auf dem Gerät wird eine Lua-Skript-Engine ausgeführt, die eine Reihe von Zuweisungsgrößen erfordert (schwer auf den 32-Byte-Blöcken). Die Hauptanforderung ist, dass dieses Gerät für eine lange Zeit ausgeführt wird, ohne seinen Heap in einen unbrauchbaren Zustand zu versetzen. Hinweis

auch:

-Für Referenz, wir sprechen über ein Cortex-M und PIC32-Teile, mit Speicher im Bereich von 128K und 16MB oder Speicher (mit einem Schwerpunkt auf dem unteren Ende).

-Ich möchte nicht den Heap des Compilers verwenden, weil 1) Ich möchte konsistente Leistung über alle Compiler und 2) ihre Implementierungen sind in der Regel sehr einfach und sind die gleichen oder schlechter für die Fragmentierung.

-Double indirekte Optionen sind out wegen der großen Lua-Code-Basis, die ich nicht grundlegend ändern und revalidate wollen.

Meine Begünstigungs Ansätze So Far:

1) Haben Sie einen binären Kumpel allocator und Speichernutzungseffizienz opfern (Rundung auf eine Leistung von 2 Größe nach oben). -dies würde (wie ich es verstehe) einen binären Baum für jede Reihenfolge/Ablage erfordern, um freie Knoten zu speichern, sortiert nach Speicheradresse für einen schnellen Buddy-Block-Lookup zum erneuten Speichern.

2) Zwei Binärbäume für freie Blöcke haben, eine sortiert nach Größe und eine nach Speicheradresse sortiert. (Alle binären Baumverknüpfungen sind im Block selbst gespeichert.) -allocation würde am besten mit einem Nachschlagen in der Tabelle nach Größe und dann entfernen Sie diesen Block aus dem anderen Baum durch Adresse -deallocation würde benachbarte Blöcke nach Adresse für suchen wiedererhalten

-Beide Algorithmen würden auch erfordern, eine Zuweisungsgröße vor dem Start des zugewiesenen Blocks zu speichern, und Blöcke gehen als eine Potenz von 2 minus 4 (oder 8 abhängig von der Ausrichtung). (Es sei denn, sie speichern einen Binärbaum an anderer Stelle, um Zuordnungen nach Speicheradresse zu verfolgen, was ich nicht für eine gute Option halte)

- Beide Algorithmen erfordern höhenausgleichenden Binärcode.

-Algorithmus 2 hat nicht die Anforderung, Speicher durch Aufrunden auf eine Zweierpotenz zu verschwenden.

- In jedem Fall werde ich wahrscheinlich eine feste Bank von 32-Byte-Blöcken durch verschachtelte Bitfelder zugewiesen haben, um Blöcke dieser Größe oder kleiner zu entladen, die gegen externe Fragmentierung immun wären.

Meine Fragen:

-Ist es einen Grund, warum Ansatz 1 mehr immun gegen Fragmentierung als Ansatz wäre 2?

- Gibt es irgendwelche Alternativen, die ich vermisse, die den Anforderungen entsprechen könnten?

Answer 1

Wenn Blockgrößen nicht auf Potenzen von zwei oder einem Äquivalent (*) aufgerundet werden, erzeugen bestimmte Folgen von Zuweisung und Freigabe eine im Wesentlichen unbegrenzte Menge an Fragmentierung, selbst wenn die Anzahl der nicht permanenten kleinen Objekte bei Jede gegebene Zeit ist begrenzt. Ein Binary-Buddy-Allokator wird dieses spezielle Problem natürlich vermeiden. Andernfalls, wenn man eine begrenzte Anzahl von gut verwandten Objektgrößen verwendet, aber kein "binäres Buddy" -System verwendet, muss man möglicherweise noch einige Urteile treffen, um zu entscheiden, wo neue Blöcke zugewiesen werden sollen.

Ein anderer zu berücksichtigender Ansatz ist die Verwendung verschiedener Zuweisungsmethoden für Dinge, von denen erwartet wird, dass sie permanent, temporär oder halbpersistent sind. Fragmentierung verursacht oft den größten Ärger, wenn temporäre und permanente Dinge auf dem Heap verschachtelt werden. Ein derartiges Verschachteln zu vermeiden, kann die Fragmentierung minimieren.

Schließlich weiß ich, dass Sie nicht wirklich doppel-indirekte Zeiger verwenden möchten, aber die Objektverschiebung zuzulassen, kann Fragmentierungs-Probleme stark reduzieren. Viele von Microsoft abgeleitete Mikrocomputer-BASICs verwendeten einen durch Müll gesammelten Saitenhaufen; Microsofts Garbage Collector war wirklich schrecklich, aber sein String-Heap-Ansatz kann mit einem guten verwendet werden.

Answer 2

Sie können einen (nie für echte) Buddy-System-Allokator bei http://www.mcdowella.demon.co.uk/buddy.html, mit meinem Segen für jeden Zweck, den Sie mögen. Aber ich glaube nicht, dass Sie ein Problem haben, das einfach durch das Einstecken eines Speicherzuordners gelöst werden kann. Die Systeme mit langer Laufzeit und hoher Integrität, mit denen ich vertraut bin, haben eine vorhersehbare Ressourcennutzung, die in mehr als 30 Seiten für jede Ressource beschrieben wird (hauptsächlich CPU- und E/A-Bus-Bandbreite - Speicher ist einfach, da sie beim Start immer dieselbe Menge zuweisen und dann nie wieder).

In Ihrem Fall kann keiner der üblichen Tricks - statische Zuweisung, freie Listen, Zuordnung auf dem Stapel, funktionieren, denn - zumindest wie beschrieben - haben Sie ein Lua interpretiert im Hintergrund schwebend bereit zu tun Wer weiß was zur Laufzeit - was ist, wenn es nur in eine Schleife gerät, die Speicher reserviert, bis sie ausgeht?

Können Sie die Speicherbelegung in zwei Abschnitte trennen - traditioneller Code, der fast alles, was er beim Start benötigt, und nie wieder verteilt, und erweiterbaren Code (z. B. Lua) zuzuteilen, was es benötigt, wenn es benötigt wird bleibt nach der statischen Zuweisung übrig? Könnten Sie dann einen Neustart oder eine Art Aufräumung des entbehrlichen Codes auslösen, wenn es seinen gesamten Speicherbereich belegt oder fragmentiert, ohne den traditionellen Code zu stören?