Modèle de producteur – consommateur

Cas1 : un producteur, un consommateur et un tampon de capacité égale à un message

Considérons les deux processus suivants :

• P1 : producteur de messages
• P2 : consommateur de messages

Un message est prélevé une et une seule fois.
Chaque message produit doit être consommé

Il s’agit de contrôler l’accès au tampon qui est un objet partagé.

A première vue, nous pouvons assimiler ce problème à un problème d’exclusion mutuelle. D’où l’utilisation d’un sémaphore d’exclusion mutuelle:

Sémaphore Mutex = 1;

Avec cette solution nous avons deux problèmes (2 anomalies) :

• Si le consommateur exécute sa séquence avant celle du producteur, il va trouver le tampon libre. Il va donc prélever un message qui n’a jamais été déposé ou produit.
• On risque aussi d’écraser plusieurs messages avant d’avoir le temps de les consommer (cas où le producteur reprend sa boucle avant que le consommateur n’ait le temps de dérouler la sienne).

Donc, le problème de producteur/consommateur n’est pas seulement un problème d’exclusion mutuelle mais aussi un problème de synchronisation.

Algorithmes

Les comportements de ces processus doivent être modifiés pour pouvoir prendre en compte les cas cités ci-dessus. Ainsi, doit-on adopter les algorithmes suivants :

Comme nous pouvons le constater, le producteur doit attendre que le tampon soit vide (nécessité d’un sémaphore, B_vide, pour illustrer cette barrière et l’attente se traduit alors par l’exécution de l’opération P sur ce sémaphore) et le consommateur doit attendre pour sa part que le tampon soit rempli (nécessité d’un deuxième sémaphore, B_plein, pour illustrer cette autre barrière et l’attente se traduit alors par l’exécution de l’opération P sur ce deuxième sémaphore).

La résolution de ce problème nécessite alors l’utilisation de deux sémaphores :

Sémaphore B_vide, B_plein ;

La question suivante à régler est de savoir quelles devraient être alors leurs valeurs initiales.

Valeur initiale de B_vide

La valeur initiale de ce sémaphore correspond au nombre d’autorisations de passage accordées au producteur sans qu’il soit obligé d’attendre l’intervention du consommateur. Par ailleurs, nous disposons d’un seul tampon pouvant recevoir un seul message. Ce message doit être prélevé avant que le producteur puisse être autorisé à déposer un autre message.
Par conséquent, chaque intervention du producteur doit être suivie par une du consommateur. Ainsi, déduit-on que B_vide doit être initialisé à 1.

Valeur initiale de B_plein

La valeur initiale de ce sémaphore correspond au nombre d’autorisations de passage accordées au consommateur sans qu’il soit obligé d’attendre l’intervention du producteur. Or, le consommateur n’a pas le droit de passer avant le dépôt d’un message par le producteur. Par conséquent, chaque intervention du consommateur doit être précédée par une du producteur. Ainsi, déduit-on que B_plein doit être initialisé à 0.

• Quand le producteur veut déposer un message, Si B_vide == 1 alors l‘opération est possible et B_vide passe à 0.
• C’est le consommateur qui la remettra à 1 après avoir prélevé le message
• Il faut bloquer le consommateur quand le buffer est vide, s’il arrive en premier ( pas de message déposé) donc blocage.
• C’est le producteur qui le met à 1 après avoir déposé un message ce qui permet à l’utilisateur d’entrer et consommer le message.

Sémaphore B_vide = 1;
Sémaphore B_plein = 0;

Cas2 : un producteur, un consommateur et un tampon de capacité égale à N messages

La solution précédente assure le déroulement de la séquence suivante :

• Déposer, Prélever, Déposer, Prélever, Déposer, Prélever, ……

Le producteur ne peut déposer d’autres messages tant que le dernier n’a pas été consommé. Le producteur dépend donc de la vitesse du consommateur.

Afin d’augmenter la rapidité, nous utilisons un tampon plus grand. Le tampon utilisé possède N cases pouvant recevoir chacune un message.
Là aussi on se donne la tâche de synchroniser l’accès à ce tampon. Nous gardons aussi la même contrainte : Tout message produit doit être consommé une et une seule fois.

La gestion du tampon se fait de manière circulaire :
Quand on arrive à la case N – 1 on repasse à la case 0 (les opérations de dépôt et de prélèvement se font modulo N)

On utilise deux indices :

• I : Pour le producteur
• J :Pour le consommateur

Le dépôt effectué par le producteur se traduit par Tampon[I] = m ;
Le prélèvement effectué par le consommateur se traduit par m = Tampon[J] ;

• Pour le producteur, déposer un message est possible s’il existe au moins une case vide. Il doit donc commencer par attendre une case vide.
• Pour le consommateur, prélever un message est possible s’il existe au moins une case pleine. Il doit donc commencer par attendre une case pleine.

Au départ, toutes les cases sont vides et par conséquent, nous n’avons pas de cases pleines.
Sémaphore Case_vide = N ;
Sémaphore Case_pleine = 0 ;
Message Tampon[N] ;
Int I, J = 0 ;

Cas3 : Cas de M producteurs et N consommateurs et un tampon de capacité égale à N messages :

On pourrait penser faire adopter le comportement précédent du producteur par chacun des producteurs et le comportement précédent du consommateur par chacun des consommateurs. Mais, on aurait ainsi le risque de voir certains messages se perdent sans qu’ils soient consommés. De même, certains messages risqueraient d’être consommés plusieurs fois.
Pour se convaincre, il suffit d’examiner les exemples suivants :

Exemple 1

• 2 producteurs font chacun Case_vide.P()
• ils arrivent à passer tous les deux (le nombre des cases vides est supérieur à 1)
  • Le premier exécute Bufer[I] = m ;
  • Il est interrompu avant qu’il puisse exécuter l’instruction I = (I + 1) mod N
  • le deuxième prend le contrôle de l’unité centrale et exécute Tampon[I] = m
  • Il écrase ainsi le message déposé par le producteur précédent parce qu’iI n’a pas eu le temps de pointer la case libre suivante.

Exemple 2
Une situation similaire peut se produire pour les consommateurs conduisant à la consommation et l’utilisation d’un même message par plusieurs consommateurs.
Pour résoudre ce problème, il faut gérer correctement l’accès à notre tampon. Concrètement, il faut interdire à plusieurs producteurs d’accéder à une même case en même temps. De même, il faut interdire à plusieurs consommateurs d’accéder à une même case en même temps. En d’autres termes, il faut que l’accès à une case se fasse en exclusion mutuelle entre le producteurs lors du dépôt De même, le prélèvement effectué par les consommateurs doit se faire aussi en exclusion mutuelle. D’où la nécessité de protéger les indices I et J.

Sémaphore Case_vide = N ;
Sémaphore Case_pleine = 0 ;
Sémaphore Mutex1 = 1 ;
Sémaphore Mutex2 = 1 ;
Message Tampon[N] ;
Int I, J = 0 ;