Examen Unix, mai 1997

1. Communication entre processus

Décrire et comparer les différents modes de communication entre processus Unix. Pour chacun d'entre eux, vous indiquerez en quelques lignes : Cette question couvre l'ensemble du cours, et pas seulement le chapitre intitulé IPC. Barème indicatif : 2 points par mode de communication correctement décrit. Ne perdez pas de temps avec des développements vagues qui ne vous rapporteront aucun point.

2. Mesure du temps, gestion de la mémoire

Un corrigé est disponible pour cette partie, inspirée d'un exercice de l'ouvrage de Jean-Marie Rifflet, Unix, 99 exercices corrigés (Ediscience, 1996).

Le programme mm manipule une matrice t de taille fixe 4096 x 1024 ; les éléments de t sont des réels, de type double. Le programme comporte trois phases ; dans chacune des deux premières phases, on calcule les éléments d'une partie de la matrice, ligne par ligne, par une double boucle :

  for (i = 0; i < hauteur; i++)
    for (j = 0; j < largeur; j++)
      t[i][j] = f (i, j);
Dans la troisième phase, le calcul est effectué colonne par colonne :
  for (j = 0; j < largeur; j++)
    for (i = 0; i < hauteur; i++)
      t[i][j] = f (i, j);
f est une fonction de calcul simple, dont la nature exacte est sans importance ; hauteur et largeur sont, dans cet ordre, les arguments du programme. On mesure, pour chaque phase, trois temps : le temps total d'exécution, le temps passé par le processus en mode utilisateur, et le temps passé par le processus en mode système (ces deux derniers temps sont appelés ``temps CPU'') ; on utilise pour cela l'appel système times, dont un extrait de la page de manuel est fourni en annexe. Les temps sont fournis en ``tics'' d'horloge (100 tics par seconde sur la machine utilisée).

Le programme complet est fourni en annexe, pour lever toute ambiguïté. Il est conseillé de lire le sujet en entier avant de répondre aux questions.

  1. (2 points) Expliquer la différence, pour un processus, entre mode utilisateur et mode système (ou mode noyau).

  2. (3 points) Expliquer pourquoi l'unité de temps est le "tic", c'est-à-dire dans ce cas le centième de seconde, et non par exemple la microseconde ; expliquer quand et comment le système enregistre les temps CPU consommés par le processus actif. Décrire schématiquement l'opération effectuée par le système pour traiter la primitive times.


    Voici une première exécution de ce programme, qui remplit 1000 lignes et 200 colonnes de la matrice. Chaque temps est affiché sous la forme t=t1+t2+t3, où ti concerne la phase i :
    modigliani% mm 1000 200
    Processus 11241 : temps ecoule       305 =  201 +   49 +   55
    Processus 11241 : temps utilisateur  160 =   58 +   47 +   55
    Processus 11241 : temps systeme      119 =  119 +    0 +    0
    

  3. (3 points) Expliquer pourquoi le processus passe un temps important en mode système pendant la première phase, et pas pendant les deux suivantes.

  4. (1 point) Calculer l'ordre de grandeur du temps de calcul d'un élément de la matrice (on rappelle que les temps sont affichés en centièmes de secondes).

  5. (1 point) Calculer l'ordre de grandeur du temps de modification, par le système, de sa table des pages.


    Voici une seconde exécution de ce programme, qui remplit 2000 lignes et 100 colonnes de la matrice :
    modigliani% mm 2000 100
    Processus 11242 : temps ecoule     11122 =  834 + 4825 + 5463
    Processus 11242 : temps utilisateur  207 =   66 +   64 +   77
    Processus 11242 : temps systeme      872 =  256 +  329 +  287
    

  6. (3 points) Expliquer pourquoi le temps passé en mode système pendant la première phase a approximativement doublé (par rapport à la première exécution), alors que le temps passé en mode utilisateur n'a pas varié de façon significative.

  7. (2 points) Expliquer pourquoi le processus passe maintenant un temps comparable en mode système pendant chacune des phases.

  8. (2 points) Expliquer pourquoi le temps réel écoulé, surtout pendant les deux dernières phases, est très supérieur au temps CPU (aucun autre processus-utilisateur n'a évidemment perturbé l'exécution).

  9. (1 point) Que peut-on déduire de ces observations sur la taille de la mémoire physique disponible lors de ces expériences ?

  10. (1 point) Calculer l'ordre de grandeur du temps de lecture ou d'écriture d'une page sur disque.


    Si l'on tente de remplir 4000 lignes de la matrice, le programme s'effondre ; voici une exécution limitée à 5 colonnes :
    modigliani% mm 4000 5
    Processus 11245 : temps ecoule     24821 =  794 + 5205 + 18822
    Processus 11245 : temps utilisateur  167 =   22 +   31 +   114
    Processus 11245 : temps systeme     2186 =  261 +  309 +  1616
    

  11. (3 points) Expliquer ce qui se passe pendant la troisième phase.

  12. (1 point) Le temps passé en mode utilisateur est-il cohérent avec celui observé précédemment ? A votre avis, pourquoi ?


    Voici la trace de l'exécution de trois processus simultanés (toujours sans autre processus actif sur le système) :
    modigliani% mm 1000 200 & mm 1000 200 & mm 1000 200 & 
    [2] 11286
    [3] 11287
    [4] 11288
    [4]    Killed               mm 1000 200
    modigliani%
    Processus 11286 : temps ecoule     21392 =  657 + 9894 + 10841
    Processus 11286 : temps utilisateur  169 =   50 +   53 +    66
    Processus 11286 : temps systeme      472 =  138 +  151 +   183
    
    Processus 11287 : temps ecoule     22969 =  874 + 10103 + 11992
    Processus 11287 : temps utilisateur  180 =   47 +    63 +    70
    Processus 11287 : temps systeme      512 =  134 +   160 +   218
    

  13. (2 points) Pourquoi le système a-t-il tué le troisième processus (sans intervention externe, bien entendu) ?

  14. (2 points) Commenter cette exécution.

