Discussion :

[raphael_kindt]

Bonjour à tous,

J'explique mon petit problème à l'aide d'un exemple simple. Je suis certain que la réponse est aussi très simple.

Admettons que nous ayons 3 threads dans un processus: soit les threads A, B et C. Chaque thread peut manipuler une liste unique, celle-ci est donc partagée entre ces 3 threads.
Les threads A et B ne font que lire dans la liste. Par contre le thread C effectue une écriture (ajoute ou retire des éléments).
Je ne veux pas introduire de synchronisation entre A et B puisque ces threads ne font qu'une lecture. Le thread C, par contre, doit pouvoir écrire dans la liste dès que possible. Pendant cette écriture, ni A, ni B ne peut lire au risque de manipuler une valeur aberrante.

En développant un peu le problème, je peux dire que le thread C doit donc attendre qu'il n'y ait plus de lecture avant de pouvoir écrire. Dès que le thread C écrit, les threads de lecture A et B ne peuvent plus lire pendant toute la durée de l'écriture.

J'ai résumé le problème en utilisant 2 threads de lecture. Dans un cas pratique, je peux en avoir bien plus.

Que faudrait-il utiliser comme méthode?
Quel objet de synchronisation est le plus adapté (mutex, sémaphore, section critique, etc.)?
Des suggestions?

Merci pour vos remarques, vos idées, etc.

[Médinoc]

C'est ce qu'on appelle le modèle lecteurs/écrivain.

Si tu as la possibilité de réserver d'un coup plusieurs ressources sur un sémaphore (ce qui n'est pas le cas sous Windows, par exemple), alors je pense que le sémaphore est le plus adapté.

Sinon, il faut au moins un compteur "lecteurs", un événement manuel "lecture possible" (plus d'écrivain, activé par l'écrivain quand il libère), un autre événement manuel "écriture possible" (activé par le dernier lecteur qui libère lorsque que son compteur atteint zéro) et sans doute quelques mutexes/sections critiques pour protéger le compteur.

[JeromeBcx]

Bonjour Médinoc,

Si l'accès en écriture/lecture à la liste est simple (du type, une fonction de lecture pour A, une pour B, et une fonction écriture pour C), j'opterais pour un mutex.

Lorsque A (ou B) doit lire, il active le mutex, bloquant l'accès à son (ses) homologue(s) ainsi qu'à C.
Pareil pour C lors de l'écriture.
Libération du mutex à la fin de la fonction.
Boucle d'attente de libération de mutex en début de fonction.

Mais cette technique empêche les "classes" de lecture d'effectuer des lectures en simultané, mais à mon gout, ce n'est pas plus mal.

Cdt

[raphael_kindt]

Si tu as la possibilité de réserver d'un coup plusieurs ressources sur un sémaphore (ce qui n'est pas le cas sous Windows, par exemple), alors je pense que le sémaphore est le plus adapté.

Je confirme, je suis bien sous Windows.
Je comprend ta méthode. Les compteurs sont nécessaire mais ils doivent être protégés. En protégeant les compteurs, il ne faut pas que je synchronise mes threads de lecture...

Si l'accès en écriture/lecture à la liste est simple (du type, une fonction de lecture pour A, une pour B, et une fonction écriture pour C), j'opterais pour un mutex.

La méthode de lecture est supposée être la même pour les threads de lecture (A et B).
Par contre, je ne peux pas introduire de délai de synchronisation entre deux lectures. Je dois respecter un délai de fonctionnement. Ma méthode ne peux pas introduire de délai trop long à chaque lecture car celle-ci peut-être utilisée par n'importe qui, dans un thread "client".

Une chose importante à noter, je ne connais pas, à priori, le nombre de thread de lecture.

[JeromeBcx]

Je confirme, je suis bien sous Windows.
Je comprend ta méthode. Les compteurs sont nécessaire mais ils doivent être protégés. En protégeant les compteurs, il ne faut pas que je synchronise mes threads de lecture...

Pour les compteurs, un Interlock exchange (sous MFC si mes souvenirs sont bon ou une fonction similaire) permet de modifier un long en toute sécurité sans pour autant prendre du temps.
Néamoins, la protection du compteur reste "léger" et ne devrait pas perturber la lecture. Après tout dépend du contexte...

[nicroman]

Si c'est du windows pur....

