Pthread Programm Deadlocks Bedingungsvariablen mit

Question

Was dieses Programm zu erreichen versucht:

Dieses Programm soll mehrere Threads von „Besucher“ und „Autos“ synchronisieren. Besucher wandern für eine zufällige Zeit herum, bis sie sich entscheiden, eine Autofahrt zu unternehmen. Wenn sie für eine Autofahrt an der Reihe sind und ein Auto zur Verfügung steht, fahren sie mit, sonst müssen sie warten, bis sie an der Reihe sind oder ein Auto zurückkommt. Wenn keine Besucher in der Schlange stehen, warten die Autos, bis ein Besucher mitfahren möchte.

Weitere Hintergrundinformationen:

ich meinen Thread Synchronisationsprogramm neu gemacht Variablen Zustand als here in der akzeptierten Antwort vorgeschlagen. Ich weiß, dass ich auf dem richtigen Weg bin, aber mein Programm ist aus irgendeinem Grund immer noch blockiert, und für das Leben von mir kann ich nicht herausfinden warum. Ich weiß nicht, wie Sie mir helfen, wenn ich Dir den Code geben, so ist es hier:

Probleme:

1.) Deadlock nach kurzer Bit

2.) manchmal Ein Besucher ist der Erste für ein Auto, kommt aber nie in ein Auto.

Die Lösung:

Es war einfach zu viele Fehler in meinem Code ... und ich denke, wie ich eine beheben würde ich oft war (versehentlich) einen anderen einzuführen. Ich entfernte einfach die Funktionen des Programms, bis ich alle Fehler beseitigt hatte, und baute die Funktionen dann nacheinander so auf, dass mein Programm nicht blockiert wurde. Danke Ihnen allen für Ihre Vorschläge.

Answer 1

Erstens ist xscott korrekt, dass Sie Mutexe falsch verwenden. Es spielt keine Rolle, ob es für eine kurze Zeit zu funktionieren scheint, es ist immer noch falsch, und es scheint, als würde es nur aus Zufall funktionieren.

Anstatt Ihren Code Zeile für Zeile durchzugehen, denke ich, dass der beste Ansatz darin besteht, das Design aus den ersten Prinzipien aufzubauen. Ich würde den grundlegenden Algorithmus beschreibt, dass ich glaube, Sie nach wie dies sind:

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 
} 

Bitte beachte, dass ich nicht explizit die Wake-up-Punkte markiert - nur die Wartezeiten. Dies ist der beste Ansatz - herauszufinden, wo Sie auf etwas warten müssen, um den Status zu ändern, dann müssen Sie nur die Wakeups setzen (die Zustandsvariable signalisieren), wenn sich dieser Status ändert.

Der nächste Schritt wäre die Identifizierung der wichtigsten gemeinsam genutzten Daten, die durch Mutexe geschützt werden müssen. Ich sehe:

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

So ist der detaillierteste Ansatz einen Mutex für die Besucher Schlange zu haben wäre (wir Ihre v_mutex verwenden können), eine für die Auto-Warteschlange (c_mutex) und einem für jedes Auto (sc[CARS]). Alternativ können Sie c_mutex verwenden, um die Wagenwarteschlange und den Status jedes Autos zu schützen; oder einfach v_mutex verwenden, um alles zu schützen. Aber um zu lernen, gehen wir mit dem komplizierteren Ansatz.

Der nächste Schritt besteht darin, die Wartepunkte zu identifizieren, an denen Zustandsvariablen nützlich sein werden. Für wait until at head of visitor queue werden Ihre pro-Besucher-Zustandsvariablen (v_cond) in Ordnung sein; Für wait until there is a car free wird es am einfachsten sein, eine weitere Zustandsvariable hinzuzufügen (v_car_cond). Für wait until occupied sind die pro-Fahrzeug-Zustandsvariablen c_cond geeignet. Für wait until not in car anymore könnte entweder v_cond oder c_cond verwendet werden, da es an diesem Punkt einen 1-zu-1-Nexus zwischen Autos und Besuchern gibt. Es besteht keine Notwendigkeit für v_cond2.

Wir können jetzt den obigen Pseudo-Code in Bezug auf Pthreads-Primitive neu schreiben. In den meisten Fällen ist dies sehr in der Nähe von dem, was Sie bereits hatten - also waren Sie definitiv auf dem richtigen Weg.Zunächst wird der Besucher:

