Eviter les deadlocks

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:

---

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.

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.

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.

Citation:

---

Envoyé par 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.

---

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.

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:

---

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 ?

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.

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.