4.12. Communication par boîte aux lettres

On dispose d’un fichier constitué de 100000 blocs (un bloc = un secteur), chaque bloc étant constitué de 10 articles. On désire construire une application qui effectue un traitement sur chacun des articles du fichier. Le schéma général est donné ci-dessous.
module de lecture
	numéro_dans_bloc : entier; 
	bloc : tableau 1..10 de type_article;
procédure initialiser;
début ouvrir (...); numéro_dans_bloc := 11
fin;
procédure obtenir_suivant (a : type_article);
début si numéro_dans_bloc = 11 alors
		lire bloc;
		numéro_dans_bloc := 1;
	  finsi; 
	  a := bloc [numéro_dans_bloc];
	  numéro_dans_bloc := numéro_dans_bloc + 1; 
fin;
programme 
	a : type_article; 
début pour i dans 1 .. 1000000 faire
		obtenir_suivant (a);
		-- traitement de l’article a
	  fait;
fin;
La lecture d’un bloc dure 20 ms, correspondant à l’attente du secteur, que l’on supposera fixe; elle consomme aussi 0,1 ms d’unité centrale, mais ceci peut être négligé. Le traitement d’un article consomme 2 ms d’unité centrale.
A- Calculer la durée totale d’exécution du programme ci-dessus, avec un seul processus.
B- Le système utilisé est multiprocessus, et propose un mécanisme de communication entre processus par l’intermédiaire d’un tampon de taille fixe selon le schéma producteur consommateur. Deux opérations sur le tampon sont fournies (Il ne s'agit pas de les redéfinir):
dépôt(a) met l’article a dans une case libre du tampon. S’il n’y a pas de place, le processus est bloqué jusqu’à ce qu’il y en ait. Par ailleurs, lorsque le dépôt a eu lieu, si un processus est en attente de retrait, l’article lui est délivré.
retrait(a) extrait un article du tampon et le met dans la variable argument a. S’il n’y en a pas, le processus est bloqué jusqu’à ce qu’il y en ait. Par ailleurs, lorsque le retrait a eu lieu, si un processus est en attente de dépôt, il est débloqué.
Remarque 1: Les articles sont extraits dans l’ordre où ils ont été déposés.
Remarque 2: Le temps d’exécution de ces opérations est considéré comme négligeable.
Pour gagner les temps d’attente des secteurs de l’application ci-dessus, et diminuer ainsi la durée totale d’exécution, on découpe le programme sous forme de deux processus P1 et P2. Le processus P1 est prioritaire sur P2, ce qui veut dire que si les deux processus sont prêts, P1 est activé.
P1	a : type_article; 
	début pour i dans 1 .. 1000000 faire
			obtenir_suivant (a);
			dépôt (a);
		  fait;
	fin;
P2	a : type_article; 
	début pour i dans 1 .. 1000000 faire
			retrait (a);
			-- traitement de l’article a
		  fait;
	fin;
B.1- Le tampon peut contenir 4 articles. Les deux processus sont prêts au même instant initial (temps 0). Décrire ce qui se passe au temps 20 ms, lors de la fin de la première lecture disque, jusqu’au moment où le processeur commence à traiter le premier article.
B.2-  Donner sur le graphique ci-après l’évolution temporelle des processus et du nombre de cases occupées dans le tampon durant les 70 premières millisecondes. Etant donné la priorité de P1 et son temps négligeable dans l’état actif, il y a lieu de préciser essentiellement, pour P1, la cause de blocage (attente disque ou attente tampon), et pour P2, les états actif ou bloqué en attente du tampon. Justifier votre réponse.

B.3- Que se passe-t-il au delà? En déduire le temps total.
C- Le tampon peut contenir 10 articles. Les deux processus sont prêts au même instant initial (temps 0). Donner sur le graphique ci-après l’évolution temporelle des processus et du nombre de cases occupées dans le tampon. En déduire le temps total.

D- Cela apporterait-il quelque chose d’augmenter la taille du tampon au delà de 10 articles?
E- Le temps de traitement des articles n’est plus fixe de 2 ms, mais de 1 ms par article, auquel il faut ajouter 25 ms tous les 25 articles (notons que la moyenne reste donc à 2 ms par article). Les deux processus sont toujours lancés en même temps. P2 demande une activité processeur de 45 ms avant de commencer les cycles traitement de 25 articles - traitement de 25 ms. Le tampon peut contenir 20 articles. Donner sur le graphique ci-après l’évolution temporelle des processus et du nombre de cases occupées dans le tampon.

Solution de l’exercice 4.12

4.12.1. Question A

Il y a 100000 blocs à lire, chaque lecture prenant 20 ms, soit au total 2000 secondes. Par ailleurs, il y a 1000000 traitements, chacun d’eux prenant 2 ms, soit au total 2000 secondes. Si les opérations se font avec un seul processus, cela veut dire que ce processus soit effectue les traitements soit attend la fin de la lecture du bloc suivant. L’ensemble durera donc 4000 secondes.

4.12.2. Question B

4.12.2.1. Question B.1

Dès la fin de la lecture, se déroule la séquence suivante :
  1. Le processus P1 devient prêt, dépose 4 articles dans le tampon et se bloque le tampon étant plein.
  2. P2 devient prêt dès le dépôt du premier article, mais la priorité de P1 l’empêche de passer actif.
  3. P2 devient actif lors du blocage de P1. Il extrait un article, ce qui entraîne le déblocage de P1.
  4. P1 dépose le cinquième article et se bloque.
  5. P2 repasse actif et commence à traiter le premier article.

4.12.2.2. Question B.2

Au temps 30 ms, l’extraction de l’article 6 par P2 permet le dépôt de l’article par P1 qui lance alors la lecture du bloc suivant et se bloque. Au temps 40 ms, P2 finit de traiter le dixième article et se bloque. Au temps 50 ms, on se retrouve dans la même situation qu’au temps 20 ms : P2 est en attente d’article, et P1 passe prêt avec un bloc complet à traiter.
Pour faciliter la compréhension, les numéros des articles sont mis dans les cases du tampon correspondant. Les cases blanches signifient qu’elles sont vides. Notons que l’article 1 et 11 n’apparaissent pas, car ils sortent pratiquement tout de suite du tampon, puisque pour ceux-là, P2 est en attente.

4.12.2.3. Question B.3

Comme nous l’avons dit précédemment, au temps 50 ms, on se retrouve dans la même situation qu’au temps 20 ms : P2 est en attente d’article, et P1 passe prêt avec un bloc complet à traiter. Durant ces 30 ms, 10 articles ont été traités complètement. On peut donc en conclure que la durée totale d’exécution est maintenant de 3000 secondes. Il y a un parallélisme partiel : P1 est en attente de disque et P2 est actif.

4.12.3. Question C


Si on porte la taille du tampon à 10 articles, P1 va pouvoir déposer tous les articles du bloc, pratiquement immédiatement, et relancer la lecture du bloc suivant. Pendant ce temps P2 va traiter les 10 premiers articles. Lorsqu’il aura fini de les traiter, ce sera la fin de la lecture du deuxième bloc, entraînant la réactivation de P1 pour lui permettre de déposer les 10 articles suivants. Nous aurons donc un parallélisme complet, et une durée totale de 2000 secondes. Notons que sur le graphique, le tampon semble ne jamais être plein. En fait il l’est pendant un très court instant, entre le moment où P1 dépose le dernier article du bloc et celui où P2 extrait le premier de ce bloc. Notons que 9 cases seraient sufffisantes : lorsque la neuvième est pleine, P1 se bloquerait, permettant à P2 d’extraire le premier et de le débloquer pour lui permettre de faire son dernier dépôt. En fait, ceci entraînerait une succession de changements de contexte du processeur, et donc une certaine déperdition inutile.

4.12.4. Question D

Il est inutile d’augmenter la taille du tampon, puisque nous avons vu qu’il n’était plein que pendant un très court instant. Les cases supplémentaires ne sont pas nécessaires.

4.12.5. Question E

Au temps 20 ms, le tampon se remplit de 10. Au temps 40 ms, il se remplit de nouveau de 10 et il devient plein. Au temps 45 ms P2 commence à extraire les articles à raison de 1 par ms. Au temps 60 ms, P2 en a traité 15 et il en reste encore 5 dans le tampon lorsque P1 en rajoute 10. Le tampon en contient donc 15. Au temps 70 ms, P2 arrête l’extraction alors que le tampon en contient encore 5. Au temps 80 ms, P1 en remet 10 et le tampon en contient 15. Au temps 95, P2 reprend l’extraction. Au temps 100, le tampon contient 10 articles et P1 en rajoute 10 ; le tampon est plein. Au temps 120, P2 arrête l’extraction (25ième), le tampon est vide et P1 en met 10. Au temps 140, P1 en rajoute 10 et le tampon passe à 20. Nous sommes ramenés à la même situation qu’en 40 : le tampon est plein, P1 lance une lecture et il reste 5 ms d’activité continue pour P2 avant de reprendre l’extraction. On constate que le temps total reste de 2000 secondes, avec un parallélisme complet, la taille du tampon permettant d’amortir les variations du temps de traitement de P2.