Issue with synchronization of threads using condition variables to output the Mandelbrot

Question

I try to syncronize threads with condition variables to output mandelbrot but i get wrong mandelbort. The functions output_mandel_line and compute_mandel_line are given and are correct. I made the void *function() and int main(). I suspect the issue is with the if statement inside the mutex_lock. I tried different if or while statement but i couldn't fix it. Perhaps there issue also on how i use the cond_wait ,cond_broadcast.


int nthreads;
pthread_cond_t cond;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

/***************************
 * Compile-time parameters *
 ***************************/

/*
 * Output at the terminal is is x_chars wide by y_chars long
 */
int y_chars = 50;
int x_chars = 90;

/*
 * The part of the complex plane to be drawn:
 * upper left corner is (xmin, ymax), lower right corner is (xmax, ymin)
 */
double xmin = -1.8,
    xmax = 1.0;
double ymin = -1.0,
    ymax = 1.0;

/*
 * Every character in the final output is
 * xstep x ystep units wide on the complex plane.
 */
double xstep;
double ystep;

/*
 * This function computes a line of output
 * as an array of x_char color values.
 */
void
compute_mandel_line(int line, int color_val[])
{
}

/*
 * This function outputs an array of x_char color values
 * to a 256-color xterm.
 */
void
output_mandel_line(int fd, int color_val[])
{
}

    /* Now that the line is done, output a newline character */
    if (write(fd, &newline, 1) != 1) {
        perror("compute_and_output_mandel_line: write newline");
        exit(1);
    }
}

void *
function(void *arg)
{
    int *number = (int *) arg,
        line;

    int color_val[x_chars];

    for (line = *number; line < y_chars; line += nthreads) {
        compute_mandel_line(line, color_val);
        pthread_mutex_lock(&mutex);

        output_mandel_line(1, color_val);
        pthread_cond_signal(&cond);
        if (line + nthreads < y_chars) {
            pthread_cond_wait(&cond, &mutex);
        }

        pthread_cond_signal(&cond);
        pthread_mutex_unlock(&mutex);

    }
    free(arg);

    return NULL;
}

int
main(int argc, char **argv)
{
    if (argc != 2) {
        fprintf(stderr, "Wrong format");
        exit(1);
    }
    nthreads = atoi(argv[1]);
    int i;
    pthread_t t[nthreads];

    // pthread_t *t =(pthread_t*)malloc(nthreads * sizeof(pthread_t));

    // ret =(pthread_cond_t*)malloc(nthreads * sizeof(pthread_cond_t));
    int ret;

    xstep = (xmax - xmin) / x_chars;
    ystep = (ymax - ymin) / y_chars;

    pthread_cond_init(&cond, NULL);
    pthread_mutex_init(&mutex, NULL);

    for (i = 0; i < nthreads; i++) {
        int *a = malloc(sizeof(int));

        *a = i;
        ret = pthread_create(&t[i], NULL, function, a);
        if (ret) {
            perror_pthread(ret, "error");
            exit(1);
        }
    }

    for (i = 0; i < nthreads; i++) {
        ret = pthread_join(t[i], NULL);
        if (ret) {
            perror_pthread(ret, "error");
            exit(1);
        }
    }

    pthread_cond_destroy(&cond);
    pthread_mutex_destroy(&mutex);

    /*
     * Allocate memory for threads and semaphores
     * draw the Mandelbrot Set, one line at a time.
     * Output is sent to file descriptor '1', i.e., standard output.
     */

    reset_xterm_color(1);
    return 0;
}

I tried changing the if statement and the condition variable order of cond_wait , cond_signal

