Discussion :

[Rewpparo]

Bonjour !
Je cherche a faire un graphe dans un environnement extrêmement multithreadé. Les nodes du graphe doivent pouvoir être liés, c'est a dire que les deux nodes du lien stockent un pointeur vers l'autre élément. Je veux le rendre thread safe dans le sens où n'importe quel thread peut appeler link() avec n'importe quelle instance. Plusieurs thread peuvent le faire en même temps.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class A
{
     A* m_link
     Mutex m_mutex;
public:
     bool link(A* p_other)
     {
          //checks
          if(!p_other) return false; //No link to null pointer
          if(m_link) return false; //Already linked
          //Lock mutexes
          Lock l1(p_other->m_mutex);
          if(p_other->m_link) return false; //p_other already linked
          Lock l2(m_mutex);
          //Link
          m_link = p_other;
          p_other->m_link=this;
          return true;
     }
};

Avec cette implémentation cependant, je cours le risque de gros deadlocks. Je me demandais s'il existait une solution à ce problème, ou s'il s'agit d'un problème de design.

[backlash]

Et oui tout le problème d'enchainer 2 lock de mutexes :

thread A
1. lock m1
2. lock m2

thread B
1. lock m2
2. lock m1

Tu peux t'en sortir avec des timed_lock ou des try_lock sur les second lock.

[Rewpparo]

J'y avais pensé, mais je pensais que ça ne faisait que décaler le problème.
En cas d’échec du try, si je fais une boucle pour relâcher le premier mutex et recommencer, j'ai l'impression que dans des cas très rares cette boucle peut devenir bloquante. Et si ça arrive, bonjour le débug.
As tu une expérience en prod de cette boucle ?
Le multithread me fait un peu peur en fait, j'ai vraiment l'impression que tout peut me péter à la gueule, et je suis a la recherche de bonnes pratiques.

[white_tentacle]

J'y avais pensé, mais je pensais que ça ne faisait que décaler le problème.
En cas d’échec du try, si je fais une boucle pour relâcher le premier mutex et recommencer, j'ai l'impression que dans des cas très rares cette boucle peut devenir bloquante. Et si ça arrive, bonjour le débug.
As tu une expérience en prod de cette boucle ?
Le multithread me fait un peu peur en fait, j'ai vraiment l'impression que tout peut me péter à la gueule, et je suis a la recherche de bonnes pratiques.

Avec des time aléatoires, ça finit inévitablement par se débloquer. Mais ça rend le programme non déterministe, ce qui est à éviter autant que possible.

Par contre, je n’ai pas compris ta structure de données. A ça représente quoi exactement ? Parce que ça ne ressemble pas à un nœud… Un nœud aurait une liste de nœuds auxquels il est relié, pas un seul.

[Rewpparo]

C'est un graphe un peu particulier, chaque noeud dispose d'une liste de demi-liens, et relier ces demi liens créé une liaison entre les noeuds. C'est lié au gameplay d'un jeu vidéo.

J'ai essayé avec des opérations atomiques, mais ça me laisse les liens dans un état incohérent par moments.
Les timings aléatoires de mutex sont une bonne idée. Ce système est assez isolé, ça ne devrait pas trop faire boule de neige. Je vais tester comme ça.
Est ce qu'un simple yield() pourrait faire l'affaire ? un truc du genre :

Code :

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

1
2
3
4
5
6
7
8
9
std::mutex mutex1, mutex2;
 
mutex1.lock();
while(!mutex2.try_lock())
{
     mutex1.unlock();
     std::this_thread::yield();
     mutex1.lock();
}

Ca marcherait ?


EDIT : Je viens de tomber sur std::lock, C'est moi ou c'est exactement ce que je recherche ?

[JolyLoic]

Je pense que std::lock peut répondre à ton problème. Une autre solution, meilleure ou pas (selon le nombre de nœuds, la fréquence à laquelle les liens sont tirés...), consisterait à avoir non pas un mutex par noeud, mais un mutex global pour l'ensemble du graphe.

[Rewpparo]

En fait je ne peux pas me servir partout de std::lock, car j'ai besoin que le premier mutex soit locké pour pouvoir accéder de manière sure au deuxième. J'ai testé le code présent dans mon post précédent, ça a l'air de tenir.

Pour le mutex unique, ça ne colle pas dans le contexte actuel, car d'autres opérations vont s'effectuer en utilisant ces mutex, et j'ai besoin de profiter de plus de parallélisme que ça. Mais je garde en tête, c'est une bonne idée qui sera surement la solution a un autre problème a un moment ou a un autre.

Existe t il de bons bouquins sur la programmation parallèle ? Anglais ou français peu importe, mais que ce soit pratique, avec des exemples d'algos.