Context Navigation

Changes between Version 41 and Version 42 of AS6-TME-B6

Timestamp:: Mar 29, 2022, 4:41:33 PM (3 years ago)
Author:: franck
Comment:: --

Legend:

: Unmodified
: Added
: Removed
: Modified

AS6-TME-B6

-                      v41
+                      v42
  * Pour lutter contre la fragmentation, on peut aligner des objets alloués sur des segments par trop petit de sorte à toujours avoir des espaces utilisables entre les objets, mais cela crée une fragmentation interne.
  * On peut aussi gérer des ensembles d'objets de même taille.
  * En bref, dans le cas général, la fragmentation est inévitable, mais si on sait à l'avance quelles sont les tailles des objets alloués, alors on peut fortement la réduire.
+ * En bref, dans le cas général, la fragmentation est inévitable, mais si l’on sait à l'avance quelles sont les tailles des objets alloués, alors on peut fortement la réduire.
 '''
 }}}
 …
  * Il ne faut pas seulement parcourir une liste, il faut aussi pouvoir ajouter ou extraire des éléments n'importe où.
  * Pour ajouter un élément devant un autre, il faut accéder à l'élément précédent et donc avoir un double chaînage.
  * Cela permet aussi d'ajouter en fin de liste très facilement, puis que l'élément de fin de liste est celui qui précède la racine (si on construit une liste circulaire).
+ * Cela permet aussi d'ajouter très facilement en fin de liste puisque l'élément de fin de liste est celui qui précède la racine (si l’on construit une liste circulaire).
 '''
 }}}
 …
 {{{#!protected ------------------------------------------------------------------
 '''
  * L'allocateur de piles user sert pour les threads de l'application, il faut une pile par thread pour les contexte d'exécution des fonction.
+ * L'allocateur de piles user sert pour les threads de l'application, il faut une pile par thread pour les contextes d'exécution des fonctions.
  * C'est le noyau qui fait l'allocation des piles lorsqu'il crée les threads et ce sont les threads qui les utilisent.
  * Dans l'état actuel de kO6, la taille des piles n'est pas paramétrable.
 …
  * Un mécanisme possible serait de lever des exceptions ''accès mémoire interdit'' lorsqu'on sortirait d'une pile, mais il n'y en a pas.
  * C'est un problème, parce que déborder une pile, c'est écraser des données. Le plus grave, c'est que la perte de donnée due à l'écrasement peut ne pas être visible avant plusieurs dizaines de millions de cycles et le debug devient particulièrement difficile.
  * Pour traiter ce problème, kO6 écrit au début et à la fin des piles, des nombres magiques qui ne devront jamais être écrasés si les piles est correctement utilisées. Ces sont des sentinelles.
+ * Pour traiter ce problème, kO6 écrit au début et à la fin des piles, des nombres magiques qui ne devront jamais être écrasés si les piles sont correctement utilisées. Ces sont des sentinelles.
  * kO6 peut regarder périodiquement (par exemple à chaque commutation) que la pile n'a débordée, si les sentinelles sont toujours là.
  * Avec ce mécanisme, on ne peut pas détecter précisément quand le problème arrive mais on a une fourchette temporelle d'un tick d'horloge, c'est déjà pas mal.
+ * Avec ce mécanisme, on ne peut pas détecter précisément quand le problème arrive, mais on a une fourchette temporelle d'un tick d'horloge, c'est déjà pas mal.
 '''
 }}}
 …
  * Il y a trois avantages :
 . ça limite la fragmentation externe puisque les trous entre les objets font au moins une ligne, et ils ont donc plus de chance d'être utilisés.
 . ça évite les faux partages. En effet, si on met dans une même ligne de cache des variables non partagées utilisées par plusieurs threads s'exécutant sur des cœurs différents, le mécanisme de cohérence de cache se met en route à chaque modification des variables alors que c'est inutile.
 . Si les structures de données allouées de manière dynamique sont alignées alors lorsqu'on lit le premier champ de la structure on lit aussi les suivants et on bénéficie de la localité spatiale. C'est un gain en performance (certes mineur).
