14 mar. 2011

De la gestion de la mémoire

Et bien, il était temps ! Après plus d'un mois sans nouvelle, ce blog commençait à se dessécher, et sa peau parcheminée commençait même à craquer. A ma décharge, je dois dire que je prépare un volumineux, très volumineux scénario pour Dungeons & Dragons 4 qui devrait paraître dans un numéro ultérieur du webzine Petit Dragon, et que cette activité est tout aussi chronophage que mes activités sur ce blog (ce qui pose un problème puisque les journées n'ont que 24h). Mais je vais tenter de publier un autre article d'ici la fin du mois (et si j'en ai le temps, je tenterais d'être plus régulier à l'avenir).

Maintenant que tout est en ordre, attaquons le sujet du jour, et parlons justement de ces gestionnaires de mémoire. Je ne vais pas ici vous livrer le code d'un gestionnaire de mémoire ; inutile de me poser des questions sur les algorithmes à utiliser ; tout ceci est un problème d'implémentation, alors que pour une fois (étrange, me direz vous) c'est le coté fonctionnel et la vision architecturale qui m'intéresse. Incroyable, non ?

Un gestionnaire de mémoire, c'est quoi ?

D'abord, c'est un très mauvais nom, qui me rappelle tout à coup que j'avais déjà prévu depuis longtemps d'écrire un billet sur la notion même de gestionnaire. Mais laissons pour l'instant de coté ce débat, et concentrons nous sur les fonctionnalités généralement offerte par un tel sous-système.

En premier lieu, un gestionnaire de mémoire a pour but de nous donner accès à la mémoire de notre système. Cette fonctionnalité suppose l'existence de deux opérations distinctes :

  • Une opération permettant au programme client d'obtenir un bloc contigu en mémoire[1]. Cette opération est communément appelée allocation ou réservation de mémoire. La bloc de mémoire obtenu via cette opération est dit alloué.
  • Une opération permettant au programme client de signifier qu'il n'a plus besoin d'un bloc de mémoire particulier - c'est la libération, ou la désallocation. Un bloc de mémoire auquel on applique cette opération est dit libre.

Un système qui propose ses deux fonctionnalités seules est un système très simple du point de vue de la gestion de la mémoire ; la plupart du temps, ce type de système est utilisé à bas niveau, ou via des librairies dans les langages dit "système" (dont le C est un exemple reconnu ; mais on peut aussi considérer le langage Pascal et beaucoup d'autres langages aux fonctionnalités similaires).

Où un problème et sa solution se précisent

Des langages (ou des librairies) plus évolués peuvent fournir au programmeur d'autres outils, dont un des plus important est le collecteur de mémoire. Son premier rôle (qui n'est pas, contrairement à ce que semble penser la majorité de mes codisciplinaires, le plus important) de collecter les blocs de mémoire inutilisés pour les libérer à la place du développeur. Pour cela, un collecteur compte le nombre de fois où ce bloc de mémoire est référencé ; à chaque opération concernant ce bloc mémoire, le compteur est incrémenté ou décrémenté - lorsqu'il atteint 0, le bloc est inaccessible, et peut donc être réclamé.

Un collecteur de mémoire qui ne ferait que ces opérations offre peu d'intérêt, car il ne résout pas un des problèmes important lié à la gestion de la mémoire : la fragmentation de celle-ci. Il y a fragmentation de la mémoire dès lors qu'entre deux blocs de mémoire alloués se trouve un bloc de mémoire libre.

Ce problème de la fragmentation est important, car il limite les allocations successive. Supposons que j'ai 1 Mo de mémoire vive ; j'alloue 3 blocs : 256 Ko, puis 512 Ko, puis 256 Ko. Puis je libère mon premier et mon dernier bloc ; à ce stade, je suis censé avoir 512 Ko de mémoire libre, et je suis donc censé pouvoir allouer cette mémoire à nouveau. Pourtant, une allocation de 384 Ko a toute les chances d'échouer, car les deux blocs ne sont pas contigus en mémoire.

