Le modèle de lecteurs/rédacteurs
Il s’agit de résoudre le problème d’accès à une ressource commune (un fichier par exemple) devant être partagée par deux types de processus :
- Les lecteurs qui consultent le fichier sans le modifier. Ils peuvent donc l’accéder en parallèle
- Les rédacteurs qui accèdent au fichier pour le modifier. Ils doivent accéder au fichier en exclusion mutuelle entre eux et en exclusion mutuelle avec les lecteurs.
Solution
- Demander_Lire
- Signaler_Fin_Lecture
- Demander_Ecrire
- Signaler_Fin_Ecriture
Il faut déterminer les conditions dans lesquelles les demandes mentionnées seront bloquantes ainsi que la signification des "Signaler_..".
Lecteur
While(1)
{
:
/* demander */
Si je suis le premier Alors attendre fichier libre ;
un lecteur de plus
F.lire(X)
/*signaler Fin lecture*/
un lecteur de moins;
Si je suis le dernier Alors libérer le fichier ;
:
:
}
Rédacteur
While(1)
{
:
:
:
:
/* demander */
Attendre fichier libre
F.Ecrire(X)
/*signaler Fin écriture*/
Libérer le fichier ;
:
:
:
}
Comme nous pouvons le constater, un rédacteur doit toujours attendre que le fichier soit libre. Pour les lecteurs, nous distinguons deux cas : le cas du premier lecteur arrivant et le cas de tous les autres. C'est le premier lecteur qui doit demander le fichier pour lui et tous les autres lecteurs. Il doit attendre que le fichier soit libre. Son blocage doit entraîner celui de tous les autres lecteurs qui vont le suivre. Dans le contraire, les autres lecteurs doivent pouvoir le suivre pour effectuer leurs lectures simultanément.
Donc, nous avons d'un sémaphore, Fichier_Libre, pour illustrer cette barrière. L’attente se traduit alors par l’exécution de l’opération P sur ce sémaphore. La libération du fichier se traduit, quant à elle, par l’exécution de l’opération P sur ce même sémaphore.
Les lecteurs ont à utiliser un autre sémaphore, Mutex, pour pouvoir accéder en exclusion mutuelle au nombre courant de lecteurs.
La solution en termes de sémaphores de ce problème est illustrée par les algorithmes suivants:
Le problème de la voie unique
On considère des véhicules circulant sur 3 voies parallèles avec parfois des tronçons à voie unique. Bien entendu, il ne peut y avoir 2 véhicules circulant en sens inverses sur la voie unique. On définit le type direction par :
Enum direction {OUEST, EST}
On se donne comme objectif de résoudre ce problème de synchronisation dans les trois variantes suivantes :
- Un seul véhicule à la fois sur la voie unique,
- Le nombre de véhicules à un instant donné sur la voie unique est illimité,
- La capacité de la voie est limitée à N véhicules.
Le comportement d’un véhicule est donné par l’algorithme suivant :
While(1)
{
Demander la voie unique ;
Accéder sur la voie unique ;
Libérer la voie unique ;
}
Pour cette variante, le problème de la gestion de l’accès à la voie unique est un pur problème d’exclusion mutuelle. Pour le résoudre, il suffit d'utiliser un sémaphore initialisé à 1 et partagé par tous les véhicules. Le comportement d'un véhicule, en termes de sémaphores, est donné par l'algorithme suivant:
Sémaphore VU = 1 ;
While(1)
{
/*Demander la voie unique*/
P(VU) ;
Accéder sur la voie unique ;
/*Libérer la voie unique*/
V(VU) ;
}
Variante 2: Le nombre de véhicules à un instant donné sur la voie unique est illimité
Le comportement d’un véhicule peut toujours être décrit par l’algorithme adopté pour la première variante, à savoir:
While(1)
{
Demander la voie unique ;
Accéder sur la voie unique ;
Libérer la voie unique ;
}
Cependant, nous avons par rapport à la première variante un problème supplémentaire. Il faut bloquer les véhicules arrivant dans le sens contraire au sens courant. Pour cette variante :
La demande de la voie n’est pas bloquant si :
La voie est libre
Ou
Le sens-courant sur la voie correspond au sens du demandeur
Si aucune de ces 2 conditions n’est pas vérifiée alors on doit attendre.
Algorithme (pour un véhicule OUEST):
While(1)
{
/*Demander la voie unique*/
Si voie libre Alors sens_courant? OUEST ;
Si sens_courant ? OUEST Alors bloquer le demandeur ;
Sinon compter un véhicule de plus sur la voie unique ;
Traverser ;
/*Signaler fin utilisation de la voie*/
Signaler un véhicule de moins sur la voie
Si dernier véhicule sur la voie Alors il faut libérer les véhicules bloqués (contre-sens)
}
En termes de sémaphores, nous obtenons le comportement suivant :
Sémaphore Contre-Sens = 0 ;
Sémaphore MUTEX = 1 ;
Entier NB_ENGAGES, NB_BLOQUES = 0 ;
Direction Sens-Courant ;
Véhicule OUEST ;
Boolean Sens_Contraire = faux ; /*variable privé*/
While(1)
{
P(MUTEX)
Si NB_ENGAGES = 0 alors Sens_Courant = OUEST ;
Si Sens-Courant ? OUEST Alors
{
NB_BLOQUES++ ;
Sens-Contraire = Vrai ;
}
SINON NB_ENGAGES++ ;
V(MUTEX) ;
Si (Sens_Contraire) alors P(Contre_Sens) ;
Accés à la voie unique ;
P(MUTEX) ;
NB_ENGAGES-- ;
Si (NB_ENGAGES = 0) ET (NB_BLOQUES ? 0) Alors
{
Sens-Courant = EST ;
NB_ENGAGES = NB_BLOQUES ;
NB_BLOQUES = 0 ;
I =1 ;
TANT QUE (I = NB_ENGAGES) V(Contre-Sens) ;
}
V(MUTEX) ;
Contre exemple:
Sens_Courant == OUEST
P1 : Véhicule–EST, Il est interrompu après V(MUTEX) de la partie "demande"
et avant d’exécuter P(Contre-Sens) ;
P2 : Véhicule_OUEST, Il exécute la partie "libérer" en effectuant la
boucle TANT QUE …. V(Contre-Sens) ; il met un ticket de plus dans ce sémaphore.
P3 : Véhicule_OUEST (Sens_Courant == EST), Il va faire P(Contre_Sens)
mais sans se bloquer.
Il faut modifier l’algorithme précédent pour remédier à ce problème. La solution consiste tout simplement à ne pas mélanger les processus (véhicules appartenant aux deux sens) dans la même file. Il faut associer une file à chaque sens.
Sémaphore Contre-Sens[2] ={0, 0} ;
Sémaphore MUTEX = 1 ;
Entier NB_ENGAGES, NB_BLOQUES = 0 ;
Direction Sens-Courant ;
Véhicule OUEST ;
Boolean Sens_Contraire = faux ;
…
While(1)
{
MUTEX.P() ;
Si (NB_ENGAGES == 0) Alors Sens_Courant = OUEST ;
Si (Sens_Courant ? OUEST) Alors
{
NB_BLOQUES++ ;
Sens_Contraire = Vrai ;
}
SINON NB_ENGAGES++ ;
MUTEX.V() ;
Si (Sens_Contraire) Alors Contre_Sens[OUEST].P() ;
Accès à la voie unique ;
MUTEX.P() ;
NB_ENGAGES-- ;
Si (NB_ENGAGES = 0) ET (NB_BLOQUES ? 0) Alors
{
Sens_Courant = EST ;
NB_ENGAGES = NB_BLOQUES ;
NB_BLOQUES = 0 ;
I =1 ;
TANT QUE ( I = NB_ENGAGES)
{
Contre_Sens[EST].V() ;
I++ ;
}
}
MUTEX.V() ;
}
La capacité de la voie est limitée à N véhicules
Un véhicule est non admis sur la voie, si :
Sens_Courant ? Sens_Véhicule
ou
(Sens_Courant == Sens_Véhicule) ET (NB_ENGAGES ==N)
/*Signaler fin utilisation de la voie*/
S’il existe de véhicules de même sens que moi bloqué ALORS réveiller un de ces
véhicules.
SINON Signaler un véhicule de moins sur la voie
SI je suis le dernier véhicule ALORS réveiller au maximum N véhicules de l’autre sens
Sémaphore Véhicules-Bloqués[2] ={0, 0} ;
Sémaphore MUTEX = 1 ;
Entier NB_ENGAGES = 0 ;
Entier NB_BLOQUES[2] = {0,0} ;
Direction Sens-Courant ;
Véhicule OUEST ;
Boolean Non_Admis = faux ;
…
While(1)
{
MUTEX.P() ;
SI (NB_ENGAGES == 0) Alors Sens_Courant = OUEST ;
SI (Sens_Courant ? OUEST) OU (NB-ENGAGES == N) Alors
{
NB_BLOQUES[OUEST]++ ;
Non_Admis = Vrai ;
}
SINON NB_ENGAGES++ ;
MUTEX.V() ;
Si (Non_Admis) Alors Véhicules_Bloqués[OUEST].P() ;
Accès à la voie unique ;
MUTEX.P() ;
NB_ENGAGES-- ;
SI (NB_BLOQUES[OUEST] ? 0) Alors
{
NB_BLOQUES[OUEST]-- ;
Véhicules-Bloqués[OUEST].V() ;
}
SINON
{
NB_ENGAGES--;
SI (NB_ENGAGES == 0) ET (NB_BLOQUES[EST]) Alors
{
Sens_Courant = EST ;
NB_ENGAGES = min(NB_BLOQUES[EST], N) ;
NB_BLOQUES[EST] -= NB_ENGAGES ;
I =1 ;
TANTQUE(I = NB_ENGAGES)
{
Contre-Sens[EST].V() ;
I++;
}
}
}
MUTEX.V() ;
}
Une autre solution. Utiliser un sémaphore VU matérialisant le contrôle de la voie unique par un des deux classes de véhicules.
Il faut comptabiliser les véhicules engagés dans chaque sens. Donc, il faut utiliser 2 compteurs. Chaque compteur est accédé en Exclusion mutuelle par les éléments de sa classe.
Le même sémaphore est utilisé pour les deux rôles :
- Exclusion mutuelle
- Bloquer les voitures si la première voiture de même classe est bloquée
Sémaphore Voie_Unique = 1 ;
Sémaphore MUTEX[2] = {1,1} ;
Entier NB_ENGAGES[2] == {0,0} ;
Direction Sens_Courant ;
Véhicule OUEST ;
/*Demander la voie*/
While(1)
{
MUTEX[OUEST].P()
SI (NB_ENGAGES [OUEST] == 0) Alors
{
Voie_Unique.P() ;
Sens_Courant = OUEST ;
}
NB_ENGAGES++ ;
MUTEX[OUEST].V() ;
Accés à la voie unique ;
/*Libérer la voie*/
MUTEX[OUEST].P() ;
NB_ENGAGES[OUEST]-- ;
SI (NB_ENGAGES[OUEST] == 0) Alors Voie_Unique.V() ;
MUTEX[OUEST].V() ;
}
