Coordinating Multi-Stage Computations with `pthread_barrier`

1. The Barrier Concept and API

Imagine a team of sprinters. They all line up, but the race doesn't start until the last sprinter is in position. Once the final sprinter is ready, the starting pistol fires, and they all take off simultaneously. A pthread_barrier works just like that starting line.

To get a quick and clear overview of this concept and the core functions involved, please watch the following video.

As the video explained, the barrier API is straightforward:

• pthread_barrier_t barrier;
  Declares a barrier object.

• int pthread_barrier_init(pthread_barrier_t *barrier, const pthread_barrierattr_t *attr, unsigned int count);
  Initializes a barrier. The count parameter is crucial: it specifies how many threads must call pthread_barrier_wait() before they are all released. We'll typically pass NULL for the attributes (attr).

• int pthread_barrier_wait(pthread_barrier_t *barrier);
  This is the function a thread calls to signal its arrival at the barrier. The thread will block here until count threads have called it. Once the last thread arrives, all waiting threads are unblocked and resume execution.

• int pthread_barrier_destroy(pthread_barrier_t *barrier);
  Cleans up the resources used by the barrier when it's no longer needed.

2. A Practical Example: A Multi-Stage Dice Game

Barriers are most useful when a computation has distinct stages that depend on each other. Let's analyze a scenario:

• Stage 1: Data Generation. Multiple worker threads perform a task (e.g., roll a dice, compute a value).
• Synchronization Point: We must ensure all threads have finished Stage 1 before proceeding.
• Stage 2: Data Processing. A thread (often the main thread) processes the results from Stage 1 (e.g., determines the winner of the dice game).
• Synchronization Point: We must ensure Stage 2 is complete before threads move on to display their final status.

The next video walks through exactly this scenario, demonstrating a common problem and how to solve it elegantly with two barriers. This is a perfect illustration of a multi-stage computation.

This example highlights two critical insights:

1. The main thread can participate. The barrier count was set to NUM_THREADS + 1 to include the main thread in the synchronization. This is a common and powerful technique.
2. Barriers are reusable. As shown in the while(1) loop at the end, once threads pass a barrier, it resets and can be used again for the next iteration of a computation. This is what makes them ideal for cyclic, multi-stage algorithms.

3. The Serial Thread: Performing One-Off Actions

In the dice game, the main thread was responsible for the serial task of calculating the winner. The Pthreads API provides a more general mechanism for this. When count threads have arrived at a barrier, one arbitrarily chosen thread will receive a special return value from pthread_barrier_wait(): PTHREAD_BARRIER_SERIAL_THREAD. All other threads will receive 0.

This allows you to designate one thread to perform a setup or cleanup action for the next stage, without having to hardcode it to be the main thread.

The following resource provides a full code example demonstrating this feature.

This pattern is extremely useful. For example, in a parallel physics simulation:

1. All threads compute forces for their assigned particles (Stage 1).
2. All threads wait at a barrier.
3. The serial thread could sum up total system energy or prepare a data structure for the next time step.
4. All threads proceed to the next stage (e.g., updating particle positions).

4. Your Turn: Parallel Array Processing

Let's apply these concepts. Your task is to complete a program that processes an array in parallel over multiple stages.

The Goal:

1. Stage 1: Each of N threads will multiply the elements in its assigned slice of a large array by 2.
2. Synchronization: After all threads have finished Stage 1, they must wait at a barrier.
3. Serial Task: The single thread that gets PTHREAD_BARRIER_SERIAL_THREAD will calculate the sum of the entire modified array and print it.
4. Stage 2: After the sum is printed, all threads are released and proceed to a (simulated) second stage of work before terminating.

Here is the skeleton code. Fill in the sections marked /* TODO */.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define NUM_THREADS 4
#define ARRAY_SIZE 1000

int data[ARRAY_SIZE];
pthread_barrier_t barrier;

typedef struct {
    int thread_id;
    int start;
    int end;
} thread_arg_t;