/* 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]); 

Zweitens das Auto:

/* 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]); 

Die oben vereinfacht werden kann - überall dort, wo ein pthread_mutex_unlock() sofort von einem pthread_mutex_lock() des gleichen Mutex gefolgt, die Unlock/Lock Paar entfernt werden.

PS:

Sie sollten sich keine Sorgen über Ihre Autos das Auto Warteschlange in der „falschen Reihenfolge“ joining - sie gehen aus, um zu bekommen, da sie ohnehin rund um den Park rumpeln. Wenn Sie sich wirklich darum kümmern, legen Sie die Autos in die Warteschlange im Hauptthread, bevor Sie einen der Autothreads starten, und ändern Sie den Fahrzeugcode so, dass er sich am Ende der Hauptschleife wieder in die Warteschlange einfügt.

---

Der Gesamtcode mit diesem Ansatz, der globalen Variablen und Helferfunktionen auslassen, die in Ordnung sind, sieht wie folgt aus:

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; 
} 

Ich hoffe, dass dies hilfreich ist ...

Answer 2

Sie haben eine Menge Code, also ist es unwahrscheinlich, dass irgendjemand alle Fehler für Sie findet. Allerdings ein paar Kommentare:

Mutexe sind keine Semaphoren. Einige Ihrer for-Schleifen in main() entsperren einen Mutex, den Sie noch nicht gesperrt haben. Dies ist mit ziemlicher Sicherheit ein Fehler. Konzeptionell könnten Mutexe mit Semaphoren implementiert werden, und Sie könnten einen Semaphor mit Mutex und Condvar implementieren, aber Sie entsperren einen entsperrten Mutex, und das ist falsch.

Jeder Thread sollte einen Mutex sperren, etwas arbeiten und dann entsperren. Ein Thread sollte einen Mutex, der von einem anderen Thread gesperrt wurde, nicht entsperren oder einen Mutex, den er nicht gesperrt hat, vorläufig entsperren. Wenn das überhaupt funktioniert, ist das eine Eigenart in der Implementierung, die Sie gerade verwenden, und nicht für andere Implementierungen.

Ihre zweite for-Schleife in Hauptsperren den gleichen Mutex zweimal in Folge. Kommen Sie über diesen Punkt im Code hinaus? Da Sie eine Schleife erstellen, sperren Sie sie mehr, als Sie sie entsperren. Ich wäre nicht überrascht, wenn dein Code hier aufhört. (Manchmal können Mutexe rekursiv sein, aber Pthread-Mutexe sind nicht standardmäßig.)

pthread_cond_signal() ist eigentlich nur eine Optimierung über pthread_cond_broadcast(). Nutze die Übertragung, bis deine Rennbedingungen erfüllt sind.

Sie sollten alle Ihre Mutexe und Condvars am Anfang von Main initialisieren, bevor Sie Ihre Threads starten. Es ist möglich, dass Sie hier keinen Fehler haben, aber es wird nicht schaden, und es könnte helfen.

Sie könnten es besser machen, wenn Sie für einen kurzen Zeitraum alles auf einen einzigen Mutex und einen einzigen Condvar reduzieren. Es sieht so aus, als ob Sie versuchen, feinkörniges Locking mit allem zu machen, aber wenn Sie nicht wirklich auf die Reihenfolge Ihrer Locks achten, werden Sie mit Race Conditions und Deadlocks konfrontiert.

Wirklich, es ist nur ein Muster/Vorlage, die Sie mit mutexes und condvars verwenden sollten:

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(...); 

Wenn Sie ein einzelnes Mutex und condvar haben, sollten Sie versuchen, alle Synchronisationsblöcke so aussehen zu machen. Sie können die while (...)/wait-Funktion weglassen, wenn Sie nicht warten müssen, und Sie können die Übertragung auslassen, wenn sich keine anderen Threads um die Änderung kümmern, aber wenn Ihr Code nicht grob aussieht Für jeden Synchronisationsblock ist das wahrscheinlich ein Fehler.

Answer 3

Ich denke, Sie sind wohler mit Semaphoren. Hier ist eine Implementierung von Semaphoren in Bezug auf mutexes und 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); 
} 

Vielleicht, wenn Sie Ihre Lösung in Bezug auf die Semaphore implementieren, können Sie die Ergebnisse sind Sie nach bekommen.