Threads and a nested for loop with dependencies (pthreads in C)

Question

Im trying to learn how to program using threads in C by using the pthreads library. In my thread function I have a nested for loop:

void* thread_func(void* a) {
    int i, t;
    struct type *b = (struct type*)a;
    int start = b->start;
    int stop = b->stop;
    for(t = 0; t < 1000; t++) {

        for(i = start; i < stop; i++) {
        /* This inner loop is evenly divided among the threads.*/
        /***** Calculation*****/
        }
    }
    return NULL;
}

The calculation in the inner for-loop depends on the result of the previous t-step of the outer for loop, so the threads have to wait for the other threads to finish the current t-step, before continuing. Is there a way to wait for all the threads to finish each t-step before continuing the next t-step? I tried to use pthread_join() but that doesn't seem the work within the thread_func(). Can someone point me in the right direction? Or am I trying something which isn't possible?

EDIT: i and t are local variables in thread_func()..forgot to mention that..

EDIT2: Maybe my explanation is not very clear... Im creating some threads in main() (not shown in the code) and each thread calls thread_func(). I've divided the inner for-loop among the threads. But before going to the next t-step in the outer for loop, I should be sure that all threads have finished the current t-step, because the result of the next t-step depends on the result of the current t-step. How can I do that? Hope that makes more sense now..

Answer 1

You seem to be somewhat confused about how threads work in general.

In reality, thread_func() will not be shared among the different threads you create. Each thread has its own context; even if all of them are executing thread_func(), none of them messes with the computations of the other as far as everything is local.

The only case in which you have to worry about concurrent accesses is with shared data (global variables, for example). In this case, you generally use mutexes or semaphores. Read about pthread_mutex_t and sem_t

UPDATE: Since you don't specify what exactly is t and i, I assumed they were local variables. If they are global, you have to use mutexes to sync access to these variables. Keep in mind that calling a global variable meaningless names like t or i is generally bad practice.

UPDATE2: With your edits, I now understand what you really want. The only solution I can think of at the moment is that you need to have a global variable that will serve as t for every thread. Let's call it step. step is global because every thread can read it and know what is the current iteration. However, to coordinate concurrent access to this variable, we will need a mutex, as I mentioned earlier.

The basic layout goes like this: A thread stores the last iteration that was executed inside its context. It is repeatedly testing step to see if it was updated by another thread. When that happens, it begins execution of the for loop (the one with i = start; .... After executing the loop, the thread must test if it was the last one for this iteration; if it was, it must increment the global value for step (note that when this happens, any threads that were stuck waiting for new values for step will move forward).

Testing if we're the last thread implies that you somehow know the number of threads you created. You can pass this as a parameter, or define it as a constant. I will assume it is defined as THREADS_NO.

As a consequence, we will also need a global counter and mutex to know how many threads have ended current iteration

Thus, your file would look something like:

pthread_mutex_t step_mutex;
pthread_mutex_t counter_mutex;

int step;
int counter;

void* thread_func(void* a) {
    int t, i, curr_t;
    struct type *b = (struct type*)a;
    int start = b->start;
    int stop = b->stop;
    t = -1;
    curr_t = 0;
    while (1) {
        while (curr_t == t) {
            /* Wait for the next step */
            pthread_mutex_lock(&step_mutex);
            curr_t = step;
            pthread_mutex_unlock(&step_mutex);      
        }
        /* New value for t arrived */
        t = curr_t;
        if (t >= 1000) {
            break;
        }
        for (i = start; i < stop; i++) {
            /***** Calculation*****/
        }
        pthread_mutex_lock(&counter_mutex);
        if (++counter == THREADS_NO) {
            counter = 0;
            pthread_mutex_lock(&step_mutex);
            step++;
            pthread_mutex_unlock(&step_mutex);
        }
        pthread_mutex_unlock(&counter_mutex);
    }   
    return NULL;
}

You have to initialize both mutexes before creating any thread, possibly in main(), with:

pthread_mutex_init(&step_mutex, NULL);
pthread_mutex_init(&counter_mutex, NULL);

And when you get the job done, don't forget to destroy them:

pthread_mutex_destroy(&step_mutex);
pthread_mutex_destroy(&counter_mutex);

Note that you should test the return value of the functions that initialize, lock, and destroy mutexes, since an error can occur.

Finally, consider if this is what you really want: maybe you need to redesign your program or algorithm. This approach is not very efficient, because threads will waste CPU cycles to repeatedly test for new values for step (this is called busy waiting). Pretty much like "Are we there yet? Are we there yet? Are we there yet?"... not very clever.

NOTE: I couldn't test this code. The code you posted makes it a little harder to know what you're trying to achieve, so I'm not sure this will work entirely for you.