Le second rôle du collecteur de mémoire est de permettre que ces deux blocs de 256 Ko non contigus soient regroupés en un seul bloc de 512 Ko. Pour ce faire, il effectue une défragmentation. Mais cette opération de défragmentation n'est pas aussi simple qu'il y parait. Et pour mettre cette difficulté en évidence, prenons un autre exemple simple, celui d'une liste chaînée.

J'ai 4 noeuds de cette liste en mémoire, le premier référençant le second, le second référençant le troisième, etc, et le quatrième marquant la fin de la liste en de référençant aucun des autres noeuds. Ces quatre noeuds sont consécutifs en mémoire. Maintenant, je supprime le premier et le troisième noeud ; le nouveau premier noeud référence maintenant l'ancien quatrième et dernier, et ces deux noeuds sont chacun précédés d'un bloc de mémoire libre. Mettons en route le collecteur de mémoire, qui va voir ces deux blocs libres et donc défragmenter la mémoire. Le second bloc va être déplacé à la place du premier, et le quatrième bloc va être déplacé à la position du second. Quid de la référence existante entre les deux noeuds de la chaine ?

Deux cas se posent :

  • la référence prends la forme d'une référence directe, c'est à dire un pointeur sur l'adresse en mémoire du bloc référencé. Au moment du déplacement du second noeud, le collecteur doit trouver toutes les références externes à ce noeud et les modifier. Le problème est le suivant : comment identifier ces références ? Après tout, un pointeur n'est jamais qu'une valeur comme une autre lorsqu'il est stocké en mémoire, et il est indistinguable des autres données stockées - et ce, quelle que soit la forme que prend la valeur du pointeur. Certains chercheurs ont développé des heuristiques qui, selon le système d'exploitation considéré, peuvent permettre de détecter de manière plus ou moins efficace ces pointeurs afin de les modifier en cas de déplacement de la mémoire (le système le plus connu ayant été développé par H. Boem pour son collecteur de mémoire C/C\++ - qui ne propose pas la fonction de défragmentation ; un autre système, développé par J. Bartlet, utilise un mécanisme de classification des pointeurs et différencie les pointeurs sûrs et modifiable par le collecteur des pointeurs moins sûrs, non modifiables, et qui à priori références des blocs de mémoire qui n'ont donc pas le droit d'être déplacés. Cf. cette courte explication).
  • la référence est indirecte ; une indirection supplémentaire est créée, et lorsqu'un bloc de mémoire est déplacé, c'est le contenu de cette référence qui est modifié. En pratique, cela nécessite que le programme utilisateur connaisse ce fait, car il ne manipule pas des référence sur des blocs de mémoire, mais des références sur des références sur ces blocs. Il doit donc dépiler un niveau d'indirection afin de pouvoir accéder aux données qu'il souhaite traiter. Cette architecture a un avantage certain : il n'y a pas besoin de chercher ce qui représente un pointeur, car il n'y a pas de pointeurs. Seule une table d'indirection (implicite ou explicite) doit être modifiée lorsque les blocs sont déplacés en mémoire (cette table peut aussi contenir d'autres informations, comme le nombre de références sur le bloc considéré).

Où la solution est oubliée de tous

Bon, j'exagère, pas tous.

Les langages haut niveau tels que le C# ou Java ont opté pour une solution proche de la seconde, et cette solution étant intégrée au langage même, la gestion complète de la mémoire en est simplifiée et elle en devient transparente pour l'utilisateur. Mais dans les langages plus bas niveau tel que le C, une telle approche est plus délicate. En effet, les librairies sont rarement conçues pour oeuvrer de conserve avec un tel collecteur de mémoire : bien trop souvent, elles considèrent qu'une allocation mémoire leur renvoie un pointeur directement utilisable. Hors, un niveau d'indirection ajouté par le collecteur signifie naturellement qu'un tel pointeur doit être transformé de manière à pouvoir être utilisé.

