Allocation Dynamique Flashcards
(50 cards)
Comment est organisé l’espace d’adressage d’un processus ?
Un exécutable = plusieurs sections
- .text = les instructions
- .data = les variables globales
- .heap = le tas
- .stack = la pile d’adresse
Allocation statique
Emplacement et taille fixés début de l’exécution
Les instructions et les variables globales
Allocation dynamique
Faite sur le tas
Pile d’exécution
Zone dédiée à l’allocation “dynamique”, utilisée pour variables locales et adresses de retour
Politique LIFO
Croissance automatique de la pile d’exécution
- Application exécute un PUSH
- MMU cherche à traduire VA -> PA, trouve un PTE invalide et envoie une IRQ au noyau
- Noyau examine la VA demandée, et reconnaît un débordement de pile
- Noyau cherche une PP libre
- Noyau place la page dans VAS = màj la PT du processus
- Rend la main à l’application. PUSH retentée avec succès
Allocation dynamique sur le tas (heap allocation)
Permettre allocations et libérations arbitraires, grâce aux primitives allouer et libérer
Primitive allouer(taille)
Cherche une zone libre et retourne son adresse de début (ou renvoie une erreur si incapable de servir la requête)
Primitive libérer(adresse)
Indique au gestionnaire mémoire qu’une zone n’est plus utilisée et qu’elle peut être recyclé
Gestionnaire de mémoire dynamique (memory allocator)
Répond aux requêtes d’allocation (resp. de désallocation) émises par l’application en réservant (resp. recyclant) des blocs de taille variées à l’intérieur d’une grande zone appelée le tas
Structure de données du gestionnaire de mémoire dynamique
Freelist, ou liste de blocs libres
À quoi correspond une activation de fonction ?
À un morceau de la pile
- variable locales, arguments de fonction, adresse de retour
Quelles sont les instructions CPU dédiées à la pile ?
PUSH, POP, CALL et RET
Problème de fragmentation du tas
Morcellement progressif de l’espace libre en des blocs trop petit pour satisfaire les requêtes d’allocation de l’application
Causes de la fragmentation du temps
Disparité des durées de vie et disparité les tailles allouées
Découpage de blocs libres lors de l’allocation
Réduit la fragmentation interne mais risque de produire des blocs libres trop petits
Fusion de blocs libres lors de la désallocation
Réduit la fragmentation externe mais risque de causer du travail improductif
Fragmentation interne
Espace inutilisé dans les blocs
Stratégies d’allocation
On comparer les différentes scénarios
Fragmentation = espace total occupé par le tas / somme des tailles des blocs alloués
Performance = temps d’exécution de l’algo de choix de bloc
Stratégie First-fit
Examiner le moins de bloc possible
• parcourir la freelist et choisir le premier bloc libre de taille suffisante
Fragmentation externe
Blocs trop petits pour être utile?
Comment choisir le «meilleur» bloc dans la freelist ?
Optimal = choisir le bloc qui causera le moins de fragmentation
mémoire dans le futur ▶ impossible à deviner
En pratique, on va chercher un compromis entre fragmentation et performance
Compromis entre fragmentation et performance
- fragmentation = espace total occupé par le tas / somme des tailles des blocs alloués
- performance = temps d’exécution de l’algo. de choix de bloc
Stratégie Next-fit
Ne pas retraverser toute la freelist à chaque fois
• variante de First-fit : démarrer le parcours à l’endroit du dernier bloc alloué précédemment (on considère la freelist comme une liste circulaire)
Stratégie Best-fit
Préserver les gros blocs libres
• considérer l’intégralité de la freelist et choisir le bloc acceptable le plus petit
