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). 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. 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. 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_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.