Annexe

NAME
     times - get process and child process times

SYNOPSIS
     #include <sys/times.h>

     clock_t times(struct tms *buffer);

DESCRIPTION
     times() fills the tms structure pointed to  by  buffer  with
     time-accounting  information.  The tms structure, defined in
     <sys/times.h>, contains the following members:

               clock_t    tms_utime;
               clock_t    tms_stime;
               [...]
     
     All times are reported in clock  ticks.  The specific  value
     for a  clock tick  is defined by the variable CLK_TCK, found
     in the header <limits.h>.

     tms_utime is the CPU time used while executing  instructions
     in the user space of the calling process.

     tms_stime is the CPU time used by the system  on  behalf  of
     the calling process.

RETURN VALUES
     Upon successful completion, times() returns the elapsed real
     time,  in  clock  ticks, from an arbitrary point in the past
     (for example, system start-up time).  This  point  does  not
     change  from  one  invocation  of  times()  to  another.  If
     times() fails, a value of -1 is returned and errno is set to
     indicate the error.

#include <sys/times.h>
#include <math.h>

#define LIGNE_MAX 4096
#define COL_MAX 1024

double t[LIGNE_MAX][COL_MAX];

double a, b;

double f (int i, int j) {
  return a * i + b * j;
}

main (int argc, char **argv) {
  int i, j, pid, largeur, hauteur, tic1, tic2, tic3, tic4;
  struct tms cpu1, cpu2, cpu3, cpu4;
  
  a = sqrt (2.0);
  b = exp (1);
  hauteur = atoi (argv[1]);
  largeur = atoi (argv[2]);
  pid = getpid ();

  tic1 = times (&cpu1);
  for (i = 0; i < hauteur; i++)
    for (j = 0; j < largeur; j++)
      t[i][j] = f (i, j);
            
  tic2 = times (&cpu2);
  for (i = 0; i < hauteur; i++)
    for (j = 0; j < largeur; j++)
      t[i][j] = f (i, j);
      
  tic3 = times (&cpu3);
  for (j = 0; j < largeur; j++)
    for (i = 0; i < hauteur; i++)
      t[i][j] = f (i, j);
      
  tic4 = times (&cpu4);
  printf ("Processus %d : temps ecoule      %4d = %4d + %4d + %4d\n", pid,
    tic4 - tic1, tic2 - tic1, tic3 - tic2, tic4 - tic3);
  printf ("Processus %d : temps utilisateur %4d = %4d + %4d + %4d\n", pid,
    cpu4.tms_utime - cpu1.tms_utime,
    cpu2.tms_utime - cpu1.tms_utime,
    cpu3.tms_utime - cpu2.tms_utime,
    cpu4.tms_utime - cpu3.tms_utime);
  printf ("Processus %d : temps systeme     %4d = %4d + %4d + %4d\n\n", pid,
    cpu4.tms_stime - cpu1.tms_stime,
    cpu2.tms_stime - cpu1.tms_stime,
    cpu3.tms_stime - cpu2.tms_stime,
    cpu4.tms_stime - cpu3.tms_stime);
}

