Sujet Précédent Sujet Suivant

Plus court chemin entre deux noued d'un graphe avec muti Thread

boubakri.ab Messages postés 1 Date d'inscription samedi 18 août 2007 Statut Membre Dernière intervention 10 novembre 2013 - 10 nov. 2013 à 00:21
cptpingu Messages postés 3837 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 28 mars 2023 - 10 nov. 2013 à 01:54
salut à tous,

j'ai un petit souci avec mon premier programme de Thread

j'ai un graphe de 10 noeuds relier entre eux avec des arcs avec une tableaux 10X10 de liaisons et leurs temps de parcours

mon programme et commence à lire le noeud d'entrée et sortie
puis le main commence à lire la ligne correspondant à noeud d'entrée à chaque fois qu'il trouve un lien valide (valeur Tableau[Départ ][i] !=0 )il crée un thread de parcours vers cet nouvelles noeud cette noeud devient elle même ma nouvelle noeud de départ
à chaque thread nouvellement crée je dois lui passer une structure de donnée construite par le thread parent à partir de ma tableau de liaison contenant le Noeud parent (départ) le Noeud destination valeur de [i] le valeur du tableau [depart][i]

j'ai deux questions dans le deuxième niveau d'exécution j'ai plusieurs thread qui peuvent être crée avec différent thread parent comment dois choisir l'index de mon thread
et commet crée ma structure qui je dois passer aux thread .



#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdbool.h>
#include <pthread.h>
#include <math.h>
#include <errno.h>

// Multi-threaded code checking the speedest trajet betwen two node

#define DEBUG 0

// Number of nodes
#define NODE_COUNT 10

int start; // start node
int end; // end node

// Stores the distance between each node
int distances[NODE_COUNT][NODE_COUNT] = {
{0,2,5,0,0,2,1,0,0,0}, //Noeud N°1
{1,0,3,0,0,0,0,0,3,0}, //Noeud N°2
{0,0,0,2,0,0,1,0,0,1}, //Noeud N°3
{0,0,0,0,3,0,0,0,0,0}, //Noeud N°4
{3,0,0,1,0,0,0,1,0,0}, //Noeud N°5
{0,0,0,5,3,0,1,0,0,0}, //Noeud N°6
{0,0,0,0,0,0,0,1,3,0}, //Noeud N°7
{2,0,0,0,0,2,0,0,0,1}, //Noeud N°8
{0,0,1,0,0,4,0,0,0,1}, //Noeud N°9
{0,0,0,3,1,0,2,0,0,0}};//Noeud N°10

// Indicates whether a node was visited
bool visits[] = {false, false, false, false, false, false, false, false, false, false};
pthread_t *threads;
int thread_count;

struct param_st {
int thread_idx;
int sleep_value;
int new_depart;
};

typedef struct param_st param;

void cancel_threads(pthread_t initiator) {
// Make sure a thread cancelling other threads can't get cancelled!
pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, NULL);

int i;
for ( i = 0; i < thread_count; i++) {
pthread_t thread = threads[i];

// Skip non-created threads and ourselves
if (thread == 0 || thread == initiator)
continue;
#if DEBUG
printf("Thread %ld: canceling thread %ld\n", initiator, thread);
#endif
// A return code of ESRCH means the thread has already finished
// (the ESRCH constant is defined in errno.h)
int code = pthread_cancel(thread);
if (code != 0 && code != ESRCH) {
fprintf(stderr, "pthread_cancel error %ld!\n", thread);
exit(EXIT_FAILURE);
}
}
}

void *next_step(void *parameter) {
// Make the thread cancellable anytime/anywhere
// NOTE: Setting the 2nd params to NULL is implementation SPECIFIC!
pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, NULL);
pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, NULL);

param *p = (param *) parameter;
pthread_t me = threads[p->thread_idx];


#if DEBUG
printf("Thread %ld: checking divisors in [%ld,%ld]\n", me, p->first, p->last);
#endif
sleep(p->sleep_value);
if (visits[p->new_depart] == false)
{
visits[p->new_depart] = true ;
if (p->new_depart == end)
exit(0);
else
{
for (int i = 0; i < NODE_COUNT ; i++) {
if ((distances[p->new_depart][i] != 0) &&(!visits[i])) {
parameter[i].thread_idx;
parameter[i].sleep_value = distances[p->new_depart][i];
parameter[i].new_depart = i;

#if DEBUG
printf("Thread %ld: %ld divide %ld\n", me, i, number);
#endif

int code = pthread_create(&threads[p->thread_idx], NULL, next_step, ¶meter[i]);
if (code != 0) {
fprintf(stderr, "pthread_create failed!\n");
return EXIT_FAILURE;
}
cancel_threads(me);
break;
}
}}
}
return NULL;
}

void init(int argc, char **argv) {
if (argc != 3) {
fprintf(stderr, "Syntax Error: %s <First Node> <#Last Node>\n", argv[0]);
exit(EXIT_FAILURE);
}

start = (int) atoi(argv[1]);
end = (int) atoi(argv[2]);
threads = (pthread_t *) malloc(sizeof(pthread_t)* NODE_COUNT);
// Initialize all thread ids to zero
int i;
for (i = 0; i < NODE_COUNT; i++)
threads[i] = 0;

}

int main(int argc, char **argv) {
init(argc, argv);
int i;
//int sleep_value = 0;
//int new_depart = 0;

param params[NODE_COUNT];
params[0].thread_idx = 0;
params[0].sleep_value = 0;
params[0].new_depart = start;


int code = pthread_create(&threads[0], NULL, next_step, ¶ms[0]);
if (code != 0) {
fprintf(stderr, "pthread_create failed!\n");
return EXIT_FAILURE;
}



free(threads);
threads = NULL;

return EXIT_SUCCESS;
}

1 réponse

Réponse 1 / 1
cptpingu Messages postés 3837 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 28 mars 2023 123
10 nov. 2013 à 01:54
Bonjour.

Merci d'éditer ta question afin de:
- Indenter ton code.
- Colorer ton code via les "balises de code".
0
Rejoignez-nous