Home | Projects | Notes > Multi-Threading (POSIX Threads) > Thread Synchronization - Thread Barrier

Thread Synchronization - Thread Barrier

Introduction to Thread Barrier

Thread Barrier is a thread synchronization data structure which blocks all threads at a particular line of code until some specified number of threads arrives at the barrier point.
In case where you must wait for a number of tasks to be completed before an overall task can proceed, barrier synchronization can be used.
Practical use case:
Internet Download Manager (IDM) is an application that downloads the big files through multiple downloader threads. Each downloader thread downloads a section of a file independently, and concurrently (or in parallel depending on the number of available CPUs). When all threads complete, the application reports "file download success".

Functionality of Thread Barrier

barrier threshold $n$ $n-1$ barrier point $n^{th}$ thread arrives then the barrier will be released. Release of a barrier means that all the blocked threads will resume their execution beyond the barrier point. It is also called "the thread barrier has been disposed (or disposition of the thread has begun)". The disposition begin state continues until ALL the threads blocked at the barrier have resumed their execution beyond the barrier point and only then the disposition ends. And during this time interval the disposition of the barrier is in progress.
POSIX API provides a built-in support to work with thread barriers (pthread_barrier_t).

Implementing Thread Barrier Data Structure

Thread barrier works on the concept of relay:
A thread which is just signaled (meaning that the thread has just resumed its execution from the blocked state) will signal other blocked threads to resume execution, and thereby creating a chain of signals. (It just just like when we get stuck at a barricade, we pass the barricade when allowed by the authority.)

thread-barrier

Interface for thread barrier data structure:


xxxxxxxxxx
32
1
/*
2
 * File Name    : thread_barrier.h
3
 * Description  : Interface for thread barrier data structure
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/11/2023
6
 */
7

8
#ifndef THREAD_BARRIER
9
#define THREAD_BARRIER
10

11
#include <stdint.h>
12
#include <stdbool.h>
13
#include <pthread.h>
14

15
typedef struct th_barrier_
16
{
17
    uint32_t threshold_count;   /* threshold */
18
    uint32_t curr_wait_count;   /* current # of threads waiting at the barrier [0, threshold - 1]*/
19
    pthread_cond_t cv;          /* condition variable (necessary for threads to be blocked) */
20
    pthread_mutex_t mutex;      /* to gurantee mutual exclusion for operations on barrier DS */
21
    bool is_ready_again;        /* true (deault), false (disposition in progress), true (disp. end) */
22
    pthread_cond_t busy_cv;     /* condition variable to block any additional threads arrive at the 
23
                                   barrier while disposition is in progress */                  
24
} th_barrier_t;
25
    
26
/* interface */
27
void thread_barrier_init(th_barrier_t *barrier, uint32_t threshold_count);
28
void thread_barrier_wait(th_barrier_t *barrier);
29
void thread_barrier_destroy(th_barrier_t *barrier);
30
void thread_barrier_print(th_barrier_t *th_barrier);
31

32
#endif

Implementation of thread barrier data structure:


xxxxxxxxxx
74
1
/*
2
 * File Name    : thread_barrier.c
3
 * Description  : Implementation of thread barrier data structure
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/11/2023
6
 */
7

8
#include <stdio.h>
9
#include <unistd.h>
10
#include "thread_barrier.h"
11

12
void thread_barrier_init (th_barrier_t *barrier, uint32_t threshold_count)
13
{    
14
    barrier->threshold_count = threshold_count;
15
    barrier->curr_wait_count = 0;
16
    pthread_cond_init(&barrier->cv, NULL);
17
    pthread_mutex_init(&barrier->mutex, NULL);
18
    barrier->is_ready_again = true;
19
    pthread_cond_init(&barrier->busy_cv, NULL);
20
}
21

