:tocdepth: 2 ================== Gestion d'un tas ================== .. include:: common.rst.inc Problématique ============= Exemple +++++++ .. code-block:: c Tpoint* alloue_point (double x, double y, double z) { Tpoint* p = malloc(sizeof(Tpoint)); p->x = x; p->y = y; p->z = z; return p; } void libere_point (Tpoint* p) { free(p) } .. index:: single: allocation; statique single: pile see: stack; pile Rappels: allocation statique ++++++++++++++++++++++++++++ * s'applique aux *variables locales* * stockage dans la pile (en anglais *stack*) * allocation en entrant dans la fonction/procédure * libération en sortant de la fonction/procédure * gérée automatiquement par le compilateur .. index:: single: allocation; dynamique single: tas see: heap; tas Rappels: allocation dynamique +++++++++++++++++++++++++++++ * stockage dans le tas (en anglais *heap*) * allocation/libération à la demande du programmeur * ``malloc``/``free`` * ``new``/``delete`` Besoins +++++++ **Besoins**: gérer l'occupation d'une plage de mémoire (éventuellement extensible) * réserver (allouer) des zones d'une taille spécifiée (``malloc``) * libérer une zone préalablement réservée (``free``) **Critères**: * rapidité des opérations d'allocation et de libération * surcoût en mémoire * gaspillage (mémoire inutilisée sans raison) Remarques +++++++++ * Géré par les bibliothèques standards (``malloc/free``), * voire par le langage lui même (``new/delete``), * parfois de manière implicite (ramasse-miettes). → notion `étendue `:ref: de système d'exploitation. Méthodes ======== .. contents:: :local: :depth: 0 :backlinks: none .. index:: carte de bits Carte de bits +++++++++++++ * le tas est subdivisé en blocs de taille fixe * on établit une **carte**: un tableau de bits dont chaque bit représente l'état (libre/alloué) d'un bloc \ .. figure:: _static/carte_de_bits.* :width: 100% | ``map: 11000111 11000000 00111000 01111110`` | ``limits: 01000000 01000000 00001000 00100010`` Avantages --------- * surcoût en mémoire raisonnable exemple : blocs de 8 octets → 1,6 % (3,2 % avec les limites) Inconvénients ------------- * allocation coûteuse en temps (recherche d'espace libre) * **fragmentation interne**: certains blocs marqués comme occupés ne sont pas totalement utilisés \ → Peu utilisé en pratique .. index:: single: liste chaînée; gestion d'un tas Liste chaînée +++++++++++++ On représente l'état de la mémoire par une liste chaînée dont chaque maillon représente une zone (adresse, taille), son état (alloué ou libre) et pointe vers le maillon représentant la zone suivante. \ .. figure:: _static/tas_liste_chainee.* :width: 100% Évaluation ---------- * La durée des opérations et le surcoût en mémoire dépendent du *nombre de zones alouées*, et non de la *taille du tas*. * Pas de fragmentation interne. * Permet de gérer des zones allouées contigües. * L'allocation et la libération sont encore relativement coûteuses (recherche dans la liste, y compris pour la libération). Allocation ---------- .. container:: build animation stacked .. figure:: _static/tas_liste_chaine_anim01.* :width: 100% \1. On recherche une zone libre de taille suffisante (de taille ≥ à la taille réclamée). .. figure:: _static/tas_liste_chaine_anim02.* :width: 100% \2. On fractionne la zone libre en deux (la première ayant exactement la taille à allouer). .. figure:: _static/tas_liste_chaine_anim03.* :width: 100% \3. On marque la première comme allouée et on retourne son adresse.   Libération ---------- .. container:: build animation stacked .. figure:: _static/tas_liste_chaine_anim04.* :width: 100% \1. On parcours la liste jusqu'à trouver le maillon pointant vers la zone à libérer. .. figure:: _static/tas_liste_chaine_anim05.* :width: 100% \2. On marque ce maillon comme libre. Attention à la **fragmentation externe**. .. figure:: _static/tas_liste_chaine_anim06.* :width: 100% \3. Le cas échéant, on fusionne la zone libre avec les zones libres voisines. .. figure:: _static/tas_liste_chaine_anim07.* :width: 100% NB: seuls les voisins immédiats peuvent être libres, donc la fusion ne pénalise pas l'opération de libération (temps constant). Choix d'une zone libre ---------------------- Lors d'une allocation mémoire, si plusieurs zones libres de taille suffisante sont disponibles, laquelle choisir? * Premier trouvé (*first fit*) : méthode la plus simple et la plus rapide * Meilleur trouvé (*best fit*) : cherche la zone libre la plus petite, c.à.d. la plus *proche* de la taille recherchée. * Pire trouvé (*worse fit*) : cherche la zone libre la plus grande. Avantages ? Inconvénients ? .. ifnotslides:: * Sauf lorsqu'elle trouve une zone de la taille exacte, *best fit* a tendance a laisser des zones libres trop petites pour être utilisables. * *Worse fit* n'a pas cet inconvénient, mais crée plus de fragmentation à terme. * *First fit* a l'avantage d'être significativement plus rapide. Variante 1 -------------- .. figure:: _static/tas_liste_chaine_ext1a.* :width: 100% Séparer les zones libres et occupées en deux listes. Variante 1 (suite) `````````````````` .. figure:: _static/tas_liste_chaine_ext1b.* :width: 100% Oblige à maintenir deux structures en parallèle. Variante 2 ---------- .. figure:: _static/tas_liste_chaine_ext2a.* :width: 100% Séparer les zones libres par taille. Variante 2 (suite) `````````````````` .. figure:: _static/tas_liste_chaine_ext2b.* :width: 100% Oblige en plus à gérer les changements de taille. .. index:: buddy Méthode Buddy +++++++++++++ **Principe** Méthode basée sur le principe dichotomique, permettant de diviser la taille du tas par des puissances de 2. **Inconvénients** * fragmentation interne (contrainte sur la taille des zones) * fragmentation externe **Avantages** * efficace en temps (logarithmique par rapport à la taille de la mémoire) Fonctionnement -------------- * À chaque taille de zone correspond une liste chaînée. * Allocation : au besoin, on divise par deux une zone libre, jusqu'à atteindre la taille (la plus proche de celle) à allouer. * Libération : on fusionne deux zones libres si elles sont *buddy* (« potes ») c.à.d. issue de la division d'un même « père ». Exemple ------- .. container:: build animation stacked .. figure:: _static/buddy_anim01.* :width: 95% tas de 16ko .. figure:: _static/buddy_anim02.* :width: 95% alloue 3ko (1) .. figure:: _static/buddy_anim03.* :width: 95% alloue 3ko (2) .. figure:: _static/buddy_anim04.* :width: 95% alloue 2ko (1) .. figure:: _static/buddy_anim05.* :width: 95% alloue 2Ko (2) .. figure:: _static/buddy_anim06.* :width: 95% libère zone 2 (1) .. figure:: _static/buddy_anim07.* :width: 95% libère zone 2 (2) .. figure:: _static/buddy_later.* :width: 95% un peu plus tard Application ----------- Linux utilise la méthode *Buddy* pour l'allocation des pages. → La fragmentation (interne ou externe) n'est plus un problème puisque * les pages ont toutes la même taille, * elles n'ont pas besoin impérativement d'être contigües. .. index:: slab Méthode Slab ++++++++++++ * **Limitation** : toutes les zones à allouer sont de la même taille (structures d'un type particulier) * Principe : on réserve à l'avance un grand tableau (*slab*, ou « dalle »). * On conserve * la taille du tableau, * une liste chaînée des cases libres. * Allocation et libération *en temps constant*. Illustration ------------ .. figure:: _static/slab_naive.* :width: 100% NB: * aucune référence *explicite* aux zone allouées. * le dernier maillon de la liste désigne *tout le reste* du tableau. Optimisation ------------ On peut recycler les cases libres du tableaux elles même pour stocker * l'entête du tableau, * la liste chaînée, → surcoût mémoire minime. \ .. figure:: _static/slab_optimized.* :width: 100% Applications ------------ * Linux utilise la méthode *Slab* pour l'allocation de ses structures internes (PCB, fichiers ouverts, i-nodes...). * Chaque tableau occupe un nombre entier de pages. * Pour chaque type de structure, Linux gère en fait une *liste* de tableaux (buffer) et y ajoute des tableaux au besoin. Applications (2) ```````````````` * Utilisable au niveau applicatif * pour un type de structure nécessitant de nombreuses allocations / libérations, * plus efficace que ``malloc``\ / ``free`` ou ``new``\ / ``delete`` → mais **attention**: pas d'optimisation prématurée. Extension: ramasse-miettes ========================== .. index:: ramasse-miettes see: garbage collector; ramasse-miettes Ramasse-miettes +++++++++++++++ **Problème** * La gestion dynamique est une tâche fastidieuse et une source d'erreur (« fuites mémoires ») pour les programmeurs. * Ceux-ci utilisent par ailleurs des outils informatiques pour les détecter et les corriger. * Ne pourrait-on pas laisser l'ordinateur gérer la libération de mémoire tout seul? **Mise en œuvre** La plupart des langages modernes (Java, Javascript, PHP, Python, Ruby...) intègrent un mécanisme de **ramasse-miettes** (*garbage collector*). .. index:: single: compteur de références; mémoire Compteur de références ---------------------- * Chaque objet possède un **compteur de références** indiquant combien de liens pointent vers lui. * Chaque qu'on crée ou que l'on brise un lien vers un objet, son compteur de références est mis à jour. * Lorsque son compteur de références atteint 0, l'objet est libéré, et ses liens son brisés. Exemple ``````` .. container:: build animation stacked opacify .. graphviz:: _static/garbage_collector.dot .. graphviz:: _static/garbage_collector_anim1.dot .. graphviz:: _static/garbage_collector_anim2.dot .. graphviz:: _static/garbage_collector_anim3.dot .. graphviz:: _static/garbage_collector_anim4.dot .. graphviz:: _static/garbage_collector_anim5.dot .. graphviz:: _static/garbage_collector_anim6.dot Références cycliques -------------------- Le comptage des références n'est pas suffisant. .. graphviz:: _static/garbage_collector_cycle.dot → nécessité de trouver un compromis entre l'économie de mémoire et le temps de clacul.