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 :
-
les principaux appels-système
(même si vous en ignorez le nom et le prototype exact) ;
-
les usages typiques, et les contre-indications.
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.
- (2 points)
Expliquer la différence, pour un processus,
entre mode utilisateur
et mode système (ou mode noyau).
- (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 points)
Expliquer pourquoi le processus passe un temps
important en mode système pendant la première
phase, et pas pendant les deux suivantes.
- (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).
- (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
- (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.
- (2 points)
Expliquer pourquoi le processus passe maintenant un temps
comparable en mode système pendant chacune des phases.
- (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).
- (1 point)
Que peut-on déduire de ces observations
sur la taille de la mémoire physique disponible
lors de ces expériences ?
- (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
- (3 points)
Expliquer ce qui se passe
pendant la troisième phase.
- (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
- (2 points)
Pourquoi le système a-t-il tué le troisième processus
(sans intervention externe, bien entendu) ?
- (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é
-
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.
-
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
-
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.
-
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).
-
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
-
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é.
-
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.
-
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.
-
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.
-
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
-
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).
- (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
-
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.
-
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.