programme Pthread utilisant des variables blocages état

Question

Qu'est-ce que ce programme tente d'accomplir:

Ce programme est censé synchroniser plusieurs threads de « visiteurs » et « voitures ». Les visiteurs se promènent pendant une période aléatoire jusqu'à ce qu'ils décident de faire un tour en voiture. S'ils sont en première ligne pour un trajet en voiture et qu'une voiture est disponible, ils font un tour, sinon ils doivent attendre jusqu'à ce qu'ils soient en première ligne ou qu'une voiture revienne. S'il n'y a pas de visiteurs en ligne, les voitures attendent dans l'ordre jusqu'à ce qu'un visiteur veuille faire un tour.

Plus d'informations de fond:

Je refit mon programme de synchronisation des threads en utilisant les variables de condition comme suggéré dans la réponse acceptée here. Je sais que je suis sur la bonne voie, mais mon programme reste bloquant pour une raison quelconque et pour la vie de moi, je ne peux pas comprendre pourquoi. Je ne sais pas comment vous pouvez me aider à moins que je vous donne le code, si elle est ici:

Problèmes:

1.) après une courte impasse peu

2.) parfois un visiteur est en première ligne pour une voiture, mais ne monte jamais dans une voiture.

La solution:

Il y avait tout simplement trop de bugs dans mon code ... et je pense que je fixerais que j'étais souvent (involontairement) l'introduction d'un autre. Je continuais simplement à supprimer les fonctionnalités du programme jusqu'à ce que j'aie éliminé tous les bogues, puis je construisais les fonctionnalités une par une d'une manière qui ne bloquait pas mon programme. Merci à tous pour vos suggestions.

Answer 1

Premièrement, xscott a raison d'utiliser incorrectement les mutex. Cela n'a pas d'importance si cela semble fonctionner pendant un petit moment, c'est toujours faux, et ne semble fonctionner que par hasard. Plutôt que de parcourir votre code ligne par ligne, je pense que la meilleure approche consiste à construire la conception à partir des principes premiers. Je dirais que l'algorithme de base que je pense que vous êtes après comme ceci:

visitor { 
    sleep 
    join end of visitor queue 
    wait until at head of visitor queue 
    wait until there is a car free 
    remove car from car queue 
    remove self from visitor queue 
    occupy car 
    wait until not in car anymore 
} 

car { 
    join end of car queue 
    wait until occupied 
    sleep 
    eject visitor from car 
} 

Notez que je ne marque pas explicitement les points de réveil - seulement les attend. C'est la meilleure approche - comprendre où vous devez attendre que quelque chose change d'état, alors vous avez juste besoin de mettre les wakeups (signalant la variable de condition) chaque fois que cet état change. L'étape suivante consisterait à identifier les principales données partagées qui doivent être protégées par des mutex. Je vois:

- The visitor queue; 
- The car queue; 
- The status of each car. 

donc l'approche la plus granulaire serait d'avoir un mutex pour la file d'attente des visiteurs (nous pouvons utiliser votre v_mutex), un pour la file d'attente de voiture (c_mutex) et un pour chaque voiture (sc[CARS]). Alternativement, vous pouvez utiliser c_mutex pour protéger la file d'attente de voiture et le statut de chaque voiture; ou utilisez simplement v_mutex pour tout protéger. Mais pour apprendre, nous suivrons l'approche plus compliquée.

L'étape suivante consiste à identifier les points d'attente où les variables de condition seront utiles. Pour wait until at head of visitor queue, vos variables de condition par visiteur (v_cond) conviennent; pour wait until there is a car free, il sera plus facile d'ajouter une autre variable de condition (v_car_cond). Pour wait until occupied, les variables d'état par voiture c_cond sont appropriées. Pour wait until not in car anymore soit v_cond ou c_cond pourrait être utilisé, car il existe un lien 1-à-1 entre les voitures et les visiteurs à ce moment-là. Il n'y a pas besoin de v_cond2.

Nous pouvons maintenant réécrire le pseudo-code ci-dessus en termes de primitives pthreads. Dans la plupart des cas, c'est très proche de ce que vous aviez déjà - donc vous étiez définitivement sur la bonne voie.Tout d'abord le visiteur:

/* join end of visitor queue */ 
    pthread_mutex_lock(&v_mutex); 
    v_line[v_id] = set_visitor_place_in_line(); 
    printf("Visitor %d is %d in line for a ride\n", v_id, v_line[v_id]); 
    pthread_mutex_unlock(&v_mutex); 

    /* wait until first in line */ 
    pthread_mutex_lock(&v_mutex); 
    while (v_line[v_id] != 1) { 
     pthread_cond_wait(&v_cond[v_id], &v_mutex); 
    } 
    pthread_mutex_unlock(&v_mutex); 

    /* wait until there is a car free */ 
    pthread_mutex_lock(&c_mutex); 
    while ((car = get_next_car()) == CARS) { 
     pthread_cond_wait(&v_car_cond, &c_mutex); 
    } 
    pthread_mutex_unlock(&c_mutex); 

    /* remove car from car queue */ 
    pthread_mutex_lock(&c_mutex); 
    move_car_line(); 
    /* NOTE: We do not need to signal v_car_cond here, because only the first 
    * visitor in line can be waiting there, and we are still the first visitor 
    * in line at this point. */ 
    pthread_mutex_unlock(&c_mutex); 

    /* remove self from visitor queue */ 
    pthread_mutex_lock(&v_mutex); 
    move_passenger_line(); 
    next_v = get_next_passenger(); 
    if (next_v < VISITORS) 
     pthread_cond_signal(&v_cond[next_v]); 
    pthread_mutex_unlock(&v_mutex); 

    /* occupy car */ 
    pthread_mutex_lock(&sc[car]); 
    c_state[car] = v_id; 
    pthread_cond_signal(&c_cond[car]); 
    pthread_mutex_unlock(&sc[car]); 

    /* wait until not in car anymore */ 
    pthread_mutex_lock(&sc[car]); 
    while(c_state[car] == v_id) { 
     pthread_cond_wait(&v_cond[v_id], &sc[car]); 
    } 
    pthread_mutex_unlock(&sc[car]); 

En second lieu, la voiture:

/* join end of car queue */ 
    pthread_mutex_lock(&c_mutex); 
    c_line[c_id] = set_car_place_in_line(); 
    if (c_line[c_id] == 1) 
     pthread_cond_signal(&v_car_cond); 
    pthread_mutex_unlock(&c_mutex); 

    /* wait until occupied */ 
    pthread_mutex_lock(&sc[c_id]); 
    while ((v_id = c_state[c_id]) == VISITORS) { 
     pthread_cond_wait(&c_cond[c_id], &sc[c_id]); 
    } 
    pthread_mutex_unlock(&sc[c_id]); 

    /* visitor is on car ride for random amount of time */ 
    sleep(rand()%5); 

    /* eject visitor from car */ 
    pthread_mutex_lock(&sc[c_id]); 
    c_state[c_id] = VISITORS; 
    pthread_cond_signal(&v_cond[v_id]); 
    pthread_mutex_unlock(&sc[c_id]); 

ci-dessus peut être simplifiée - partout où il y a un pthread_mutex_unlock() immédiatement suivi par un pthread_mutex_lock() du même mutex, le déverrouillage/paire verrouillage peut être retiré.

PS:

Vous ne devriez pas vous soucier de votre voiture se joindre à la file d'attente de voiture dans le « mauvais ordre » - ils vont sortir de l'ordre qu'ils Trundle autour du parc de toute façon. Si cela vous intéresse vraiment, placez les voitures dans la file d'attente dans le fil principal avant de démarrer l'un des threads de la voiture, et changez le code de la voiture pour qu'il s'ajoute à la file d'attente à la fin de sa boucle principale.

---

Le code général avec cette approche, en laissant vos variables globales et les fonctions d'aide qui sont très bien, ressemble à ceci:

pthread_mutex_t c_mutex = PTHREAD_MUTEX_INITIALIZER; /* mutex protecting c_line and cars_out */ 
pthread_mutex_t v_mutex = PTHREAD_MUTEX_INITIALIZER; /* mutex protecting v_line */ 
pthread_cond_t c_cond[CARS]; /* condition variables for waiting for c_state[i] to change from VISITORS to another value */ 
pthread_cond_t v_cond[VISITORS]; /* condition variables for visitor waiting to be first in line or ejected from a car */ 
pthread_cond_t v_car_cond = PTHREAD_COND_INITIALIZER; /* Condition variable for a visitor first in line, but waiting for a car. */ 
pthread_mutex_t sc[CARS]; /* one mutex per car, sc[i] protects c_state[i] */ 

