Discussion :

[hyphens]

Bonjour!
Dans le cadre d'un projet de recherche je dois mettre en oeuvre des algorithmes multithreadés pour la résolution de problèmes complexes (problème à N corps, heuristiques pour problèmes NP-Complets...)

Je bloque sur un sérieux problème de synchronisation : en effet je dois gérer n threads exécutant le même code, et je dois pouvoir à partir de l'un quelconque suspendre l'exécution de p autres, faire le boulot du thread, puis indiquer aux p threads suspendus qu'ils peuvent reprendre leur boulot! Il se peut, de plus, que plusieurs threads ait à faire ce blocage en même temps...

Pour être plus concret, un exemple! J'ai un graphe de n sommet, chaque sommet est associé à un thread. Le thread change son état en fonction de son voisinage, je dois donc bloquer les p voisins du sommet pendant que le thread change son état pour garantir la cohésion de l'ensemble...

Des mutex et des conditions ne semblent pas réalisables ici, car un thread pourrait très bien demander de bloquer un autre alors que ce dernier vient de passer le test (ce qui ne le bloquerait pas...)

Je cherche donc un moyen de mettre en pause un thread sans avoir besoin de code dans la fonction qu'il exécute... Je n'ai trouvé aucune piste dans les documentations des pthreads consultés jusqu'à présent...

Toute piste est la bienvenue et merci d'avance,
Pierre.

[zintelix3d]

Voila ce que j'ai trouvé en espérant que sa puisse t'aider, a+

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
class CThread  
{
public:
 void Resume(void);
 void Suspend(void);
 virtual void Terminate(void);
 
 CDAQThread();
 virtual ~CDAQThread(); 
 
protected:
 
 virtual void Quit(void);
 virtual void Run(void);
 virtual void Init(void);
 
private:
   HANDLE m_hThread;
   DWORD  m_dwThreadId;
 
private:
 static void Thread(LPVOID lpvParameter);
}; 
 
CThread  ::CThread  ()
{
   m_hThread = ::CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)CDAQThread::Thread, (LPVOID)this, CREATE_SUSPENDED , &m_dwThreadId );
}
 
CThread  ::~CThread  ()
{
 
}
 
 
void CThread  ::Init()
{
 
}
 
void CThread  ::Run()
{
 
}
 
void CThread  ::Quit()
{
 
}
 
void CThread  ::Suspend()
{
   if(m_hThread)
      ::SuspendThread(m_hThread);
}
 
void CThread  ::Resume()
{
   if(m_hThread)
      ::ResumeThread(m_hThread);
}
 
void CThread  ::Thread(LPVOID lpvParameter)
{
   CDAQThread* pDAQThread=(CDAQThread*)lpvParameter;
 
   pDAQThread->Init();
   pDAQThread->Run();
   pDAQThread->Quit();
} 
 
void CThread  ::Terminate()
{
   if(m_hThread)
      ::TerminateThread(m_hThread,0);
 
   DWORD dwExitCode;
   DWORD dwTimeout=DAQTHREAD_TIMEOUT;
 
   while(GetExitCodeThread(m_hThread,&dwExitCode) &&  dwExitCode==STILL_ACTIVE){
      Sleep(100);
      if(!(dwTimeout--)) return;
   }
 
   ::CloseHandle(m_hThread);
}

[hyphens]

Merci beaucoup pour ta réponse, le problème est que je ne comprends pas le code, il semble incomplet? Notamment la partie qui m'intéresse avec la fonction

Code :

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

 ::SuspendThread(m_hThread);

Sa définition m'échappe???

Sinon j'ai trouvé des éléments de réponses avec les signaux, logiquement

Code :

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

 if(pthread_kill(mThread, SIGSTOP)!=0) cerr<<"Impossible de mettre en pause le thread"<<endl;

devrait mettre en pause le thread et

Code :

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

 if(pthread_kill(mThread, SIGCONT)!=0) cerr<<"Impossible de faire repartir le thread"<<endl;

le faire repartir...

Malheureusement c'est tout le programme qui s'arrête sans que je ne comprenne pourquoi?

[hyphens]

Ok c'est une fonction windows.. .
J'ai oublié de préciser que je développais sous Linux...
Mais merci quand même!!!

[zintelix3d]

Tu utilise pthread_kill avec

SIGCONT Continue executing, if stopped.
SIGSTOP Stop executing (cannot be caught or ignored).

Difficile de dire sans essayer, je vais essayer sa sur mon ubuntu.