22
void thread_barrier_wait (th_barrier_t *barrier)
23
{
24
    pthread_mutex_lock (&barrier->mutex);
25

26
    /* do not allow threads to access the barrier when the barrier disposition is in progress */
27
    while (barrier->is_ready_again == false) /* 'while' instead of 'if' to avoid spurious wakeup */
28
    {
29
        pthread_cond_wait(&barrier->busy_cv, &barrier->mutex);
30
    }
31

32
    /* if the current thread is the last thread to hit the barrier point */
33
    if (barrier->curr_wait_count + 1 == barrier->threshold_count)
34
    {
35
        /* signal a blocked thread, pass through the barrier by unlocking the mutex */
36
        /* mark "disposition begin" */
37
        barrier->is_ready_again = false;
38
        pthread_cond_signal(&barrier->cv);
39
        pthread_mutex_unlock (&barrier->mutex);
40
        return;
41
    }
42

43
    /* if the current thread is NOT the last thread to hit the barrier point */
44
    barrier->curr_wait_count++;
45
    /* block the current thread on the barrier */
46
    pthread_cond_wait(&barrier->cv, &barrier->mutex);
47
    /* when a blocked thread resumes its execution and signals the condition variable */
48
    barrier->curr_wait_count--;
49

50
    /* if the current thread is the last thread to leave the barrier point */
51
    if (barrier->curr_wait_count == 0)
52
    {
53
        /* do not need to signal the condition variable since there are no more threads left blocking */
54
        /* mark "disposition end" */
55
        barrier->is_ready_again = true;
56
        /* allow blocked thread (arrived during 'disposition in progress' state) to use barrier if any */
57
        pthread_cond_broadcast(&barrier->busy_cv);
58
    }
59
    /* if the current thread is NOT the last thread to leave the barrier point */
60
    else 
61
    {
62
        /* signal the condition variable for a thread that is left blocking on the barrier point */
63
        pthread_cond_signal(&barrier->cv);
64
    }
65
    
66
    pthread_mutex_unlock (&barrier->mutex);
67
}
68

69
void thread_barrier_print(th_barrier_t *th_barrier)
70
{   
71
    printf("th_barrier->threshold_count = %u\n", th_barrier->threshold_count);
72
    printf("th_barrier->curr_wait_count = %u\n", th_barrier->curr_wait_count);
73
    printf("th_barrier->is_ready_again = %s\n", th_barrier->is_ready_again ? "true" : "false");
74
}

thread-barrier-algorithm

Test driver for thread barrier data structure:


xxxxxxxxxx
50
1
/*
2
 * File Name    : thread_barrier_main.c
3
 * Description  : Test driver for thread barrier data structure
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/11/2023
6
 */
7

8
#include <stdio.h>
9
#include "thread_barrier.h"
10

11
static th_barrier_t th_barrier;
12
static pthread_t pthreads[3];
13

14
void* thread_fn_callback (void *arg)
15
{
16
    thread_barrier_wait(&th_barrier);
17
    printf("1st barricade cleared by thread %s\n", (char *)arg);
18

19
    thread_barrier_wait(&th_barrier);
20
    printf("2nd barricade cleared by thread %s\n", (char *)arg);
21

22
    thread_barrier_wait(&th_barrier);
23
    printf("3rd barricade cleared by thread %s\n", (char *)arg);
24
    
25
    pthread_exit(0);
26
    return NULL;
27
}
28

29
int main(int argc, char *argv[])
30
{
31
    thread_barrier_init(&th_barrier, 3); 
32
    
33
    /* create joinable threads since we don't want the application to terminate before threads do */
34
    static const char *th1 = "th1";
35
    pthread_create(&pthreads[0], NULL, thread_fn_callback, (void *)th1);
36
    
37
    static const char *th2 = "th2";
38
    pthread_create(&pthreads[1], NULL, thread_fn_callback, (void *)th2);
39
    
40
    static const char *th3 = "th3";
41
    pthread_create(&pthreads[2], NULL, thread_fn_callback, (void *)th3);
42
    
43
    pthread_join(pthreads[0], NULL);
44
    pthread_join(pthreads[1], NULL);
45
    pthread_join(pthreads[2], NULL);
46

47
    /* to test if the barrier is left in a correct state before the application terminates */
48
    thread_barrier_print(&th_barrier);
49
    return 0;
50
}


xxxxxxxxxx
12
1
1st barricade cleared by thread th3
2
1st barricade cleared by thread th2
3
1st barricade cleared by thread th1
4
2nd barricade cleared by thread th1
5
2nd barricade cleared by thread th3
6
2nd barricade cleared by thread th2
7
3rd barricade cleared by thread th1
8
3rd barricade cleared by thread th3
9
3rd barricade cleared by thread th2
10
th_barrier->threshold_count = 3
11
th_barrier->curr_wait_count = 0
12
th_barrier->is_ready_again = true

What matters is if all three threads appear at each of the three barricade clearances. The order in which they appear does not matter!
My test results show, though, 1st barricade is always cleared by the thread th3. Think why!

References

Sagar, A. (2022). Part A - Multithreading & Thread Synchronization - Pthreads [Video file]. Retrieved from https://www.udemy.com/course/multithreading_parta/