POSIX threads

POSIX threads

Enable the hardware (or the OS), and compute faster!

Program execution

To understand threads, it is important to understand how programs execute.

Assuming the program is compiled as an executable of some sort, a standard program like the one shown below runs synchronously, i.e. it is printed in order. Therefore the output will be 'Waffles available: 10', followed by 'Waffles available: 5'.

#include <stdio.h>

int waffles = 0;

void sell_waffle() { waffles--; }

void bake_waffle() { waffles++; }

void waffle_balance() { printf("Waffles available: %d\n", waffles); }

int main()
{
    for (int i = 0; i < 10; i++) bake_waffle();
    waffle_balance();
    for (int i = 0; i < 5; i++) sell_waffle();
    waffle_balance();

    return 0;
}

But life is asynchronous, the waffles are sold and baked independently of each other. Asynchronous programming handles this challenge, and the terminology used is quite confusing.

Parallel execution: Two or more operations physically execute at the same time, which means two or more processors run alongside each other in time.

Concurrent execution: Two or more operations appear to execute at the same time, either parallel as described above (actual same time), or more commonly by sharing one processor in slices of time.

Threads

A thread could be thought of as its own small and simple program. Threads are created within a process. A process has many definitions, but I prefer any active or running, instance of a program (further explanation is beyond the scope of this article). On Linux, each process has its own memory, all threads created within the process then have access to this memory, such as the 'waffles' variable in the previous program.

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

int waffles = 0;

void *bake_waffles(void *arg)
{
    for (int i = 0; i < 10; i++)
    {
        int producer_id = (int)arg;
        waffles++;
        printf("Baker %d made a waffle, total is: %d\n", producer_id, waffles);
    }
}

void *eat_waffles(void *arg)
{
    for (int i = 0; i < 5; i++)
    {
        int consumer_id = (int)arg; 
        waffles--;
        printf("Consumer %d ate a waffle, total is: %d\n", consumer_id, waffles);
    }
}

int main()
{
    pthread_t producer_thread, consumer_thread;
    int id = 1;

    pthread_create(&producer_thread, NULL, *bake_waffles, (void*) id);
    pthread_create(&consumer_thread, NULL, *eat_waffles, (void*) id);

    pthread_join(producer_thread, NULL);
    pthread_join(consumer_thread, NULL);

    return 0;
}

Before reviewing the program output, let's go through the new setup. The 'pthread_t' is a structure, it contains attributes that determine thread behavior. The 'create' function initiates a thread and takes four arguments.

  1. The thread to create passed by reference

  2. The thread attributes, NULL set's default attributes

  3. Pointer to a callback function, the function is what the thread executes

  4. Arguments passed to the callback function, an ID in this example

Lastly, the main program awaits both threads with the 'join' function, if the main program terminates before the threads are done, the threads will not finish their work.

The new iteration of the program is identical to the first one in many ways. A baker bakes 10 waffles, and the consumer eats 5 waffles. But if you run this program, it is easily visible that something unusual happens.

Baker 1 made a waffle, total is: 1
Baker 1 made a waffle, total is: 1
Baker 1 made a waffle, total is: 2
Baker 1 made a waffle, total is: 3
Baker 1 made a waffle, total is: 4
Baker 1 made a waffle, total is: 5
Baker 1 made a waffle, total is: 6
Baker 1 made a waffle, total is: 7
Consumer 1 ate a waffle, total is: 0
Consumer 1 ate a waffle, total is: 7
Consumer 1 ate a waffle, total is: 6
Consumer 1 ate a waffle, total is: 5
Consumer 1 ate a waffle, total is: 4
Baker 1 made a waffle, total is: 8
Baker 1 made a waffle, total is: 5

We end up with a total of 5 waffles, but we never get to a total of 10 waffles. That is because both threads access the 'waffles' variable, as one thread increments it, the other may decrement it at the same time. As the code stands, one thread eats five waffles. We could also design a solution where 5 threads eat one waffle each by removing the 'for' loop in the callback function, the output would be as below.

