Thema: Memory Management

[TeeJay]

Alloa.

Ich hab mir schon ne ganze weile den Kopf zerbrochen wie man Speichverwaltung realisiert.

Also was die Funktion malloc im Grund macht und wie man das ganze Verwaltet.

Jedes mal eine neue Page von 4KB zu reservieren wäre zwar einfach, aber doch recht verschwenderich.

Ich unter Windows mal ein bisschen rumprobiert. Dort hab ich festgestellt, das vor jedem reserviertem kleinen Speicherbereich eine Art Header vorangestellt wird, der wohl Infos zu dem reserviertem Block gibt.
Ich hab den Header bisher noch nicht entschlüsseln können. Aber wichtig ist ja nunerstmal das es diesen gibt.

Nun müsste es aber trotzdem noch eine Art Tabelle geben, die sämtliche reservierten Speicherbereiche listet. Weil irgendwie muss die Funktion malloc ja auch feststellen können, wo bereits Speicher belegt ist und wo sie neuen reservieren kann.

Was ich im Grunde mal fragen wollte, ist wie IHR das bei euch mit der Speicherverwaltung gelöst habt.

Paging ist zwar auch Speicherverwaltung, setzt jedoch eigentlich an einem anderen Punkt an.

[joachim_neu]

du könntest eine tabelle anlegen, in der jeder eintrag 32 bit groß ist, und die zahl enthält, wie viel byte reserviert sind. dann kannste jede "Page" mit der nummer aufrufen, und dann einfach so viele double weiter gehen. allerdings müssten dann die teile direkt hinter einander liegen, sodass du viele schieberrei bei einer disallokierung machen musst... aber du verbrauchst weniger speicher! oder du machst es mit den festen pages.

[GhostCoder]

Hiho,

ich hab bei mir die Speicherverwaltung folgendermaßen realisiert:

Unterste Schicht ist der Blockallocator, der eine(!) physikalische Page zurückgibt. Das hab ich über eine Stack gelöst.

Danach kommt die Schicht für virtuelle Pages. Die Funktionen reservieren im virtuellen Addressraum Pages, und mappen die (wenn gewünscht) mittels dem Blockallocator auf physikalische Pages. Ne passende Win32 Funktion hierfür wäre VirtualAlloc/VirtualFree.

und wie malloc/free funktioniert erkläre ich nachher, habe jetzt keine Zeit mehr, sonst bringt mich meine Freundin um Wobei das mit dem Header schon richtig ist...

MfG GhostCoder

[GhostCoder]

Hiho,

da bin ich wieder

Also, bei mir hab ich ein ziemlich einfaches Heap System eingebaut. Erstmal die HEAP struct:

Code: [Auswählen]


struct HEAP
{
    DWORD dwFlags;
    DWORD dwSize;
    DWORD dwPageSize;
    struct HEAP *psNext;
};

Es funktioniert also wie eine einfach verkettete Liste. Wenn du jetzt mittels HeapAlloc Speicher haben willst, durchsucht die Funktion alle vorhandenen Blöcke, und schaust ob zwischen dwPageSize und dwSize genug Platz ist, eine neue Heapstruct+Speicher anzulegen, soll heißen, wenn ein Block noch Speicher hat, den zu nutzen. Wird da nichts gefunden, wird nach nicht gesuchten Blöcken gesucht(mittels dwFlags,dazu später). Wird auch da nichts gefunden, werden einfach die passendene Anzahl Pages (VirtualAlloc) geholt, am Anfang der Pages wird die struct geschrieben, und der Heapspeicher folgt danach. Zurückgegeben wird dann immer

Code: [Auswählen]


(void*) (psHeap+sizeof(struct HEAP));


HeapFree setzt die Flags des Blockes (die Heapstruct liegt ja direkt vor dem Heapbuffer) auf Null.

Als letzte Funktion gibt es noch HeapClean (unter Win32 heißt die ein bisschen anders), und die räumt einfach alle unbenutzten Blöcke auf(gibt deren Speicher frei, und löscht sie aus der Liste). Und hier krankt mein Ansatz, der ganze Vorgang ist ziemlich schwer zu realisieren, hab die Funktion auch noch nicht implementiert...

Ein anderer Ansatz wäre, eine verkettete Liste aus Pages zu machen. Also, wenn eine Page 4096 Bytes fasst, und die Heapstruct 16 Byte groß ist, kann man ja 255 heapstructs + prev/next zeiger in eine Page packen, und darüber die Heapblöcke verwalten... Die heapstruct müsste dann nurnoch über einen blockzeiger erweitert werden. Der Vorteil wäre, das die HeapClean Funktion jetzt viel einfacher zu realisieren wäre, Nachteil aber, das es lange dauert, bis man zu einem Zeiger(von HeapAlloc zurückgegeben) die passende Heapstruct findet (Alle heap pages durchgehen, und vergleichen...). Musst du selber entscheiden, welche Variante du wählst, wobei meine Ansätze doch eher einfach sind, gibt noch viele andere Prinzipe...

