gestion de la mémoire intelligente avec des opérations de temps constant?

Question

Considérons un segment de mémoire (dont la taille peut augmenter ou diminuer, comme un fichier, en cas de besoin) sur lequel vous pouvez effectuer deux opérations d'allocation de mémoire de base comportant des blocs de taille fixe:

• l'attribution d'un bloc
• libérant un bloc précédemment alloué qui ne sert plus.

En outre, comme condition, le système de gestion de la mémoire ne peut pas déplacer des blocs actuellement attribués:. Leur indice / adresse doit rester inchangé

L'algorithme de gestion de la mémoire la plus naïve incrémenter un compteur global (avec une valeur initiale 0) et utiliser sa nouvelle valeur d'adresse pour l'attribution suivante. Toutefois, cela ne permettra de raccourcir le segment lorsque seulement quelques blocs alloués restent.

approche mieux. Garder le comptoir, mais maintenir une liste des blocs désallouées (qui peut être fait en temps constant) et l'utiliser comme une source de nouvelles allocations tant que ce n'est pas vide

Et ensuite? Y at-il quelque chose d'intelligent qui peut être fait, toujours avec les contraintes d'allocation de temps constant et désaffectation, qui garderait le segment de la mémoire aussi courte que possible?

(Un objectif pourrait être de suivre le bloc actuellement non affecté à l'adresse la plus petite, mais il ne semble pas être possible en temps constant ...)

Answer 1

Avec des blocs de taille fixe, ce que vous avez décrit est un liste libre. Ceci est une technique très courante, avec la torsion suivante: la liste des blocs libres est stockée dans les blocs libres eux-mêmes. Dans le code C, il ressemblerait à ceci:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

Cela fonctionne bien aussi longtemps que tous les blocs alloués ont la même taille et que la taille est un multiple de la taille d'un pointeur, de sorte que l'alignement est conservé. Allocation et récupération sont à temps constant (qui est, comme à temps constant que les accès mémoire et additions élémentaires - dans un ordinateur moderne, un accès mémoire peut impliquer misses cache et même la mémoire virtuelle, d'où les accès disque, de sorte que la « constante de temps » peut être assez grand). Il n'y a pas de frais généraux de mémoire (pas de pointeurs supplémentaires par bloc ou des choses comme ça, les blocs alloués sont contigus). En outre, le pointeur d'allocation atteint un point donné que si, à un moment donné, que de nombreux blocs devaient être attribués: puisque l'allocation préfère en utilisant la liste libre, le pointeur d'allocation est augmentée que si l'espace situé sous le pointeur est horloge complet. En ce sens, c'est une technique optimale .

diminution le pointeur d'allocation après une libération peut être plus complexe, puisque les blocs libres peuvent être identifiés de manière fiable uniquement en suivant la liste libre, qui passe par eux pour imprévisibles. Si la diminution de la grande taille du segment lorsque cela est possible est important pour vous, vous pourriez vouloir utiliser une autre technique, plus les frais généraux: entre deux blocs attribués, vous mettez un « trou ». Les trous sont reliés entre eux avec une liste doublement lié, dans l'ordre de mémoire. Vous avez besoin d'un format de données pour un trou de telle sorte que vous pouvez trouver l'adresse de départ du trou en sachant où elle se termine, et aussi la taille du trou si vous savez où le trou commence dans la mémoire. Ensuite, lorsque vous relâchez un bloc, vous créez un trou qui vous fusionnez avec l'autre et les trous précédents, la reconstruction (toujours en temps constant) la liste ordonnée de tous les trous. Les frais généraux est alors de deux mots de taille pointeur-par bloc alloué; mais, à ce prix, vous pouvez détecter de manière fiable l'apparition d'un « trou final », à savoir une occasion de réduire la grande taille du segment.

Il existe de nombreuses variantes possibles. Un bon document d'introduction est allocation dynamique de stockage: Une enquête et un examen critique par Wilson et al.

Answer 2

Cette réponse est sur les techniques de gestion de mémoire génériques. J'ai manqué que la question porte sur le cas où tous les blocs ont la même taille (et sont alignés).

---

Les stratégies de base que vous devez savoir sont la première forme, la prochaine forme, la mieux adaptée, et le copain système . J'ai écrit un bref résumé une fois pour un cours que j'appris, je espérons qu'il est lisible. Je signale qu'il y une enquête assez exhaustive .

Dans la pratique, vous verrez diverses modifications de ces stratégies de base. Mais aucun d'entre eux est vraiment constante de temps! Je ne pense pas que ce soit possible dans le pire des cas, tout en utilisant une quantité limitée de mémoire.

Answer 3

Vous pouvez jeter un oeil à amorti analyse et dans des tableaux dynamiques de particuliers. Même si les opérations ne sont pas vraiment fait en temps constant à chaque étape, à long terme, il semble que ce soit le cas.