Schreiben Sie Ihren eigenen guten Speichermanager

Guten Tag, Leser. Vielleicht haben Sie meine vorherigen Artikel bereits gelesen und wissen, dass ich mein eigenes Betriebssystem schreibe. Heute werden wir uns mit einem einfachen und ziemlich schnellen Algorithmus für die Speicherverwaltung befassen. Der Speichermanager ist ein wichtiger Bestandteil des Betriebssystems, da eine schnelle, zuverlässige und nicht verschwendete Arbeit mit dem Speicher der Schlüssel zu einem guten Betriebssystem ist.
Ich suchte nach einfachen und angemessenen Ideen für den Manager sowohl in Runet als auch auf englischsprachigen Websites - ich konnte immer noch keine guten Artikel über einen angemessenen, keinen O (N) -Zuweiser finden. Nun, heute werden wir eine bessere Idee für einen Speichermanager in Betracht ziehen, ich setze die Fortsetzung unter Katze.

Theorie

Aus dem Wiki: Speichermanager - Teil eines Computerprogramms (sowohl Anwendung als auch Betriebssystem), das Anforderungen für die Zuweisung und Freigabe von RAM oder (für einige Computerarchitekturen) Anforderungen verarbeitet, um einen bestimmten Speicherbereich in den Adressraum des Prozessors aufzunehmen.

Ich schlage auch vor, diesen Artikel weiter zu lesen.

Watermak Allokator

Nun, der wahrscheinlich einfachste aller Allokatoren ist der Wasserzeichen-Allokator. Sein Wesen ist ungefähr das Folgende: Der gesamte Speicher ist in Blöcke unterteilt, der Block hat einen Header, der die Größe dieses und des vorherigen Blocks enthält, den Status des Blocks (beschäftigt / frei), die Adresse des Blocks bekannt, wir können die Adresse des nächsten und vorherigen Blocks für O (1) erhalten.

Speicherzuordnung

Um Speicher zuzuweisen, müssen wir lediglich die Blöcke durchlaufen und nach einem Block suchen, dessen Größe größer oder gleich der Größe des für die Zuweisung erforderlichen Speichers ist. Wie Sie bereits verstanden haben, ist das asymptotische Verhalten von O (N) schlecht.

Speicherfreigabe

Um Speicher freizugeben, reicht es aus, den Status des Blocks auf "frei" zu setzen - O (1) - super!

Wie Sie verstehen, können sich jedoch Löcher bilden, in denen zwei oder mehr freie Blöcke defragmentiert werden. Wenn sie freigegeben werden, können benachbarte Blöcke angezeigt werden. Wenn einer oder zwei frei sind, führen Sie sie zu einem zusammen.

Logarithmischer Allokator

Wir wissen, dass wir nur zwischen freien Blöcken suchen müssen. Wenn Sie nur kostenlos laufen, wird die Geschwindigkeit im Durchschnitt zweimal verbessert, aber es ist immer noch eine Linie. Nun, warum sollten wir alle Blöcke durchgehen und nach Größe suchen, wenn wir einen Baum aus freien Blöcken organisieren können? Anfangs haben wir nur einen freien Block, und dann fügen wir dem binären Suchbaum freie Blöcke hinzu. Der Schlüssel ist die Blockgröße. Um Speicher zuzuweisen, reicht es daher aus, einen Block in einem Baum zu finden, dessen Größe größer oder gleich dem ist, was wir benötigen. Wir machen das leise für O (log N) und gehen einfach den Baum hinunter. Außerdem schneiden wir den Block entweder in zwei Teile oder geben ihn vollständig an denjenigen weiter, der die Erinnerung angefordert hat. Als nächstes entfernen wir den Block aus dem Baum für O (1). Fügen Sie gegebenenfalls den Rest des Blocks wieder hinter O ein (log N). Für die Freigabe müssen wir nur den Block zurück einfügen und die Fragmentierung nicht vergessen.

Es ist logisch, dass Sie keinen einfachen Baum verwenden müssen, sondern einen selbstausgleichenden Baum, Rot-Schwarz oder AVL. Sie können den Blockbaum in einem statischen Array speichern oder herausfinden, wie Sie dies anders machen.

Eigentlich ist der Code:

char * malloc(size_t size) { if (!size) { return 0; } char * addr = 0; int i; for (i = 0; i < allocationAvlTree.size; ) { int r; node_t *n; n = &allocationAvlTree.nodes[i]; /* couldn't find it */ if (!n->key) { return NULL; } r = allocationAvlTree.cmp(n->key, size); if (r <= 0) { //We're lucky today. //Get memory block header alloc_t * block = (size_t)n->val - sizeof(alloc_t); //Set to used block->status = 1; //Set size block->size = size; alloc_t * next = (size_t)n->val + size; next->prev_size = size; next->status = 0; next->size = n->key - size - 16; avltree_remove(&allocationAvlTree, n->key, n->val); if (n->key - size - 16) avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t)); memset((size_t)block + sizeof(alloc_t), 0, block->size); block->signature = 0xDEADBEEF; unlockTaskSwitch(); return (size_t)block + sizeof(alloc_t); } else if (r > 0) i = __child_r(i); else assert(0); } return 0; } void free(void * mem) { if (!mem) return; //Get current alloc alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t)); if (alloc->signature != 0xDEADBEEF) return; alloc->status = 0; alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size); if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size) { //Merge blocks if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) { left->size += sizeof(alloc_t) + alloc->size; alloc = left; } else assert(0); } alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size; if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF) { if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t))) alloc->size += sizeof(alloc_t) + right->size; else assert(0); } avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t)); } 

Viel Glück und ethisches Hacken! Jede objektive Kritik ist willkommen. Der Zweck des Artikels besteht nicht darin, zu sagen, dass es sich um eine Art Allokator handelt, sondern lediglich um einen Allokator, der besser ist als dumme Implementierungen einfacher Allokatoren.