Université BORDEAUX 1 U.F.R. Mathématiques et Informatique
Epreuve de J.Bétréma 25 mai 2000


Maîtrise d'Informatique
Architecture Unix-NT

Durée: 3 heures
Tous documents interdits.

Avertissement : le sujet est probablement long, pour que personne ne s'ennuie. Il n'est pas recommandé de chercher à tout traiter : des réponses superficielles rapportent peu de points.

1. Répertoires Unix

La lecture de répertoires, sous Unix, s'effectue à l'aide des fonctions standard opendir(), readdir() et closedir(). La première retourne un pointeur sur la structure suivante (en principe opaque) :
typedef struct{
  int dd_fd;      /* file descriptor */
  int dd_loc;     /* offset in block */
  int dd_size;    /* amount of valid data */
  char *dd_buf;   /* directory block */
} DIR;            /* stream data from opendir() */
readdir() retourne un pointeur sur une structure dirent :
struct dirent {
  ino_t d_ino;
  off_t d_off;
  unsigned short d_reclen;
  char d_name[1];
};
Voici le squelette d'une fonction de lecture d'un répertoire :
void catalogue (char *chemin) {
  DIR *rep;
  struct dirent *ligne;

  rep = opendir (chemin);
  while ( (ligne = readdir (rep) ) != NULL )
    afficher (rep, ligne);
  closedir (rep);
}
La fonction d'affichage (pour cet exercice) est la suivante :
static void afficher (DIR *rep, struct dirent *entree){
  printf ("%u: d_off %d, d_reclen %d, ",
      entree, entree->d_off, entree->d_reclen);
  printf ("inode %6u, %s\n", entree->d_ino, entree->d_name);
  printf ("%u: dd_loc %d, dd_size %d, dd_buf %u\n",
    rep, rep->dd_loc, rep->dd_size, rep->dd_buf);
}
et voici un exemple d'exécution :
136432: d_off 12, d_reclen 12, inode 200129, .
136416: dd_loc 0, dd_size 488, dd_buf 136432
136444: d_off 24, d_reclen 16, inode  83072, ..
136416: dd_loc 12, dd_size 488, dd_buf 136432
136460: d_off 44, d_reclen 20, inode 200132, chemin
136416: dd_loc 28, dd_size 488, dd_buf 136432
136480: d_off 64, d_reclen 20, inode 200134, Makefile
136416: dd_loc 48, dd_size 488, dd_buf 136432
136500: d_off 88, d_reclen 24, inode 200135, catalogue.c
136416: dd_loc 68, dd_size 488, dd_buf 136432
[etc.]
136876: d_off 428, d_reclen 20, inode 200379, dir.c%
136416: dd_loc 444, dd_size 488, dd_buf 136432
136896: d_off 512, d_reclen 24, inode 200380, dir.session
136416: dd_loc 464, dd_size 488, dd_buf 136432
  1. ino_t (inode type) et off_t (offset type) désignent en fait le type int. Pourquoi cette complication apparente ?
  2. En analysant l'exemple d'exécution, expliquer le rôle exact du champ d_reclen, et la façon dont il est calculé.
  3. En déduire comment est calculé le champ dd_loc.
  4. La première exécution de readdir() utilise l'appel-système getdents() (get directory entries) qui tente de charger en une fois toutes les entrées du répertoire.
    1. Où cet appel-système trouve-t-il l'adresse de chargement ?
    2. Comment se déroulent, à votre avis, les exécutions suivantes de readdir() ? En particulier, où cette fonction trouve-t-elle l'adresse de l'entrée courante du répertoire ?
    3. Quel est le rôle du champ dd_size ?
  5. Quand l'allocation de la mémoire nécessaire au stockage des entrées du répertoire a-t-elle lieu ?
  6. Le champ d_off est périmé ; que désignait-il, dans un lointain passé, à votre avis ?

2. NTFS

Quelles sont les différences fondamentales entre NTFS (système de fichiers NT) et un système de fichiers Unix : Note : seules les réponses précises et techniques rapporteront des points.

3. Gestion de la mémoire

Voici un extrait du chapitre concernant la gestion de la mémoire, dans un ouvrage décrivant Windows NT :

“Lorsque la mémoire disponible tombe en dessous d'un certain seuil, le gestionnaire de mémoire utilise une technique appelée élagage automatique des espaces de travail (working sets) pour augmenter la quantité de mémoire libre. L'élagueuse, une routine exécutée dans le contexte de l'équilibrage de charges (balance set manager), examine chaque processus et compare la taille actuelle de son espace de travail avec la taille minimale allouée à ce processus. Lorsqu'elle découvre des processus utilisant plus que les minima alloués, elle évince des pages de leurs espaces de travail, et les rend disponibles pour d'autres usages. Si la quantité de mémoire libre reste trop basse, elle poursuit son travail, jusqu'à obtenir un nombre minimal de pages libres. Si, depuis le dernier élagage, un processus a provoqué un nombre non négligeable de défauts de pages, il est exempté d'élagage jusqu'au prochain cycle (6 secondes).”

  1. S'agit-il de mémoire physique ou virtuelle ?
  2. Expliquer ce que signifie probablement, du point de vue technique, l'expression “une routine exécutée dans le contexte de ... ”
  3. Une technique plus simple serait d'évincer des pages à la demande, lorsque se produisent des défauts de pages ; quel est l'avantage de la méthode décrite ici ?
  4. Dans d'autres systèmes, lorsque la mémoire libre devient insuffisante, les pages les moins récemment utilisées sont évincées, sans tenir compte des processus propriétaires de ces pages, jusqu'à ce que la mémoire libre repasse au-dessus d'un certain seuil. Expliquer les avantages et les inconvénients par rapport à la méthode décrite ici.
  5. Quel est l'intérêt de la dernière phrase, concernant l'exemption temporaire d'élagage ?

4. Processus

Soit le programme suivant :
#include <stdio.h>

static int successeur = 0;

static void ecrire (int n) {
  write (1, &n, sizeof (int));
}

static int lire (int *n) {
  return read (0, n, sizeof (int));
}

static void transmettre (int n) {
  int filtre, tube[2];
  
  if (successeur) {
    ecrire (n);
    return;
  }
  
  pipe (tube);
  if ( successeur = fork () ) { /* pere */
    dup2 (tube[1], 1);
    close (tube[0]);
    close (tube[1]);
    ecrire (n);
  }
  else { /* fils */
    dup2 (tube[0], 0);
    close (tube[0]);
    close (tube[1]);
    filtre = n;
    while ( lire (&n) )
      if (n % filtre)
        transmettre (n);
    exit (0);
  }
}

main (int argc, char **argv) {
  int i, n;
  
  n = atoi (argv[1]);
  for (i = 2; i <= n; i++)
    transmettre (i);
}
Décrire l'exécution de ce programme avec l'argument 30.

Note : cet exercice comporte une seule (brève) question, mais la réponse demande des explications soigneuses et une présentation claire des différents processus et tubes mis en jeu.