1

I have written a multithreaded program in C using pthreads to solve the N-queens problem. It uses the producer consumer programming model. One producer who creates all possible combinations and consumers who evaluate if the combination is valid. I use a shared buffer that can hold one combination at a time.

Once I have 2+ consumers the program starts to behave strange. I get more consumptions than productions. 1.5:1 ratio approx (should be 1:1). The interesting part is that this only happens on my MacBook and is nowhere to be seen when I run it on the Linux machine (Red Hat Enterprise Linux Workstation release 6.10 (Santiago)) I have access to over SSH.

I'm quite sure that my implementation is correct with locks and conditional variables too, the program runs for 10+ seconds which should reveal if there are any mistakes with the synchronization.

I compile with GCC (Apple clang version 12.0.5) via xcode developer tools on my MacBook Pro (2020, x86_64) and GCC on Linux too, but version 4.4.7 20120313 (Red Hat 4.4.7-23).

compile: gcc -o 8q 8q.c
run: ./8q <producers> <N>, NxN chess board, N queens to place
parameters: ./8q 2 4 Enough to highlight the problem (should yield 2 solutions, but every other run yields 3+ solutions, i.e duplicate solutions exist
note: print(printouts) Visualizes the valid solutions (duplicates shown)

 
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <assert.h>

typedef struct stack_buf {
    int positions[8];
    int top;
} stack_buf;

typedef struct global_buf {
    int positions[8];
    volatile int buf_empty;
    volatile long done;
} global_buf;

typedef struct print_buf {
    int qpositions[100][8];
    int top;
} print_buf;

stack_buf queen_comb = { {0}, 0 };
global_buf global = { {0}, 1, 0 };
print_buf printouts = { {{0}}, -1 };

int N; //NxN board and N queens to place

clock_t start, stop, diff;
pthread_mutex_t buffer_mutex, print_mutex;
pthread_cond_t empty, filled;

/* ##########################################################################################
   ################################## VALIDATION FUNCTIONS ##################################
   ########################################################################################## */


/* Validate that no queens are placed on the same row */
int valid_rows(int qpositions[]) {
    int rows[N];
    memset(rows, 0, N * sizeof(int));
    int row;
    for (int i = 0; i < N; i++) {
        row = qpositions[i] / N;
        if (rows[row] == 0) rows[row] = 1;
        else return 0;
    }
    return 1;
}

/* Validate that no queens are placed in the same column */
int valid_columns(int qpositions[]) {
    int columns[N];
    memset(columns, 0, N*sizeof(int));
    int column;
    for (int i = 0; i < N; i++) {
        column = qpositions[i] % N;
        if (columns[column] == 0) columns[column] = 1;
        else return 0;
    }
    return 1;
}

/* Validate that left and right diagonals aren't used by another queen */
int valid_diagonals(int qpositions[]) {
    int left_bottom_diagonals[N];
    int right_bottom_diagonals[N];
    int row, col, temp_col, temp_row, fill_value, index;

    for (int queen = 0; queen < N; queen++) {
        row = qpositions[queen] / N;
        col = qpositions[queen] % N;
        
        /* position --> left down diagonal endpoint (index) */
        fill_value = col < row ? col : row; //min of col and row
        temp_row = row - fill_value;
        temp_col = col - fill_value;
        index = temp_row * N + temp_col; // position

        for (int i = 0; i < queen; i++) { // check if interference occurs
            if (left_bottom_diagonals[i] == index) return 0;
        }
        left_bottom_diagonals[queen] = index; // no interference

        /* position --> right down diagonal endpoint (index) */
        fill_value = (N-1) - col < row ? N - col - 1 : row; // closest to bottom or right wall
        temp_row = row - fill_value;
        temp_col = col + fill_value;
        index = temp_row * N + temp_col; // position
        
        for (int i = 0; i < queen; i++) { // check if interference occurs
            if (right_bottom_diagonals[i] == index) return 0;
        }
        right_bottom_diagonals[queen] = index; // no interference
    };
    return 1;
}

/* ##########################################################################################
   #################################### HELPER FUNCTIONS ####################################
   ########################################################################################## */

/* print the collected solutions  */
void print(print_buf printouts) {
    static int solution_number = 1;
    int placement;

    for (int sol = 0; sol <= printouts.top; sol++) { // number of solutions
        printf("Solution %d: [ ", solution_number++);
        for (int pos = 0; pos < N; pos++) {
            printf("%d ", printouts.qpositions[sol][pos]+1);
        } 
        printf("]\n");

        printf("Placement:\n");
        for (int i = 1; i <= N; i++) { // rows
            printf("[ ");
            placement = printouts.qpositions[sol][N-i];
            for (int j = (N-i)*N; j < (N-i)*N+N; j++) { // physical position
                if (j == placement) {
                    printf(" Q ");
                } else printf("%2d ", j+1);

            }
            printf("]\n");
        }
        printf("\n");
    }
    
}


/* push value to top of list instance */
void push(stack_buf *instance, int value) {
    assert(instance->top <= 8 || instance->top >= 0);
    instance->positions[instance->top++] = value;
}

/* pop top element of list instance */
void pop(stack_buf *instance) {
    assert(instance->top > 0);
    instance->positions[--instance->top] = -1;
}

/* ##########################################################################################
   #################################### THREAD FUNCTIONS ####################################
   ########################################################################################## */

static int consumptions = 0;
/* entry point for each worker (consumer)
workers will check each queen's row, column and 
diagonal to evaluate satisfactory placements */
void *eval_positioning(void *id) {
    long thr_id = (long)id;
    int qpositions[N];
    
    while (!global.done) {
        pthread_mutex_lock(&buffer_mutex);
        while (global.buf_empty == 1) {
            if (global.done) break;  // consumers who didn't get last production
            pthread_cond_wait(&filled, &buffer_mutex);
        }
        if (global.done) break;
        consumptions++;
        memcpy(qpositions, global.positions, N * sizeof(int)); // retrieve queen combination
        global.buf_empty = 1;
        pthread_cond_signal(&empty);
        pthread_mutex_unlock(&buffer_mutex);

        if (valid_rows(qpositions) && valid_columns(qpositions) && valid_diagonals(qpositions)) {
            /* save for printing later */
            pthread_mutex_lock(&print_mutex);
            memcpy(printouts.qpositions[++printouts.top], qpositions, N * sizeof(int));
            pthread_mutex_unlock(&print_mutex);
        }
    }
    return NULL;
}

static int productions = 0;
/* recursively generate all possible queen_combs */
void rec_positions(int pos, int queens) {
    if (queens == 0) { // base case
        pthread_mutex_lock(&buffer_mutex);
        while (global.buf_empty == 0) {
            pthread_cond_wait(&empty, &buffer_mutex);
        }
        productions++;
        memcpy(global.positions, queen_comb.positions, N * sizeof(int));
        global.buf_empty = 0;
        pthread_mutex_unlock(&buffer_mutex);
        pthread_cond_broadcast(&filled); // wake one worker
        return;
    }

    for (int i = pos; i <= N*N - queens; i++) {
        push(&queen_comb, i); // physical chess box
        rec_positions(i+1, queens-1);
        pop(&queen_comb);
    }
}

/* binomial coefficient | without order, without replacement
8 queens on 8x8 board: 4'426'165'368 queen combinations */
void *generate_positions(void *arg) {
    rec_positions(0, N);
    return (void*)1;
}

/* ##########################################################################################
   ########################################## MAIN ##########################################
   ########################################################################################## */

/* main procedure of the program */
int main(int argc, char *argv[]) {
    if (argc < 3) {
        printf("usage: ./8q <workers> <board width/height>\n");
        exit(1);
    }

    int workers = atoi(argv[1]);
    N = atoi(argv[2]);

    pthread_t thr[workers];
    pthread_t producer;

    // int sol1[] = {5,8,20,25,39,42,54,59};
    // int sol2[] = {2,12,17,31,32,46,51,61};
    printf("\n");
    
    start = (float)clock()/CLOCKS_PER_SEC;

    pthread_create(&producer, NULL, generate_positions, NULL);
    for (long i = 0; i < workers; i++) {
        pthread_create(&thr[i], NULL, eval_positioning, (void*)i+1);
    }

    pthread_join(producer, (void*)&global.done);
    pthread_cond_broadcast(&filled);
    for (int i = 0; i < workers; i++) {
        pthread_join(thr[i], NULL);
    }

    stop = clock();
    diff = (double)(stop - start) / CLOCKS_PER_SEC;
    
    /* go through all valid solutions and print */
    print(printouts);
    
    printf("board: %dx%d, workers: %d (+1), exec time: %ld, solutions: %d\n", N, N, workers, diff, printouts.top+1);
    printf("productions: %d\nconsumptions: %d\n", productions, consumptions);
    return 0;
}

EDIT: I have reworked sync around prod_done and made a new shared variable last_done. When producer is done, it will set prod_done and the thread currently active will either return (last element already validated) or capture the last element at set last_done to inform the other consumers.

Despite the fact that I solved the data race in my book, I still have problems with the shared combination. I have really put time looking into the synchronization but I always get back to the feeling that it should work, but it clearly doesn't when I run it.


#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <assert.h>


typedef struct stack_buf {
    int positions[8];
    int top;
} stack_buf;

typedef struct global_buf {
    int positions[8];
    volatile int buf_empty;
    volatile long prod_done;
    volatile int last_done;
} global_buf;

typedef struct print_buf {
    int qpositions[100][8];
    int top;
} print_buf;

stack_buf queen_comb = { {0}, 0 };
global_buf global = { {0}, 1, 0, 0 };
print_buf printouts = { {{0}}, -1 };
int N; //NxN board and N queens to place
long productions, consumptions = 0;

clock_t start, stop, diff;
pthread_mutex_t buffer_mutex, print_mutex;
pthread_cond_t empty, filled;


/* ##########################################################################################
   ################################## VALIDATION FUNCTIONS ##################################
   ########################################################################################## */

/* Validate that no queens are placed on the same row */
int valid_rows(int qpositions[]) {
    int rows[N];
    memset(rows, 0, N*sizeof(int));
    int row;
    for (int i = 0; i < N; i++) {
        row = qpositions[i] / N;
        if (rows[row] == 0) rows[row] = 1;
        else return 0;
    }
    return 1;
}

/* Validate that no queens are placed in the same column */
int valid_columns(int qpositions[]) {
    int columns[N];
    memset(columns, 0, N*sizeof(int));
    int column;
    for (int i = 0; i < N; i++) {
        column = qpositions[i] % N;
        if (columns[column] == 0) columns[column] = 1;
        else return 0;
    }
    return 1;
}

/* Validate that left and right diagonals aren't used by another queen */
int valid_diagonals(int qpositions[]) {
    int left_bottom_diagonals[N];
    int right_bottom_diagonals[N];
    int row, col, temp_col, temp_row, fill_value, index;

    for (int queen = 0; queen < N; queen++) {
        row = qpositions[queen] / N;
        col = qpositions[queen] % N;
        
        /* position --> left down diagonal endpoint (index) */
        fill_value = col < row ? col : row; // closest to bottom or left wall
        temp_row = row - fill_value;
        temp_col = col - fill_value;
        index = temp_row * N + temp_col; // board position
        for (int i = 0; i < queen; i++) { // check if interference occurs
            if (left_bottom_diagonals[i] == index) return 0;
        }
        left_bottom_diagonals[queen] = index; // no interference

        /* position --> right down diagonal endpoint (index) */
        fill_value = (N-1) - col < row ? N - col - 1 : row; // closest to bottom or right wall
        temp_row = row - fill_value;
        temp_col = col + fill_value;
        index = temp_row * N + temp_col; // board position
        for (int i = 0; i < queen; i++) { // check if interference occurs
            if (right_bottom_diagonals[i] == index) return 0;
        }
        right_bottom_diagonals[queen] = index; // no interference
    }
    return 1;
}

/* ##########################################################################################
   #################################### HELPER FUNCTIONS ####################################
   ########################################################################################## */

/* print the collected solutions  */
void print(print_buf printouts) {
    static int solution_number = 1;
    int placement;

    for (int sol = 0; sol <= printouts.top; sol++) { // number of solutions
        printf("Solution %d: [ ", solution_number++);
        for (int pos = 0; pos < N; pos++) {
            printf("%d ", printouts.qpositions[sol][pos]+1);
        } 
        printf("]\n");

        printf("Placement:\n");
        for (int i = 1; i <= N; i++) { // rows
            printf("[ ");
            placement = printouts.qpositions[sol][N-i];
            for (int j = (N-i)*N; j < (N-i)*N+N; j++) { // physical position
                if (j == placement) {
                    printf(" Q ");
                } else printf("%2d ", j+1);

            }
            printf("]\n");
        }
        printf("\n");
    }
}

/* ##########################################################################################
   #################################### THREAD FUNCTIONS ####################################
   ########################################################################################## */

/* entry point for each worker (consumer)
workers will check each queen's row, column and 
diagonal to evaluate satisfactory placements */
void *eval_positioning(void *id) {
    long thr_id = (long)id;
    int qpositions[N];
    
    pthread_mutex_lock(&buffer_mutex);
    while (!global.last_done) {    
        while (global.buf_empty == 1) {
            pthread_cond_wait(&filled, &buffer_mutex);
            if (global.last_done) { // last_done ==> prod_done, so thread returns
                pthread_mutex_unlock(&buffer_mutex);
                return NULL;
            }
            if (global.prod_done) { // prod done, current thread takes last elem produced
                global.last_done = 1;
                break;
            }
        }

        if (!global.last_done) consumptions++;
        memcpy(qpositions, global.positions, N*sizeof(int)); // retrieve queen combination
        global.buf_empty = 1;
        pthread_mutex_unlock(&buffer_mutex);
        pthread_cond_signal(&empty);

        if (valid_rows(qpositions) && valid_columns(qpositions) && valid_diagonals(qpositions)) {
            /* save for printing later */
            pthread_mutex_lock(&print_mutex);
            memcpy(printouts.qpositions[++printouts.top], qpositions, N*sizeof(int));
            pthread_mutex_unlock(&print_mutex);
        }
        pthread_mutex_lock(&buffer_mutex);
    }
    pthread_mutex_unlock(&buffer_mutex);
    return NULL;
}

/* recursively generate all possible queen_combs */
void rec_positions(int pos, int queens) {
    if (queens == 0) { // base case
        pthread_mutex_lock(&buffer_mutex);
        while (global.buf_empty == 0) {
            pthread_cond_wait(&empty, &buffer_mutex);
        }
        productions++;
        memcpy(global.positions, queen_comb.positions, N*sizeof(int));
        global.buf_empty = 0;
        pthread_mutex_unlock(&buffer_mutex);
        pthread_cond_signal(&filled);
        return;
    }

    for (int i = pos; i <= N*N - queens; i++) {
        queen_comb.positions[queen_comb.top++] = i;
        rec_positions(i+1, queens-1);
        queen_comb.top--;
    }
}

/* binomial coefficient | without order, without replacement
8 queens on 8x8 board: 4'426'165'368 queen combinations */
void *generate_positions(void *arg) {
    rec_positions(0, N);
    return (void*)1;
}

/* ##########################################################################################
   ########################################## MAIN ##########################################
   ########################################################################################## */

/* main procedure of the program */
int main(int argc, char *argv[]) {
    if (argc < 3) {
        printf("usage: ./8q <workers> <board width/height>\n");
        exit(1);
    }

    int workers = atoi(argv[1]);
    N = atoi(argv[2]);

    pthread_t thr[workers];
    pthread_t producer;

    printf("\n");
    
    start = (float)clock()/CLOCKS_PER_SEC;

    pthread_create(&producer, NULL, generate_positions, NULL);
    for (long i = 0; i < workers; i++) {
        pthread_create(&thr[i], NULL, eval_positioning, (void*)i+1);
    }

    pthread_join(producer, (void*)&global.prod_done);
    pthread_cond_broadcast(&filled);
    for (int i = 0; i < workers; i++) {
        printf("thread #%d done\n", i+1);
        pthread_join(thr[i], NULL);
        pthread_cond_broadcast(&filled);
    }

    stop = clock();
    diff = (double)(stop - start) / CLOCKS_PER_SEC;
    
    /* go through all valid solutions and print */
    print(printouts);
    
    printf("board: %dx%d, workers: %d (+1), exec time: %ld, solutions: %d\n", N, N, workers, diff, printouts.top+1);
    printf("productions: %ld\nconsumptions: %ld\n", productions, consumptions);
    return 0;
}
Improve this question
6
  • 3
    Re, "...correct with locks...10+ seconds...should reveal...mistakes..." Sometimes, six months of extensive testing is not enough to reveal mistakes that actually are present. (Don't ask me how I know!) I'm not saying that there's anything wrong with how you synchronize your threads—how could I? I haven't seen your code. But, it's typical of incorrectly synchronized programs that they work on one platform, but not on another; they work when built with this tool chain, but not with that one; before an OS update, but not after; etc. Commented Jan 29, 2022 at 14:12
  • Haha alright, I am new to concurrent programming but I will surely take that into account in the future! Would you mind taking a look at the code for producers and consumers? I sat all day yesterday and thought about the synchronization but came to no conclusions. Commented Jan 29, 2022 at 14:18
  • Why don't you see if you can turn it into an SSCCE, and then edit that into your question here? Commented Jan 29, 2022 at 14:26
  • There, I was a little unsure of how to do an SSCCE. If you'd like to, report back if I could improve something for my next SSCCE hehe. Commented Jan 29, 2022 at 14:43
  • 1
    Without going too deep into the code, there's one things that's sooner or later going to cause problems: You don't have a plan what data to share and how to sync it. Make sure you document which mutex protects which data. Commented Jan 30, 2022 at 17:15

1 Answer 1

Reset to default
2

I'm quite sure that my implementation is correct with locks and conditional variables

That is a bold statement, and it's provably false. Your program hangs on Linux when run with clang -g q.c -o 8q && ./8q 2 4.

When I look at the state of the program, I see one thread here:

#4  __pthread_cond_wait (cond=0x404da8 <filled>, mutex=0x404d80 <buffer_mutex>) at pthread_cond_wait.c:619
#5  0x000000000040196b in eval_positioning (id=0x1) at q.c:163
#6  0x00007ffff7f8cd80 in start_thread (arg=0x7ffff75b6640) at pthread_create.c:481
#7  0x00007ffff7eb7b6f in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

and the main thread trying to join the above thread. All other threads have exited, so there is nothing to signal the condition.

One immediate problem I see is this:

void *eval_positioning(void *id) {
    long thr_id = (long)id;
    int qpositions[N];
    
    while (!global.done) {
...
int main(int argc, char *argv[]) {
...
    pthread_join(producer, (void*)&global.done);

If the producer thread finishes before the eval_positioning starts, then eval_positioning will do nothing at all.

You should set global.done when all positions have been evaluated, not when the producer thread is done.

Another obvious problem is that global.done is accessed without any mutexes held, yielding a data race (undefined behavior -- anything can happen).

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Yes that was silly of me to not think of, will make sure to correct that. Though I'm still wondering how it is possible, when the program actually runs to completion, that I end up with too many consumptions. I don't understand how the shared variable consumptions is not protected with mutual exclusion. When a thread is returning from sleep (on cond var filled) is shall have the lock, and also in case it never sleeps, since the lock is acquired before the inner while-loop. And the lock is released after the consumptions is incremented.
@Beethoven "how is it possible ..." -- once you have a data race, anything is possible. Understanding how it happens is mostly pointless. And once you fix data races, the program will just work (I promise :-).
Updated the code (see original post). I fixed the data races I could find, but it still doesn't sync correctly. Would appreciate additional analysis, I feel like I'm blind to my own code at this point.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.