Il existe des librairies C dans lesquelles ont peut greffer un allocateur - généralement, cette greffe prends la forme d'une structure composée de deux ou trois pointeurs sur fonction - une pour la fonction d'allocation, un autre pour la fonction de libération de la mémoire, et (optionnellement) un troisième pointeur pour la fonction de réallocation (afin d'augmenter la taille d'un bloc de mémoire donné). Une telle greffe est intrinsèquement limitée si elle n'offre pas la possibilité de traiter l'indirection supplémentaire bien souvent imposée par l'implémentation d'un collecteur de mémoire. La conclusion s'impose d'elle même : dès lors que vous permettez à un utilisateur de librairie de greffer son propre allocateur, il vous faut aussi penser au fait qu'il pourrait souhaiter ajouter le niveau de redirection lui permettant de traiter aisément la défragmentation de la mémoire, sans quoi cette ouverture n'est que partiellement utile.

Je prêche donc pour qu'on se souviennent enfin que toutes les utilisation de la mémoire ne sont pas aussi limitées que le simple couple allocation/libération. Certains contextes très particuliers peuvent nécessiter d'autres fonctionnalités (un exemple parmi d'autres : allocation dans un bloc de mémoire délimité, utilisé par plusieurs processus via une zone de mémoire partagée ; dans ce cas, la fragmentation de la mémoire peut rapidement devenir très handicapante, et un système de défragmentation devient nécessaire. Mais ce n'est pas le seul exemple : on peut aussi prendre le cas relativement courant d'un système embarqué sans MMU avec un accès directe à la mémoire physique ; encore une fois les problèmes de fragmentation doivent être obligatoirement réglés au mieux).

En attendant, il ne vous reste plus qu'à faire les choses correctement !

Notes

[1] en mémoire virtuelle ; la plupart des processeurs permettent de s'affranchir des contraintes de contiguïté physique en utilisant une MMU, où Memory Management Unit, qui rajoute un niveau d'indirection entre la mémoire physique et la mémoire telle qu'elle apparaît au programme l'utilisant. Dans certains cas, le processeur utilisé est si simple qu'il ne propose pas de MMU - cette configuration est très rare de nos jours, où les systèmes ayant besoin d'intelligence ont tendance à se baser sur des processeurs ARM, Mips ou Atom, mais elle existe néanmoins

Commentaires

1. Le mercredi, mai 18 2011, 19:25 par olizit

Gestion des exceptions dans un constructeur.
Je suis face à un dilemme pour gérer d'une manière la plus systématique possible les exceptions dans un constructeur.
Je pars du principe que le destructeur d'un objet est appelé seulement si un objet est construit intégralement.

class CObject
{
  private:
    int* m_i;
  public:
    CObject()
    {
      m_i = new int(0);
      throw Exception;
    }
    ~CObject()
    {
      delete m_i;
    }
};

Ce petit example de code provoque une fuite mémoire. En effet l'objet CObject n'est pas totalement initialisé et son destructeur ne sera donc pas appelé.
Je vois deux manière de gérer cette exception.

CObject()
{
  try
  {
    m_i = new int(0);
    throw Exception;
  }
  catch(...)
  {
    delete m_i;
  }
}

Je trouve cette solution pas très élégante sans compter qu'il faut modifier le destructeur et le constructeur dès qu'un membre alloué dynamiquement est ajouté.

class CObject
{
  private:
    auto_ptr<int> m_i;
  public:
  CObject() : m_i(new int(0))
  {
    throw Exception;
  }
  ~CObject()
  {
  }
};

Le destructeur de l'objet m_i sera bien appelé car l'objet m_i a été complètement construit. Il n'y aura donc pas de fuite mémoire.

Que pensez-vous de ces deux approches ?

2. Le mercredi, mai 25 2011, 14:51 par Emmanuel Deloget

La seconde est préférable : RAII doit être utilisé le plus possible dès lors qu'on essaie d'écrire un code résistant aux exceptions, car RAII simplifie énormément l'écriture de ce type de code. On préférera donc utiliser des outils logiciels dont la destruction va libérer les ressources allouées (auto_ptr<>, vector<>, etc).

Fait attention sur ton deuxième exemple : sur un int, tu n'auras pas de problème, mais si tu fait un auto_ptr<class_type> et que class_type n'est pas un type complet lorsque le destructeur automatique de l'auto_ptr<> est appelé, tu va aussi avoir une fuite de ressource. cf. cet autre article

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet