4.6. Synchronisation de lecteurs/rédacteurs

Le but de cet exercice est l'étude d'un problème courant de synchronisation de processus, communément appelé “lecteurs-rédacteurs”. Plusieurs processus, un par terminal, dotés de leur propre espace de mémoire centrale, ont un comportement identique, c'est-à-dire, exécutent le même programme. Celui-ci permet la consultation et la mise à jour d'un fichier aléatoire par numéro (ensemble d'enregistrements logiques auxquels on accède directement par leurs numéros), qui est relié au même fichier externe lors de l'ouverture. Il est schématisé sur la page suivante.
En plus des opérations de lecture et d'écriture mentionnées ci-dessus, le système fournit le type et les opérations suivantes:
var f : fichier;
   enrg: t_enregistrement;
   tab_numéro: tableau [1..2] de entier;
début début_prog;
	  répéter
		lecture_terminal (type);
		cas type dans
			consultation: début
				 lecture_terminal (tab_numéro);
				 début_consult;
				 pour i := 1 jusqu'à 2 faire
					 lire_enrg (f, enrg, tab_numéro[i]);
					 afficher ("stock = ", enrg.quantite);
				 fait;
				 fin_consult;
			fin;
			mise_à_jour: début
				 lecture_terminal (numéro, variation);
				 début_mise_à_jour;
				 lire_enrg (f, enrg, numéro);
				 enrg.quantité := enrg.quantité + variation;
				 écrire_enrg (f, enrg, numéro);
				 fin_mise_à_jour;
			fin;
			sortie:;
		fincas;
	  jusqu'à commande = sortie;
	  fin_prog;
fin;
Les durées d'exécution des opérations, ainsi que les durées totales d'attente qui en résultent (entrées-sorties) lorsque le processus est seul, sont données par le tableau suivant:
opération
lecture_terminal
ouvrir
fermer
lire_enrg
écrire_enrg
afficher
attente en ms.
10000
300
0
50
50
250
durée UC en ms.
20
30
10
10
50
10
A- On fait l'ouverture du fichier “stock” en mode partagé dans début_prog, et la fermeture dans fin_prog, les autres début/fin étant vides. Montrer que ceci peut conduire à des erreurs dans les valeurs mémorisées dans le fichier.
B- On modifie le mode d'ouverture en mode exclusif. Cela empêche-t-il ces erreurs de se produire? Quelles sont les conséquences de cette modification, pour l'utilisateur assis devant son terminal? Évaluer le nombre de consultations ou de mises à jour par minute.
C- On fait l'ouverture du fichier “stock” dans début_consult et début_mise_à_jour, et la fermeture dans fin_consult et fin_mise_à_jour, tandis que début_prog et fin_prog sont vides. Quels doivent être les modes d'ouvertures dans chacun des cas? Quelles sont les conséquences de ces modifications? On étudiera, en particulier, les différents temps d'attente et UC d'une consultation ou d'une modification, et on tentera d'en déduire le nombre de consultations ou de modifications qui sont possibles par minute. Montrer, sur un exemple, qu'une mise à jour peut être retardée indéfiniment.
D- Pour améliorer le comportement des processus, le système fournit deux opérations supplémentaires (le temps d'exécution de chacune d'elles est de 10 ms. unité centrale uniquement):
Proposer les procédures de début/fin qui vous paraissent acceptables dans ces conditions. Quelles sont les conséquences sur le comportement des processus? On étudiera, en particulier, les différents temps d'attente et UC d'une consultation ou d'une modification, et on tentera d'en déduire le nombre de consultations ou de modifications qui sont possibles par minute. Montrer que ceci n'empêche toujours pas le retard indéfini des mises à jour.
E- Quelle devrait être la fonctionnalité de réouvrir et de fermer_tempo pour empêcher le retard indéfini des mises à jour?
Solution de l’exercice 4.6

4.6.1. Question A

Prenons deux processus qui tentent d'effectuer une mise à jour d'un enregistrement de même numéro, par exemple 1, et lui porter une variation de 5. Supposons que initialement la quantité mémorisée dans cet enregistrement soit de 20. Le résultat de l'exécution séquentielle de ces deux processus, c'est-à-dire, l'un derrière l'autre, est égal à 20 + 5 + 5 = 30. Puisque le mode d'ouverture est partagé, les deux processus pourront accéder au fichier en même temps. Proposons l'ordonnancement suivant des actions de ces deux processus:
processus 1						processus 2
lire_enrg (f, enrg, numéro);
{ enrg.quantité vaut 20 }
							lire_enrg (f, enrg, numéro);
							{ enrg.quantité vaut 20 }
							enrg.quantite := enrg.quantité + variation;
							{ enrg.quantité vaut 25 }
							écrire_enrg (f, enrg, numéro);
							{ la valeur 25 est écrite dans le fichier }
{ enrg.quantité vaut toujours 20 }
enrg.quantite := enrg.quantité + variation;
{ enrg.quantité vaut 25 }
écrire_enrg (f, enrg, numéro);
{ la valeur 25 est écrite dans le fichier }
Le résultat final est alors de 25 au lieu de 30. Il y a bien risque d'erreurs.

4.6.2. Question B

Si on change le mode d'ouverture en exclusif, ces problèmes ne pourront plus se produire, puisque dans ce cas les deux processus ne peuvent accéder au fichier en même temps. Le premier obtiendra l'ouverture, le second sera mis en attente jusqu'à ce que le premier ferme le fichier. La conséquence immédiate est que le premier utilisateur qui lancera ce programme ouvrira le fichier en exclusif, empêchant tous les autres processus d'accéder au fichier. Tant que le premier utilisateur n'a pas terminé ses consultations ou ses mises à jour, les autres processus sont bloqués! Cela peut durer des heures.
Le temps total d'une consultation est 2 * 10020 + 2 * (60 + 260) = 20.7 sec, le temps total d'une mise à jour est 2 * 10020 + 60 + 100 = 20.2 sec; il y a donc en moyenne 3 consultations ou mise à jour par minute.

4.6.3. Question C

L'ouverture du fichier dans début_consult doit se faire en mode partagé. Il n'est pas gênant en effet que plusieurs processus accèdent en même temps au fichier en consultation, puisque alors le fichier n'est pas modifié. Par contre, l'ouverture dans début_mise_à_jour doit se faire en mode exclusif, pour éviter les problèmes énoncés dans la question A. Ceci a pour conséquence qu'un processus “réserve” le fichier pour la durée d'une consultation ou d'une modification au lieu de la durée totale d'exécution du programme.
Supposons d'abord qu'il n'y ait que des consultations. Le processus répartit son temps de la façon suivante:
attente utilisateur
2 * 10000
= 20 secondes
attente disque
300 + 2 * 50
= 400 ms
attente affichage
2 * 250
= 500 ms
traitement UC
2 * 20 + 30 + 2 * (10 + 10) + 10
= 120 ms
total
= 21 secondes
réservation fichier
2 * (10 + 50 + 250 + 10) + 10
= 650 ms
Le disque limite à 60 / 0.4 = 150 le nombre de consultations par minute, pour l'ensemble des processus, alors qu'un processus ne peut faire au plus que 3 consultations par minute. On peut donc en conclure que, en théorie, 150 / 3 = 50 processus peuvent faire des consultations simultanément. Notons que l'UC est occupée 150 * 120 = 18 secondes par minute.
Supposons maintenant qu'il n'y ait que des mises à jour. Le processus répartit son temps de la façon suivante:
attente utilisateur
2 * 10000
= 20 secondes
attente disque
300 + 2 * 50
= 400 ms
traitement UC
2 * 20 + 30 + 10 + 50 + 10
= 140 ms
total
= 20.5 secondes
réservation fichier
2 * 50 + 10 + 50 + 10
= 170 ms
La réservation du fichier en accès exclusif n'interdit pas les accès disque nécessaires à son ouverture par un autre processus. La limite prépondérante reste alors l'occupation disque, donnant au mieux 150 mises à jour par minute, en acceptant 50 processus. On obtient alors 21 secondes d'UC par minute.
En conclusion la méthode permet d'atteindre théoriquement 150 consultations ou mises à jour par minute, à partir de 50 terminaux. Mais la réservation pour consultation par un processus dure 650 ms. Si on suppose, par exemple, que 45 processus se coalisent pour demander des consultations en permanence, chacun d'eux sera candidat toutes les 21 secondes, et le rythme des demandes d'ouverture en mode partagé sera de 1 toutes les 21 / 45 = 0.46 secondes. Ces demandes arriveront donc toujours avant que le processus précédent ait terminé sa consultation. Le fichier restera alors ouvert en mode partagé, empêchant indéfiniment les 5 autres processus de faire des mises à jour.

4.6.4. Question D

début_prog:		ouvrir (f, "stock", partagé);
				fermer_tempo (f);
début_consult:		réouvrir (f, partagé);
fin_consult:		fermer_tempo (f);
début_mise_à_jour:	réouvrir (f, exclusif);
fin_mise_à_jour:	fermer_tempo (f);
fin_prog:			réouvrir (f, partagé);
				fermer (f);
Les changements qui interviennent sont liés à l'absence d'opération disque pour la réouverture.
Supposons d'abord qu'il n'y ait que des consultations. Le processus répartit son temps de la façon suivante:
attente utilisateur
2 * 10000
= 20 secondes
attente disque
2 * 50
= 100 ms
attente affichage
2 * 250
= 500 ms
traitement UC
2 * 20 + 10 + 2 * (10 + 10) + 10
= 100 ms
total
= 20.7 secondes
réservation fichier
2 * (10 + 50 + 250 + 10) + 10
= 650 ms
Le disque limite à 60 / 0.1 = 600 le nombre de consultations par minute, pour l'ensemble des processus, alors qu'un processus ne peut faire au plus que 3 consultations par minute. On peut donc en conclure que, en théorie, 600 / 3 = 200 processus peuvent faire des consultations simultanément. Notons que l'UC est occupée 600 * 100 = 1 minute par minute, donc à 100 %.
Supposons maintenant qu'il n'y ait que des mises à jour. Le processus répartit son temps de la façon suivante:
attente utilisateur
2 * 10000
= 20 secondes
attente disque
2 * 50
= 100 ms
traitement UC
2 * 20 + 10 + 10 + 50 + 10
= 120 ms
total
= 20.2 secondes
réservation fichier
2 * 50 + 10 + 50 + 10
= 170 ms
La limite prépondérante devient ici la réservation du fichier en mode exclusif, qui limite à 60 / 0.17 = 352 mises à jour par minute, en acceptant 352 / 3 = 117 processus. On obtient alors 352 * 120 = 42 secondes d'UC par minute, et 352 * 100 = 35 secondes d'occupation disque par minutes.
En conclusion la méthode permet d'atteindre théoriquement 600 consultations ou 352 mises à jour par minute, en utilisant un nombre de terminaux compris entre 117 et 200, suivant la proportion de consultations par rapport aux mises à jour. Mais la réservation pour consultation par un processus dure toujours 650 ms. Comme dans la question précédente, une coalition de 45 processus pour demander des consultations en permanence donnera un rythme des demandes d'ouverture en mode partagé de 1 toutes les 0.46 secondes. Ces demandes arriveront donc toujours avant que le processus précédent ait terminé sa consultation. Le fichier restera alors ouvert en mode partagé, empêchant indéfiniment les autres processus de faire des mises à jour. Le problème sera d'autant plus grave que le nombre de processus est plus grand, et survient donc avec une proportion plus faible de processus qui se coalisent.

4.6.5. Question E

Pour corriger cette dernière anomalie, il suffit que réouvrir bloque systématiquement le processus demandeur, quel que soit le mode d'ouverture demandé, si la file d'attente n'est pas vide, et mette ce processus en bout de la file. Par ailleurs, l'opération fermer_tempo doit être modifiée pour ne pas réactiver les processus de la file qui demandent l'ouverture en mode partagé et qui sont derrière un processus qui demande l'ouverture en mode exclusif.
réouvrir:
	si file [f] non vide
	ou f déja ouvert en exclusif
	ou f déja ouvert en partagé et demande en exclusif alors
		bloquer le demandeur et l'ajouter en bout de file [f]
	finsi;
	autoriser les accès du processus à f
fermer_tempo:
	si file [f] non vide et f n'est plus ouvert alors
		extraire et activer le processus de tête de file [f]
		si demande en partagé alors
			tant que file [f] non vide
			et demande du processus de tête en partagé faire
				extraire et activer le processus de tête de file [f]
			fait;
		finsi;
	finsi;