int main(){ 
    int i; 
    void *status; 
    pthread_t c[CARS]; 
    pthread_t v[VISITORS]; 

    srand(time(NULL)); 

    printf("Jurassic Park is open, cars are being prepped for passengers\n"); 

    for (i = 0; i < CARS; i++){ 
     pthread_mutex_init(&sc[i], NULL); 
     pthread_cond_init(&c_cond[i], NULL); 
    } 

    for (i = 0; i < VISITORS; i++){ 
     pthread_cond_init(&v_cond[i], NULL); 
    } 

    for (i = 0; i < CARS; i++){ 
     c_state[i] = VISITORS; 
     pthread_create(&c[i], NULL, car, (void *)i); 
    } 

    for (i = 0; i < VISITORS; i++){ 
     pthread_create(&v[i], NULL, visitor, (void *)i); 
    } 

    for (i = 0; i < VISITORS; i++){ 
     pthread_join(v[i], &status); 
    } 

    museum_empty++; 

    printf("All visitors have left Jurassic Park\n"); 

    for (i = 0; i < CARS; i++){ 
     pthread_mutex_lock(&sc[i]); 
     c_state[i] = -1; 
     pthread_cond_signal(&c_cond[i]); 
     pthread_mutex_unlock(&sc[i]); 
    } 

    for (i = 0; i < CARS; i++){ 
     pthread_join(c[i], &status); 
    } 

    printf("Jurrasic Park is closed, all cars have been parked\n"); 

    pthread_exit(NULL); 

    return 0; 
} 

void *car(void *i) 
{ 
    int c_id = (int) i; 
    int v_id; 

    while (museum_empty != 1) { 

     /* join end of car queue */ 
     pthread_mutex_lock(&c_mutex); 
     c_line[c_id] = set_car_place_in_line(); 
     if (c_line[c_id] == 1) 
      pthread_cond_signal(&v_car_cond); 
     printf("Car %d is ready for a passenger and is %d in line      %d of %d cars are out\n", c_id, c_line[c_id], cars_out, CARS); 
     pthread_mutex_unlock(&c_mutex); 

     /* wait until occupied */ 
     pthread_mutex_lock(&sc[c_id]); 
     while ((v_id = c_state[c_id]) == VISITORS) { 
      pthread_cond_wait(&c_cond[c_id], &sc[c_id]); 
     } 
     pthread_mutex_unlock(&sc[c_id]); 

     if(museum_empty == 1){ 
      break; 
     } 

     pthread_mutex_lock(&c_mutex); 
     cars_out++; 
     printf("Visitor %d is riding in car %d           %d of %d cars are out --\n", v_id, c_id, cars_out, CARS); 
     pthread_mutex_unlock(&c_mutex); 

     /* visitor is on car ride for random amount of time */ 
     sleep(rand()%5); 

     printf("Visitor %d is done riding in car %d\n", v_id, c_id); 

     /* eject visitor from car */ 
     pthread_mutex_lock(&sc[c_id]); 
     c_state[c_id] = VISITORS; 
     pthread_cond_signal(&v_cond[v_id]); 
     pthread_mutex_unlock(&sc[c_id]); 

     pthread_mutex_lock(&c_mutex); 
     cars_out--; 
     pthread_mutex_unlock(&c_mutex); 
    } 

    return NULL; 
} 

void *visitor(void *i) 
{ 
    int v_id = (int) i; 
    int next_v; 
    int j = 0; 
    int car; 

    while (j < RIDES) { 
     if (j == 0) { 
      printf("Visitor %d entered museum and is wandering around\n", v_id); 
     } else { 
      printf("Visitor %d got back from ride and is wandering around\n", v_id); 
     } 

     sleep(rand()%3); /* visitor is wandering */ 

     /* join end of visitor queue */ 
     pthread_mutex_lock(&v_mutex); 
     v_line[v_id] = set_visitor_place_in_line(); 
     printf("Visitor %d is %d in line for a ride\n", v_id, v_line[v_id]); 

     /* wait until first in line */ 
     while (v_line[v_id] != 1) { 
      pthread_cond_wait(&v_cond[v_id], &v_mutex); 
     } 
     pthread_mutex_unlock(&v_mutex); 

     /* wait until there is a car free */ 
     pthread_mutex_lock(&c_mutex); 
     while ((car = get_next_car()) == CARS) { 
      pthread_cond_wait(&v_car_cond, &c_mutex); 
     } 

     /* remove car from car queue */ 
     move_car_line(); 
     pthread_mutex_unlock(&c_mutex); 

     /* remove self from visitor queue */ 
     pthread_mutex_lock(&v_mutex); 
     move_passenger_line(); 
     next_v = get_next_passenger(); 
     if (next_v < VISITORS) 
      pthread_cond_signal(&v_cond[next_v]); 
     pthread_mutex_unlock(&v_mutex); 

     /* occupy car */ 
     pthread_mutex_lock(&sc[car]); 
     c_state[car] = v_id; 
     pthread_cond_signal(&c_cond[car]); 

     /* wait until not in car anymore */ 
     /* NOTE: This test must be against v_id and *not* VISITORS, because the car could have been 
     * subsequently occupied by another visitor before we are woken. */ 
     while(c_state[car] == v_id) { 
      pthread_cond_wait(&v_cond[v_id], &sc[car]); 
     } 
     pthread_mutex_unlock(&sc[car]); 

     j++; 
    } 

    printf("Visitor %d leaving museum.\n", v_id); 
    return NULL; 
} 

