Thema: Verwaltung von dyn. Speicher

[[MM]]

Hallo,
ich habe mir grad einige Funktionen für die Verwaltung meines dynamischen Speichers in meinem OS geschrieben, und finde, dass es doh etwas viel Overhead ist, denn für jeden freien oder belegten Speicherblock lege ich zusätzlich noch eine solche Struktur im Speicher an:

Code: [Auswählen]

struct sMemList{
  unsigned int start; // Startadresse
  unsigned int size;  // Größe des Blocks in Byte
  sMemList *next;
};
Wie man sieht wird für jeden freien oder belegten Block eine solche Struktur von 12 Bytes benötigt, die als Liste organisiert sind.
Das Konzept ist denkbar einfach, am Anfang gibt es einen Eintrag in der Free-List, der den ganzen möglichen dyn. Speicher umfasst. Wird etwas allociert, wird der Eintrag verändert und es wird ein Eintrag in die Alloc-List eingefügt. Wird nun free aufgerufen, wird die Alloc-List nach dem Eintrag durchsucht usw.
Funktioniert auch soweit ganz nett, ich bin mir nur nicht ganz sicher, ob es da nicht noch bessere Lösungen gibt.
Kennt einer von euch eventuell eine bessere Strategie?

MM

[Roshl]

Wenn du die Infoblöcke im aufgeteilten Speicher speicherst also |Info|Speicher|Info|Speicher...
dann reicht es nur die Größe zu speichern. next ergibt sich aus der grösse der struktur + size und die startadresse ergibt sich logischerweise von selbst. Da du next mit speichers gehe ich davon aus, das du soetwas willst. Nimmst du eine extra tabelle um sowas zu handlen, dann ist next eh sinnlos und man kann einfach einen array benutzen, braucht da dann aber startaddi und grösse drin.
Es wäre auch nicht verkehrt eine Doppelt verlinkte liste zu nehmen, also ein pointer auf prev mit zu speichern, das beschleunigt das freigeben der blöcke.

[[MM]]

Hab mal über deinen Vorschlag nachgedacht und mir sind dabei folgende Sachen aufgefallen:
Angenommen man speichert nur die Größe des folgenden Blocks (und zB im Bit 31, ob er frei oder belegt ist), dann ist es zum einen sehr mühsam einen freien Block zu finden, da man auch alle Belegten durchgehen muss, und zum Anderen kann man sich die folgende Situation vorstellen:

Code: [Auswählen]

4 Byte Size, 7 Byte Daten, danach der nächste Block:
|b size=7||data...||b size=x||data..........|
Nun wird der 1. Block frei gegeben:
|f size=7||.......||b size=x||data..........|
Wenn ich nun zb 6 Bytes allociere:
|b size=6||data..|.|b size=x||data..........|

Dann hängt ein Byte alleine rum und es ist kein Platz um einen 4 Byte langen size-Block einzuschieben, woraus folgt, dass man nur Lücken füllen darf, wenn sie komplett gefüllt werden können, oder man noch mind. 4 Byte übrig behält.
Da gefällt mir das mit der Liste doch irgendwie besser...

Und was das mit dem prev-Zeiger betrifft, ich kann mir doch beim durchgehen der Liste in der Schleife das vorherige Element immer merken, denn mehr als eins zurück muss ich ja nie.

MM

[Roshl]

Zum prev Zeiger, wenn du free aufrufst gibste als paramter den pointer. Da ist nichts mit vorher durchgehen mein Junge^^
Und wegen dem einen Byte... das kannste einfach mitgeben^^ ob der Zugeteilte Bereich nun grösser ist, ist dem Programm doch wurscht. Ausserdem wird sowieso meist ein Alignment von 16Byte (1 Paragraph) eingehalten, wegen dem Caching. Wenn du dich mal mit SSE beschäftigt hast wirst du das wissen, dass Zugriffe auf aligned daen schneller sind, das gilt bei allen Daten. Auf neuen Prozessoren auf 16 Byte, bei älteren auf 4 Byte Alignment. Von daher ist es ohnehin sinnvoll sowas reinzusetzen, ausserdem wird verhindert, das ausversehen der nächste Infoblock überschrieben wird, wenn du etwas mehr gibst^^ Alignment bringt teils extreme Geschwindigkeitsschübe. Bsp SSE, bei unaligned Zugriff können nur 2 von 3 Datenleitungen der ALU und FPU Einheiten genutzt werden, bei aligned alle 3. selbst wenn es nur ein Takt wäre der dadurch verloren geht kann sich das Bemerkbar machen, ich schreibe grade an einem Raytracer und habe durch das Alignment ca 3Millionen Takte weniger im Verbrauch, und das wenn nur Primärstrahlen verwendet werden, mit Sekundärstrahlen würde sich das mal eben um den Faktor 256 erhöhen (wenn ich diffuse Refletion dazusetzte^^)

[[MM]]

Ja, bei free wird ein Pointer übergeben, aber nicht auf den Infoblock, sondern auf den Anfang des allocierten Speichers und wenn ich die Blöcke in einer Linked-List (siehe oben) verwalte, dann kann ich aus dem Zeiger auf den allocierten Speicher nicht sofort auf den Verwaltungseintrag schließen, da dieser sich nicht zwangsläufig davor befinden muss, mein Junge...
Ich denke ich werde es jetzt so machen, dass ich am Anfang und am Ende je 4 byte für Größe/Flag für belegt, frei (das Flag im Bit 31) anlege und nur die freien Einträge in einer Liste speichere. Beim Allocieren kann ich dann durch die Liste gehen, und beim Freigeben kann ich auf einfache Weise ggf vorhergehende/nachfolgende Blöcke sehr leicht vergrößern:

