Problème des lecteurs et des rédacteurs

Le problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données.

Il fut énoncé sous cette forme par Edsger Dijkstra, qui est également à l'origine du problème du dîner des philosophes (problème relatif en particulier à l'ordonnancement des processus).

Le problème

Supposons qu'une base de données ait des lecteurs et des rédacteurs, et qu'il faille programmer les lecteurs et les rédacteurs de cette base de données.

Les contraintes sont les suivantes :

  • plusieurs lecteurs doivent pouvoir lire la base de données en même temps ;
  • si un rédacteur est en train de modifier la base de données, aucun autre utilisateur (ni rédacteur, ni même lecteur) ne doit pouvoir y accéder.

Solutions

Il est assez simple de faire en sorte que le rédacteur soit mis en attente tant qu'il y a encore des lecteurs.

Mais cette solution présente de gros problèmes, si le flux de lecteurs est régulier : le rédacteur pourrait avoir à patienter un temps infini.

Il existe donc une deuxième solution, qui consiste à mettre en attente tous les lecteurs ayant adressé leur demande d'accès après celle d'un rédacteur.

Edsger Dijkstra, qui a formulé ce problème, propose de le résoudre au moyen de sémaphores.

Solution avec utilisation des sémaphores et priorité aux lecteurs

La solution suivante permet de résoudre le problème des lecteurs et des rédacteurs en donnant priorité aux lecteurs. Cette solution nécessite trois sémaphores et une variable, à savoir :

  • Un sémaphore M_Lect, initialisé à 1 qui permet de protéger la variable lect. Il s'agit donc d'un mutex.
  • Un sémaphore M_Red, initialisé à 1 qui permet de bloquer les tâches de rédaction (en induisant une priorité aux lecteurs). Il s'agit donc d'un mutex.
  • Un sémaphore Red, initialisé à 1 qui permet de bloquer les tâches de lecture si une rédaction est en cours.
  • Une variable lect qui compte le nombre de lecteurs.

Cette solution utilise les quatre méthodes suivantes :

Commencer une lecture

Commencer_Lire:
   P(M_Lect)
   SI (red) ALORS
      pbloque=true
      V(M_Lect)
      p(synch)   
   FIN SI
   SINON
      lect++;
   V(M_Lect)

Cette méthode incrémente le nombre de lecteurs ; ensuite, s'il s'agit du premier lecteur à essayer d'entrer, elle n'autorise l'entrée que s'il n'y a pas de rédaction en cours. Dans le cas contraire, la méthode doit attendre que la rédaction soit finie. L'utilisation de deux sémaphores pour les rédacteurs permet d'induire la priorité aux lecteurs.

Finir une lecture

Finir_Lire:
   P(M_Lect)
   lect--
   SI Lect==0 ALORS
      V(Red)
   FIN SI
   V(M_Lect)

Cette méthode décrémente le nombre de lecteurs. Ensuite, s'il s'agit du dernier lecteur à sortir, elle autorise les rédacteurs à entrer (si nécessaire).

Commencer une écriture

Commencer_Ecrire:
    P(M_Red)
    P(Red)
    SI (red or lect>0) ALORS
       pbloque=true
       V(Red)
    SINON
       red=true
       V(Red)
    V(M_Red)

Cette méthode à l'aide du sémaphore M_Red permet de faire en sorte que la priorité soit donnée aux lecteurs lors de la fin d'un rédacteur (en effet la fin d'un rédacteur libère le sémaphore Red -libérant ainsi un éventuel lecteur- avant de libérer le sémaphore M_Red).

Finir une écriture

Finir_Ecrire:
    V(Red)
    V(M_Red)

Cette méthode permet de faire en sorte que la priorité soit donnée aux lecteurs (en effet la libération du sémaphore Red libère un éventuel lecteur avant de libérer un éventuel rédacteur à l'aide du sémaphore M_Red).

Solution avec copie asynchrone de la structure de données

Supposons que le but des lecteurs soit de lire les données de manière asynchrone. Tous les lecteurs disposent de l'information au moment où leur requête (depuis une machine distante éventuellement) a été posée.

Soit un pointeur DATA sur une structure de données contenant toutes les informations disponibles. Les rédacteurs vont envoyer des requêtes qui seront stockées dans une file d'attente FILE.

Un mutex M1 protège la structure suivante : 

Liste de DATA : PRECEDENT
DATA : ACTUEL
DATA : PROCHAIN
booléen : MISAJOUR

Un mutex M2 protège la structure suivante : 

File de mises à jour : FILE
Date de dernière modification : DERNIER

Code exécuté par le lecteur

verrouille M1:
    si MISAJOUR est vrai:
        enfile ACTUEL dans PRECEDENT
        pour chaque élément de PRECEDENT:
            effacer l'élément si son compteur de références est nul (1)
        fin pour
        ACTUEL := PROCHAIN (2)
        PROCHAIN := copie de ACTUEL
        MISAJOUR := faux
    fin si
    récupérer un pointeur P sur ACTUEL et incrémenter son compteur de références
déverrouille M1
lire dans P
...
décrémenter le compteur de références de P

Code exécuté par le rédacteur

verrouille M2:
    enfiler les modifications dans FILE
    si DERNIER est dépassé de 10 secondes:
        verrouiller M1:
            effectuer toute modification de FILE dans PROCHAIN
            vider FILE
            MISAJOUR := vrai (3)
        déverrouille M1
    fin si
déverrouille M2

Remarques

  1. Lorsque la structure de données a été mise à jour, son ancienne version peut subsister sous la forme d'un pointeur dans des processus légers concurrents. Une bonne manière d'éviter les fuites de mémoire est donc de tenir un compteur de références de manière à effacer les zones mémoires pointées lorsque plus aucun processus ne l'utilise.
  2. ACTUEL et PROCHAIN étant des pointeurs statiques, copier le second sur le premier revient à une affectation de pointeur. Comme dit au premier point, l'ancien pointeur subsiste dans les processus légers exécutés antérieurement. Par contre, dans la ligne suivante, on effectue une copie intégrale des données pointées par ACTUEL et fait pointer PROCHAIN vers la copie.
  3. Le simple fait de mettre ce booléen à vrai permettra aux prochains lecteurs d'utiliser la version des données qui convient.

Ce modèle est adapté lorsque les mises à jour ne nécessitent pas de gestion des transactions, ce que doivent fournir les bases de données.

Voir aussi