Écrire votre propre bon gestionnaire de mémoire

Bonjour, lecteur. Vous avez peut-être déjà lu mes articles précédents et vous savez que j'écris mon propre système d'exploitation. Aujourd'hui, nous allons parler et considérer un algorithme simple et assez rapide pour gérer la mémoire - le gestionnaire de mémoire est une partie critique du système d'exploitation, car un travail rapide, fiable et sans gaspillage avec la mémoire est la clé d'un bon système d'exploitation.
Je cherchais des idées simples et adéquates pour le gestionnaire à la fois dans Runet et sur des sites en anglais - je ne pouvais toujours pas trouver de bons articles sur un allocateur adéquat, pas un O (N). Bon, aujourd'hui on va envisager une meilleure idée pour un gestionnaire de mémoire, je mets la suite sous chat.

Théorie

À partir du wiki: Gestionnaire de mémoire - partie d'un programme informatique (application et système d'exploitation) qui traite les demandes d'allocation et de libération de RAM ou (pour certaines architectures informatiques) les demandes d'inclure une zone de mémoire donnée dans l'espace d'adressage du processeur.

Je suggère également avant de continuer à lire cet article .

Répartiteur Watermak

Eh bien, probablement le plus simple de tous les allocateurs est le Watermark Allocator. Son essence est approximativement la suivante: toute la mémoire est divisée en blocs, le bloc a un en-tête qui contient la taille de celui-ci et du bloc précédent, l'état du bloc (occupé / libre), connaissant l'adresse du bloc, nous pouvons obtenir l'adresse du bloc suivant et précédent pour O (1).

Allocation de mémoire

Pour allouer de la mémoire, il suffit de parcourir les blocs et de rechercher un bloc dont la taille est supérieure ou égale à la taille de la mémoire requise pour l'allocation. Comme vous l'avez déjà compris, le comportement asymptotique de O (N) est mauvais.

Libération de la mémoire

Pour libérer de la mémoire, il nous suffit de définir l'état du bloc comme «libre» - O (1) - super!

Mais, comme vous le comprenez, des trous peuvent commencer à se former dans lesquels 2 blocs libres ou plus sont défragmentés, lorsqu'ils sont libérés, les blocs voisins peuvent être affichés, et si un ou deux sont libres, les fusionner en un seul.

Allocateur logarithmique

Nous savons que nous devons rechercher uniquement parmi les blocs libres. Courir uniquement en mode libre améliore la vitesse en moyenne deux fois, mais c'est toujours une ligne. Eh bien, pourquoi devrions-nous parcourir tous les blocs, en recherchant la taille, si nous pouvons organiser un arbre à partir de blocs libres! Initialement, nous n'avons qu'un seul bloc libre, puis nous ajoutons des blocs libres à l'arbre de recherche binaire, la clé sera la taille du bloc. Ainsi, pour allouer de la mémoire, il nous suffit de trouver un bloc dans un arbre dont la taille est supérieure ou égale à ce dont nous avons besoin. Nous le faisons tranquillement pour O (log N), en descendant simplement dans l'arbre. De plus, nous coupons le bloc en deux ou le donnons complètement à celui qui a demandé la mémoire. Ensuite, nous supprimons le bloc de l'arbre pour O (1). Et, si nécessaire, insérez le reste du bloc derrière O (log N). Pour la sortie, nous avons juste besoin d'insérer le bloc en arrière, et n'oubliez pas la fragmentation.

Il est logique que vous n'ayez pas besoin d'utiliser une arborescence simple, vous devez utiliser une arborescence auto-équilibrée, Rouge-Noir ou AVL. Vous pouvez stocker l'arborescence des blocs dans un tableau statique, ou vous pouvez comprendre comment le faire différemment.

En fait, le 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)); } 

Bonne chance et piratage éthique! Toute critique objective est la bienvenue, le but de l'article n'est pas de dire qu'il s'agit d'une sorte d'allocateur, mais simplement de parler d'un allocateur qui sera meilleur que les implémentations stupides d'allocateurs simples.