(C) Quelles sont les politiques de tas les plus souvent utilisées?

Question

J'ai entendu dire que «better-fit» est assez communément utilisé, mais je ne semble pas en lire beaucoup à ce sujet en ligne. Quelles sont les stratégies les plus couramment utilisées/considérées comme les plus efficaces utilisées par les allocateurs de tas?

(j'admettez mon vocabulaire peut être imparfait, quand je dis « politique » je veux dire des choses comme « meilleur ajustement, » « première forme, » « prochain ajustement », etc.)

Edit: I Je suis également particulièrement intéressé par la façon dont les politiques de «meilleur ajustement» et la stratégie de doug lea (http://gee.cs.oswego.edu/dl/html/malloc.html) comparer. Doug utilise un type de meilleur ajustement, mais son approche utilise des bacs d'index, tandis qu'un meilleur ajustement utilise un arbre cartésien.

Answer 1

environnements de programmation C utilisent la mise en œuvre de malloc fourni par la bibliothèque standard C qui vient avec le système d'exploitation Les concepts Doug Lea's memory allocator (appelés dlmalloc) sont les plus largement utilisés dans la plupart des allocataires de mémoire sous une forme ou une autre sous UNIX systèmes. dlmalloc utilise des corbeilles de différentes tailles pour accueillir des objets - la corbeille la plus proche de la taille de l'objet est utilisée pour allouer l'objet. FreeBSD utilise un nouvel allocateur de mémoire multi-thread appelé jemalloc conçu pour être concurrentiel et thread-safe, qui fournit de bonnes caractéristiques de performance lorsqu'il est utilisé dans les systèmes multicœurs d'aujourd'hui. Une comparaison de l'ancien malloc et le nouveau multithread peut être trouvé here. Même s'il est multi-thread, il utilise toujours les concepts de blocs de tailles différentes pour accommoder les objets en fonction de leur taille (les blocs les plus proches de la taille de l'objet sont utilisés pour allouer l'objet).

À l'intérieur des noyaux UNIX, l'allocateur de mémoire le plus populaire est l'allocateur de blocs , qui a été introduit par Sun Microsystems. Le slab allocator utilise de gros morceaux de mémoire appelés dalles. Ces dalles sont réparties entre des caches d'objets (ou pools) de tailles différentes. Chaque objet est attribué à partir du cache qui contient les objets les plus proches de sa taille.

Comme vous remarquerez que les caches/blocs/dalles de plaque ci-dessus ne sont que des formes de l'algorithme meilleur ajustement. Ainsi, vous pouvez facilement supposer que l'algorithme «best fit» est l'un des algorithmes malloc les plus utilisés (bien que les allocateurs de mémoire diffèrent d'autres façons importantes).