+. ça évite les faux partages. En effet, si l’on met dans une même ligne de cache des variables non partagées utilisées par plusieurs threads s'exécutant sur des cœurs différents, le mécanisme de cohérence de cache se met en route à chaque modification des variables alors que c'est inutile.
+. Si les structures de données allouées de manière dynamique sont alignées alors lorsqu'on lit le premier champ de la structure, on lit aussi les suivants et l’on bénéficie de la localité spatiale. C'est un gain en performance (certes mineur).
 '''
 }}}
 …
 {{{#!protected ------------------------------------------------------------------
 '''
  * L'allocation ''first fit'' signifie que l'allocateur utilise le premier bloc libre assez grand pour l'objet alloué. Ce bloc libre est coupé en deux s'il est trop grand pour produire un nouveau bloc libre, mais plus petit parce que amputé de la partie alloué à l'objet.
+ * L'allocation ''first fit'' signifie que l'allocateur utilise le premier bloc libre assez grand pour l'objet alloué. Ce bloc libre est coupé en deux s'il est trop grand pour produire un nouveau bloc libre, mais plus petit parce qu’amputé de la partie allouée à l'objet.
  * On a aussi l'allocation ''next fit'' qui consiste à ne pas partir du début dans la recherche d'un bloc libre, mais de l'endroit de la dernière affectation, et la l'allocation ''best fit'' qui consiste à trouver un bloc libre de la bonne taille en premier.
  * Il en existe d'autres, leur but est d'augmenter les performances et de réduire la fragmentation.
  * Il n'y a pas de meilleurs solutions, mais si on connaît la nature des besoins en terme d'allocation, on peut imaginer des mécanismes plus efficaces.
+ * Il n'y a pas de meilleures solutions, mais si on connaît la nature des besoins en termes d'allocation, on peut imaginer des mécanismes plus efficaces.
 '''
 }}}
 …
 '''
  * `void * malloc(size_t)` et `void free(void *)`.
  * Non, ces fonctions ne font pas d'appel système à chaque fois. L'allocateur de la libc se fait alloué un segment assez grand par l'appel système `sbrk_heap` et ensuite, il alloue des segments (nommés blocs dans le cours) et les libère à la demande.
  * L'appel système, c'est pour demander un peu plus plus pour `malloc()`, mais `free()` ne demande jamais de réduire l'espace.
+ * Non, ces fonctions ne font pas d'appel système à chaque fois. L'allocateur de la libc se fait allouer un segment assez grand par l'appel système `sbrk_heap` et ensuite, il alloue des segments (nommés blocs dans le cours) et les libère à la demande.
+ * L'appel système, c'est pour demander un peu plus pour `malloc()`, mais `free()` ne demande jamais de réduire l'espace.
 '''
 }}}
 …
 '''
  * Un slab est un segment d'adresses contenant des objets de même taille.
  * Pour kO6, il n'y a qu'une seule taille, une page de 4kO, mais normalement la taille des slabs dépend de la taille des objets. En effet, quand la taille du slab n'est pas un multiple de la taille de l'objet, il y a un fragment inutile créé dans le slab. Ce fragment est d'autant plus grand que les objets sont grands. C'est pourquoi au delà d'1/8 de page (512 octets), on prend des slabs de 2, 4 ou 8 pages (des puissances de 2 pour des raisons que je n'aborderai pas ici).