You have a race condition. I think you need two condition variables. When you do pthread_cond_signal while holding the lock and immediately do pthread_cond_wait on the same condition variable, the receiver will never get released because the sender will get the signal. And, you have to loop the condition vaiable(s): pthread_mutex_lock(&mutex); while (line + nthreads < y_chars) pthread_cond_wait(&cond,&mutex); pthread_mutex_unlock(&mutex); And, I'm not totally sure, but you may have to release the mutex before doing the signal. — Craig Estey
– Craig Estey, Commented May 15, 2024 at 21:08
The first question to answer wherever you perform a wait on a condition variable is what condition are you waiting for?. You can use the same CV in multiple threads or at multiple times to wait for different conditions to become true, but if there is not an expression you can test to determine whether to wait (or whether to wait more) then you are using your CV incorrectly. — John Bollinger
– John Bollinger, Commented May 16, 2024 at 19:39
And since you have to test the condition after you return from waiting, and possibly wait some more, the idioms for correct CV usage mostly perform the wait inside a loop. — John Bollinger
– John Bollinger, Commented May 16, 2024 at 19:41
@CraigEstey, CV signals do not queue or persist, not even one. (They are not "signals" in the sense of the kill() function.) Only a thread already blocked in pthread_cond_wait() can be awoken by a call to pthread_cond_signal(). No thread can break itself out of its own pthread_cond_wait(), no matter what mutex it holds or when. — John Bollinger
– John Bollinger, Commented May 16, 2024 at 19:50

John Bollinger · Accepted Answer · 2024-05-16 20:42:18Z

Your objective here seems to be to spread the computation over multiple threads, while ensuring that they write their output in the correct order. A condition variable can help with that, though it's not the only possible approach. In fact, it would probably be easier to set up a semaphore for each thread by which to notify it of its turn to output.

But if you want to use a CV, then it's essential to understand the usage model:

The point of a CV is to allow a thread to suspend operation, if necessary, until some condition becomes true through the action of another thread. If there is no condition for the thread to test to determine whether to proceed, then a CV is the wrong tool for the job.
A thread arriving at a CV-mediated wait point should first check whether the condition for it to proceed is already true. If so, then it does not wait at all.
If a thread does perform a CV wait, then after it unblocks it must test again whether the (a) condition for it to proceed is satisfied. This accommodates several possibilities:
- that the CV was signaled for some other reason than the particular condition the thread was waiting on having changed
- that the condition, though perhaps having been true at the time of the CV signal, is false again by the time the thread gets a chance to run
- that the thread woke spurriously, without a signal having been dispatched to the CV at all.
Ordinarily, the waiting thread goes back to waiting if its condition for proceeding is not satisfied.
It is not arbitrary that CVs are used together with mutexes. A thread waiting on a CV needs to observe the effects of one or more other threads on some piece of (shared) data that make a condition true that previously was false. Avoiding a data race around that data requires synchronization, which is (when done correctly) provided by the mutex.

Apparently, you want your threads to take turns, writing their output in round-robin fashion. In that case, the condition that each thread wants to wait for is, in English, "it's my turn". In order for a thread to evaluate that computationally, there needs to be a shared variable that determines whose turn it is. Maybe something like this:

static int whose_turn = 0;

Your wait loop might then look like this:

        pthread_mutex_lock(&mutex);

        while (whose_turn != *number) { // check the condition
            // it's not my turn yet
            pthread_cond_wait(&cond, &mutex);
        }

        // do my work
        output_mandel_line(1, color_val);
        
        // now it's the next thread's turn
        whose_turn = (*number + 1) % nthreads;

        pthread_mutex_unlock(&mutex);

        // wake _all_ the threads, to ensure that the one whose turn it is
        // is wakened
        pthread_cond_broadcast(&cond);

Additional notes:

You should minimize the work done in the critical region, which is mostly that performed by output_mandel_line(). I'm uncertain what your set_xterm_color() function does, but if it is possible to move all those calls to that function outside the critical region then that will help your performance. Not least by allowing you to dispatch the whole line via a single write() call.
I omitted return-value checks from the above code for clarity, but you should be checking the return value of every function call that uses its return value to signal errors. Except possibly where you don't actually care about errors.

Collectives™ on Stack Overflow

Issue with synchronization of threads using condition variables to output the Mandelbrot

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related