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+

[hyphens]

Le fait est que SIGSTOP et SIGCONT ne fonctionnent pas chez moi, tout le programme se bloque...
J'ai vu plusieurs messages de personnes expérimentant les même problèmes...

J'ai trouvé une alternative qui fonctionne, (bien qu'un peu crade) en utilisant deux signaux...
J'ai une classe Thread ( qui marche un peu à la java) avec mes deux nouvelles méthodes

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
 
    	/**
         * On met le thread en pause en lui envoyant le signal SIGUSR1 attrapé par SIGUSR1Handler qui se met à boucler
         */
	void Pause(){
		if(mExecution){
			if(pthread_kill(mThread, SIGUSR1)!=0) cerr<<"Impossible de mettre en pause le thread"<<endl;
		}
	}
 
    	/**
         * On débloque le thread en envoyant SIGUSR2 attrapé par SIGUSR2Handler qui arrete la boucle de SIGUSR1Handler
         */
	void Reprise(){
		if(mExecution){
			if(pthread_kill(mThread, SIGUSR2)!=0) cerr<<"Impossible de faire repartir le thread"<<endl;
		}
	}

Bien sur, il faut indiquer à la création de la classe les handlers respectifs:

Code :

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

1
2
3
 
	signal(SIGUSR1, SIGUSR1Handler);
	signal(SIGUSR2, SIGUSR2Handler);

Une variable globale en dehors de la classe pour gérer le blocage:

Code :

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

1
2
 
static bool geler=false;

Et enfin les handlers

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
	static void SIGUSR1Handler(int errno){
		geler=true;
		while(geler){ //On attend donc
			usleep(100000);
		}
 
	}
 
	static void SIGUSR2Handler(int errno){
		geler=false;
	}

Bon c'est quand même du bricolage mais là, je vois pas plus propre... Tous les avis sont les bienvenus!!!
Et merci beaucoup zintelix3d pour ton interêt, si tu essayes sur ton ubuntu, je suis curieux de voir si pthread_kill fonctionne comme il faut chez toi...

[valefor]

Je ne garantis pas que cela soit ce que tu cherches, mais tu peux essayer les pthread_barrier.

