Corrigé Mines-Ponts 2025 Informatique I MPI — Partie 2 (Q12 à Q18) : Ramasse-miettes par marquage et balayage

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique I MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Les arbres immuables partagent des sous-arbres : on ne sait plus quand libérer un nœud. Un nœud devient inutile dès qu'il n'est plus atteignable, en suivant des pointeurs, depuis les variables globales. La structure reçoit un champ marque, initialement faux :


struct abrNoeud_s {
  char* clef;
  int valeur;

  struct abrNoeud_s* fils_gauche;
  struct abrNoeud_s* fils_droit;

  // partie propre au ramasse-miettes
  bool marque;
};
typedef struct abrNoeud_s abrNoeud;

Le ramasse-miettes procède en deux temps : (1) marquer tous les nœuds atteignables (par clôture transitive) depuis les variables globales ; (2) libérer les nœuds alloués non marqués et effacer la marque des autres. La figure 1 du sujet :

La liste des nœuds alloués et la structure globale :


struct rmListeMemoire_s {
  abrNoeud* element;
  struct rmListeMemoire_s* suivant;
};
typedef struct rmListeMemoire_s rmListeMemoire;

#define MAX_NB_ARBRES 16
struct RM_s {
  abrNoeud* arbres[MAX_NB_ARBRES]; /* arbres accessibles */
  int nb_elements;      /* nombre total de noeuds alloués */
  rmListeMemoire* premierElement;
};
typedef struct RM_s RM;

RM* rm; /* variable globale pour l'ensemble du programme */

Un nœud alloué est ajouté à la liste premierElement ; un nœud libéré en est retiré. Le ramasse-miettes et la fonction de libération fournis :


void rm_ramasse_miettes(RM* rm) {
  assert(rm != NULL);
  int nb_noeuds = rm->nb_elements;
  for (int i = 0; i < MAX_NB_ARBRES; i++) {
    if (rm->arbres[i] != NULL) {
      rm_marquer_elements_accessibles(rm->arbres[i]);
    }
  }
  rm_recuperer_elements_inaccessibles(rm);
  printf("noeuds collectes : %d, ", nb_noeuds - rm->nb_elements);
  printf("noeuds encore accessibles : %d\n", rm->nb_elements);
}

void rm_recuperer_elements_inaccessibles(RM* rm) {
  assert(rm != NULL);
  rmListeMemoire* objet = rm->premierElement;
  rmListeMemoire* objets_conserves = NULL;

  while (objet != NULL) {
    if (!objet->element->marque) {
      /* Ce noeud n'a pas été marqué,
         on le retire de la liste et on le libère */
      rmListeMemoire* a_detruire = objet;
      objet = a_detruire->suivant;
      // PARTIE A
      // ici il faut libérer la mémoire
      // FIN PARTIE A
      rm->nb_elements--;
    } else {
      // PARTIE B
      /* Ce noeud a été marqué,
         on enlève la marque et on passe au noeud suivant */
      objet->element->marque = false;
      rmListeMemoire* a_garder = objet;
      objet = a_garder->suivant;
      // FIN PARTIE B
    }
  }
  rm->premierElement = objets_conserves;
}

Q12. Seuls $a_{0}$ et $b_{1}$ sont référencés par des variables globales : nœuds marqués, nœuds libérés ; complexités (sans preuve) du marquage et de la libération.
Q13. Écrire rmListeMemoire* rm_inserer_tete(abrNoeud* element, rmListeMemoire* liste), en temps constant.
Q14. Écrire RM* rm_creer_rm(void), qui alloue et initialise la structure (appelée au début de main).
Q15. Écrire void rm_marquer_elements_accessibles(abrNoeud* element).
Q16. Compléter la partie A (libération de la mémoire).
Q17. Spécificité des nœuds de la liste premierElement en fin d'exécution.
Q18. Pourquoi la partie B est-elle incorrecte ? La corriger.

Corrigé

Q12. Le marquage part de $a_{0}$ et de $b_{1}$ et suit les pointeurs vers les fils :

nœuds marqués : $a_{0}, a_{1}, a_{2}, a_{3}$ (tout l'arbre de $a_{0}$ ) et $b_{1}, b_{2}, b_{3}$ (le sous-arbre de $b_{1}$ ), soit $7$ nœuds ;
nœuds libérés : $b_{0}$ , $b_{4}$ , $c_{0}$ et $c_{2}$ , soit $4$ nœuds. Le père $b_{0}$ de $b_{1}$ n'est pas atteignable : les pointeurs vont du père vers les fils, jamais en sens inverse.

Complexités, avec $A$ le nombre de nœuds atteignables et $M$ le nombre de nœuds alloués : le marquage traite chaque nœud atteignable une fois, en $O (A)$ (plus le parcours des $16$ racines) ; la libération parcourt toute la liste des nœuds alloués, en $O (M)$ . Ce ne sont pas les mêmes $n$ : $A ⩽ M$ , et l'écart est le nombre de nœuds collectés.

Exécuté (avec les fonctions des questions suivantes, Figure 1 reconstruite et $a_{0}$ , $b_{1}$ placés dans rm->arbres) : le programme affiche noeuds collectes : 4, noeuds encore accessibles : 7.

Q13. Ajout en tête d'une liste chaînée : une cellule neuve dont le suivant est l'ancienne tête.


rmListeMemoire* rm_inserer_tete(abrNoeud* element,
                                rmListeMemoire* liste) {
  rmListeMemoire* cellule = malloc(sizeof(rmListeMemoire));
  assert(cellule != NULL);
  cellule->element = element;
  cellule->suivant = liste;
  return cellule;
}

Un malloc et deux affectations : temps constant, quelle que soit la longueur de la liste, qui n'est ni parcourue ni modifiée (la cellule renvoyée est la nouvelle tête ; l'appelant écrit rm->premierElement = rm_inserer_tete(n, rm->premierElement);). Ajouter en queue imposerait un parcours, en temps linéaire.

Q14. La structure est allouée dans le tas (elle doit survivre à l'appel), puis tous ses champs sont initialisés, y compris les $16$ cases du tableau :


RM* rm_creer_rm(void) {
  RM* nouveau = malloc(sizeof(RM));
  assert(nouveau != NULL);
  for (int i = 0; i < MAX_NB_ARBRES; i = i + 1) {
    nouveau->arbres[i] = NULL;
  }
  nouveau->nb_elements = 0;
  nouveau->premierElement = NULL;
  return nouveau;
}

Le contenu d'un bloc rendu par malloc est indéterminé : sans la boucle, rm_ramasse_miettes testerait rm->arbres[i] != NULL sur des valeurs quelconques et marquerait à partir d'adresses invalides. La variable locale ne s'appelle pas rm, pour ne pas masquer la globale.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →