Voir la source de 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 [[base de données|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émaphore (informatique)|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émaphore (informatique)|sémaphores]] et une variable, à savoir :
* Un sémaphore <tt>M_Lect</tt>, initialisé à 1 qui permet de protéger la variable <code>lect</code>. Il s'agit donc d'un [[Exclusion mutuelle|mutex]].
* Un sémaphore <tt>M_Red</tt>, initialisé à 1 qui permet de bloquer les tâches de rédaction (en induisant une priorité aux lecteurs). Il s'agit donc d'un [[Exclusion mutuelle|mutex]].
* Un sémaphore <tt>Red</tt>, initialisé à 1 qui permet de bloquer les tâches de lecture si une rédaction est en cours.
* Une variable <code>lect</code> 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 <tt>DATA</tt> 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 <tt>FILE</tt>.

Un mutex <tt>M1</tt> protège la structure suivante :

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

Un mutex <tt>M2</tt> 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 ====
# 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éger]]s 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.
# 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.
# 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 ==
* Luigi Zaffalon et Pierre Breguet, ''Programmation concurrente et temps réel avec ADA 95'', Presses polytechniques et universitaires romandes, [[Lausanne]], 1999
* [[dîner des philosophes]]

{{Portail|informatique}}

[[Catégorie:Programmation concurrente]]