Changes between Version 16 and Version 17 of AS6-TME-B6

Timestamp:

Mar 28, 2022, 8:57:23 AM (2 years ago)

Author:

franck

Comment:

--

AS6-TME-B6

@@ -8 +8 @@
 Vous pouvez lire les [htdocs:cours/Archi-2-B6-alloc-2p.pdf slides de cours] pour voir les détails, mais voici le résumé des principes en quelques lignes.
 
-- kO6 propose une API nommée `list` permettant de gérer les listes chaînées 
+- **kO6 propose une API nommée `list` permettant de gérer les listes chaînées** 
   - Cette API est définie dans le fichier `common/list.h` et elle est utilisable par le noyau et par l'application.
   - L'API `list` permet de chaîner des éléments de liste de type `list_t`, laquelle est une structure composée d'un double pointeur pointant vers d'autres structures `list_t`.
@@ -17 +17 @@
   - L'API `list` permets le parcours de tous les éléments d'une liste.
 
-- Le code user de l'application (on dira juste application dans la suite) et le noyau ont besoin d'allouer dynamiquement de la mémoire. 
+- **L'application et le noyau ont besoin d'allouer dynamiquement de la mémoire**. 
   - L'application et le noyau disposent chacun d'un segment d'adresse propre, nommé respectivement `.data` et `.kdata`, pour leurs données. 
   - Ces segments ont été partiellement remplis par les variables globales du programme au moment de leur chargement en mémoire.
@@ -28 +28 @@
     - D'un autre côté, les piles des threads sont certes dans l'espace utilisateur, mais elles sont allouées par le noyau au moment de la création des threads. Leur taille est standard et fixe (dans un vrai système, on peut choisir leur taille à la création du thread, mais pas pour kO6).
 
-- Nous avons donc 3 allocateurs dans kO6 :
+- **Nous avons donc 3 allocateurs dans kO6** :
   - un allocateur de variables dynamiques pour l'application ;
   - un allocateur de piles utilisateurs pour les threads de l'application mais utilisé par le noyau ;
   - un allocateur de variables dynamiques pour le noyau.
-  - L'allocateur de piles utilisateur et l'allocateur de variables doivent partager la zone libre laissée dans la section `.data`. Ainsi l'allocateur de piles utilise la partie haute de la section `.data` et l'allocateur de variables utilise la partie basse. 
-
-- L'allocateur de piles pour les threads
+  - L'allocateur de piles utilisateur et l'allocateur de variables doivent partager la zone libre laissée dans le segment `.data`. Ainsi l'allocateur de piles utilise la partie haute du segment `.data` et l'allocateur de variables utilise la partie basse. 
+
+- **L'allocateur de piles pour les threads.**
   - C'est l'allocateur le plus simple. Il alloue les piles en réservant un segment de taille fixe (`USTACK_SIZE` défini dans `common/usermem.h`) à partir du haut du segment `.data`, tant que cela n'entre pas en collision avec l'allocateur de variables dynamiques qui utilise le bas de ce même segment.
   - Lors de la libération, la pile est mise dans une liste chaînée triée par adresses décroissantes en utilisant l'API `list`.
   - Lors de l'allocation, la liste de piles libres est consultée en premier, avant de créer une nouvelle pile.
-  - Le tri des piles libres permet d'augmenter la probabilité d'usage des piles placées en haut du segment `.data`.
   - Quand une pile est libérée et qu'elle est celle placée à l'adresse la plus basse, alors la place qu'elle occupait est rendue au noyau. 
-
-- L'allocateur de variables dynamiques pour l'application
-  - Cet allocateur dispose d'un segment d'adresse nommé `heap` placé en bas de la section `.data`, juste après les variables globales, alignées sur les lignes de caches.
-  - l'adresse limite du `heap` est nommée `heap_end`
+  - Le tri des piles libres permet d'augmenter la probabilité d'usage des piles placées en haut du segment `.data` et donc la libération des piles placées plus bas.
+
+- **L'allocateur de variables dynamiques pour l'application.**
+  - Cet allocateur gère un segment d'adresses nommé `heap` placé en bas du segment `.data`, situé juste après les variables globales et aligné sur les lignes de caches.
+  - l'adresse limite du `heap` est nommée `heap_end`, c'est un pointeur.
   - L'allocateur gère des blocs (il fallait bien donner un nom...)
     - Un bloc est un segment d'adresse aligné sur les lignes de caches.
