| 1 | |
| 2 | = Gestion de la mémoire dynamique |
| 3 | |
| 4 | == Principes == |
| 5 | |
| 6 | L'allocation dynamique de la mémoire est une fonctionnalité fondamentale qui fait partie des systèmes d'exploitation depuis les années 1960. |
| 7 | |
| 8 | La zone mémoire disponible pour faire des allocations dynamiques peut être vue comme un ensemble de blocs mémoire (zone de mémoire contiguë de taille variable). l'allocateur doit répondre à des requêtes de type réservation/libération de certains nombres de ces blocs. |
| 9 | |
| 10 | Afin de répondre à ces requêtes, un allocateur doit connaitre l'état de ces blocs: quels sont les blocs libres et ceux occupés (pas encore libérés). Le but d'un allocateur est de répondre à ces requêtes en minimisant d'une part, l'espace mémoire perdu dû à la fragmentation des blocs et d'autre part, le temps de réponse (minimiser l'overhead de gestion). |
| 11 | |
| 12 | Il existe plusieurs stratégies pour atteindre ces deux buts mais il n'y a pas de stratégie optimale car cela dépend du comportement du demandeur (les tailles demandées, la durée de vie d'une réservation, l'ordre des libérations, etc...). |
| 13 | |
| 14 | La stratégie d'allocation que nous vous proposons d'implémenter est de type First-Fit. Dans cette stratégie, l'allocateur cherche parmi les blocs libres celui qui a une taille supérieure ou égale à la taille demandée. Il arrête sa recherche dès qu'il en trouve un. Si la taille du bloc trouvé est supérieure à la taille demandée (d'une certaine quantité), il soustrait la taille en trop et en fabrique un nouveau bloc libre. Enfin, il marque le bloc trouvé comme occupé et rend son adresse. Vous pouvez dans un second temps implémenter la stratégie Next-Fit. Dans cette stratégie, l'allocateur utilise un pointeur sur le premier bloc libre afin d'accélérer la recherche. |
| 15 | |
| 16 | La figure suivante illustrent un exemple d'une allocation de 128 octets. |
| 17 | |
| 18 | [[Image(exemplealloc.png, nolink, align=center, 280px)]] |
| 19 | |
| 20 | Lors d'une libération d'un bloc, l'allocateur essaie de fusionner (merger) les blocs libres qui suivent ce bloc (et pas ceux qui précèdent). Les figures 2 et 3 illustrent ce fusionnement de blocs en mettant en évidence la condition d'arrêt : plus de blocs libres contigus après le bloc libéré. |
| 21 | |
| 22 | [[Image(exemplefree.png, nolink, align=center, 400px)]] |
| 23 | |
| 24 | Nous avons vu, lors d'une allocation, que l'allocateur peut-être mené à partitionner un bloc libre si sa taille est strictement supérieur à la taille demandée de certaine quantité. Le choix de cette quantité est très important pour la réutilisation des blocs. |
| 25 | |
| 26 | L'allocateur doit définir une taille minimum acceptable au dessous du laquelle le partitionnement ne se fera pas. Autrement dit si la taille restante d'un bloc libre n'est pas significative ce n'est pas la peine de partitionner ce bloc sous peine d'accroitre la fragmentation de la mémoire. |
| 27 | |
| 28 | L'allocateur voit les blocs comme multiple de sous blocs de taille fixe, c'est la taille minimum pour répondre à une allocation mémoire. Par exemple : si la taille d'un bloc minimal (un sous bloc) est de 32 octets alors une allocation de 52 octets se traduit par une réservation d'un bloc de 2 * 32 soit de 64 octets. Une allocation de 4 octets se traduit par réservation d'un bloc de 1 * 32 octets. En fait, dans le but de mieux tirer profit du cache de données de niveau 1, on fixe la taille minimale d'un bloc à taille d'une ligne de cache. dans notre cas la taille minimale sera de 64 octets (16 mots de 4 octets). |
| 29 | |
| 30 | Lors de la libération, l'allocateur reçoit uniquement l'adresse du bloc à libérer mais pas sa taille. l'allocateur doit mettre en place un mécanisme pour retrouver la taille d'un bloc à partir de son adresse. |
| 31 | |
| 32 | L'allocateur associe à chaque bloc un descripteur qui indique l'état du bloc (libre ou occupé) et sa taille. Un bloc est donc composé de deux parties, un descripteur et un champ données. la figure suivante illustre cette association. |
| 33 | |
| 34 | [[Image(exempleblocs.png, nolink, align=center, 250px)]] |
| 35 | |
| 36 | == Définition des structures de données |
| 37 | |
| 38 | Nous allons représenter l'allocateur mémoire et la description de la zone mémoire à gérer par la structure heap_s voici sa définition en C. Le lock permet de séquencialiser les accès concurrents. Pour le test de votre API vous utiliserez un spinlock des PThreads. |
| 39 | |
10 | | 1. Nous allons modifier le programme de boot pour qu'il recopie dans la ram le code des fonctions `__do_init()` et `tty_puts()` |
11 | | avant de d'y sauter pour les exécuter. |
12 | | 2. Nous allons ajouter l'affichage du ''timestamp counter'' de chaque processeur devant le message "hello" en utilisant une |
13 | | fonction tty_putx() qui affiche un nombre en hexadécimale. |
14 | | 3. Nous allons refaire l'étape 1 en faisant faire la copie du code par le module DMA. Vous noterez la différence de vitesse grâce |
15 | | à l'affichage du ''timestamp''. |
16 | | Vous regarderez la documentation de SoCLib pour savoir comment contrôler le DMA. |
| 59 | A l'état initial, la zone mémoire est constituée d'un seul bloc libre. |
22 | | * Nous allons placer le code des fonctions C `__do_init(), tty_puts(), tty_putx, ...` dans une autre section de la mémoire. Ces fonctions seront compilées |
23 | | dans le but d'une exécution dans la section ktext, mais on demandera à l'éditeur de lien de les placer dans la section ktext_lma_base de la ROM. |
24 | | * Nous allons ensuite modifier le code du programme de boot pour que l'un des processeurs se charge du déplacement des programmes depuis la ROM jusque dans la mémoire RAM. |
25 | | Une fois que le programme est recopié, tous les processeurs saute à leur fonction `__do_init()`. |
26 | | |
27 | | == 2. Hello en chiffre == |
| 73 | == Travail demandé |
31 | | * Nous allons écrire une fonction `unsigned getTimeStamp()` permettant de récupérer la valeur de ce registre en y plaçant le code assembleur nécessaire. |
32 | | Cette fonction sera inlinée. |
33 | | * Nous allons enuite écrire une fonction `tty_putx(unsigned int tty, unsigned i)}}} qui écrit sur le terminal tty, la chaine de caractère représentant le valeur du nombre |
34 | | i en hexadécimal. |
35 | | * La fonction `__do_init()` devra écrire le message "Hello at " suivi du nombre de cycle rendu par `getTimeStamp()` |
| 77 | le contexte de l'allocateur est representé par la structure heap_manger_s, les fonctions de l'allocateur peuvent opérer sur plusieurs contextes. Autrement dit, On peut gérer plusieurs zone mémoire avec les mêmes fonctions de l'API heap_manager à condition de disposer d'autant de descripteur heap_manger_s. |
42 | | * Nous allons modifier le programme de boot pour que la boucle de copie soit remplacée par une programmation d'une requête DMA. La terminaison de la requête DMA produit normalement une interruption. |
43 | | Nous n'allons pas pouvoir l'utiliser ici car le gestionnaire d'interruption n'est pas encore en place. nous allons donc tester le registre LEN du DMA afin de savoir si le transfert est terminé. |
44 | | Le bus système transfert en moyenne 2 octets par cycles, il est donc possible d'évaluer approximativement la fin de l'opération. |
45 | | * Vous exécutez les codes `__do_init()` en notant la différence de date. |
46 | | * Pour info l'ordre des registres de commande du DMA est: |
47 | | {{{ |
48 | | enum SoclibDmaRegisters { |
49 | | DMA_SRC, |
50 | | DMA_DST, |
51 | | DMA_LEN, |
52 | | DMA_RESET, |
53 | | DMA_IRQ_DISABLED, |
54 | | }; |
55 | | }}} |
| 84 | int8_t zone [ZONE_SIZE]; |
| 85 | struct heap_s heap; |
| 86 | }}} |
| 87 | |
| 88 | Vous devez donc écrire les trois fonctions de l'API dans le fichier heap_manager.c et leur prototype dans le fichier heap_manager.h. En cas d'échec du malloc, vous devrez faire un parcours de la zone mémoire et fusionner les zones libres contiguës. |
| 89 | |
| 90 | **Vous écrirez un programme de test dans le fichier main.c mettant en évidence les cas de fonctionnement.** |
| 91 | |
| 92 | Afin de mettre au point votre allocateur, il est utile d'écrire une fonction qui affiche l'état des blocs de l'allocateur, par exemple |
| 93 | |
| 94 | {{{ |
| 95 | void heap_print(struct heap_s *mgr); |
| 96 | }}} |