Allocation Dynamique Flashcards
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
Stratégie Worst-fit
Éviter la prolifération de blocs minuscules
• considérer l’intégralité de la freelist et choisir le bloc acceptable le plus grand
Hypothèse suivie quand on cherche dans la freelist
Si le bloc choisi est trop grand, on le découpe
Meilleure stratégie ?
Il n’y en a pas ! Tout dépend du scénario et chacune possède ses désavantages
Format d’un bloc libre
Header + espace libre
Dans le header : on indique taille du bloc entier + 3 derniers bits à 000 (alignement : toujours un multiple de 8)
Format d’un bloc alloué
Header + espace utile + padding (espace perdu)
Les 3 derniers bits à 001
Pointeur p qui pointe vers début espace libre visible par l’application
Pourquoi a t-on du padding ?
C’est causé par l’arrondi à des multiples de 8
Boundary tags (footer)
Copie complète du header placée à la fin de chaque bloc, il permet de traverser la liste des blocs libres et occupés dans les deux sens (on peut localiser le bloc précédent facilement)
Chaînage explicite de la freelist
On rajoute des pointeurs de chaînage pour permettre à l’allocateur de parcourir la freelist dans l’ordre qui l’arrange
Si on n’a aucun bloc libre assez grand
Il faut agrandir le tas : appel système mmap() pour demander des pages au noyau
Comment accélérer la recherche dans la freelist grâce au chaînage explicite ?
Lors du chaînage explicite de la freelist
1) Chaîner uniquement les blocs libres
2) Garder trier la freelist dans le bon ordre
Ordre de tri de la freelist
Par adresses croissantes, par tailles croissantes ou par tailles décroissantes
Tri par adresses croissantes
Fusion facile mais allocation coûteuse
Tri par tailles croissantes
Best-fit efficace mais fusion coûteuse
Tri par tailles décroissantes
Worst-fit facile mais fusion coûteuse
Allocateur avec segregated freelist
Dans la vraie vie
= plusieurs sous listes chaînées pour les différentes tailles > approximation de best-fit sans avoir à traverser tous les blocs
Allocation et désallocation avec segregated freelist
Allocation : si pas trouvé > découper un bloc plus grand (listé triée vs non triée)
Désallocation : fusion optionnelle > recyclage des petits blocs
Pour lancer un programme…
Créer un PCB et une PT
Charger l’exécutable en mémoire
PCB.PC = adresse de main
PCB.state = ready
Ajouter le PCB à la ready queue
Que contient le registre Stack Pointer SP du CPU ?
L’adresse du sommet de pile
La pile appartient-elle à l’exécutable ?
Non, elle est allouée au fur et à mesure de l’exécution + à la demande par le noyau
Règles de gestion du tas
• interdit de «découper» les requêtes d’allocation
=> «allocation contiguë» ▶ taille allouée ⩾ taille demandée
•interdit de réordonner la séquence des requêtes (dépend du flot d’exécution de l’application)
•interdit de bouger les zones déjà allouées (chaque choix de bloc est définitif)
Inconvénient de First-fit
Beaucoup de fragmentation en début de liste
Inconvénient de Next-fit
Beaucoup de fragmentation partout
Inconvénient de Best-fit
Comment examiner efficacement tous les blocs ?
Inconvénient de Worst-fit
Comment examiner efficacement tous les blocs + énormément de fragmentation
Si aucun bloc libre assez grand
Il faut agrandir le tas : appel système mmap() pour demander des pages au noyau
Inconvénient de procéder avec ces règles
• Trop grand nombre de blocs libres ▶ allocation lente
• Blocs libres trop petits ▶ espace inutilisable