Tu peut regarder la si sa peut t'aider:
http://publib.boulder.ibm.com/iserie...s/users_95.htm

A part sa pourquoi ne pas utiliser des mutex (je sais tu ne veut pas de code dans tes thread) mais bon si tu change d'avis va voir la:

http://www.linuxquestions.org/questi...hreads-184535/

a+

[zintelix3d]

Slt ya d'autres exemple mais avec la fonction Kill

Exemple1
Exemple2

a+

[corrector]

Voila ce que j'ai trouvé en espérant que sa puisse t'aider, a+

As-tu déjà rencontré un seul cas qui justifie qu'on bloque un thread donné?

(Je parle d'un cas concret.)

[hyphens]

Je pense que tu devrais revoir ta conception.
Par ailleurs, je crois exprimer l'avis général en disant que personne ici n'a compris cette description de ton algorithme.

Pour l'avis général je ne sais pas, mais j'espère bien dans la mesure ou ma description concernait seulement mon problème et non l'algorithme qui le pose... Dans cette mesure comment peux-tu supposer que ma conception est à revoir? Comme je l'ai dit c'est un sujet de recherche, par définition en dehors des terrains battus...

As-tu déjà rencontré un seul cas qui justifie qu'on bloque un thread donné?
(Je parle d'un cas concret.)

Ben tous les cas concrets où tu as des zones critiques de code quoi... Comme deux threads qui modifient en même temps la même zone mémoire c'est pas top en général... Maintenant si tu as un unique objet partagé un mutex suffit, mais comment faire si chaque thread peut potentiellement influencer le comportement de chaque autre?

Puisse qu'il a des curieux je vous donne à titre d'éclaircissement mon sujet de recherche:

"La physique et la nature montrent de très nombreux exemples de systèmes (mécaniques, chimiques, biologiques, etc.) dont le comportement est tellement complexe qu’il ne peut être étudié analytiquement. Paradoxalement, ces systèmes sont composés d’un grand nombre d’ « acteurs élémentaires » au comportement individuel très simple. La physique classe ces problèmes sous le nom de « problème à n corps ». L’exemple le plus connu est un ensemble de particules (ou planètes) où chacune des particules a une trajectoire propre, subit une attraction (électrique ou gravitationnelle) de la part des autres particules et peut entrer en collision avec elles. A partir de trois particules, le système devient analytiquement insoluble alors que le calcul de la trajectoire d’une seule particule est très simple. Les insectes sociaux fournissent un autre exemple : les fourmis ont, individuellement, un comportement élémentaire, alors que collectivement elles forment un système au comportement très complexe. Elles réussissent, de façon collective, à apporter une solution intéressante au problème d’optimisation de trajet. Un algorithme de résolution du problème du voyageur de commerce a été conçu en « copiant » le comportement de ces insectes. Plus généralement, l’algorithmique peut-elle tirer profit de l’observation de ces systèmes ?
Le but de ce sujet est de trouver des situations dans lesquelles on peut résoudre/simuler un problème/phénomène complexe en attribuant un comportement sommaire à une multitude d’acteurs élémentaires autonomes. L’idée est que ces acteurs paraissent vivants et agissent en respectant quelques lois très simples. Cette approche n’est pas nouvelle : cf. automates cellulaires, algorithmes génétiques et colonies de fourmis. Cependant l’originalité de ce sujet repose sur l’emploi de threads : dans cette étude on impose que l’autonomie de ces acteurs soit garantie par l’emploi d’un thread séparé pour chaque acteur."

Je compte expérimenter les voies suivantes:
-La parallélisation d'un jeu de la vie (et l'étude de l'impact de l'abolition du principe de génération => un générateur original et efficace de nombres aléatoires?)
-Un algorithme heuristique pour le coloriage des graphes (d'où l'histoire des sommets et des voisins) Ou chaque sommet regarde la couleur de ses voisins, si il partage sa couleur il cherche alors à en utiliser une compatible dans la liste de celles déjà utilisées sinon il en créé une nouvelle...
-Une colonie de fourmis pour le problème du PCC multithreadé...

L'un dans l'autre ces problèmes posent des problèmes de synchronisation tellement difficiles et surtout déterminés seulement à l'exécution (et donc au bon gré de l'ordonnanceur) qu'une approche visant à gérer le soucis à même le code du thread imposerait de tester des verrous ou des conditions à chaque ligne de code...

