Discussion :

[Aspic]

Bonsoir,

J'utilise la librairie pthread pour créer mes threads et je suis face à un problème de synchronisation :
Je travaille sur la recherche bidirectionnelle dans un graphe.

J'ai donc créer une fonction qui fait une recherche de l'état initial vers l'état final (forward) et une autre qui fait dans l'autre sens (backward)

Les étapes de l'algorithme sont les suivants :

1. Tant que la solution n'est pas trouvée :
2. Récupérer le résultat de la recherche FORWARD
3. Récupérer le résultat de la recherche BACKWARD
4. Faire un test d'union entre les deux recherches
5. Si ce test est concluant alors quitter l'algo sinon continuer

En séquentiel, ca marche très bien mais je n'arrive pas à paralléliser la recherche BACKWARD (la recherche FORWARD sera faite dans le thread principal).

L'idée serait :

• Créer le thread de recherche pour BACKWARD (qui sera en boucle infinie)
• Tant que la solution n'est pas trouvée : (thread principal)
• Récupérer le résultat de la recherche FORWARD (thread principal)
• Attendre que le thread ait fini le premier tour
• Faire un test d'union entre les deux recherches (thread principal)
• Si ce test est concluant alors quitter l'algo sinon continuer (thread principal)

Je dois utiliser les threads avec conditions (et peut être des mutex) mais voilà, je sèche.

A mon avis, c'est pas clair car ce n'est pas clar pour moi non plus

Avez vous une idée ?

Merci d'avance

[Invité]

Salut
A priori une recherche ne modifie pas les données que l'on parcourt donc tu ne devrais pas avoir besoin de mutex :

Code :

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

1
2
3
4
5
6
7
8
9
void rechercheBackward(const Graphe & graphe, Resultat & resultat) { ... }
void rechercheForward(const Graphe & graphe, Resultat & resultat) { ... }
...
// recherches backward et forward en parallele
std::thread threadBackward ( rechercheBackward, std::cref(monGraphe), std::ref(resultatBackward) );
rechercheForward(monGraphe, resultatForward);
threadBackward.join();
// union des 2 recherches
...

http://en.cppreference.com/w/cpp/thread/thread/thread
Si tu veux absolument utiliser la lib pthread, le code devrait être assez similaire.

[Ehonn]

Code :

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

std::thread threadBackward ( rechercheBackward, std::cref(monGraphe), std::ref(resultatBackward) );

Avec std::thread, j'aime bien passer par une lambda du genre :

Code :

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

std::thread threadBackward([&]() { rechercheBackward(monGraphe, resultatBackward); });

Et dans notre cas, une fonction qui retourne quelque chose est légitime (resultatBackward).
Donc avec une fonction de ce genre : return_t backward(graph_t const &), on peut utiliser une std::future :

Code :

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

1
2
3
auto f = std::async(std::launch::deferred, [&]() -> return_t { return resultatBackward(monGraphe); });
// ...
auto resultatBackward = f.get() // Pour récupérer le résultat (faire un seul appel à .get() car le résultat peut être déplacé)

Edit : nokomprendo > oui, il manque bien le return (erreur copier / coller)

[Invité]

Oui tu as raison mais comme il était parti sur du pthread, je n'ai pas voulu trop le brusquer...