Statiques:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
long     nReaders = -1;
HEVENT hReaders= CreateEvent(NULL,TRUE,FALSE,NULL);
HEVENT hMutex = CreateEvent(NULL,FALSE,TRUE,NULL);
HEVENT hWriterMutex = CreateMutex(NULL,FALSE,NULL);

Lecteurs infinis:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
if (InterlockedIncrement(&nReaders) == 0) {
    WaitForSingleObject(hMutex, INFINITE);
    SetEvent(hReaders);
}
WaitForSingleObject(hReaders,INFINITE);
 
... read safely ...
 
if (InterlockedDecrement(&nReaders) < 0) {
   ResetEvent(hReaders);
   SetEvent(hMutex);
}

1 seul écrivain:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
WaitForSingleObject(hWriterMutex,INFINITE);
WaitForSingleObject(hMutex, INFINITE);
 
... do the writing....
 
SetEvent(hMutex);
ReleaseMutex(hWriterMutex);

J'ai corrigé une ou deux coquilles, avant de donner l'explication de texte...
L'idée c'est le signal "maitre" {hMutex} qui est en mode de reset automatique (dès qu'un 'wait' a été satisfait). Ca signification est: "personne ne fait rien". Seul le tout premier reader (et le writer) s'en occupe... les autres readers se basent sur un autre signal: {hReaders} à état permanent (nécessite un reset explicite) qui signifie "les readers, on peut y aller à fond les manettes".
Quant aux writers, il utilisent leur propre mutex autour, histoire de pas cadenasser sans interruption les lecteurs...

[JolyLoic]

Une autre façon de gérer le lecteur/écrivain est avec une structure lock-free. L'idée est que le lecteur travaille en direct sur la donnée, sans lecture, si l'écrivain veut modifier des choses, il fait une copie locale des données (ce qui peut être cher), travaille dessus, puis échange les nouvelles données avec les ancienne lors d'une seule opération atomique (sans lock donc). Lire par exemple http://erdani.org/publications/cuj-2004-10.pdf

[raphael_kindt]

Merci à vous pour vos suggestions et code.
Je vais analyser ces quelques codes et document pour me faire une opinion sur la meilleur méthode.

L'idée de JolyLoic est envisageable mais je n'aime pas trop de travailler sur des copies. Ma liste contient des smart pointeurs. Il faut que je surcharge l'opérateur d'affectation pour permettre une copie "correcte" de mes objets.

[corrector]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
if (InterlockedIncrement(&nReaders) == 0) {
    WaitForSingleObject(hMutex, INFINITE);
    SetEvent(hReaders);
}
WaitForSingleObject(hReaders,INFINITE);

Pas de "else"?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
WaitForSingleObject(hWriterMutex,INFINITE);
WaitForSingleObject(hMutex, INFINITE);
 
... do the writing....
 
SetEvent(hMutex);
ReleaseMutex(hWriterMutex);

Quant aux writers, il utilisent leur propre mutex autour, histoire de pas cadenasser sans interruption les lecteurs...

Je ne comprends pas : à quoi sert hWriterMutex? Qu'est-ce qu'il garanti?

[nicroman]

le else n'est pas nécessaire, mais on peut le mettre pour grapiller 3 cycles dans un code qui aura fait un wait potentiellement long


hWriterMutex garanti qu'un seul écrivain est actif à chaque fois

[corrector]

le else n'est pas nécessaire, mais on peut le mettre pour grapiller 3 cycles dans un code qui aura fait un wait potentiellement long

C'est pas un appel système qui est évité? (Un appel système en général c'est pas 3 cycles...)

hWriterMutex garanti qu'un seul écrivain est actif à chaque fois

Justement, ce n'est pas ce à quoi sert, aussi, hMutex?

Au fait, pourquoi hMutex est un Event et hWriterMutex un Mutex? Pourquoi cette différence? Et pour quelle différence, concrètement?

[becoupama]

