|
|||||||||||||||||||||||||||||||||||||||||||||
|
Note : traduction par David Brunet. Avant-propos De nombreuses parties d'AmigaOS ont été conçues il y a 25 ans. À l'époque, les ressources système étaient rares et les processeurs étaient relativement lents. Pour le noyau Exec, un simple mais souvent rapide algorithme de gestion de la mémoire fut choisi : l'algorithme "First Fit" (premier emplacement libre). Il fournit une très bonne vitesse d'allocation dans les scénarios non fragmentés. La désallocation de la mémoire n'est cependant pas très efficace. Le problème majeur est la fragmentation de la mémoire : la routine First Fit devient exponentiellement lente dès que la fragmentation augmente. Avec le temps, la fragmentation peut devenir si importante que le système est visiblement lent. Enfin, la routine First Fit favorise la fragmentation en renvoyant le premier bloc de mémoire disponible et ceci quelque en soit sa taille. MorphOS a hérité de l'algorithme de gestion de la mémoire d'AmigaOS. Il a très bien fonctionné, mais il est vite devenu évident qu'il avait de sérieux problèmes. Des sessions particulièrement longues (plusieurs jours) d'utilisation d'applications complexes (par exemple IBrowse) ralentissaient facilement le système. On devait alors remplacer First Fit par quelque chose de meilleur. J'avais trois objectifs de conception en tête lorsque j'ai développé le nouveau système de mémoire pour MorphOS :
La première exigence (la compatibilité) était clairement la plus critique car MorphOS veut généralement rester aussi compatible que possible avec AmigaOS, tout en introduisant de nouvelles fonctionnalités avancées. La compatibilité s'est également avérée être l'exigence la plus difficile à satisfaire. L'API mémoire compatible AmigaOS est remplie d'obscurités telles qu'AllocAbs(), AvailMem() et AddMemList(), qui libèrent des blocs mémoire partiels, le drapeau MEMF_REVERSE et des caractéristiques d'alignement mémoire documentées. Le défi était d'introduire un système de mémoire plus rapide sans casser ces fonctionnalités. Par exemple, il existe une séquence de code commune pour obtenir des blocs de mémoire alignés :
Pour que cela continue à fonctionner correctement, le nouveau système doit implémenter AllocAbs() correctement et respecter les spécifications d'alignement d'origine. Voici un autre exemple, une routine qui alloue le plus grand bloc mémoire :
Pour que cela fonctionne, le plus grand bloc mémoire retourné par AvailMem() doit toujours être disponible pour l'allocation. AddMemList() est une fonctionnalité assez rare du système de mémoire. Cette fonction peut être utilisée pour ajouter de la mémoire à l'environnement d'exécution du système. Tous ces éléments sont implémentés et fonctionnent correctement dans le nouveau système de mémoire. Le nouveau système est même compatible avec des bidouilles assez vicieuses, comme supposer qu'AllocVec() maintient la taille de l'allocation à ptr-4. Ceci est souvent utilisé pour implémenter des fonctionnalités comme realloc() pour la mémoire AllocVec()ed. Il n'y a pas de problème à gérer cette mesure car elle n'a pas d'incidence négative sur d'autres choses. Il est facile de comprendre que le code utilisant de telles bidouilles est sérieusement cassé, mais on comprend aussi que, souvent, il n'y a pas non plus de moyen de corriger ces applications. Pour l'utilisateur final, il est donc préférable de supporter de tels "bidouilles", plutôt que de planter lamentablement. Les développeurs peuvent utiliser des outils tels que MungWall pour détecter ces bidouilles, mais les utilisateurs finaux ne devraient pas avoir à se soucier de ces choses ! Finalement, il ne restait plus que deux choses à faire : Premièrement, FreeMem() ne peut plus être utilisé pour libérer des blocs mémoire partiels. Cette fonctionnalité était un effet collatéral de FreeMem() qui appelle en interne Deallocate(), qui à son tour gère les blocs mémoire partiels. Avec le nouveau système de mémoire, Deallocate() n'est plus appelé. Dieu merci, même les SDK d'AmigaOS ont depuis longtemps découragé les blocs partiels de FreeMem, donc je pense que ce n'est plus un gros problème. Deuxièmement, MEMF_REVERSE n'a plus aucun effet sur l'allocation. Le drapeau est discrètement ignoré. Franchement, je crois que l'ajout d'un tel drapeau au système de mémoire était une erreur dès le départ. Dans le cas de MorphOS, il n'a de toute façon aucune application, donc je ne crois pas que son retrait ait d'effets négatifs. Réduire les effets de la fragmentation La fragmentation se produit indéniablement, il n'y a pas moyen de l'éviter. Avec le temps, la mémoire se fragmentera. L'astuce consiste à réduire les effets négatifs qu'elle a sur les performances du système. Ici, le choix de l'algorithme était critique. L'algorithme TLSF (Two Level Segregated Fit) garantit un coût d'allocation/désaffectation O(1) constant indépendamment de la fragmentation de la mémoire. Cela signifie que les allocations et les désallocations se feront à la même vitesse, quel que soit le niveau de fragmentation de la mémoire. Même après, disons, cinq ans de fonctionnement. Réduire la fragmentation de la mémoire Ici, le choix de l'algorithme est également critique. Par exemple, l'algorithme original First Fit génère beaucoup de fragmentation au fil du temps. Pour obtenir des vitesses d'allocation rapides, il renvoie le premier bloc de mémoire correspondant aux besoins. Le nouvel algorithme devrait plutôt retourner le meilleur fragment de mémoire possible, en s'assurant que la fragmentation n'a lieu qu'en cas d'absolue nécessité. L'algorithme TLSF excelle ici aussi, donnant une fragmentation moyenne inférieure à 15%. Implémentation MorphOS 2.0 et ses versions ultérieures possèdent une interface mémoire interchangeable. En gros, différents schémas d'allocation peuvent être sélectionnés au démarrage. Pour l'instant, les options possibles sont First Fit (comme dans AmigaOS et MorphOS 1.x) et Two Level Segregated Fit (par défaut). L'utilisateur peut configurer le système de mémoire désiré en tapant une commande de démarrage MorphOS dans l'Open Firmware. L'algorithme TLSF est remarquablement simple : L'algorithme recherche un bloc mémoire libre dont la taille est la plus proche de l'allocation demandée. Le mécanisme de recherche de blocs mémoire libres utilise un tableau de listes libres, chaque tableau contenant des blocs libres dans une classe de taille. Les classes sont des puissances de deux : 16, 32, 64 et ainsi de suite. Pour des raisons de performance et de réduction de la fragmentation, le tableau comporte deux niveaux. Dans l'implémentation MorphOS de cet algorithme, chaque liste est divisée en 32 sous-divisions. Ceci, combiné à d'autres spécificités de l'implémentation, autorise une taille d'allocation maximale de 2 Go. Chaque tableau de listes dispose d'une table de bits afin d'indiquer quelles listes sont occupées par des blocs vides et quelles listes sont vides (toute la mémoire allouée). Les blocs libres contiennent eux-mêmes des informations sur le bloc, comme avec la routine originale First Fit. Pour de meilleures performances au niveau du regroupement des blocs pendant la désallocation de la mémoire, un pointeur arrière ("back pointer") vers le bloc libre précédent est également maintenu. Afin d'allouer un bloc mémoire, la taille d'allocation est répartie entre les deux index. Ces index sont utilisés pour trouver un bloc libre, qui est maintenant une opération O(1). Le bloc trouvé est retiré de la liste libre et marqué comme utilisé. Si le bloc libre trouvé est plus grand que la taille de l'allocation, le bloc est divisé. La taille du bloc restant est à nouveau répartie en deux index. Le nouveau bloc libre est inséré à la position correcte indiquée par les index. Pour libérer de la mémoire, la taille du bloc est obtenue à partir de l'en-tête du bloc. Le bloc est fusionné avec le bloc précédent et le bloc suivant, si possible. Si la fusion est possible, l'autre bloc est marqué comme utilisé et supprimé. La taille du bloc final est à nouveau répartie en deux index. Le nouveau bloc libre est fusionné comme bloc libre et inséré dans la position correcte indiquée par les index. L'implémentation MorphOS de cet algorithme de gestion de la mémoire ajoute certaines choses que l'algorithme original n'avait pas : le maintien de la taille libre restante (pour AvailMem), la possibilité d'allouer le plus grand bloc libre possible et l'allocation d'un bloc mémoire à une adresse absolue. De plus, les caractéristiques de l'allocateur TLSF donnent la possibilité de détecter automatiquement les tailles incorrectes des désallocations transmises aux routines de libération de la mémoire. Cela donne une sécurité supplémentaire sous la forme d'un rejet des appels visiblement illégaux. Et pour les développeurs de logiciels, il fournit un débogage supplémentaire permettant d'identifier et corriger un bogue plus tôt. Le système de mémoire TLSF remplit tous les objectifs de conception : il est très compatible même avec les applications les plus anciennes, il garde de bonnes performances quelle que soit la fragmentation de la mémoire, et il réduit la fragmentation de la mémoire. Références rtportal.upv.es/rtmalloc/files/ecrts04_tlsf.pdf. en.wikipedia.org/wiki/Dynamic_memory_allocation.
|