17.8.1 When to Use Multithreading

Sometimes multithreading is convenient for the program logic. For example, you usually should not accept a network packet and draw the graphical interface in the same thread. The graphical interface should react to user actions (clicks on the buttons) and be redrawn constantly (e.g., when the corresponding window gets covered by another window and then uncovered). The network action, however, will block the working thread until it is done. It is thus convenient to split these actions into different threads to perform them seemingly simultaneously.

Multithreading can naturally improve performance, but not in all cases. There are CPU bound tasks and IO bound tasks.

• CPU bound code can be sped up if given more CPU time. It spends most of the CPU time doing computations, not reading data from disk or communicating with devices.

• IO bound code cannot be sped up with more CPU time because it is slowed by its excessive usage of memory or external devices.

Using multithreading to speed CPU bound programs might be beneficial. A common pattern is to use a queue with the requests that are dispatched to the worker threads from a thread pool–a set of created threads that are either working or waiting for work but are not re-created each time there is a need of them. Refer to Chapter 7 of [23] for more details.

As for how many threads we need, there is no universal recipe. Creating threads, switching between them, and scheduling them produces an overhead. It might make the whole program slower if there is not much work for threads to do. In computation-heavy tasks some people advise to spawn n − 1 threads, where n is the total number of processor cores. In tasks that are sequential by their own nature (where every step depends directly on the previous one) spawning multiple threads will not help. What we do recommend is to always experiment with the number of threads under different workloads to find out which number suits the most for the given task.

17.8.2 Creating Threads

Creating threads is easy. Listing 17-6 shows an example.

Listing 17-6. pthread_create_mwe.c

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

void* threadimpl( void* arg ) {
    for(int i = 0; i < 10; i++ ) {
        puts( arg );
        sleep(1);
    }
    return NULL;
}

int main( void ) { pthread_t t1, t2;
    pthread_create( &t1, NULL, threadimpl, "fizz" );
    pthread_create( &t2, NULL, threadimpl, "buzzzz" );
    pthread_exit( NULL );
    puts("bye");
    return 0;
}

Note that the code that uses pthread library must be compiled with -pthread flag, for example,

> gcc -O3 -pthread main.c

That specifying -lpthread will not give us an esteemed result. Linking with the sole libpthread.a is not enough: there are several preprocessor options that are enabled by -pthread (e.g., _REENTRANT). So, whenever the -pthread option is available,¹ use it.

Initially, there is only one thread which starts executing the main function. A pthread_t type stores all information about some other thread, so that we can control it using this instance as a handle. Then, the threads are initialized with pthread_create function with the following signature:

int pthread_create(
    pthread_t *thread,
    const pthread_attr_t *attr,
    void *(*start_routine) (void *),
    void *arg);

The first argument is a pointer to the pthread_t instance to be initialized. The second one is a collection of attributes, which we will touch later–for now, it is safe to pass NULL instead.

The thread starting function should accept a pointer and return a pointer. It accepts a void* pointer to its argument. Only one argument is allowed; however, you can easily create a structure or an array, which encapsulates multiple arguments, and pass a pointer to it. The return value of the start_routine is also a pointer and can be used to return the work result of the thread.² The last argument is the actual pointer to the argument, which will be passed to the start_routine function.

In our example, each thread is implemented the same way: it accepts a pointer (to a string) and then repeatedly outputs it with an interval of approximately one second. The sleep function, declared in unistd.h, suspends the current thread for a given number of seconds.

After ten iterations, the thread returns. It is equivalent to calling the function pthread_exit with an argument. The return value is usually the result of the computations performed by the thread; return NULL if you do not need it. We will see later how it is possible to get this value from the parent thread.

However, the naive return from the main function will lead to process termination. What if other threads still exist? The main thread should wait for their termination first! This is what pthread_exit does when it is called in the main thread: it waits for all other threads to terminate and then terminates the program. All the code that follows will not be executed, so you will not see the bye message in stdout.

This program will output a pair of buzz and fizz lines in random order ten times and then exit. It is impossible to predict whether the first or the second thread will be scheduled first, so each time the order can differ. Listing 17-7 shows an exemplary output.

Listing 17-7. pthread_create_mwe_out

> ./main
fizz
buzzzz
buzzzz
fizz
fizz
buzzzz
fizz
buzzzz
fizz
buzzzz
buzzzz
fizz
buzzzz
fizz
buzzzz
fizz
buzzzz
fizz
buzzzz
fizz

As you see, the string bye is not printed, because the corresponding puts call is below the pthread_exit call.

The maximum number of threads spawned depends on implementation. In Linux, for example, you can use ulimit -a to get relevant information.