Pour la lambda, personnellement je préfère expliciter la fermeture (surtout s'il y a des références) et éviter le type de retour s'il peut être déduit; et je crois qu'il manque un return :

Code :

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

1
2
auto f = std::async(std::launch::deferred, [&monGraphe]() { return resultatBackward(monGraphe); });
// ...

Par contre, je ne suis pas fan de la lambda ici car il y doit y avoir un (léger) surcoût pour la créer et de plus on ne peut pas spécifier la référence capturée en const (ou du moins, je ne sais pas comment faire). Donc, je préfère vraiment :

Code :

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

1
2
3
 
auto f = std::async(std::launch::deferred, resultatBackward, std::cref(monGraphe) );
// ...

[Ehonn]

Pour la lambda [...] et je crois qu'il manque un return :

Merci, c'est corrigé.

Pour la lambda, personnellement je préfère expliciter la fermeture

Dans le cas général je n'ai pas trop d'avis là dessus. Mais ici on se sert de la lambda comme on aurait pu utiliser std::bind ou un simple foncteur. Plus le code de la lambda sera court plus il sera facile de voir que l'on cherche à transformer un appel de fonction à N arguments en un appel de fonction sans argument. Donc dans ce cas, j'ai une petite préférence à ne pas expliciter la liste de capture ainsi que le type de retour.

Par contre, je ne suis pas fan de la lambda ici car il y doit y avoir un (léger) surcoût pour la créer et de plus on ne peut pas spécifier la référence capturée en const (ou du moins, je ne sais pas comment faire). Donc, je préfère vraiment :

Code :

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

1
2
3
 
auto f = std::async(std::launch::deferred, resultatBackward, std::cref(monGraphe) );
// ...

S'il y a un surcoût dû à la lambda, il faut changer de compilateur. Les lambdas sont forcément inline et devraient être inliné.
J'aime bien la lambda car elle permet de ne pas oublier les std::ref ou std::cref et quelle s'adapte automatiquement si ces "détails" changent.
Oui, on ne peut capturer que par copie ou référence. Mais rien n'empêche d'avoir un code proche de :

Code :

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

std::async(std::launch::deferred, [&]() { return resultatBackward(fonction_qui_prend_un_T_ref_et_qui_retourne_un_T_const_ref(monGraphe)); });

[Invité]

@Ehonn: je ne suis pas expert en compilation mais il me semble qu'une lambda n'est qu'un raccourci syntaxique pour un objet-fonction donc cela implique effectivement un surcôut dans la taille de l'exécutable alors que ce n'est pas le cas si on utilise un bind ou directement la fonction.
Concernant les std::ref et std::cref, il ne faut effectivement pas les oublier mais ils permettent d'éviter des erreurs genre "modifier une donnée qui devrait être const mais que la lambda a adapté automatiquement".
Ceci dit, tout çà c'est du détail, les deux solutions fonctionnent bien.

@Aspic: si je comprends bien ton problème, tu veux chercher dans un graphe dans deux sens en même temps, tout arrêter quand tu as trouvé et tout çà en évitant de traiter des noeuds déjà traités (overlapping) ?
À mon avis, une solution simple est que les deux recherches s'observent mais sans accès "concurrent" (lecture-écriture et non écriture-écriture) :

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
21
22
23
24
25
26
27
28
29
30
31
 
bool foundForward = false;
bool foundBackward = false;
 
void rechercheForward(...) {
	// rechercheForward modifie les donnees forward et observe les donnees backward
	while (not (foundForward or foundBackward or forwardStates.empty()) {
		// mettre à jour forwardStates
		// mettre à jour foundForward si on a trouve
	}
}
 
void rechercheBackward(...) {
	// rechercheBackward modifie les donnees backward et observe les donnees forward
	while (not (foundBackward or foundForward or backwardStates.empty()) {
		// mettre à jour backwardStates
		// mettre à jour foundBackward si on a trouve
	}
}
 
int main() {
	std::thread t(rechercheBackward...);
	rechercheForward(...);
	t.join(); 
	if (foundForward)
		// récupérer le résultat de la recherche forward
	else if (foundBackward)
		// récupérer le résultat de la recherche backward
	else
		// non trouvé
}

Cet exemple ne traite pas l'overlapping mais avec une variable partagée + mutex ce ne doit pas être difficile.
Concernant ton problème de std::thread, çà m'étonne car c'est juste une surcouche (souvent à pthread justement).
Bref, j'espère que tout çà t'aidera et désolé si ce n'est pas la meilleure solution/implémentation ou si j'ai juste rien compris à ton problème.

[Aspic]

Salut
A priori une recherche ne modifie pas les données que l'on parcourt donc tu ne devrais pas avoir besoin de mutex :

Code :

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

1
2
3
4
5
6
7
8
9
void rechercheBackward(const Graphe & graphe, Resultat & resultat) { ... }
void rechercheForward(const Graphe & graphe, Resultat & resultat) { ... }
...
// recherches backward et forward en parallele
std::thread threadBackward ( rechercheBackward, std::cref(monGraphe), std::ref(resultatBackward) );
rechercheForward(monGraphe, resultatForward);
threadBackward.join();
// union des 2 recherches
...

http://en.cppreference.com/w/cpp/thread/thread/thread
Si tu veux absolument utiliser la lib pthread, le code devrait être assez similaire.

Bonjour,

Je n'utilise pas std::thread car mon compilateur ne la gère pas c'est pour ca que je souhaite passer par pthread. (et puis je ne suis pas très à l'aise avec les lambda )

J'ai déjà essayé avec pthread ton approche mais ca n'a pas marché, certainement parce que je m'y suis mal pris

Soit ma fonction

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
void rechercheBackward(...) {  
    while (!solved_backward && !backwardStates.empty())
    {  
        // ...
    }
}
void rechercheForward(...) {  
    while (!solved_forward && !forwardStates.empty())
    {  
        // ...
    }
}

Et celui qui appelle les fonctions :

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
 
int main()
{
      // création du thread avec pthread qui lance rechercheBackward(...) en parralèle
     Thread thread = pthread_create(...)
     while (!solved_forward && !forwardStates.empty()
            && !solved_backward && !backwardStates.empty())
     {
           rechercheForward(....);
 
           // Attente du thread rechercheBackward()
           pthread_join(&thread, NULL);
 
            // Union des recherches
     }
}

Le problème est que pthread_join() attend que le thread rechercheBackward() soit quitté et vu qu'il est en boucle infinie... mon thread principal reste bloqué... A mon avis, il faut utiliser pthread_cond_wait() et pthread_cond_signal() mais je n'y arrive pas.

Voilà un "pseudo" code de la version séquentielle qui marche très bien (tous les cas en sont pas gérés, c'est pour simplifier le code)

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
bool AlgoBidirect::start()
{
    bool overlapped = false;
    Node* current_fw = NULL, *current_rv=NULL;
    std::vector<Node*> succ, pred , nodes;
    std::queue<Node*> forwardStates, backwardStates;
 
    // Insert initial nodes in queue
    forwardStates.push(/* initial node */);
    backwardStates.push(/* initial node */);
 
    while (!solved_forward && !forwardStates.empty()
            && !solved_backward && !backwardStates.empty()
			)
    {
        // Forward
        {
            // Get first node in frontier
            current_fw = forwardStates.front(); forwardStates.pop();
 
            // Get successors and check if current_fw is a goal state
            succ = this->m_forward->_checkNode(current_fw, this->m_solved_forward);
            for (const auto& n : succ)
                forwardStates.push(n);
        }
 
        // Backward
        {
            current_rv = backwardStates.front(); backwardStates.pop();
 
            // Get successors and check if current_rv is a goal state
            pred = this->m_backward->checkNode(current_rv, this->m_solved_backward);
            for (const auto& n : pred)
                backwardStates.push(n);
        }
 
        // Find overlapping between forward and reverse
		{
            overlapped = checkMergeBetweenFwAndBw(...);
		}
    }
	// ici on a trouvé si overlapped = true
}

Merci