Wichtig ist nurnoch das die Heap Funktionen als libs in Userprozesse eingebunden werden, das einzige Kernelinterface für Speicher sollten die VirtualAlloc,VirtualFree,... Funktionen sein, damit einige Programme( wie .z.b viele aktuelle Spiele) ihre eigenen, schnelleren Heap Funktionen nutzen können!

Hoffe, es ist einigermaßen verständlich geworden...
MfG GhostCoder

[Roshl]

Also ich hab auch eine Einteilung der physischen 4kb Seiten ganz unten und die malloc/free funktion teilen den dann im Prozess auf. Realisieren tu ich das  mit nem kleinen 12Byteheader, der aufs vorhergehende nächste headerchen verweist und sagt ob der speicherbereich frei ist und wie gross er ist.
Hier mal meine C-struct:
typedef struct mheader
{
   mheader *next;
   mheader *prev;
   unsigned size:31;
   unsigned free:1;
}mheader;
Ist wie man sieht eine Doppelt verkette Liste.
Der malloc code ist mit 90 Zeiln bisl zu lang um den hier zu posten^^
Jedenfalls funzt alles einwandfrei, habs ausgiebig getestet. Nur man sollte die Headerstückchen nicht im Programm überschreiben sonst kann da sonstwas rauskommen^^

[GhostCoder]

Hiho,

so mache ich das ja auch...
Hast du auch schon die Aufräumfunktion für den Heap?

MfG GhostCoder

[Roshl]

Wie Aufräumfunktion?

[sp]

Ich hab eine ziehmlich simple Lösung in Nutzung, aber sie funktioniert. Allerdings habe ich auch noch kein Paging bzw. Multitasking implementiert.

Code: [Auswählen]

struct s_mem_page
{
ulong offset;

ulong size;

bool used;
};


Daraus ensteht erst einmal ein Array mit 1000 Elementen. Der Wert für offset im ersten Element wird auf 3MB gesetzt. Wenn nun das erste Mal Speicher benötigt wird, wird die Größe in size geschrieben und used auf true gesetzt. Ab der zweiten Speicheranfrage wird einfach das erste Element gesucht, welches nicht in Nutzung ist. Der neue offset errechnet sich aus offset und size des vorherigen Elementes. Dieser wird dann mit size in das aktuelle Element geschrieben und als letztes wird used auf true gesetzt.

Dazu muss ich aber sagen, das ich dringend die new-Funktion gebraucht habe. Es ist also im Moment nicht wirklich ausgefreift.

[GhostCoder]

@sp:

das Problem bei dir ist, das bei 1000 malloc's Schluß ist, und der Table direkt 12kb frisst. Außerdem dauert es z.B. wenn du z.B. das 999zigste Mal malloc aufrufst, total lange bis du durch alle vorhandenen Blöcke durch bist. Musst ja bedenken, das du später noch 2 Layer(Block und vm) darunter liegen hast, die auch Zeit brauchen. Außerdem, wenn du z.B. den 500sten Block freigibst, müssen wenn das nächste mal der 500er Block benutzt werden soll, und der Block mehr/weniger Speicher als der vorherige 500ste Block braucht, alle folgenden Blöcke geändert (und derInhalt verschoben) werden.

Ne linked-list ist also schon das beste(und schnellste)...

MfG GhostCoder

[sp]

Ich weiß, mit der Lösung fahr ich früher oder später an die Wand .

Aber, wieso ist die "Linked"-Liste schneller?

Außerdem, wenn du z.B. den 500sten Block freigibst, müssen wenn das nächste mal der 500er Block benutzt werden soll, und der Block mehr/weniger Speicher als der vorherige 500ste Block braucht, alle folgenden Blöcke geändert (und derInhalt verschoben) werden.

Wenn man das ganze in eine "Vector"-Klasse steckt, kann ich die Liste auch dynamisch vergrößern und verkleinern.  Aber wie gesagt, das könnte man dann bis zum Super-GAU weiter treiben .

Wo im Speicher liegen eigentlich deine Tabellen?

[GhostCoder]

Aber, wieso ist die "Linked"-Liste schneller?

Allgemein schnell. Damit meinte ich Memory Management mit einer linked-list.

Wenn man das ganze in eine "Vector"-Klasse steckt, kann ich die Liste auch dynamisch vergrößern und verkleiner

Ja, wenn du immer kontinuierlich hinternander Pages frei hast...

MfG GhostCoder[/quote]