Worldlex Wiki Problème des lecteurs et des écrivains
( Apprenez comment et quand supprimer ce message ) En informatique , les problèmes de lecteurs-écrivains sont des exemples de problèmes informatiques courants en matière de conc...
En informatique , les problèmes de lecteurs-écrivains sont des exemples de problèmes informatiques courants en matière de concurrence . Il existe au moins trois variantes de ces problèmes, qui traitent de situations dans lesquelles de nombreux threads d'exécution concurrents tentent d'accéder simultanément à la même ressource partagée .
Certains threads peuvent lire et d'autres écrire, avec la contrainte qu'aucun thread ne puisse accéder à la ressource partagée, que ce soit en lecture ou en écriture, pendant qu'un autre thread est en train d'y écrire. (En particulier, nous souhaitons empêcher plusieurs threads de modifier simultanément la ressource partagée et permettre à deux lecteurs ou plus d'y accéder simultanément). Un verrou de lecture/écriture est une structure de données qui résout un ou plusieurs problèmes liés à la gestion des accès lecteurs-écrivains.
Le problème fondamental des lecteurs-écrivains a été formulé et résolu pour la première fois par Courtois et al.
Problème des premiers lecteurs-écrivains
Supposons que nous ayons une zone de mémoire partagée (section critique) avec les contraintes de base détaillées ci-dessus. Il est possible de protéger les données partagées par un mutex d'exclusion mutuelle , empêchant ainsi deux threads d'accéder simultanément aux données. Cependant, cette solution est sous-optimale, car il est possible qu'un lecteur R1 possède le verrou, puis qu'un autre lecteur R2 demande l'accès. Il serait imprudent pour R2 d'attendre que R1 ait terminé avant de commencer sa propre opération de lecture ; au contraire, R2 devrait être autorisé à lire la ressource en même temps que R1 , car les lectures ne modifient pas les données, les lectures concurrentes sont donc sûres. C'est la motivation du premier problème de lecteurs-rédacteurs , auquel on ajoute la contrainte qu'aucun lecteur ne doit être maintenu en attente si la zone partagée est actuellement ouverte en lecture. Ce problème est également appelé problème de préférence des lecteurs , dont la solution est :
ressource de sémaphore = 1 ;sémaphore rmutex = 1 ;compteur de lectures = 0 ;/* resource.P() est équivalent à wait(resource) resource.V() est équivalent à signal(resource) rmutex.P() est équivalent à wait(rmutex) rmutex.V() est équivalent à signal(rmutex)*/écrivain () {ressource.P (); // Verrouiller le fichier partagé pour un éditeur< Section CRITIQUE >// L'écriture est terminéeresource.V ( ); //Libère le fichier partagé pour utilisation par d'autres lecteurs. Les écritures sont autorisées s'il n'y a pas de lecteurs qui le demandent .}lecteur () {< Section ENTRÉE >rmutex.P ( ); // Assurez-vous qu'aucun autre lecteur ne puisse exécuter la section <Entry> pendant que vous êtes dedansreadcount ++ ; // Indique que vous êtes un lecteur essayant d'entrer dans la section critiqueif ( readcount == 1 ) // Vérifie si vous êtes le premier lecteur essayant d'entrer dans CSressource.P ( ); // Si vous êtes le premier lecteur, verrouillez la ressource pour les éditeurs. La ressource reste réservée pour les lecteurs suivants .rmutex.V ( ); // Libération< Section CRITIQUE >// Faites la lecture< Section SORTIE >rmutex.P ( ); // Assurez-vous qu'aucun autre lecteur ne puisse exécuter la section <Exit> pendant que vous êtes dedansreadcount -- ; //Indique que vous n'avez plus besoin de la ressource partagée. Un lecteur de moinsif ( readcount == 0 ) // Vérifie si vous êtes le dernier (et unique) lecteur à lire le fichier partagéressource.V ( ); // Si vous êtes le dernier lecteur, vous pouvez déverrouiller la ressource. Cela la rend disponible aux auteurs .rmutex.V ( ); // Libération}
Dans cette solution au problème des lecteurs/écrivains, le premier lecteur doit verrouiller la ressource (fichier partagé) si elle est disponible. Une fois le fichier verrouillé, il peut être utilisé par plusieurs lecteurs ultérieurs sans qu'ils aient besoin de le verrouiller à nouveau.
Avant d'accéder à la section critique , chaque nouveau lecteur doit traverser la section d'entrée. Cependant, un seul lecteur peut se trouver dans la section d'entrée à la fois. Ceci afin d'éviter les conditions de concurrence entre les lecteurs (dans ce contexte, une condition de concurrence se produit lorsque deux threads ou plus se réveillent simultanément et tentent d'accéder à la section critique ; sans contrainte supplémentaire, le comportement est non déterministe. Par exemple, deux lecteurs incrémentent le compteur readcounten même temps et tentent tous deux de verrouiller la ressource, ce qui bloque l'un des lecteurs). Pour ce faire, chaque lecteur qui accède à la section d'entrée la verrouille jusqu'à ce qu'il ait terminé son traitement. À ce stade, les lecteurs ne verrouillent pas la ressource elle-même, mais uniquement la section d'entrée afin qu'aucun autre lecteur ne puisse y accéder pendant qu'ils s'y trouvent. Une fois l'exécution de la section d'entrée terminée, le lecteur la déverrouille en signalant le mutex. Ce signal est équivalent à : `mutex.V()` dans le code ci-dessus. Le même principe s'applique à la section de sortie. Un seul lecteur peut se trouver à la fois dans la zone de sortie ; par conséquent, chaque lecteur doit s'approprier et verrouiller la zone de sortie avant de l'utiliser.
Dès que le premier lecteur atteint la zone de saisie, il verrouille la ressource. Cela empêche tout auteur d'y accéder. Les lecteurs suivants peuvent utiliser la ressource verrouillée (pour les auteurs). Le dernier lecteur à terminer (indiqué par la readcountvariable) doit déverrouiller la ressource, la rendant ainsi disponible aux auteurs.
Dans cette solution, chaque auteur doit revendiquer la ressource individuellement. Cela signifie qu'une succession de lecteurs peut bloquer l'accès à la ressource à tous les auteurs potentiels et les empêcher d'y accéder. En effet, une fois la ressource verrouillée par le premier lecteur, aucun auteur ne peut la verrouiller avant sa libération. Seul le dernier lecteur la libérera. Par conséquent, cette solution ne garantit pas l'équité.
Deuxième problème lecteurs-écrivains
La première solution présente l'inconvénient de provoquer une pénurie de ressources , rendant impossible l'écriture dans un fichier constamment lu. Si un lecteur R1 détient le verrou tandis qu'un rédacteur W attend de l'obtenir, et qu'un lecteur R2 demande ensuite l'accès, il pourrait être considéré comme injuste que R2 accède immédiatement au fichier, avant W. C'est ce qui motive le second problème lecteurs-rédacteurs , qui ajoute la contrainte suivante : aucun rédacteur, une fois ajouté à la file d'attente, ne doit attendre plus longtemps que nécessaire . On parle alors de préférence des rédacteurs .
Une solution au scénario des préférences des écrivains est :
int readcount , writecount ; // (valeur initiale = 0)sémaphore readcount_mutex , writecount_mutex , readTry , reader_mutex , writer_mutex ; //(valeur initiale = 1)//LECTEURlecteur () {< Section ENTRÉE >readTry.P ( ); // Empêcher plusieurs lecteurs d'attendre un écrivainreader_mutex.P ( ); // Verrouille la section d'entrée ou attend les écrivains selon les besoinsreadcount_mutex.P ( ) ; // Empêche les conflits d'accès au mécanisme d'écriture et de lecturecompteur de lectures ++ ; //incrémente les lecteursif ( readcount == 1 ) //vérifie si vous êtes le premier lecteurwriter_mutex.P ( ); // Si vous êtes le premier lecteur, empêchez l'accès en écriturelire_mutex . V ();reader_mutex.V ( ); // Libère la section d'entrée et permet à l'écrivain de prendre en charge si nécessairereadTry.V ( ); //indique que vous avez terminé vos tentatives d'accès à la ressource< Section CRITIQUE >//la lecture est effectuée< Section SORTIE >readcount_mutex.P ( ) ; // Évite les conflits d'accès au compteur de lecture avec d'autres lecteursreadcount -- ; //indique que vous quittezif ( readcount == 0 ) //vérifie si vous êtes le dernier lecteur à quitterwriter_mutex.V ( ) ; // Si c'est le dernier, vous devez libérer la ressource verrouilléereadcount_mutex.V ( ); // Libération de la section de sortie pour les autres lecteurs}//ÉCRIVAINécrivain () {< Section ENTRÉE > // La section ENTRÉE commence iciwritecount_mutex.P ( ); // Éviter les conflits d'accès au compteur d'écritures avec d'autres processus d' écriturewritecount ++ ; // Signalez-vous comme écrivain entrantif ( writecount == 1 ) //vérifie si vous êtes le premier auteurreader_mutex.P ( ); // Si vous êtes le premier, vous devez bloquer l'accès aux lecteurs. Empêchez-les d'essayer d'entrer dans CS .writecount_mutex.V ( ) ; //section d'entrée de libération< Section CRITIQUE > // Début de la section CRITIQUEwriter_mutex.P ( ); // Réservez la ressource pour vous-même - empêche les autres rédacteurs de modifier simultanément la ressource partagée//l'écriture est effectuéewriter_mutex.V ( ); //fichier de libération< Section SORTIE > //La section SORTIE commence iciwritecount_mutex.P ( ); // section de sortie réservéewritecount -- ; //indique que vous quittezif ( writecount == 0 ) //vérifie si vous êtes le dernier auteurreader_mutex.V ( ); // Si vous êtes le dernier auteur, vous devez déverrouiller les lecteurs. Cela leur permet d'essayer d'entrer dans CS pour la lecture .writecount_mutex.V ( ) ; //section de sortie de libération}
Dans cette solution, la priorité est donnée aux écrivains. Ceci est réalisé en obligeant chaque lecteur à verrouiller et déverrouiller le readTrysémaphore individuellement. Ainsi, un seul lecteur peut signaler sa tentative de lecture à un instant donné en essayant d'acquérir le reader_mutexsémaphore. À ce stade, si un ou plusieurs écrivains se sont déclarés, le premier aura déjà acquis le reader_mutexsémaphore, bloquant ainsi le lecteur. Ce dernier ne pourra poursuivre sa lecture que lorsqu'il n'y aura plus d'autres écrivains. Étant donné que le sémaphore readcountest modifié à plusieurs endroits, son accès doit être protégé par une directive readcount_mutex.
Plusieurs rédacteurs peuvent se déclarer en incrémentant un registrewritecount ; cependant, seul le premier rédacteur verrouille le registre reader_mutexpour empêcher les lecteurs de poursuivre l'écriture. Les rédacteurs suivants utilisent ensuite la ressource séquentiellement en acquérant le registre writer_mutexavant l'opération d'écriture et en le libérant après. Le tout dernier rédacteur doit libérer le reader_mutexsémaphore, ouvrant ainsi la voie à la lecture.
Notez que si et seulement s'il n'y a pas d'écrivains, les sémaphores ` readTryand` reader_mutexsont redondants avec ` readcount_mutex,` servant uniquement à prévenir les conditions de concurrence sur la readcountvariable. Plusieurs lecteurs pourront ainsi se déclarer et lire simultanément les données partagées.
Troisième problème lecteurs-écrivains
En réalité, les solutions sous-jacentes aux deux énoncés du problème peuvent entraîner une famine : la première risque d’empêcher les processus d’écriture dans la file d’attente, et la seconde, les processus de lecture. C’est pourquoi on propose parfois un troisième problème de lecture-écriture , qui ajoute la contrainte qu’aucun processus ne soit laissé sans ressources ; autrement dit, l’opération d’acquisition d’un verrou sur les données partagées se terminera toujours dans un délai limité. Une solution équitable pour les lecteurs et les rédacteurs pourrait être la suivante :
int readcount ; // initialisé à 0 ; nombre de lecteurs accédant actuellement à la ressource// Tous les sémaphores sont initialisés à 1Ressource de sémaphore ; // contrôle l’accès (lecture/écriture) à la ressource. Sémaphore binaire.sémaphore rmutex ; // pour synchroniser les modifications de la variable partagée readcountfile d'attente de service de sémaphore ; // ÉQUITÉ : préserve l'ordre des requêtes (la signalisation doit être FIFO)//LECTEURlecteur () {< Section ENTRÉE >serviceQueue.P ( ); // attente dans la file d' attente pour être servirmutex.P ( ); // demande un accès exclusif au compteur de lecturereadcount ++ ; // mettre à jour le nombre de lecteurs actifssi ( readcount == 1 ) // si je suis le premier lecteurressource.P (); // demande d'accès à la ressource pour les lecteurs (écriture bloquée )serviceQueue.V ( ); // laisser le prochain dans la file d'attente être traitérmutex.V ( ); // libérer l'accès au compteur de lecture< Section CRITIQUE >//la lecture est effectuée< Section SORTIE >rmutex.P ( ); // demande un accès exclusif au compteur de lecturereadcount -- ; // mettre à jour le nombre de lecteurs actifsif ( readcount == 0 ) // s'il ne reste plus de lecteursressource.V (); // libérer l'accès à la ressource pour tousrmutex.V ( ); // libérer l'accès au compteur de lecture}//ÉCRIVAINécrivain () {< Section ENTRÉE >serviceQueue.P ( ); // attente dans la file d' attente pour être serviressource.P (); // demande un accès exclusif à la ressourceserviceQueue.V ( ); // laisser le prochain dans la file d'attente être traité< Section CRITIQUE >// l'écriture est effectuée< Section SORTIE >ressource.V (); // libère l'accès à la ressource pour le prochain lecteur / écrivain}
Cette solution ne peut satisfaire la condition « aucun thread ne doit être privé de ressources » que si et seulement si les sémaphores préservent l'ordre premier entré, premier sorti (FIFO) lors du blocage et de la libération des threads. Autrement, un processus d'écriture bloqué, par exemple, peut le rester indéfiniment, d'autres processus d'écriture décrémentant le sémaphore avant lui.
Problème de lecteur-écrivain le plus simple
Le problème de lecteur-écrivain le plus simple, qui n'utilise que deux sémaphores et ne nécessite pas de tableau de lecteurs pour lire les données dans le tampon.
Veuillez noter que cette solution est plus simple que le cas général car elle est ramenée au problème du tampon borné ; par conséquent, seuls readsémaphores writesont respectivement 0 et N.
Lecteur
faire { attendre ( lire ) ............ lecture des données ............ signaler ( écrire ) } tant que ( VRAI );
Écrivain
faire { attendre ( écrire ) ............. écriture des données ............. signaler ( lire ) } tant que ( VRAI );
Algorithme
- Le lecteur poursuivra l'écrivain grâce au sémaphore de lecture.
- L'écriture s'arrêtera lorsque le sémaphore d'écriture aura atteint 0.
- Le lecteur cessera de lire lorsque le sémaphore de lecture aura atteint 0.
Dans le processus d'écriture, la valeur du sémaphore d'écriture est transmise au sémaphore de lecture, et dans le processus de lecture, la valeur de lecture est transmise au processus d'écriture à la fin de la boucle.