J'espère que cela est utile ...

Answer 2

Vous avez beaucoup de code, donc il est peu probable que quelqu'un trouve tous les bugs pour vous. Cependant, quelques commentaires:

Les mutex ne sont pas des sémaphores. Plusieurs de vos boucles for dans main() débloquent un mutex que vous n'avez pas encore verrouillé. C'est presque certainement une erreur. Conceptuellement, les mutex peuvent être implémentés avec des sémaphores, et vous pouvez implémenter un sémaphore avec un mutex et une condvar, mais vous déverrouillez un mutex déverrouillé, ce qui est incorrect. Chaque thread doit verrouiller un mutex, travailler, puis le déverrouiller. Un thread ne doit pas déverrouiller un mutex qui a été verrouillé par un autre thread, ou débloquer de manière préventive un mutex qu'il n'a pas verrouillé. Si cela fonctionne, c'est une anomalie dans l'implémentation que vous utilisez actuellement et non portable pour d'autres implémentations. Votre seconde boucle for principale bloque le même mutex deux fois de suite. Avez-vous dépassé ce point dans le code? Puisque vous êtes en boucle, vous le verrouillez plus que vous ne le déverrouillez. Je ne serais pas surpris si votre code s'arrête ici. (Parfois, les mutex peuvent être récursifs, mais les mutex pthread ne le sont pas par défaut.)

pthread_cond_signal() est vraiment juste une optimisation par rapport à pthread_cond_broadcast(). Utilisez la diffusion jusqu'à ce que vous obteniez vos conditions de course.

Vous devez initialiser tous vos mutex et condvars en haut de la main avant de démarrer vos threads. Il est possible que vous n'ayez pas d'erreur ici, mais cela ne fera pas de mal, et cela pourrait aider.

Vous pourriez faire mieux si vous réduisez tout à un seul mutex et une seule condvar à court terme. On dirait que vous essayez de faire du verrouillage à grain fin avec tout, mais à moins que vous soyez vraiment prudent sur l'ordre de vos serrures, vous allez avoir des conditions de course et une impasse.

Vraiment, il n'y a qu'un seul modèle/modèle que vous devez utiliser avec mutex et condvars:

pthread_mutex_lock(...); 

// optionally wait for something to be true 
while (!some_condition) { 
    pthread_cond_wait(...); 
} 

// make changes for how things should now be 
shared_variable = new_value; 

// optionally notify the rest of the world of your change 
pthread_cond_broadcast(...); 

pthread_mutex_unlock(...); 

Si vous avez un mutex et CondVar, vous devriez essayer de faire tous les blocs de synchronisation ressemblent à cela. Vous pouvez omettre le moment (...)/attendre des choses si vous n'avez pas besoin d'attendre, et vous pouvez omettre la diffusion si aucun autre sujet ne se soucie du changement que vous avez fait, mais si votre code ne ressemble pas comme ça pour chaque bloc de synchronisation, c'est probablement un bug.

Answer 3

Je pense que vous êtes plus à l'aise avec les sémaphores. Voici une implémentation de sémaphores en termes de mutex et condvars:

typedef struct { 
    pthread_mutex_t mutex; 
    pthread_cond_t condvar; 
    unsigned long count; 
} semaphore_t; 

void semaphore_init (semaphore_t* sem, unsigned long count) { 
    pthread_mutex_init(&sem->mutex, 0); 
    pthread_cond_init(&sem->condvar, 0); 
    pthread_mutex_lock(&sem->mutex); 
    sem->count = count; 
    pthread_mutex_unlock(&sem->mutex); 
} 

void semaphore_incr (semaphore_t* sem) { 
    pthread_mutex_lock(&sem->mutex); 
    sem->count++; 
    pthread_cond_broadcast(&sem->condvar); 
    pthread_mutex_unlock(&sem->mutex); 
} 

void semaphore_decr (semaphore_t* sem) { 
    pthread_mutex_lock(&sem->mutex); 
    while (sem->count == 0) { 
     pthread_cond_wait(&sem->condvar, &sem->mutex); 
    } 
    sem->count--; 
    pthread_mutex_unlock(&sem->mutex); 
} 

Peut-être que si vous implémentez votre solution en termes de sémaphores, vous obtiendrez les résultats que vous.