[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.

[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...

[valefor]

A ce que j'ai compris, les pthread_barrier ne te seront d'aucune utilité (je pensais alors qu'il fallait que tu fasse des pas de simulation).


L'exemple du jeux de la vie étant concret, je te propose une solution (qui n'est peut-être pas excellente, je ne suis pas un gourou).

Tu as un tableau n x p représentant ton jeux. A chaque case tu affecte un thread et un mutex.

Tous les thread on la même implémentation. Il "prennent" le mutex des 8 voisins plus le leur. Il lisent l'état des 8 voisins et changent le leur. Les mutex sont relachés.

Il y a peut-être un moyen de synchro plus approprié mais tu peux commencer à implémenter des solutions de test.

[corrector]

L'exemple du jeux de la vie étant concret, je te propose une solution (qui n'est peut-être pas excellente, je ne suis pas un gourou).

Tu as un tableau n x p représentant ton jeux. A chaque case tu affecte un thread et un mutex.

Mais c'est absolument monstrueux.

Tu as essayé, jusqu'où peux-tu aller au max(n*p) avant d'exploser l'espace d'adressage?

[hyphens]

Mais c'est absolument monstrueux.

Tu as essayé, jusqu'où peux-tu aller au max(n*p) avant d'exploser l'espace d'adressage?

Oui 382...

Tu as un tableau n x p représentant ton jeux. A chaque case tu affecte un thread et un mutex.

Tous les thread on la même implémentation. Il "prennent" le mutex des 8 voisins plus le leur. Il lisent l'état des 8 voisins et changent le leur. Les mutex sont relachés.

Il y a peut-être un moyen de synchro plus approprié mais tu peux commencer à implémenter des solutions de test.

Ce que j'ai fait! Et comme je le craignais le délai entre la demande de blocage et le blocage effectif induit un deadlock à chaque fois...

Un mot sur mon implémentation:
Une classe Thread dont une méthode virtuelle pure est exécutée par le pthread en lui-même
Une implémentation Cellule qui hérite donc de Thread
Une collection de Thread* qui hérite de ma classe Singleton qui fabrique via héritage des singletons
Une matrice n*p avec l'état des cellules PCMatrice elle aussi un singleton

Du coup chaque Cellule dans son constructeur fait:

Code :

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

1
2
3
4
 
//Récupération des ressources partagées 
mMatrice=PCMatrice::GetInstance();
mCellules=ThreadCompositeSingleton::GetInstance();

Et peut du coup modifier la matrice ou l'état des autres threads...

J'essaie donc d'implémenter deux méthodes Pause et Reprise dans ma classe Thread, avec ta méthode valefor c'est simplement un lock (resp) unlock sur le mutex (donnée membre de Thread)

Le code de Traitement est:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void *Traitement(){
	mExecution=true;
	for(unsigned int i=0; i<10; i++){
		mVerrou.Lock();
		BloquerVoisines();
		RegleJeuDeLaVie();
		DebloquerVoisines();
		mVerrou.Unlock();
		cout<<"La cellule ("<<mLigne<<","<<mColonne<<") a fait "<<i<<" itérations"<<endl;
	}
	mExecution=false;
	return NULL;
}

BloquerVoisines() fait 8 lock sur les threads ce qui les arrêtes, le problème est qu'avant d'être arrétés il font la même chose, du coup il s'entrebloquent tous...

Démarrage du jeu de la vie
--------
|x x x |
|x x |
|x |
--------
Je suis la cellule (0,0) et je bloque mes voisines
(0,0)Blocage de (1,1)
(0,0)Blocage de (1,0)
(0,0)Blocage de (1,2)
(0,0)Blocage de (0,1)
(0,0)Blocage de (0,2)
Je suis la cellule (0,1) et je bloque mes voisines
(0,1)Blocage de (1,0)
(0,1)Blocage de (1,0)
Je suis la cellule (0,2) et je bloque mes voisines
(0,2)Blocage de (1,0)
Je suis la cellule (1,0) et je bloque mes voisines
(1,0)Blocage de (0,1)
Je suis la cellule (1,1) et je bloque mes voisines
(1,1)Blocage de (0,0)
Je suis la cellule (1,2) et je bloque mes voisines
(1,2)Blocage de (0,0)
Je suis la cellule (2,0) et je bloque mes voisines
(2,0)Blocage de (0,1)
Je suis la cellule (2,1) et je bloque mes voisines
(2,1)Blocage de (0,0)
Je suis la cellule (2,2) et je bloque mes voisines
(2,2)Blocage de (0,0)

Ici on voit bien que toutes les cellules finissent bloquées... Je ne vois pas comment contourner le problème avec des sémaphores!
Ma méthode avec les signaux marche un peu mieux mais là aussi, celà tourne en deadlock (le code a le temps de s'exécuter un peu!!!)

[hyphens]

En fait, ma méthode semble marcher, les deadlocks que je constate viennent d'une méthode que je viens de développer ce matin (pour le traitement toroïdal de la matrice) et qui a un comportement très bizarre:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
	couple Coordonnees(int i, int j) const{
		cout<<"\t("<<mLigne<<","<<mColonne<<") Les coordonnées pour ("<<i<<","<<j<<") sont ";
		couple cp;
		cp.l=i; cp.c=j;
		if(i<0) cp.l=mNbLignes-1;
		if(i>mLigne-1) cp.l=0;
		if(j<0) cp.c=mNbColonnes-1;
		if(j>mColonne-1) cp.c=0;
		cout<<"("<<cp.l<<","<<cp.c<<")"<<endl;
		return cp;
	}

avec

Code :

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

1
2
3
4
5
 
	struct couple{
		unsigned int l;
		unsigned int c;
	};

Pour une raison obscure elle me retourne n'importe quoi!

Je suis la cellule (0,0) et je bloque mes voisines
(0,0) Les coordonnées pour (-1,-1) sont (3,3)
(0,0) Les coordonnées pour (-1,0) sont (3,0)
(0,0) Les coordonnées pour (-1,1) sont (3,1)
(0,0) Les coordonnées pour (0,-1) sont (0,3)
(0,0) Les coordonnées pour (0,1) sont (0,1)
(0,0) Les coordonnées pour (1,-1) sont (1,3)
(0,0) Les coordonnées pour (1,0) sont (1,0)
(0,0) Les coordonnées pour (1,1) sont (1,1)
(0,0) Blocage de (1,1)
(0,0) Blocage de (1,0)
(0,0) Blocage de (1,3)
(0,0) Blocage de (0,1)
Je suis la cellule (0,1) et je bloque mes voisines
(0,1) Les coordonnées pour (-1,0) sont (3,0)
(0,1) Les coordonnées pour (-1,1) sont (3,0)
(0,1) Les coordonnées pour (-1,2) sont (3,0)
(0,1) Les coordonnées pour (0,0) sont (0,0)
(0,1) Les coordonnées pour (0,2) sont (0,0)
(0,1) Les coordonnées pour (1,0) sont (1,0)
(0,1) Les coordonnées pour (1,1) sont (1,0)
(0,1) Les coordonnées pour (1,2) sont (1,0)
(0,1) Blocage de (1,0)

Quand la cellule (0,1) s'en sert elle retourne la même chose pour des coordonnées différentes (genre les 3 (3,0) à la suite....) Ca ressemble foutrement à des pointeurs qui se prennent les pieds dans le tapis du salon mais dans ce cas précis je sèche...

[valefor]

Code :

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

mVerrou.Lock();

Cela bloque le verrou de la cellule en cours ?

Hé bien à la limite j'aurais pris un verrou global que tu prends avant de prendre les verrous et que tu lâches après. Cad que dans "BloquerVoisines();" j'aurai aussi pris le verrou de la cellule courante, et j'aurai protégé le code de la fonction par un verrou statique.

[screetch]

la regle d'or pour les blocages est de tous les faire dans le meme ordre. par exemple :

A et B sont deux threads, avec deux locks a et b.

A veut locker a et b
B veut locker b et a

alors les instructions sont :
A:
a.lock()
b.lock()

B:
b.lock()
a.lock()

mettons que A est interrompu juste apres a.lock() et B est interrompu juste apres b.lock()
alors :
a est verrouillé
b est verrouillé.
dans la suite, A va attendre que b se libere, et B va attendre que a se libere : deadlock.

pour que ton programme marche tu dois definir un ordre de blocage. le plus simple est de travailler sur les coordonnées et de dire que pour locker, tu fais suivant lex x et y croissants (Y COMPRIS LA CELLULE CENTRE). retire donc le cas special de la cellule centre.