-    - Un bloc est défini par une taille (en nombre de lignes de cache) et un état vide ou plein
-  - Au début, le heap n'a pas de place, alors il demande de la place au kernel avec l'appel système `sbrk_heap` qui lui octroie de l'espace en déplaçant `heap_end` vers le haut (tant que cela n'entre pas en collision avec les piles de threads qui utilisent le haut de la section `.data`. 
+    - Un bloc est défini par : (1) une taille (en nombre de lignes de cache) et (2) un état vide ou plein
+  - Au début, le `heap` est vide (il ne contient pas de bloc), alors il demande de la place au kernel avec l'appel système `sbrk_heap` qui lui octroie de l'espace en déplaçant le pointeur `heap_end` vers le haut (tant que cela n'entre pas en collision avec les piles de threads qui utilisent le haut du segment `.data`. 
   - Cette demande de place a pour effet de créer un bloc vide.
-  - L'API de cet allocateur est `void * malloc(size)` et `void free(void *)`
-  - `void * malloc(size)`
+  - L'API de cet allocateur est `void * malloc(size_t)` et `void free(void *)`
+  - `void * malloc(size)` (politique de remplissage first fit)
     - La fonction parcourt l'ensemble des blocs en commençant par le tout premier à la recherche d'un bloc vide assez grand pour contenir `size`. 
     - Si la place restante est plus petite qu'une ligne de cache, alors l'ensemble du bloc est marqué comme `plein`.
-    - Sinon, le bloc est scindé en deux blocs, le premier `plein` et le second `vide`.
-    - Si l'allocateur ne trouve pas de bloc assez grand, alors il parcourt l'ensemble des blocs et si deux blocs voisins sont libres, il les réunit, puis il retente l'allocation. S'il échoue encore, il sort avec NULL.
+    - Sinon, le bloc est scindé en deux blocs, le premier à l'état `plein` et le second à l'état `vide`.
+    - Si l'allocateur ne trouve pas de bloc assez grand, alors il parcourt l'ensemble des blocs et si deux blocs voisins sont libres, il les réunit, puis il retente l'allocation. S'il échoue encore et il sort avec NULL.
     - Quand l'allocateur a trouvé un bloc, il rend un pointeur dessus.
   - `void free(void *)` 
     - La fonction vérifie que l'adresse en argument a bien été allouée par `malloc()`.
-    - Elle marque le bloc pointé comme `vide`.
-
-- L'allocateur de variables dynamiques pour le noyau
+    - Elle marque le bloc pointé comme `vide`, c'est-à-dire non alloué.
+
+- **L'allocateur de variables dynamiques pour le noyau.**
   - Le noyau alloue des structures ou des tables pour rendre ses services, pour les threads, les devices drivers, les ressources de synchronisation, le système de fichiers, etc. 
-  - Nous appelons ces structures et ces tables des objets (pour leur donner un nom différent de bloc), les objets ont un nombre entier de lignes de cache.
-  - Le noyau doit pouvoir allouer et libérer ses objets très rapidement.
-  - L'allocateur d'objets gère des listes d'objets libres de même taille.
-  - Pour allouer un objet, l'allocateur se contente de prendre le premier objet libre dans la liste des objets libres de la bonne taille.
-  - Pour libérer un objet, l'allocateur se contente de remettre l'objet au début de la liste des objets libres de la bonne taille.
-  - Au départ, toutes les listes sont vides. Lorsqu'une demande d'allocation est faite pour une certaine taille, l'allocateur va allouer une dalle (slab en anglais) de 4kO, il découpe la dalle avec autant d'objets de la taille demandée que possible et il chaine ces objets pour former une liste d'objets libres. Il alloue alors le premier objet.
-  - Lors de la libération d'un objet, il peut s'avérer que tous les objets d'une dalle X sont libres. Dans ce cas, l'allocateur retire de la liste d'objets libres tous les objets appartenant à la dalle X et il rend cette dalle à la liste des dalles libres.
+  - Nous appelons ces structures et ces tables des objets (pour leur donner un nom différent de bloc), les objets ont un nombre entier de lignes de cache. Le noyau doit pouvoir allouer et libérer ses objets très rapidement.
+  - L'API de cet allocateur est `void * kmalloc(size_t)` et `void free(void *, size_t)`
+  - `void * kmalloc(size)` (politique de remplissable `slab`)
+    - L'allocateur d'objets du noyau gère des listes d'objets libres de même taille.
+    - Au départ, toutes les listes d'objets libres sont vides.
+    - Lorsqu'une demande d'allocation est faite pour une certaine taille `T` et que la liste des objets libres de cette taille `T` est vide alors l'allocateur alloue une dalle (ou `slab` en anglais) de 4kO.
+    - Il découpe la dalle en autant d'objets que possible de la taille `T` demandée et il chaine ces objets pour remplir la liste d'objets libres.
+    - Pour allouer un objet, l'allocateur prend le premier objet de la liste des objets libres de la bonne taille.
+  - `void kfree(void *, size_t)` 
+    - Pour libérer un objet, l'allocateur se contente de le remettre au début de la liste des objets libres de la bonne taille donnée en argument.
+    - Lors de la libération d'un objet, il peut s'avérer que tous les objets d'une dalle X sont libres. Dans ce cas, l'allocateur retire de la liste d'objets libres tous les objets appartenant à la dalle X et il rend cette dalle à la liste des dalles libres.
+  - Les listes d'objets libres se remplissent ou se vident dynamiquement. 
+