Code: [Auswählen]

|size||...data...||size||size||...data...||size|
Und was das alignment angeht, man könnte ja gleich beim malloc-Aufruf die Größe auf 4Byte ausrichten, aber dadurch würde man leider die Möglichkeit verlieren zu ermitteln, wie groß ein allocrierter Speicherbereich ist, was in diesem oben beschriebenen Falle ja so ginge:

Code: [Auswählen]

size=(*((unsigned int*)(ptr-4)))&0x7FFFFFFF;

MM

[Roshl]

in meiner variante liegt der infoblock immer davor, bei fast allen gängigen OS's wird so verfahren, das hat schon seinen grund

[DDR-RAM]

na jungs

Also ich muss Roshl rechtgeben, die InfoBereich liegt vor dem jeweiligen Datenblock.
Unter windows z.b. ist der Infoblock 24 Bytes groß, der Datenblock wird auf 8 Byte aligned (standard user allokation mit malloc/HeapAlloc).

Die freien Blöcke würde ich in den freien blöcken selbst organisieren.
Die Blöcke müssten ja (wenn wie unter win auf 8 Byte aligned wird) mindestens 8 Byte groß sein.
Bei meinem Speichermanager habe ich in den Freien Blöcken einen AVL-Baum. Damit sind Zugriffe mit maximal logarithmischer Laufzeit gewährleistet. An einem Festen ort muss dann nur ein Zeiger auf den Rootknoten liegen, bzw. falls man es wie ihr mit Listen macht auf das Head-Element der Liste.

Der WinAPI Heap verwendet übrigens einen Heap, daher der Name.
Auch hier sind Zugriffszeiten maximal logarithmisch.
Bei Allozierung wird immer der größte Block genommen (und meisten geteilt).
In meinem System würde ich vorher noch einbauen, erst einen genau passenden Block zu finden und erst danach den größtmöglichen Block, dies wäre der Algorithmus, der die interne Fragmentierung am geringsten hält, aber halt etwas langsamer (aber trotzdem maximal logarithmisch) als das größte Element zu nehmen.
Ich verwende übrigens alignment von 32 Bytes, was sich ein wenig übertrieben anhört, es aber nicht ist, da unter windows ein block auch mindestens 32 Bytes groß ist (also inclusive InfoHeader).

Go on Coding  

MfG
DDR-RAM

[[MM]]

Ich sehe es ein, ich hab es jetzt auch so gemacht, dass vor jedem Block die Info-Daten stehen und ein Block eine Mindestgröße von Immerhin 24 Bytes hat. Die freien Blocks in einem gewichteten Baum zu verwalten war mir aber dann doch zu viel...

MM

[WhiteDragon]

Ich möchte nun auch noch vorstellen, wie ich es bisher gemacht habe, vielleicht kann das jemand gebrauchen oder mir noch sagen, wo Denkfehler von mir stecken (obwohl ich bisher mit diesem Konzept noch ganz gut fuhr):

Zunächst einmal gibt es in meinem OS bisher keinen allgemeinen Speicherbereich. Da ich noch an meinem Kernel arbeite, sind alle Aussagen über Applikationen bisher reine Spekulation, wenn ich auch schon recht genaue Vorstellungen habe.

Der Kernel hat seinen eigenen Heap, um Datenstrukturen sowohl sehr kleiner als auch größerer Natur festzuhalten. Dieser Heap ist (wie könnte es anders sein) in Blöcke unterteilt. Jeder Block hat folgenden Aufbau:

- Länge (4 Byte)
- Inhalt (n Byte)
- Länge (4 Byte)
- Flags (1 Byte)

In den Flags ist auch verzeichnet, ob ein Block frei ist oder nicht. Auf die Verwendung des 31. Längenbits habe ich verzichtet (obwohl ich zu Beginn daran gedacht hatte), um mir nicht willkürlich eine 2GB-Grenze zu setzen.

Der Inhalt sind jeweils mindestens 8 Byte, da die freien Blöcke in einer doppelt verketteten Liste stehen.

Der Vorteil mit der doppelten Längenhaltung vorne und hinten ist, dass ich direkt nach der Freigabe eines Blockes abchecken kann, ob davor und/oder dahinter ebenfalls ein freier Block liegt. In einem solchen Fall wird daraus ein großer Freiblock gemacht. Dies wiederum bewirkt, dass ich nie zwei Freiblöcke direkt hinter einander habe. Wenn ich also erst meinen Speicher mit tausenden von kleinen Blöcken fragmentiere und später Stück für Stück wieder frei gebe, habe ich wie vorher wieder einen einzelnen, großen, sauberen Freiblock.

Dies gilt aber, wie gesagt, nur für den Heap des Kernels.

Für die Applikationen möchte ich es ähnlich machen, aber nicht innerhalb des gleichen Speicherbereiches wie dem Kernelheap, da ich vermeiden möchte, dass mir eine Applikation das System lahm legt, indem es Zeiger ungültig verbiegt. Vielmehr werde ich jeder Applikation ihren eigenen Speicherbereich zuweisen und ihren Heap in genau jenem verwalten.

Wie gesagt: Für jede Anmerkung hierzu bin ich offen.