The baker made a waffle, total is: 1
The baker made a waffle, total is: 0
The baker made a waffle, total is: 1
The baker made a waffle, total is: 2
The baker made a waffle, total is: 3
The baker made a waffle, total is: 4
The baker made a waffle, total is: 5
The baker made a waffle, total is: 6
Consumer 2 ate a waffle, total is: -1
The baker made a waffle, total is: 7
The baker made a waffle, total is: 8
Consumer 1 ate a waffle, total is: 0
Consumer 3 ate a waffle, total is: 7
Consumer 4 ate a waffle, total is: 6
Consumer 5 ate a waffle, total is: 5

It is clear to see that we run into problems with this solution, but why? Five consumers eat a waffle each, but only one baker bakes waffles, the consumers are just too fast and therefore we end up with a negative amount of waffles. Either we need more bakers, or we need to synchronize the consumers so that only one waffle could be eaten at a time.

Mutex

Several different mechanisms are used to synchronize threads. We are going to focus on mutexes, short for Mutual Exclusion. A mutex is used to place a lock around a critical section of code, such as the waffle variable.

By locking this section of code, only one thread can eat waffles at a time, thereby slowing down the consumption rate. A new 'pthread_mutex_t' struct is globally created, subsequently, it is initiated and destroyed at the start/end of the main function with default attributes (as always by passing NULL). The key functionality comes in the callback function, here the decrement and print actions are locked off so that only one thread can act at a time.

One, and only one thread may hold the mutex lock, the same thread is also the only one that may unlock the mutex. All other threads are blocked until the mutex is unlocked.

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

int waffles = 0;
pthread_mutex_t consumer_lock;

void *bake_waffles(void *arg)
{
    for (int i = 0; i < 10; i++)
    {
        waffles++;
        printf("The baker made a waffle, total is: %d\n", waffles);
    }
}

void *eat_waffles(void *arg)
{
    int consumer_id = (int)arg;
    pthread_mutex_lock(&consumer_lock);
    waffles--;
    printf("Consumer %d ate a waffle, total is: %d\n", consumer_id, waffles);
    pthread_mutex_unlock(&consumer_lock);
}

int main(int argc, int** argv)
{
    pthread_t producer_thread, consumer_thread[10];
    int id[10];

    pthread_mutex_init(&consumer_lock, NULL);

    pthread_create(&producer_thread, NULL, *bake_waffles, NULL);

    for (int i = 0; i < 5; i++)
    {
        id[i] = i + 1;
        pthread_create(&consumer_thread[i], NULL, *eat_waffles, (void*) id[i]);
    }

    pthread_join(producer_thread, NULL);
    for (int i = 0; i < 5; i++)
        pthread_join(consumer_thread[i], NULL);

    pthread_mutex_destroy(&consumer_lock);

    return 0;
}

The output of the updated code confirms our hypothesis, the consumers must now stand in line, and the baker can relax once more.

The baker made a waffle, total is: 1
The baker made a waffle, total is: 2
The baker made a waffle, total is: 3
The baker made a waffle, total is: 3
Consumer 1 ate a waffle, total is: 2
The baker made a waffle, total is: 4
The baker made a waffle, total is: 5
The baker made a waffle, total is: 6
The baker made a waffle, total is: 7
The baker made a waffle, total is: 7
The baker made a waffle, total is: 8
Consumer 5 ate a waffle, total is: 6
Consumer 4 ate a waffle, total is: 7
Consumer 3 ate a waffle, total is: 6
Consumer 2 ate a waffle, total is: 5

What now?

Threads are a feature of most programming languages, and the POSIX thread is the foundation for most of the higher-level implementations. Understand POSIX threads, and other forms of threads are just different in semantics and syntax. This is only a short introduction to a vast subject, and threads can be manipulated and controlled in countless more ways.

For example, try using conditionals to ensure that at least five waffles must be baked and ready until consumers may eat one. Use the internet, or my recommendation "Programming with POSIX Threads" by David Butenhof.

Happy threading!