Corrigé

  1. Un processus en mode utilisateur exécute son propre code, et n'a accès qu'à son propre espace d'adressage. En mode système, le processus exécute le code du noyau, et est dans un état privilégié qui lui donne accès à l'ensemble de la mémoire.

    Un processus passe en mode système pendant le traitement d'un appel-système, ou bien, comme c'est le cas ici, pendant le traitement d'une exception, en particulier d'un défaut de page.

  2. L'unité de temps est le "tic", c'est-à-dire ici le centième de seconde, pour des raisons logicielles, et non matérielles. Le noyau enregistre les temps CPU consommés par le processus actif en incrémentant l'un des champs correspondants dans la table des processus lors de chaque interruption d'horloge ; ces interruptions ne doivent pas être fréquentes, à l'échelle de temps du processeur, c'est-à-dire actuellement du centième de microseconde, pour ne pas ralentir le système.

    La primitive times lit les champs concernés dans la table des processus. Elle lit aussi un compteur global, incrémenté lors de chaque interruption d'horloge, indépendamment du processus actif et de son mode.


    modigliani% mm 1000 200
    Processus 11241 : temps ecoule       305 =  201 +   49 +   55
    Processus 11241 : temps utilisateur  160 =   58 +   47 +   55
    Processus 11241 : temps systeme      119 =  119 +    0 +    0
    

  3. Pendant la première phase, la matrice n'est pas chargée en mémoire (pagination à la demande), donc le système doit traiter les défauts de pages correspondants ; pendant les deux phase suivantes, il n'y a plus de défaut de page.

  4. 200 000 éléments sont traités environ en 50 centièmes de secondes, soit :
    (50 x 10-2) / (2 x 105) = 2.5 x 10-6 secondes par élément,
    ou encore 2.5 microseconde, ce qui est vraisemblable (ce temps comporte l'incrémentation de la boucle, l'appel de fonction, et l'exécution des opérations en virgule flottante).

  5. Le point fondamental, qui servira pour la suite, est que chaque ligne de la matrice comporte 1024 éléments, et occupe donc 8Ko (car un réel en double précision occupe 8 octets), soit deux pages. Ici on utilise seulement les 200 premiers éléments de chaque ligne, qui tiennent dans une page (sauf malchance, si l'adresse relative de début de la matrice, dans une page, est grande ; on suppose dans la suite que ce n'est pas le cas); mais lorsqu'on passe à la ligne suivante, on change nécessairement de page : t[i+1][0] n'est pas stocké à la suite de t[i][199].

    Le nombre de défauts de pages est donc égal au nombre de lignes, soit 1000 ; le temps système de traitement vaut 119 centièmes de secondes, de l'ordre de grandeur de la seconde ; donc l'ordre de grandeur du temps de modification de la table des pages est la milliseconde, ce qui est raisonnable.


    modigliani% mm 2000 100
    Processus 11242 : temps ecoule     11122 =  834 + 4825 + 5463
    Processus 11242 : temps utilisateur  207 =   66 +   64 +   77
    Processus 11242 : temps systeme      872 =  256 +  329 +  287
    

  6. La taille de la matrice (200 000 éléments) n'a pas varié, donc le temps passé en mode utilisateur n'a pas varié de façon significative. Par contre, le nombre de pages a doublé, pour les raisons expliquées ci-dessus, et le temps passé en mode système pendant la première phase, pour allouer ces pages, a approximativement doublé.

  7. On a atteint les limites de la mémoire physique disponible pour le processus : lors de l'allocation des dernières pages, les premières sont évincées, selon un algorithme de type LRU ; dans les phases suivantes, il faut recharger progressivement toutes les pages.

  8. Lorsque des pages de la matrice sont évincées, elles sont sauvegardées sur disque, puisqu'elles ont été modifiées ; et lorsqu'elles sont rechargées, elles sont lues sur le disque. Le temps réel écoulé comporte donc le temps d'attente des opérations de lecture/écriture sur disque, pendant lequel le processus est suspendu.

  9. Les opérations sur disque sont environ 5 fois moins nombreuses pendant la première phase ; d'autre part le traitement de la matrice par colonnes (voir ci-dessous), ne provoque pas d'effondrement des performances ; ces deux constatations indiquent que la taille de la mémoire physique disponible est voisine des 2000 pages nécessaires au traitement de la matrice, soit 8 Mo.

  10. La lecture et l'écriture de 2000 pages dure approximativement 50 secondes, soit 25 millisecondes par page, ce qui est vraisemblable (ce temps comporte une écriture et une lecture).


    modigliani% mm 4000 5
    Processus 11245 : temps ecoule     24821 =  794 + 5205 + 18822
    Processus 11245 : temps utilisateur  167 =   22 +   31 +   114
    Processus 11245 : temps systeme     2186 =  261 +  309 +  1616
    

  11. Une colonne est constituée de 4000 éléments, chacun dans une page différente ; comme ces pages ne peuvent pas être simultanément présentes en mémoire, le traitement d'une seule colonne demande presque autant d'opérations sur disque que le traitement de la matrice entière ligne par ligne (environ 50 secondes).

  12. (1 point) Le temps passé en mode utilisateur n'est pas cohérent avec celui observé précédemment, probablement parce que mode utilisateur et mode système sont ici très étroitement entremêlés : lors d'une interruption d'horloge, la situation du processus est aléatoire (avec une probabilité supérieure pour le mode système).


    modigliani% mm 1000 200 & mm 1000 200 & mm 1000 200 & 
    [2] 11286
    [3] 11287
    [4] 11288
    [4]    Killed               mm 1000 200
    modigliani%
    Processus 11286 : temps ecoule     21392 =  657 + 9894 + 10841
    Processus 11286 : temps utilisateur  169 =   50 +   53 +    66
    Processus 11286 : temps systeme      472 =  138 +  151 +   183
    
    Processus 11287 : temps ecoule     22969 =  874 + 10103 + 11992
    Processus 11287 : temps utilisateur  180 =   47 +    63 +    70
    Processus 11287 : temps systeme      512 =  134 +   160 +   218
    

  13. La mort du troisième processus est a priori très surprenante : rien n'interdit, sous Unix, d'exécuter autant de processus qu'on le veut. En fait, le système a tué le troisième processus car la zone de swap est de taille insuffisante pour contenir trois matrices de 32 Mo. En pratique, c'est la taille de cette zone de swap qui limite la mémoire virtuelle disponible pour un processus.

  14. Lorsque l'ordonnanceur donne la main à un processus, pendant la seconde ou la troisième phase, ses pages ont été évincées par l'autre ; donc l'exécution de chacune de ces phases est aussi longue que dans le cas d'une matrice 2000 x 100, soit environ 50 secondes ; et comme les processus sont exécutés simultanément, le temps d'exécution apparent de chacune des seconde et troisième phases est voisin de 100 secondes.