pardonnez cette intervention tardive, et arrêtez moi si je dis une ânerie,
mais je ne suis pas convaincu par les solutions proposées (sauf le lock-free mais qui semble malheureusement inadapté - ? -), ceci pour plusieurs raisons :
fiabilité ??? et dans la mesure où le nombre de lecteurs est inconnus, mettre en place un système de synchronisation (event mutex et toute la ménagerie) qui garantisse réciproquement les safe read et safe write serait tout de suite trop couteux en temps cpu, surtout si le nombre de thread de lecture est conséquent.
aussi je me permets de proposer une solution blindée, simple et aux contraintes de mise en place limitées :
tout se joue dans une fonction qui centralise lecture et écriture, confinée dans une criticalsection (pardon pour la syntaxe approx, je le fais à l'arrache):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
void CriticalReadWrite (void * lpData, int mode)
{
EnterCriticalSection (&cs);
if (mode == MODE_READ)  ReadData(lpData);
else                              WriteData(lpData);
LeaveCriticalSection (&cs);
}

voilà, voyez l'idée........

[nicroman]

Mais là... deux readers sont mutuellement exclusifs... ce qui n'est pas le but recherché

[nicroman]

Justement, ce n'est pas ce à quoi sert, aussi, hMutex?

Pas tout à fait.... Là on dit... je veux être le seul écrivain, et si je ne suis pas le seul, je n'essaye même pas d'attendre/locker l'event global "y a personne", histoire de pas empêcher d'autres readers à entrer.

Au fait, pourquoi hMutex est un Event et hWriterMutex un Mutex? Pourquoi cette différence? Et pour quelle différence, concrètement?

Un event est partagé par tous les threads....
Un mutex est reservé à un thread ....

[becoupama]

Mais là... deux readers sont mutuellement exclusifs... ce qui n'est pas le but recherché

c'est certain, si les traitements de lecture sont parallélisables et/ou relativement longs, ma soluce est sans doute inadaptée en l'état, mais facilement améliorable: du fait qu'on ne connait pas le nombre de threads de lecture, les criticalsection sont assez top pour regler ce genre de probleme...

euh, que penses tu d'une fonction critique qui gère les droits en lecture écriture sur telle ou telle ressource, ainsi seul la consultation/mise a jour des droits de lecture est en exclusion mutuelle, mais pas le process de lecture/ecriture ??

ca aurait egalement l avantage de ne pas bloquer toutes les lectures des que l ecrivain prend sa plume

[nicroman]

Ben oui... mais on en revient à:

AcquireReadRights();
... read safely ...
ReleaseReadRights();

AcquireWriteRights();
... write safely ...
ReleaseWriteRights();


Maintentant tu regardes mon mail plus haut, et tu remplaces

[becoupama]

Maintentant tu regardes mon mail plus haut, et tu remplaces

j ai bien compris que tu preferes ta maniere, aucun probleme. merci aussi de ne pas comparer les deux méthodes, tu entretiens une confusion non avenue.

ta soluce est de prime abord tres astucieuse et bien pensée mais elle est selon moi insuffisante en terme de fiabilité... car elle ne peut garantir que l ecrivain aura un jour la main pour ecrire, de surcroit si le traitement de lecture est assez long, que les thread de lecture sont nombreuses et les requetes frequentes, ton ecrivain aura surtout le droit de se taire...

un ecrivain disposant d'une priorite superieure aux lecteurs a, grace a l'astuce de la fonction critique, la garantie de placer son bazard rapidement...

bon, je suis nouveau sur le forum et j'ai pas non plus envie d'enflammer une polémique à peine arrivé, hein ? a la tienne !

[becoupama]

bah, deux reponses du tac o tac et puis plus rien....

bon je te propose une correction pour ton code :

Statiques:
Code :
HEVENT hReadRights = CreateEvent(NULL,TRUE,TRUE,NULL);

les lecteurs :
Code :
WaitForSingleObject(hReadRights);
[...]

l' écrivain :
Code :
ResetEvent(hReadRights);
[...]
SetEvent(hReadRights);

ca doit garantir que l'ecrivain aura son tour de parole... mais au final, je hais les event et autres mutex, c'est la plaie, une galere abominable, faut en mettre des couches et des couches pour avoir un truc vraiment fiable, regarde ton code, c'est de l'horlogerie fine, limite oeuvre d'art... et pourtant tu n'as pas tout vu, alors que tu as conçu la partie essentielle, il manque un grain de sable presque insignifiant qu'il est souvent ultra dur de détecter une fois en production - jusqu'au jour ou la charge augmente et là, le drame de la track au bug de synchronisation commence

les CS sont transparentes et faciles a comprendre, c'est pas la panacée - et on peut pas tout faire avec, mais en terme de maintenabilité du code et donc de temps et donc d'argent, les CS coûtent vraiment moins chères...

bref, j'y go - j'ai tout de même été ravi de cet échange, @+