Problème des producteurs et des consommateurs

Le problème des producteurs et des consommateurs est un exemple informatique de synchronisation de ressources, qui peut s'envisager dans différents contextes de programmation concurrente, notamment en environnement multi-thread. Il s'agit de partager entre deux tâches, le producteur et le consommateur, une zone de mémoire tampon utilisée comme une file. Le producteur génère un élément de données, l'enfile sur la file et recommence ; simultanément, le consommateur retire les données de file[1].

Ce problème peut être généralisé à plusieurs producteurs ou consommateurs[2].

Implémentation

L'implémentation d'un tel algorithme pose souvent problème, surtout si la mémoire partagée est de taille fixée, puisqu'il faut alors s'assurer que le producteur ne va pas ajouter des données sur une file pleine et que le consommateur ne va pas essayer de retirer des données d'une file vide[3].

Différentes solutions peuvent être envisagées. Une solution courante est de modifier le producteur afin qu'il retienne le nombre de places libres dans la file et se mette en pause au lieu d'écrire les données si la file est pleine. Il faut alors que le consommateur réveille le producteur lorsqu'il a consommé des données et que la file n'est plus pleine. On implémente également un comportement similaire pour le consommateur, qui suspend son activité si la file est vide et est réveillé par le producteur si elle ne l'est plus. Cette solution peut être mise en place à l'aide de sémaphores[4] ou de la communication inter-processus.

Exemple

Soit un ensemble de producteurs, un consommateur et une file F. Le problème est de synchroniser l'accès à une imprimante.

Le code exécuté par les producteurs est le suivant :

créer un document D
verrouiller F
ajouter D à la fin de la file F
déverrouiller F
envoyer un signal au consommateur

Le code exécuté par le consommateur :

répéter
    attendre un signal de F
    tant que F n'est pas vide
        pour chaque élément E de F
            verrouiller F
            imprimer E
            supprimer E de F
            déverrouiller F
        fin pour
    fin tant que
    attendre un signal d'un producteur
fin répéter

L'implémentation est inspirée des threads POSIX (pthreads). Notons que l'attente du signal est une opération qui déverrouille le mutex associé, attend un signal d'un autre thread, puis verrouille de nouveau le mutex une fois le signal reçu.

Notes et références
  1. « Comment : implémenter divers modèles de producteur-consommateur », sur msdn.microsoft.com, Microsoft
  2. [PDF]S. Vialle, « Protocoles de synchronisation producteurs-consommateurs et lecteurs-rédacteurs »
  3. David Billard, « Le modèle producteur-consommateur »
  4. « Exemple : le producteur-consommateur »

Liens externes
  • Portail de l’informatique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.