The threads can create other threads; there is no limitation on that.

It is indeed guaranteed by the pthreads implementation that a call for pthread_create acts as a full compiler memory barrier as well as a full hardware memory barrier.

pthread_attr_init is used to initialize an instance of an opaque type pthread_attr_t (implemented as an incomplete type ). Attributes provide additional parameters for threads such as stack size or address.

The following functions are used to set attributes :

• pthread_attr_setaffinity_np–the thread will prefer to be executed on a specific CPU core.

• pthread_attr_setdetachstate–will we be able to call pthread_join on this thread, or will it be detached (as opposed to joinable). The purpose of pthread_join will be explained in the next section.

• pthread_attr_setguardsize–sets up the space before the stack limit as a region of forbidden addresses of a given size to catch stack overflows.

• pthread_attr_setinheritsched–are the following two parameters inherited from the parent thread (the one where the creation happened), or taken from the attributes themselves?

• pthread_attr_setschedparam–right now is all about scheduling priority, but the additional parameters can be added in the future.

• pthread_attr_ setschedpolicy–how will the scheduling be performed. Scheduling policies with their respective descriptions can be seen in man sched.

• pthread_attr_setscope–refers to the contention scope system, which defines a set of threads against which this thread will compete for CPU (or other resources).

• pthread_attr_setstackaddr–where will the stack be located?

• pthread_attr_setstacksize–what will be the thread stack size?

• pthread_attr_setstack–sets both stack address and stack size.

All of them have their “get” counterparts (e.g., pthread_attr_getscope).

17.8.3 Managing Threads

What we have learned is already enough to perform work in parallel. However, we have no means of synchronization yet, so once we have distributed the work for the threads, we cannot really use the computation results of one thread in other threads.

The simplest form of synchronization is thread joining. The idea is simple: by calling thread_join on an instance of pthread_t we put the current thread into the waiting state until the other thread is terminated. Listing 17-8 shows an example.

Listing 17-8. thread_join_mwe.c

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

void* worker( void* param ) {
    for( int i = 0; i < 3; i++ ) {
        puts( (const char*) param );
        sleep(1);
    }
    return (void*)"done";
}

int main( void ) {

    pthread_t t;
    void* result;

    pthread_create( &t, NULL, worker, (void*) "I am a worker!" );
    pthread_join( t, &result );
    puts( (const char*) result );
    return 0;
}

The thread_join accepts two arguments : the thread itself and the address of a void* variable, which will be initialized with the thread execution result.

Thread joining acts as a full barrier because we should not place before the joining any reads or writes that are planned to happen after.

By default, the threads are created joinable, but one might create a detached thread. It might bring a certain benefit: the resources of the detached thread can be released immediately upon its termination. The joinable thread, however, will be waiting to be joined before its resources can be released. To create a detached thread

• Create an attribute instance pthread_attr_t attr;

• Initialize it with pthread_attr_init( &attr );

• Call pthread_attr_setdetachstate( &attr, PTHREAD_CREATE_DETACHED ); and

• Create the thread by using pthread_create with a &attr as the attribute argument.

The current thread can be explicitly changed from joinable to detached by calling pthread_detach(). It is impossible to do it the other way around.

17.8.4 Example: Distributed Factorization

We have picked a simple CPU bound program of counting the factors of a number. First, we are going to solve it using the most trivial brute-force method on a single core. Listing 17-9 shows the code.

Listing 17-9. dist_fact_sp.c

#include <pthread.h>
#include <unistd.h>
#include <inttypes.h>
#include <stdio.h>
#include <malloc.h>

uint64_t factors( uint64_t num ) {
    uint64_t result = 0;
    for (uint64_t i = 1; i <= num; i++ )
        if ( num % i == 0 ) result++;
    return result;
}

int main( void ) {
    /* volatile to prevent constant propagation */
    volatile uint64_t input = 2000000000;

    printf( "Factors of %"PRIu64": %"PRIu64"\n", input, factors(input) );
    return 0;
}

The code is quite simple: we naively iterate over all numbers from 1 to the input and check whether they are factors or not. Note that the input value is marked volatile to prevent the whole result from being computed during the compilation. Compile the code with the following command:

> gcc -O3 -std=c99 -o fact_sp dist_fact_sp.c

We will start parallelization with a dumbed-down version of multithreaded code, which will always perform computations in two threads and will not be architecturally beautiful. Listing 17-10 shows it.

Listing 17-10. dist_fact_mp_simple.c

#include <pthread.h>
#include <inttypes.h>
#include <stdio.h>

int input = 0;

int result1 = 0;
void* fact_worker1( void* arg ) {
    result1 = 0;
    for( uint64_t i = 1; i < input/2; i++ )
        if ( input % i == 0 ) result1++;
    return NULL;
}

int result2 = 0;
void* fact_worker2( void* arg ) {
    result2 = 0;
    for( uint64_t i = input/2; i <= input; i++ )
        if ( input % i == 0 ) result2++;
    return NULL;
}

uint64_t factors_mp( uint64_t num ) {
    input = num;
    pthread_t thread1, thread2;

    pthread_create( &thread1, NULL, fact_worker1, NULL );
    pthread_create( &thread2, NULL, fact_worker2, NULL );

    pthread_join( thread1, NULL );
    pthread_join( thread2, NULL );

    return result1 + result2;
}
                                                                                          
int main( void ) {
    uint64_t input = 2000000000;
    printf( "Factors of %"PRIu64": %"PRIu64"\n",
            input, factors_mp(input ));
    return 0;
}

Upon launching it produces the same result, which is a good sign.

Factors of 2000000000: 110

What is this program doing? Well, we split the range (0, n] into two halves. Two worker threads are computing the number of factors in their respective halves. Then when both of them have been joined, we are guaranteed that they have already had performed all computations. The results just need to be summed up.

Then, in Listing 17-11 we show the multithreaded program that uses an arbitrary number of threads to compute the same result. It has a better-thought-out architecture .

Listing 17-11. dist_fact_mp.c

#include <pthread.h>
#include <unistd.h>
#include <inttypes.h>
#include <stdio.h>
#include <malloc.h>

#define THREADS 4

struct fact_task {
    uint64_t num;
    uint64_t from, to;
    uint64_t result;
};

void* fact_worker( void* arg ) {
    struct fact_task* const task =  arg;
    task-> result = 0;
    for( uint64_t i = task-> from; i < task-> to; i++ )
        if ( task->num %  i ==  0 ) task-> result ++;
    return NULL;
}

/* assuming threads_count < num */
uint64_t factors_mp( uint64_t num, size_t threads_count ) {

    struct fact_task* tasks = malloc( threads_count * sizeof( *tasks ) );
    pthread_t* threads = malloc( threads_count * sizeof( *threads ) );

    uint64_t start = 1;
    size_t step = num / threads_count;

    for( size_t i = 0; i < threads_count; i++ ) {
        tasks[i].num = num;
        tasks[i].from = start;
        tasks[i].to = start + step;
        start += step;
    }
    tasks[threads_count-1].to = num+1;

    for ( size_t i = 0; i < threads_count; i++ )
        pthread_create( threads + i, NULL, fact_worker, tasks + i );

    uint64_t result = 0;
    for ( size_t i = 0; i < threads_count; i++ ) {
        pthread_join( threads[i], NULL );
        result  +=  tasks[i].result;
    }

    free( tasks );
    free( threads );
    return result;
}
int main( void ) {
    uint64_t input = 2000000000;
    printf( "Factors of %"PRIu64": %"PRIu64"\n",
            input, factors_mp(input, THREADS ) );
    return 0;
}

Suppose we are using t threads . To count the number of factors of n, we split the range from 1 to n on t equal parts. We compute the number of factors in each of those intervals and then sum up the results.

We create a type to hold the information about single task called struct fact_task. It includes the number itself, the range bounds to and to, and the slot for the result, which will be the number of factors of num between from and to.

All workers who calculate the number of factors are implemented alike, as a routine fact_worker, which accepts a pointer to a struct fact_task, computes the number of factors, and fills the result field.

The code performing thread launch and results collection is contained in the factors_mp function, which, for a given number of threads, is

• Allocating the task descriptions and the thread instances;

• Initializing the task descriptions;

• Starting all threads;

• Waiting for each thread to end its execution by using join and adding up its result to the common accumulator result; and

• Freeing all allocated memory .

So, we put the thread creation into a black box, which allows us to benefit from the multithreading.

This code can be compiled with the following command:

> gcc -O3 -std=c99 -pthread -o fact_mp dist_fact_mp.c

The multiple threads are decreasing the overall execution time on a multicore system for this CPU bound task.

To test the execution time, we will stick with the time utility again (a program, not a shell builtin command). To ensure, that the program is being used instead of a shell builtin, we prepend it with a backslash.

> gcc -O3 -o sp -std=c99 dist_fact_sp.c && \time ./sp
Factors of 2000000000: 110
21.78user 0.03system 0:21.83elapsed 99%CPU (0avgtext+0avgdata 524maxresident)k
0inputs+0outputs (0major+207minor)pagefaults 0swaps

> gcc -O3 -pthread -o mp -std=c99 dist_fact_mp.c && \time ./mp
Factors of 2000000000: 110
25.48user 0.01system 0:06.58elapsed 387%CPU (0avgtext+0avgdata 656maxresident)k
0inputs+0outputs (0major+250minor)pagefaults 0swaps

The multithreaded program took 6.5 seconds to be executed, while the single-threaded version took almost 22 seconds. That is a big improvement.

In order to speak about performance we are going to introduce the notion of speedup. Speedup is the improvement in speed of execution of a program executed on two similar architectures with different resources. By introducing more threads we make more resources available, hence the possible improvement might take place.

Obviously, for the first example we have chosen a task that is easy and more efficient to solve in parallel. The speedup will not always be that substantial, if any; however, as we see, the overall code is compact enough (could be even less would we not take extensibility into account—for example, fix a number of threads, instead of using it as a parameter).

17.8.5 Mutexes

While thread joining is an accessible technique, it does not provide means to control the thread execution “on the run.” Sometimes we want to ensure that the actions performed in one thread are not being performed before some other action in the other threads are performed. Otherwise, we will get a situation where the system is not always working in a stable manner: its output will become dependent on the actual order in which the instructions from the different threads will be executed. It occurs when working with the mutable data shared between threads. Such situations are called data races, because the threads compete for the resources, and any thread can win and get to them first.

To prevent such situations, there is a number of tools, and we will start with mutexes.

Mutex (a shorthand for “mutual exclusion”) is an object that can be in two states: locked and unlocked. We work with them using two queries.

• Lock. Changes the state from unlocked to locked. If the mutex is locked, then the attempting thread waits until the mutex is unlocked by other threads.

• Unlock. If the mutex is locked, it becomes unlocked.

Mutexes are often used to provide an exclusive access to a shared resource (like a shared piece of data). The thread that wants to work with the resource locks the mutex, which is exclusively used to control an access to a resource. After the work with the resource is finished, the thread unlocks the mutex.

Mutex locking and unlocking acts as both a compiler and full hardware memory barriers, so no reads or writes can be reordered before locking or after unlocking.

Listing 17-12 shows an example program which needs a mutex.

Listing 17-12. mutex_ex_counter_bad.c

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

pthread_t t1, t2;

uint64_t value = 0;

void* impl1( void* _ ) {
    for (int n = 0; n < 10000000; n++) {
        value +=  1;
    }
    return NULL;
}

int main(void) {
    pthread_create(  &t1, NULL, impl1, NULL );
    pthread_create(  &t2, NULL, impl1, NULL );

    pthread_join( t1, NULL );
    pthread_join( t2, NULL );
    printf( "%"PRIu64"\n", value );
    return 0;
}

This program has two threads , implemented by the function impl1. Both threads are constantly incrementing the shared variable value 10000000 times.

This program should be compiled with the optimizations disabled to prevent this incrementing loop from being transformed into a single value += 10000000 statement (or we can make value volatile).

gcc -O0 -pthread mutex_ex_counter_bad.c

The resulting output is, however, not 20000000, as we might have thought, and is different each time we launch the executable:

> ./a.out
11297520
> ./a.out
10649679
> ./a.out
13765500

The problem is that incrementing a variable is not an atomic operation from the C point of view. The generated assembly code conforms to this description by using multiple instructions to read a value, add one, and then put it back. It allows the scheduler to give the CPU to another thread “in the middle” of a running increment operation. The optimized code might or might not have the same behavior.

To prevent this mess we are going to use a mutex to grant a thread a privilege to be the sole one working with value. This way we enforce a correct behavior. Listing 17-13 shows the modified program.

Listing 17-13. mutex_ex_counter_good.c

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

pthread_mutex_t m; //

pthread_t t1, t2;

uint64_t value = 0;

void* impl1( void* _ ) {
    for (int n = 0; n < 10000000; n++) {
        pthread_mutex_lock( &m );//

        value += 1;

        pthread_mutex_unlock( &m );//
    }
    return NULL;
}

int main(void) {
    pthread_mutex_init( &m, NULL );     //

    pthread_create(  &t1, NULL, impl1, NULL );
    pthread_create(  &t2, NULL, impl1, NULL );

    pthread_join( t1, NULL );
    pthread_join( t2, NULL );
    printf( "%"PRIu64"\n", value );

    pthread_mutex_destroy( &m ); //
    return 0;
}

Its output is consistent (although takes more time to compute):

> ./a.out
20000000

The mutex m is associated by the programmer with a shared variable value. No modifications of value should be performed outside the code section between the m lock and unlock. If this constraint is satisfied, there is no way value can be changed by another thread once the lock is taken. The lock acts as a memory barrier as well. Because of that, value will be reread after the lock is taken and can be cached in a register safely. There is no need to make the variable value volatile, since it will only suppress optimizations and the program is correct anyway.

Before a mutex can be used, it should be initialized with pthread_mutex_init, as seen in the main function. It accepts attributes, just like the pthread_create function, which can be used to create a recursive mutex, create a deadlock detecting mutex, control the robustness (what happens if the mutex owner thread dies?), and more.

To dispose of a mutex, the call to pthread_mutex_unlock is used.

17.8.6 Deadlocks

A sole mutex is rarely a cause of problems. However, when you lock multiple mutexes at a time, several kinds of strange situations can happen. Take a look at the example shown in Listing 17-14.

Listing 17-14. deadlock_ex

mutex A, B;

thread1 () {
    lock(A);
    lock(B);
    unlock(B);
    unlock(A);
}

thread2() {
    lock(B);
    lock(A);
    unlock(A);
    unlock(B);
}

This pseudo code demonstrates a situation where both threads can hang forever. Imagine that the following sequence of actions happened due to unlucky scheduling:

• Thread 1 locked A; control transferred to thread 2.

• Thread 2 locked B; control transferred to thread 1.

After that, the threads will try to do the following:

• Thread 1 will attempt to lock B, but B is already locked by thread 2.

• Thread 2 will attempt to lock A, but A is already locked by thread 1.

Both threads will be stuck in this state forever. When threads are stuck in a locked state waiting for each other to perform unlock, the situation is called deadlock.

The cause of the deadlock is the different order in which the locks are being taken by different threads. It leads us to a simple rule that will save us most of the times when we need to lock several mutexes at a time.

17.8.7 Livelocks

Livelock is a situation in which two threads are stuck but not in a waiting-for-mutex-unlock state. Their states are changing, but they are not really progressing. For example, pthreads does not allow you to check whether the mutex is locked or not. It would be useless to provide information about the mutex state, because once you obtain information about it, the latter can already be changed by the other thread.

if ( mutex is not locked ) {
    /* We still do not know if the mutex is locked or not.
       Other thread might have locked or unlocked it
       several times already.  */
}

However, pthread_mutex_trylock is allowed, which either locks a mutex or returns an error if it has already been locked by someone. Unlike pthread_mutex_lock, it does not block the current thread waiting for the unlock. Using pthread_mutex_trylock can lead to livelock situations. Listing 17-15 shows a simple example in pseudo code.

Listing 17-15. livelock_ex

mutex m1, m2;

thread1() {
    lock( m1 );
    while ( mutex_trylock m2 indicates LOCKED ) {
        unlock( m1 );
        wait for some time;
        lock( m1 );
    }
    // now we are good because both locks are taken
}

thread2() {
    lock( m2 );
    while ( mutex_trylock m1 indicates LOCKED ) {
        unlock( m2 );
        wait for some time;
        lock( m2 );
    }
    // now we are good because both locks are taken
}

Each thread tries to defy the principle “locks should always be performed in the same order.” Both of them want to lock two mutexes m1 and m2.

The first thread performs as follows:

• Locks the mutex m1.

• Tries to lock mutex m2. On failure, unlocks m1, waits, and locks m1 again.

This pause is meant to provide the other thread time to lock m1 and m2 and perform whatever it wants to do. However, we might be stuck in a loop when

1. Thread 1 locks m1, thread 2 locks m2.

2. Thread 1 sees that m2 is locked and unlocks m1 for a time.

3. Thread 2 sees that m1 is locked and unlocks m2 for a time.

4. Go back to step one.

This loop can take forever to complete or can produce significant delays; it is entirely up to the operating system scheduler. So, the problem with this code is that execution traces exist that will forever prevent threads from progress.

17.8.8 Condition Variables

Condition variables are used together with mutexes. They are like wires transmitting an impulse to wake up a sleeping thread, waiting for some condition to be satisfied.

Mutexes implement synchronization by controlling thread access to a resource; condition variables, on the other hand, allow threads to synchronize based upon additional rules. For example, in case of shared data, the actual value of data might be a part of such rule.

The core of condition variables usage consists of three new entities:

• The condition variable itself of type pthread_cond_t.

• A function to send a wake-up signal through a condition variable pthread_cond_signal.

• A function to wait until a wake-up signal comes through a condition variable pthread_cond_wait.

These two functions should only be used between a lock and unlock of the same mutex.

It is an error to call pthread_cond_signal before pthread_cond_wait, otherwise the program might be stuck.

Let us study a minimal working example shown in Listing 17-16.

Listing 17-16. condvar_mwe.c

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

pthread_cond_t condvar = PTHREAD_COND_INITIALIZER;
pthread_mutex_t m;

bool sent = false;
void* t1_impl( void* _ ) {
    pthread_mutex_lock( &m );
    puts( "Thread2 before wait" );

    while (!sent)
        pthread_cond_wait( &condvar, &m );

    puts( "Thread2 after wait" );
    pthread_mutex_unlock( &m );
    return  NULL;
}

void* t2_impl( void* _ ) {
    pthread_mutex_lock( &m );
    puts( "Thread1 before signal" );

    sent = true;
    pthread_cond_signal( &condvar );

    puts( "Thread1 after signal" );
    pthread_mutex_unlock( &m );
    return NULL;
}

int main( void ) {
    pthread_t t1, t2;

    pthread_mutex_init( &m, NULL );
    pthread_create( &t1, NULL, t1_impl, NULL );
    sleep( 2 );
    pthread_create( &t2, NULL, t2_impl, NULL );

    pthread_join( t1, NULL );
    pthread_join( t2, NULL );

    pthread_mutex_destroy( &m );
    return 0;
}

Running this code will produce the following output:

./a.out
Thread2 before wait
Thread1 before signal
Thread1 after signal
Thread2 after wait

Initializing a condition variable can be performed either through an assignment of a special preprocessor constant PTHREAD_COND_INITIALIZER or by calling pthread_cond_init. The latter can accept a pointer to attributes of type pthread_condattr_t akin to pthread_create or pthread_mutex_init.

In this example, two threads are created: t1, performing instructions from t1_impl, and t2, performing ones from t2_impl.

The first thread locks the mutex m. It then waits for a signal that can be transmitted through the condition variable condvar. Note that pthread_cond_wait also accepts the pointer to the currently locked mutex.

Now t1 is sleeping, waiting for the signal to come. The mutex m becomes immediately unlocked! When the thread gets the signal, it will relock the mutex automatically and continue its execution from the next statement after pthread_cond_wait call.

The other thread is locking the same mutex m and issuing a signal through condvar. pthread_cond_signal sends the signal through condvar, unblocking at least one of the threads, blocked on the condition variable condvar.

The pthread_cond_ broadcast function would unblock all threads waiting for this condition variable, making them contend for the respective mutex as if they all issued pthread_mutex_lock. It is up to the scheduler to decide in which order will they get access to the CPU.

As we see, condition variables let us block until a signal is received. An alternative would be a “busy waiting” when a variable’s value is constantly checked (which kills performance and increases unnecessary power consumption) as follows:

while (somecondition == false);

We can of course put the thread to sleep for a time, but this way we will still wake up either too rarely to react to the event in time or too often:

while (somecondition == false)
    sleep(1); /* or something else that lets us sleep for less time */

Condition variables let us wait just enough time and continue the thread execution in the locked state.

An important moment should be explained. Why did we introduce a shared variable sent? Why are we using it together with the condition variable? Why are we waiting inside the while (!sent) cycle?

The most important reason is that the implementation is permitted to issue spurious wake-ups to a waiting thread. It means that the thread can wake up from waiting on a signal not only after receiving it but at any time. In this case, as the sent variable is only set before sending the signal, spurious wake-up will check its value and if it is still equal to false will issue the pthread_cond_wait again.

17.8.9 Spinlocks

A mutex is a sure way of doing synchronization. Trying to lock a mutex which is already taken by another thread puts the current thread into a sleeping state. Putting the thread to sleep and waking it up has its costs, notably for the context switch, but if the waiting is long, these costs justify themselves. We spend a little time going to sleep and waking up, but in a prolonged sleep state the thread does not use the CPU.

What would be an alternative? The active idle, which is described by the following simple pseudo code:

while ( locked == true ) {
    /* do nothing */
}
locked = true;

The variable locked is a flag showing whether some thread took the lock or not. If another thread took the lock, the current thread will constantly poll its value until it is changed back. Otherwise it proceeds to take the lock on its own. This wastes CPU time (and increases power consumption), which is bad. However, it can increase performance in case the waiting time is expected to be very short. This mechanism is called spinlock .

Spinlocks only make sense on multicore and multiprocessor systems. Using spinlock in a single core is useless. Imagine a thread enters the cycle inside the spinlock. It keeps waiting for other thread to change the locked value, but no other thread is executing at this very time, because there is only one core switching from thread to thread. Eventually the scheduler will put the current thread to sleep and allow other threads to perform, but it just means that we have wasted CPU cycles executing an empty loop for no reason at all! In this case, going to sleep right away is always better, and hence there is no use for a spinlock.

This scenario can of course occur on a multicore system as well, but there is also a (usually) good chance, that the other thread will unlock the spinlock before the time quantum given to the current thread expires.

Overall, using spinlocks can be beneficial or not; it depends on the system configuration, program logic, and workload. When in doubt, test and prefer using mutexes (which are often implemented by first taking a spinlock for a number of iterations and then falling into the sleep state if no unlock occurred).

Implementing a fast and correct spinlock in practice is not that trivial. There are questions to be answered, such as the following:

• Do we need a memory barrier on lock and/or unlock? If so, which one? Intel 64, for example, has lfence, sfence, and mfence.

• How do we ensure that the flag modification is atomic? In Intel 64, for example, an instruction xchg suffices (with lock prefix in case of multiple processors).

pthreads provide us with a carefully designed and portable mechanism of spinlocks. For more information, refer to the man pages for the following functions:

• pthread_spin_lock

• pthread_spin_destroy

• pthread_spin_unlock

17.12.1 Overview

Most of the time we want to write code that is correct on every architecture. To achieve that, we base it on the memory model described in the C11 standard. The compiler might implement some operations in a straightforward manner or emit special instructions to enforce certain guarantees, when the actual hardware architecture is weaker.

Contrary to Intel 64, the C11 memory model is rather weak. It guarantees data dependency ordering, but nothing more, so in the classification mentioned in section 17.4 it corresponds to the second one: weak with dependency ordering. There are other hardware architectures that provide similar weak guarantees, for example ARM.

Because of C weakness, to write portable code we cannot assume that it will be executed on an usually strong architecture, such as Intel 64 , for two reasons.

• When recompiled for other, weaker architecture, the observed program behavior will change because of how the hardware reorderings work.

• When recompiled for the same architecture, compiler reorderings that do not break the weak ordering rules imposed by the standard might occur. That can change the observed program behavior, at least for some execution traces.

17.12.2 Atomics

The important C11 feature that can be used to write fast multithreaded programs is atomics (see section 7.17 of [7]). These are special variable types, which can be modified atomically. To use them, include the header stdatomic.h.

Apparently, an architecture support is needed to implement them efficiently. In the worst-case scenario, when the architecture does not support any such operation, every such variable will be paired with a mutex, which will be locked to perform any modification of the variable or even to read it.

Atomics allow us to perform thread-safe operations on common data in some cases. It is often possible to do without heavy machinery involving mutexes. However, writing data structures such as queue in a lock-free way is no easy task. For that we highly advise using such existing implementations as “black boxes.”

C11 defines a new _Atomic() type specifier. You can declare an atomic integer as follows:

_Atomic(int) counter;

_Atomic transforms the name of a type into the name of an atomic type. Alternatively, you can use the atomic types directly as follows:

atomic_int counter;

A full correspondence between _Atomic(T) and atomic_T direct type forms can be found in section 7.17.6 of [7].

Atomic local variables should not be initialized directly; instead, the macro ATOMIC_VAR_INIT should be used. It is understandable, because on some architectures with fewer hardware capabilities each such variable should be associated with a mutex, which has to be created and initialized as well. Global atomic variables are guaranteed to be in a correct initial state. ATOMIC_VAR_INIT should be used during the variable declaration coupled with initialization; however, if you want to initialize the variable later, use atomic_init macro.

void f(void) {
    /* Initialization during declaration */
    atomic_int x = ATOMIC_VAR_INIT( 42 );
    atomic_int y;

    /* initialization later */
    atomic_init( &y, 42 );
}

It is your responsibility to guarantee that the atomic variable initialization ends before anything else is done with it. In other words, concurrent access to the variable being initialized is a data race.

Atomic variables should only be manipulated through an interface, defined in the language standard. It consists of several operations, such as load, store, exchange, etc. Each of them exists in two versions.

• An explicit version, which accepts an extra argument, describing the memory ordering . Its name ends with _explicit. For example, the load operation is

  T atomic_load_explicit( _Atomic(T) *object, memory_order order );

• An implicit version, which implies the strongest memory ordering (sequentially consistent). There is no _explicit suffix. For example,

  T atomic_load( _Atomic(T) *object );

17.12.3 Memory Orderings in C11

The memory ordering is described by one of enumeration constants (in order of increasing strictness).

• memory_order_relaxed implies the weakest model: any memory reordering is possible as long as the single thread program’s observable behavior is left untouched.

• memory_order_consume is a weaker version of memory_order_acquire.

• memory_order_acquire means that the load operation has an acquire semantics.

• memory_order_release means that the store operation has a release semantics.

• memory_order_acq_rel combines acquire and release semantics.

• memory_order_seq_cst implies that no memory reordering is performed for all operations that are marked with it, no matter which atomic variable is being referenced.

By providing an explicit memory ordering constant, we can control how we want to allow the operations to be observably reordered. It includes both compiler reorderings and hardware reorderings, so when the compiler sees that compiler reorderings do not provide all the guarantees we need, it will also issue platform-specific instructions, such as sfence.

The memory_order_consume option is rarely used. It relies on the notion of “consume operation.” This operation is an event that occurs when a value is read from memory and then used afterward in several operations, creating a data dependency.

In weaker architectures such as PowerPC or ARM its usage can bring a better performance due to exploitation of the data dependencies to impose a certain ordering on memory accesses. This way, the costly hardware memory barrier instruction is spared, because these architectures guarantee the data dependency ordering without explicit barriers. However, due to the fact that this ordering is so hard to implement efficiently and correctly in compilers, it is usually mapped directly to memory_order_acquire, which is a slightly stronger version. We do not recommend using it. Refer to [30] for additional information.

The acquire and release semantics of these memory ordering options correspond directly to the notions we studied in section 17.7.

The memory_order_seq_cst corresponds to the notion of sequential consistency, which we elaborated in section 17.4. As all non-explicit operations with atomics accept it as a default memory ordering value, C11 atomics are sequentially consistent by default. It is the safest route and also usually faster than mutexes. Weaker orderings are harder to get right, but they allow for a better performance as well.

The atomic_thread_fence(memory_order order) allows us to insert a memory barrier (compiler and hardware ones) with a strength corresponding to the specified memory ordering. For example, this operation has no effect for memory_order_relaxed, but for a sequentially consistent ordering in Intel 64 the mfence instruction will be emitted (together with compiler barrier).

17.12.4 Operations

The following operations can be performed on atomic variables (T denotes the non-atomic type, U refers to the type of the other argument for arithmetic operations; for all types except pointers, it is the same as T, for pointers it is ptrdiff_t).

void atomic_store(volatile _Atomic(T)* object, T  value);
T atomic_load(volatile _Atomic(T)* object);

T atomic_exchange(volatile _Atomic(T)* object, desired);

T atomic_fetch_add(volatile _Atomic(T)* object, U operand);
T atomic_fetch_sub(volatile _Atomic(T)* object, U operand);
T atomic_fetch_or (volatile _Atomic(T)* object, U operand);
T atomic_fetch_xor(volatile _Atomic(T)* object, U operand);
T atomic_fetch_and(volatile _Atomic(T)* object, U operand);

bool atomic_compare_exchange_strong(
    volatile _Atomic(T)* object, T * expected, T desired);
bool atomic_compare_exchange_weak(
    volatile _Atomic(T)* object, T * expected, T desired);

All these operations can be used with an _explicit suffix to provide a memory ordering as an additional argument.

Load and store functions do not need a further explanation; we will discuss the other ones briefly.

atomic_exchange is a combination of load and store: it replaces the value of an atomic variable with desired and returns its old value.

fetch_op family of operations is used to atomically change the atomic variable value. Imagine you need to increment an atomic counter. Without fetch_add it is impossible to do since in order to increment it you need to add one to its old value, which you have to read first. This operation is performed in three steps: reading, addition, writing. Other threads may interfere between these stages, which destroys atomicity.

atomic_compare_exchange_ strong is preferred to its weak counterpart, since the weak version can fail spuriously. The latter has a better performance on some platforms.

The atomic_compare_exchange_strong function is roughly equivalent to the following pseudo code:

if ( *object == *expected )

    *object = desired;
else
    *expected = *object;

As we see, this is a typical CAS instruction that was discussed in section 17.11.

atomic_is_lock_free macro is used to check whether a specific atomic variable uses locks or not.

Remember that without providing explicit memory ordering, all these operations are assumed to be sequentially consistent, which in Intel 64 means mfence instructions all over the code. This can be a huge performance killer.

The Boolean shared flag has a special type named atomic_flag. It has two states: set and clear. It is guaranteed that operations on it are atomic without using locks.

The flag should be initialized with the ATOMIC_FLAG_INIT macro as follows:

atomic_flag is_working = ATOMIC_FLAG_INIT;

The relevant functions are atomic_flag_test_and_set and atomic_flag_clear, both of which have _explicit counterparts, accepting memory ordering descriptions.