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 ...
Walls of Code wie dieser bekommt normalerweise nicht viel Aufmerksamkeit. Versuchen Sie, es auf eine minimale Teilmenge zu reduzieren, die immer noch das Problem aufweist. –
Bitte beschreiben Sie, was dieses Programm zu erreichen versucht. Welche Vorgehensweise modelliert es? Welche Regeln muss es folgen? Welche Invarianten dürfen nicht verletzt werden? Wie sehen Start- und Endzustand aus? –
Was ist das Backtrace vom Deadlock? das ist oft hilfreich –