Si tu as une idée Corrector pour traiter celà autrement je serais ravi que tu la partages avec moi, sinon voilà trois situations "concrètes" (cela reste un sujet de recherche tout de même ) qui j'espère t'éclaireront...

[valefor]

J'avais lu un truc sur le vol des oiseaux. Sans leader il peuvent voler en formation sans colision (et en plus c'est optimisé aérodynamiquement).

Ton sujet est assurément intéressant vu le nombre d'exemple.

Maintenant, pour synchroniser tes thread, je ne comprend pas.

Tu veux modéliser chaque élément par un thread, et "à chaque pas de simulation les synchroniser avant de lancer le pas suivant" ? Cela m'étonne, car la contrainte des threads n'est pas justifiée.

Sur un de tes exemples tu pourrais nous donner un petit scénario d'accès concurrent à une donnée te posant problème ?

[hyphens]

Merci, j'aime beaucoup ce sujet aussi Et en effet le vol des oiseaux est un exemple, que je mettrais peut-être en oeuvre dans mes expérimentations

Tu veux modéliser chaque élément par un thread, et "à chaque pas de simulation les synchroniser avant de lancer le pas suivant" ? Cela m'étonne, car la contrainte des threads n'est pas justifiée.

L'idée maîtresse du sujet est qu'il n'y ait pas de "pas de simulation" justement, d'ou le problème...

Je sais pas si je vais être clair, mais je vais essayé d'être plus précis pour le jeu de la vie:
Chaque cellule du jeu de la vie (un tableau de n*p cases) passent d'un état vivant ou mort en fonction du nombre de cellules vivantes dans son voisinage.
Chaque cellule a 8 voisines (Un carré de 9 cellules moins la cellule elle-même, au milieu)...
Itérativement, le tableau correspondant à la génération suivante est réalisé d'après le tableau précédent, case par case, ce qui ne pose donc aucun soucis car il suffit de créér un nouveau tableau et de le remplir à mesure...
En parallèle, en revanche, l'idée est que chaque cellule puisse changer d'état à tout moment peut-être plus souvent qu'une autre (selon l'ordonnanceur des tâches du système) et en parrallèle d'autre cellules si l'architecture CPU le permet...

(
Inconvénient par rapport à un jeu de la vie classique: plus de déterminisme, donc plus moyen de prévoir des structures stables, oscillateurs et autres vaisseaux...
Avantage espéré: un comportement plus proche d'un comportement vivant amenant à plus de réalisme pour la simulation des problèmes: comme le vol des oiseaux!
)

Pb de synchronisation:
Un thread par cellule= un état par thread (vivant ou mort) il ne faut donc pas qu'un thread du voisinage change d'état avant que le thread qui a la main analyse son voisinage est décide en fonction soit de continuer à vivre, soit de mourir soit de naître!
Le blocage des threads ici est obligatoire si l'on veut respecter la règle de transition de l'automate cellulaire!

Un scénario simpliste avec juste 5 cellules et une règle de transition portant sur les deux seules voisines de gauche est droite. Disons qu'on ait à un instant t le tableau
0 0 1 0 0
Le thread vivant à 1a la main, il a un voisinage 0 et 0 et la règle pour 010 est de mourir il doit donc mourir! Manque de bol son voisin de droite s'exécute en parallèle et la règle pour 100 est de vivre, il devient donc vivant.
0 0 1 1 0
Imaginons que le premier n'ait pas dans l'intervalle changé son état on se retrouve donc avec
0 0 0 1 0
Mais en fait le voisinage du premier thread aurait du être 011! Ce qui aurait pu le conduire à un autre état que la mort!!! => ERREUR Le premier thread a avoir la main doit donc bloquer les deux autres...

Je ne sais pas si je suis plus clair sur les contraintes que j'aimerais vérifier, si tel n'est pas le cas je m'efforcerais de préciser... Ici le blocage est un choix, en revanche pour le coloriage du graphe c'est une véritable contrainte... Il me semble que c'est moins simple à expliquer donc j'ai commencé par ce sujet du jeu de la vie! En revanche je peux l'expliquer également si tu veux!

Et au fait je regarde du coté de pthread_barrier mais je ne comprends pas trop pour le moment...

[corrector]

chaque sommet est associé à un thread

Toute piste est la bienvenue et merci d'avance,
Pierre.

Je pense que tu devrais revoir ta conception.

Par ailleurs, je crois exprimer l'avis général en disant que personne ici n'a compris cette description de ton algorithme.