void* worker(void* arg) {
    thread_arg_t* my_arg = (thread_arg_t*)arg;
    
    printf("Thread %d: Starting stage 1...\n", my_arg->thread_id);

    // Stage 1: Multiply my slice of the array by 2
    for (int i = my_arg->start; i < my_arg->end; ++i) {
        data[i] *= 2;
    }
    
    printf("Thread %d: Finished stage 1, waiting at barrier.\n", my_arg->thread_id);

    // /* TODO */: Wait at the barrier and check the return value.
    // The serial thread should calculate and print the sum.
    // Others should just print a message that they passed.
    int barrier_ret = pthread_barrier_wait(&barrier);

    if (barrier_ret == PTHREAD_BARRIER_SERIAL_THREAD) {
        long long total_sum = 0;
        for (int i = 0; i < ARRAY_SIZE; ++i) {
            total_sum += data[i];
        }
        printf("\n--- SERIAL THREAD: All threads reached barrier. Total sum is %lld. ---\n\n", total_sum);
    } else if (barrier_ret == 0) {
        // This thread passed the barrier, but wasn't the serial one.
        // Waiting for the serial thread to finish its work.
    } else {
        // Error
        printf("Thread %d: Error waiting on barrier.\n", my_arg->thread_id);
        exit(1);
    }
    
    // Threads are released implicitly after the barrier.
    printf("Thread %d: Passed barrier, starting stage 2.\n", my_arg->thread_id);
    
    // Simulate Stage 2 work
    sleep(1);

    free(my_arg);
    return NULL;
}

int main() {
    pthread_t threads[NUM_THREADS];
    thread_arg_t* args[NUM_THREADS];

    // Initialize data array
    for (int i = 0; i < ARRAY_SIZE; ++i) {
        data[i] = i + 1;
    }

    // /* TODO */: Initialize the barrier with the correct count.
    if (pthread_barrier_init(&barrier, NULL, NUM_THREADS) != 0) {
        perror("pthread_barrier_init");
        return 1;
    }

    int slice_size = ARRAY_SIZE / NUM_THREADS;
    for (int i = 0; i < NUM_THREADS; ++i) {
        args[i] = malloc(sizeof(thread_arg_t));
        args[i]->thread_id = i;
        args[i]->start = i * slice_size;
        args[i]->end = (i == NUM_THREADS - 1) ? ARRAY_SIZE : (i + 1) * slice_size;

        pthread_create(&threads[i], NULL, worker, args[i]);
    }

    for (int i = 0; i < NUM_THREADS; ++i) {
        pthread_join(threads[i], NULL);
    }

    // /* TODO */: Destroy the barrier.
    pthread_barrier_destroy(&barrier);

    printf("All threads finished.\n");
    return 0;
}

Compile your completed code with gcc your_file.c -o barrier_exercise -pthread and observe the output. You should see all threads finish Stage 1, then the single sum-total printout, followed by all threads proceeding to Stage 2.

Conclusion

You have now added another powerful tool to your concurrency toolkit. Unlike mutexes or semaphores, which are primarily about mutual exclusion or resource limiting, barriers are about coordinating the flow of execution across multiple threads.

Key Takeaways:

• A pthread_barrier forces a set number of threads to wait at a synchronization point before any can proceed.
• It is the ideal primitive for computations that occur in distinct, sequential stages (e.g., parallel data generation followed by serial data aggregation).
• The count supplied to pthread_barrier_init is critical and must include every thread that will wait on the barrier, which can include the main thread.
• The special return value PTHREAD_BARRIER_SERIAL_THREAD allows one thread to be automatically elected to perform tasks that must be done only once per barrier cycle.

Preview of the Next Lesson:
We've explored synchronization primitives that cause threads to block and yield the CPU while waiting (mutexes, semaphores, barriers). In the next lesson, we will investigate pthread_spinlock. A spinlock is a lock that causes a thread to "spin" in a tight loop, repeatedly checking for the lock to become free without yielding the CPU. We will discuss the specific scenarios—very short and highly contended critical sections—where this seemingly wasteful approach can actually improve performance.