+ * Pour kO6, il n'y a qu'une seule taille, une page de 4kO, mais normalement la taille des slabs dépend de la taille des objets. En effet, quand la taille du slab n'est pas un multiple de la taille de l'objet, il y a un fragment inutile créé dans le slab. Ce fragment est d'autant plus grand que les objets sont grands. C'est pourquoi au-delà de 1/8 de page (512 octets), on prend des slabs de 2, 4 ou 8 pages (des puissances de 2 pour des raisons que je n'aborderai pas ici).
  * Le principal intérêt de ce mécanisme c'est sa rapidité. En effet, lorsque l'allocateur a créé ses listes d'objets libres, en prendre un est très rapide, de même que le rendre.
  * Le second intérêt est la réduction de la fragmentation externe, limitée aux fragments non utilisés dans les slabs.
 …
 '''
  * En fait, la réponse est donnée dans la réponse précédente. Les slabs contiennent les objets libres et donc les futurs objets alloués. Notez que quand un objet est alloué, il n'est plus dans le slab, il y retourne quand il est libéré.
  * L'allocateur alloue un slab quand on lui demande un objet d'une certaine taille, mais que la liste des objets libres de cette taille est vide. L'allocateur demande alors un slab (ici, une page de 4kO) pour remplir la listes d'objets libres et en extraire finalement un.
  * L'allocateur recherche les slabs entièrement rempli d'objets libres et dans ce cas, il en retire tous les objets et rend le slab.
+ * L'allocateur alloue un slab quand on lui demande un objet d'une certaine taille, mais que la liste des objets libres de cette taille est vide. L'allocateur demande alors un slab (ici, une page de 4kO) pour remplir la liste d'objets libres et en extraire finalement un.
+ * L'allocateur recherche les slabs entièrement remplis d'objets libres et dans ce cas, il en retire tous les objets et rend le slab.
 '''
 }}}
 …
 '''
  * 4kO est une taille standard utilisée pour la gestion de la mémoire des applications, et pour le système de fichiers. On ne le voit pas ici, mais le noyau gère en principe une mémoire physique découpée en pages (nommé parfois cadres). En fait, la mémoire est vue comme un réservoir de pages dans lequel le noyau peut piocher pour y mapper du code, des données, des morceaux de fichiers, etc. La page est un élément atomique.
  * Honnêtement, c'est difficile de dire si c'est vraiment un problème que les slabs fassent au plus une page. Ce que l'on peut dire, c'est qu'en biologie, "le besoin crée l'organe" et bien pour le système d'exploitation, le besoin doit créer la fonction, afin de ne pas créer des codes morts (jamais utilisés) qui sont des nids de bugs. Donc, tant que le besoin est absent, ce n'est pas un problème de pas avoir la fonction :-)
+ * Honnêtement, c'est difficile de dire si c'est vraiment un problème que les slabs fassent au plus une page. Ce que l'on peut dire, c'est qu'en biologie, "le besoin crée l'organe" et bien pour le système d'exploitation, le besoin doit créer la fonction, afin de ne pas créer des codes morts (jamais utilisés) qui sont des nids de bugs. Donc, tant que le besoin est absent, ce n'est pas un problème de ne pas avoir la fonction :-)
 '''
 }}}
 …
 '''
  * `kfree()` demande la taille pour savoir dans quelle liste d'objets libre remettre l'objet.
  * Le `kfree()` de Linux ne le demande pas, mais je ne pense pas que cela soit une contrainte. On est dans le noyau et je ne pense pas que le noyau ait à libérer des objets dont il ignore le type et donc la taille. Par contre cette information donnée à `kfree()` permet de pas avoir besoin de la stocker quelque-part lors de l'allocation (comme c'est fait pour l'allocateur de la libc).
+ * Le `kfree()` de Linux ne le demande pas, mais je ne pense pas que cela soit une contrainte. On est dans le noyau et je ne pense pas que le noyau ait à libérer des objets dont il ignore le type et donc la taille. Par contre cette information donnée à `kfree()` permet de ne pas avoir besoin de la stocker quelque part lors de l'allocation (comme c'est fait pour l'allocateur de la libc).
 '''
 }}}
 …
  * L'intérêt d'avoir deux piles.
    * C'est que l'utilisateur ne peut pas découvrir ce que le noyau a fait en observant la pile.
    * Quand on entre dans le noyau on a toujours une pile vide (pas grande, mais suffisante), on a moins de risque de débordement.
+   * Quand on entre dans le noyau, on a toujours une pile vide (pas grande, mais suffisante), on a moins de risque de débordement.
 '''
 }}}
 …
 Dans le code, on peut voir qu'il existe un tableau `Objects[]` contenant de cases qu'il existe de taille d'objets possibles (mesurée en nombre de lignes) et dont chaque case contient le nombre d'objet libre
 de listes d'objets libres, indexé par les identifiants de slab (l'identifiant de slab est la taille des objets qu'il contient en nombre de lignes). Le tableau `Objects` contient le nombre d'objets alloués. Il faudrait un autre tableau semblable contenant le nombre d'objets libres disponible.
+de listes d'objets libres, indexé par les identifiants de slab (l'identifiant de slab est la taille des objets qu'il contient en nombre de lignes). Le tableau `Objects` contiens le nombre d'objets alloués. Il faudrait un autre tableau semblable contenant le nombre d'objets libres disponible.