Parallelism

Concurrency and scheduling

Tasks

In chapter 6, we had several processes working at the same time. Each had its own memory: that is safe, but to exchange data, they have to go through a pipe or a file.

This chapter studies the other way of doing it: several tasks running at the same time in the same memory. This is called concurrent programming. The tasks may really run at the same time, on several processors (this is then called parallelism), or take turns on a single processor, fast enough to give the illusion of simultaneity. The problems, as we shall see, are the same in both cases.

Within a process, these tasks are called threads of execution, or simply threads. They are presented in detail at the end of the chapter; for now it is enough to know that a thread is a function that runs at the same time as the rest of the program, with its own stack, but sharing everything else: global variables, heap, open files.

Scheduling

It is the system that decides, at every moment, which task runs on which processor: this is scheduling. It can interrupt a task at any time, between two machine instructions, to run another one, then resume it later where it left off. The program does not know when this happens, and cannot predict it.

Determinism

A sequential program is deterministic: with the same inputs, it always does the same thing. A concurrent program no longer is. The order in which the instructions of the different tasks interleave changes from one run to the next, and with it, sometimes, the result.

This is what makes concurrency bugs so hard: a wrong program can work a thousand times, then fail once, at the customer's. And the bug often vanishes as soon as you add a printf to observe it, because printing changes the timing.

Atomicity and critical section

Very few things are atomic. compteur = compteur + 1, which fits on one line of C, translates into three machine instructions:

1. Read: load compteur from memory into a register.
2. Compute: add 1 to the register.
3. Write: store the register into compteur.

If two tasks execute this line at the same time, and the scheduler interleaves them badly, this can happen (the counter is 5 at the start):

Two increments, and the counter has only gone up by 1: an update has been lost. This is a race condition: the result depends on the order of execution.

A solution to the critical-section problem must guarantee three things:

• mutual exclusion: never two tasks in the critical section at once;
• progress: if the critical section is free and a task wants to enter it, it eventually does (tasks that are not interested cannot prevent it);
• bounded waiting: a task that wants to enter cannot be overtaken indefinitely by the others.

A simple example: the counting guards

The problem

A museum has two entrances, with a guard at each. For every visitor who comes in, the guard adds 1 to a shared counter, displayed at the reception desk. We simulate each guard by a thread that counts a million visitors:

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

#define VISITEURS 1000000

static long compteur = 0;           /* shared by the two guards */

static void *gardien(void *arg)
{
    (void)arg;
    for (int i = 0; i < VISITEURS; i++)
        compteur = compteur + 1;    /* one more visitor */
    return NULL;
}

int main(void)
{
    pthread_t g1, g2;
    pthread_create(&g1, NULL, gardien, NULL);
    pthread_create(&g2, NULL, gardien, NULL);
    pthread_join(g1, NULL);
    pthread_join(g2, NULL);
    printf("visitors: %ld (expected: %d)\n", compteur, 2 * VISITEURS);
    return 0;
}

pthread_create launches the function gardien in a new thread; pthread_join waits for it to finish (we come back to this at the end of the chapter). The programs of this chapter are compiled with gcc -std=c11 -Wall -Wextra -Werror -D_POSIX_C_SOURCE=200809L -pthread. Without optimisation, three runs in a row on an eight-core machine:

$ ./compteur
visitors: 1336530 (expected: 2000000)
$ ./compteur
visitors: 1271531 (expected: 2000000)
$ ./compteur
visitors: 1463361 (expected: 2000000)

A third of the visitors lost, and never the same number. Compiled with -O2, the same program prints 2,000,000 every time: the compiler replaced the loop with a single addition, and the window in which the guards get in each other's way has become so small that it can no longer be seen. The program is still wrong; the bug is only hidden, and will come back the day the loop does something else.

We must make compteur = compteur + 1 a critical section. Let us try, with simple means.

First attempt: flags

Each guard has a flag, which he raises while counting. Before counting, he waits for the other's flag to be lowered:

while (veut[autre])
    ;                               /* wait for the other to finish */
veut[moi] = 1;
compteur = compteur + 1;            /* critical section */
veut[moi] = 0;

This does not work. The two guards can look at each other's flag at the same time, both find it lowered, each raise their own, and enter together. Between the moment you look and the moment you raise your flag, the other has time to do the same. The test and the taking do not form an atomic operation. The complete program (with atomic variables for the flags, see below) still loses visitors:

$ ./tentative1
visitors: 1697394 (expected: 2000000)

Raising your flag before looking at the other's is no better: the two guards can raise theirs at the same time, and each wait for the other to lower his, forever. This is a deadlock.

Second attempt: taking turns

A shared variable tour says which guard is allowed to count. When he has finished, he gives the turn to the other:

while (tour != moi)
    ;                               /* wait for our turn */
compteur = compteur + 1;            /* critical section */
tour = autre;                       /* hand over */

Mutual exclusion is ensured: tour designates only one guard at a time. But the guards now have to strictly alternate. If the west entrance sees a million visitors go through and the east entrance only ten, the west guard, after his eleventh visitor, waits for the east guard to hand back the turn… which will never happen. The progress condition is not met: a task that does not want to enter prevents the other from entering. The complete program never terminates (we stop it after five seconds):

$ timeout 5 ./tentative2; echo "code $?"
code 124

The solution: Peterson's algorithm

In 1981, Gary Peterson published a solution for two tasks that combines both ideas: the flags say who wants to enter, and the turn decides between the two guards when they want to enter at the same time.

static void entrer(int moi)
{
    int autre = 1 - moi;
    veut[moi] = 1;                  /* I want to enter */
    tour = autre;                   /* but I give priority to the other */
    while (veut[autre] && tour == autre)
        ;                           /* I wait if he wants to enter and it is his turn */
}

static void sortir(int moi)
{
    veut[moi] = 0;
}

Why it works:

• Mutual exclusion. If both guards are in the critical section, each has got past his waiting loop. Guard A got past it because veut[B] was false or tour was A. Since B had raised his flag before writing tour, it must be that tour was A. And symmetrically, tour was B for B. But tour has only one value: whoever wrote it last gave priority to the other, and he is the one who waits.
• Progress. If the other does not want to enter, his flag is lowered, and we enter immediately: no more forced alternation.
• Bounded waiting. If the other leaves and then wants to come back in at once, he writes tour = moi on the way in: he cannot jump the queue a second time.

The correct version:

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

#define VISITEURS 1000000

static long compteur = 0;
static atomic_int veut[2];
static atomic_int tour;

static void entrer(int moi)
{
    int autre = 1 - moi;
    atomic_store(&veut[moi], 1);    /* I want to enter */
    atomic_store(&tour, autre);     /* but I give priority to the other */
    while (atomic_load(&veut[autre]) && atomic_load(&tour) == autre)
        ;                           /* I wait if he wants to enter and it is his turn */
}

static void sortir(int moi)
{
    atomic_store(&veut[moi], 0);
}

static void *gardien(void *arg)
{
    int moi = *(int *)arg;
    for (int i = 0; i < VISITEURS; i++) {
        entrer(moi);
        compteur = compteur + 1;    /* critical section */
        sortir(moi);
    }
    return NULL;
}

int main(void)
{
    pthread_t g[2];
    int id[2] = { 0, 1 };
    for (int i = 0; i < 2; i++)
        pthread_create(&g[i], NULL, gardien, &id[i]);
    for (int i = 0; i < 2; i++)
        pthread_join(g[i], NULL);
    printf("visitors: %ld (expected: %d)\n", compteur, 2 * VISITEURS);
    return 0;
}

$ ./peterson
visitors: 2000000 (expected: 2000000)

Correct on every run. Peterson is mostly of historical and teaching interest: it shows that mutual exclusion can be ensured with plain reads and writes. In practice, we use the system's tools, presented below.

The problems of busy waiting

All these solutions wait actively: the waiting task spins in a loop, re-reading a variable over and over. It occupies a processor to do nothing, and the time spent waiting is taken away from the task that does have useful work.

Priority inversion

Worse: busy waiting can block the whole system. Suppose a priority scheduler, which always runs the highest-priority ready task. A task L, of low priority, enters a critical section. A task H, of high priority, wants to enter in turn, and busy-waits. H is ready (it is running!), it has higher priority than L: the scheduler never again gives control to L, which therefore can never leave the critical section. H waits for L, which waits for the processor that H occupies.

Even without busy waiting, priority can be inverted: if H sleeps while waiting for L, a task M of medium priority, which has nothing to do with the critical section, can occupy the processor instead of L, and delay H indefinitely. This is what happened in 1997 to the Mars Pathfinder robot, on Mars: a low-priority weather task held a lock needed by a high-priority task, and medium-priority communication tasks prevented it from releasing it. A watchdog, seeing the priority task running late, rebooted the robot, again and again. It was fixed remotely by enabling priority inheritance: a task holding a lock awaited by a higher-priority task temporarily inherits its priority.

The solution is not to busy-wait: a task that cannot enter must go to sleep, and be woken up when the critical section becomes free. Only the system can do this: that is what the following tools provide.

Synchronisation tools

Locks (mutexes)

A mutual-exclusion lock, a mutex (mutual exclusion), has two operations:

• lock (pthread_mutex_lock): if the lock is free, take it; otherwise, go to sleep until it becomes free, then take it;
• unlock (pthread_mutex_unlock): give it back, and one of the waiting tasks is woken up.

A critical section goes between the two:

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

#define VISITEURS 1000000

static long compteur = 0;
static pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;

static void *gardien(void *arg)
{
    (void)arg;
    for (int i = 0; i < VISITEURS; i++) {
        pthread_mutex_lock(&verrou);
        compteur = compteur + 1;
        pthread_mutex_unlock(&verrou);
    }
    return NULL;
}

int main(void)
{
    pthread_t g1, g2;
    pthread_create(&g1, NULL, gardien, NULL);
    pthread_create(&g2, NULL, gardien, NULL);
    pthread_join(g1, NULL);
    pthread_join(g2, NULL);
    printf("visitors: %ld (expected: %d)\n", compteur, 2 * VISITEURS);
    return 0;
}

$ ./mutex
visitors: 2000000 (expected: 2000000)

Only the task that locked can unlock. And a lock protects data only if every access to that data takes it: it is a convention, which the compiler does not check.

Conditions

A lock protects data. But often, a task must also wait for the data to be in a certain state: for a queue to be no longer empty, for a job to be ready. Testing the state in a loop means going back to busy waiting. A condition variable lets a task sleep until another task signals that the state has changed:

• pthread_cond_wait(&cond, &verrou): releases the lock and goes to sleep, in one go (atomically); on waking, takes the lock back before returning;
• pthread_cond_signal(&cond): wakes up one of the tasks waiting on cond;
• pthread_cond_broadcast(&cond): wakes them all up.

A condition is always used with a lock, and always in this pattern:

pthread_mutex_lock(&verrou);
while (!condition_voulue)
    pthread_cond_wait(&cond, &verrou);
/* here, the condition is true, and we hold the lock */
...
pthread_mutex_unlock(&verrou);

The lock must be released when going to sleep, otherwise whoever has to change the state could never take it; and this must be done atomically, otherwise the signal could arrive between the unlocking and the falling asleep, and be lost. That is why pthread_cond_wait does both at once.

Barriers

A barrier makes a group of tasks wait until all of them have reached it. This is useful when a computation proceeds in stages, and stage 2 of each task needs the results of stage 1 of all the others.

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

#define N 3

static pthread_barrier_t barriere;

static void *travail(void *arg)
{
    int num = *(int *)arg;
    printf("thread %d: stage 1\n", num);
    pthread_barrier_wait(&barriere);    /* nobody gets through before the others */
    printf("thread %d: stage 2\n", num);
    return NULL;
}

int main(void)
{
    pthread_t fil[N];
    int id[N];
    pthread_barrier_init(&barriere, NULL, N);
    for (int i = 0; i < N; i++) {
        id[i] = i;
        pthread_create(&fil[i], NULL, travail, &id[i]);
    }
    for (int i = 0; i < N; i++)
        pthread_join(fil[i], NULL);
    pthread_barrier_destroy(&barriere);
    return 0;
}

$ ./barriere
thread 0: stage 1
thread 1: stage 1
thread 2: stage 1
thread 2: stage 2
thread 0: stage 2
thread 1: stage 2

The order of the lines changes from one run to the next, but the three “stage 1” lines always come before the “stage 2” ones.

The readers-writers problem

Some shared data, a directory for instance, is read very often and modified rarely. An ordinary lock lets only one task through at a time, even if they are all only reading. Yet several simultaneous reads pose no problem at all: only writes must be alone.

A readers-writer lock can be taken in two ways: for reading (several tasks at once) or for writing (just one, and no readers):

static pthread_rwlock_t verrou = PTHREAD_RWLOCK_INITIALIZER;
static int annuaire[100];           /* the shared data */

static int lire(int i)
{
    pthread_rwlock_rdlock(&verrou); /* several readers at once */
    int x = annuaire[i];
    pthread_rwlock_unlock(&verrou);
    return x;
}

static void ecrire(int i, int x)
{
    pthread_rwlock_wrlock(&verrou); /* one writer, alone */
    annuaire[i] = x;
    pthread_rwlock_unlock(&verrou);
}

A question of policy remains: if readers keep arriving, a writer may wait indefinitely for there to be none left. This is starvation. Implementations choose to favour either readers or writers; under Linux, the default choice favours readers.

A more advanced problem: producers and consumers

The problem

Some tasks produce data (incoming requests, decoded images), others consume it (process it, display it). Between them, a queue: producers put items in, consumers take them out, in order of arrival. This is the pattern of every server, and it is also that of a pipe between two processes (chapter 5).

Three constraints:

1. Mutual exclusion: the queue is shared, only one task at a time modifies it.
2. A consumer that finds the queue empty waits for a producer to put something in.
3. The queue has a bounded capacity: a producer that finds it full waits for a consumer to make room.

With a lock and two conditions

We store the queue in a circular array. The lock ensures constraint 1; the condition non_vide makes consumers wait, the condition non_pleine producers.

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

#define CAPACITE 4
#define PRODUITS 20

/* A bounded circular queue, protected by a lock and two conditions. */
static int file[CAPACITE];
static int tete = 0, nb = 0;
static pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t non_vide = PTHREAD_COND_INITIALIZER;
static pthread_cond_t non_pleine = PTHREAD_COND_INITIALIZER;

static void deposer(int x)
{
    pthread_mutex_lock(&verrou);
    while (nb == CAPACITE)
        pthread_cond_wait(&non_pleine, &verrou);
    file[(tete + nb) % CAPACITE] = x;
    nb++;
    pthread_cond_signal(&non_vide);
    pthread_mutex_unlock(&verrou);
}

static int retirer(void)
{
    pthread_mutex_lock(&verrou);
    while (nb == 0)
        pthread_cond_wait(&non_vide, &verrou);
    int x = file[tete];
    tete = (tete + 1) % CAPACITE;
    nb--;
    pthread_cond_signal(&non_pleine);
    pthread_mutex_unlock(&verrou);
    return x;
}

static void *producteur(void *arg)
{
    (void)arg;
    for (int i = 1; i <= PRODUITS; i++)
        deposer(i);
    deposer(-1);                    /* end marker */
    return NULL;
}

static void *consommateur(void *arg)
{
    (void)arg;
    long total = 0;
    int x;
    while ((x = retirer()) != -1)
        total += x;
    printf("consumer: total = %ld\n", total);
    return NULL;
}

int main(void)
{
    pthread_t p, c;
    pthread_create(&c, NULL, consommateur, NULL);
    pthread_create(&p, NULL, producteur, NULL);
    pthread_join(p, NULL);
    pthread_join(c, NULL);
    return 0;
}

$ ./file_bornee
consumer: total = 210

The queue never contains more than four elements: the producer is held back by the consumer. The producer signals the end with a special value, -1, which the consumer recognises.

Semaphores

Definition

The semaphore was invented by Edsger Dijkstra in 1965. It is an integer counter, never negative, with two atomic operations:

• P (from the Dutch proberen, to try; in POSIX sem_wait): if the counter is positive, decrement it; otherwise, sleep until it becomes positive, then decrement it;
• V (verhogen, to increase; in POSIX sem_post): increment the counter, and wake up a waiting task.

The counter can be seen as a number of tokens: P takes one (waiting if there are none left), V gives one back. A semaphore initialised to 1 is a lock. Initialised to $n$, it lets $n$ tasks through at once. Initialised to 0, it is used to wait for an event: P blocks until another task does V.

#include <semaphore.h>

int sem_init(sem_t *s, int partage, unsigned valeur);   /* partage = 0: between threads of one process */
int sem_wait(sem_t *s);                                 /* P */
int sem_post(sem_t *s);                                 /* V */

Unlike a lock, a semaphore has no owner: a task can do V on a semaphore on which another did P. This is what makes it possible to use them to signal from one task to another.

Producers and consumers with semaphores

Three semaphores are enough: places counts the free cells (initialised to the capacity), elements counts the full cells (initialised to 0), exclusion protects the queue (initialised to 1). No more need to test whether the queue is full or empty: the counters do it.

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

#define CAPACITE 4
#define PRODUITS 1000
#define NPROD 3

static int file[CAPACITE];
static int entree = 0, sortie = 0;
static sem_t places;                /* number of free cells */
static sem_t elements;              /* number of full cells */
static sem_t exclusion;             /* only one at a time in the queue */

static void deposer(int x)
{
    sem_wait(&places);              /* P(places) */
    sem_wait(&exclusion);
    file[entree] = x;
    entree = (entree + 1) % CAPACITE;
    sem_post(&exclusion);
    sem_post(&elements);            /* V(elements) */
}

static int retirer(void)
{
    sem_wait(&elements);
    sem_wait(&exclusion);
    int x = file[sortie];
    sortie = (sortie + 1) % CAPACITE;
    sem_post(&exclusion);
    sem_post(&places);
    return x;
}

static void *producteur(void *arg)
{
    (void)arg;
    for (int i = 1; i <= PRODUITS; i++)
        deposer(i);
    return NULL;
}

int main(void)
{
    sem_init(&places, 0, CAPACITE);
    sem_init(&elements, 0, 0);
    sem_init(&exclusion, 0, 1);

    pthread_t p[NPROD];
    for (int k = 0; k < NPROD; k++)
        pthread_create(&p[k], NULL, producteur, NULL);

    long total = 0;                 /* main is the consumer */
    for (int i = 0; i < NPROD * PRODUITS; i++)
        total += retirer();
    for (int k = 0; k < NPROD; k++)
        pthread_join(p[k], NULL);
    printf("total = %ld (expected: %d)\n", total, NPROD * PRODUITS * (PRODUITS + 1) / 2);
    return 0;
}

$ ./file_semaphores
total = 1501500 (expected: 1501500)

The notion of threads

General definition

Where fork copies the whole memory, creating a thread only requires a new stack. And where two processes have to go through a pipe to exchange data, two threads only need to write into a global variable… which is both their strength and, as we have seen throughout the chapter, their danger.

Kinds of threads

Who manages the threads: the system's kernel, or a library inside the process?

• User threads are managed by a library, without the kernel knowing: it sees only one process. Creating a thread and switching from one to another is very fast (no system call). But the kernel gives the process only one processor, and if a thread makes a blocking system call (a read on the keyboard), the whole process goes to sleep.
• Kernel threads are managed by the system, which schedules them like processes. They can run on several processors, and a blocked thread blocks only itself; in exchange, every creation and every thread switch goes through the kernel.

Implementations are described by the way they map the program's threads onto kernel threads:

Advantages and drawbacks

Compared with several processes, threads:

• are faster to create and to switch;
• communicate effortlessly, through shared memory;
• but are not isolated: a thread that writes in the wrong place corrupts the memory of all the others, and a segmentation fault in one kills the whole process;
• and their shared memory forces every access to be synchronised, with all the pitfalls of this chapter.

A web browser uses both: one process per tab, so that a tab that crashes does not take the others down with it, and several threads in each process.

Programming with POSIX threads

The POSIX standard defines a thread library, pthreads (<pthread.h>). We compile with the -pthread option.

Creating and waiting

int pthread_create(pthread_t *fil, const pthread_attr_t *attributs,
                   void *(*fonction)(void *), void *argument);
int pthread_join(pthread_t fil, void **resultat);

• pthread_create launches fonction(argument) in a new thread, and stores its identifier in *fil. attributs may be NULL (default settings). It returns 0 on success, an error code otherwise.
• The function takes a void * and returns a void *: this is the generic way, in C, of passing “anything” (chapter 2). We pass it the address of some data, which it converts back to the right type.
• pthread_join waits for the thread to end, and collects what its function returned. It is the equivalent of wait for processes: a finished thread that nobody waits for keeps its resources.
• When main ends, the entire process ends, with all its threads. So they must be waited for beforehand.

To pass several pieces of data, and get a result back, we pass the address of a structure. Here is the sum of a large array, cut into four slices, one per thread:

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

#define N 4
#define TAILLE 1000000

static int tab[TAILLE];

struct tranche {
    int debut, fin;                 /* we sum tab[debut .. fin-1] */
    long somme;                     /* the result, filled in by the thread */
};

static void *sommer(void *arg)
{
    struct tranche *t = arg;
    t->somme = 0;
    for (int i = t->debut; i < t->fin; i++)
        t->somme += tab[i];
    return NULL;
}

int main(void)
{
    for (int i = 0; i < TAILLE; i++)
        tab[i] = i % 10;

    pthread_t fil[N];
    struct tranche tr[N];           /* one structure per thread: nothing shared */
    for (int k = 0; k < N; k++) {
        tr[k].debut = k * TAILLE / N;
        tr[k].fin = (k + 1) * TAILLE / N;
        pthread_create(&fil[k], NULL, sommer, &tr[k]);
    }

    long total = 0;
    for (int k = 0; k < N; k++) {
        pthread_join(fil[k], NULL);
        total += tr[k].somme;
    }
    printf("sum = %ld\n", total);
    return 0;
}

$ ./somme
sum = 4500000

No lock here: each thread writes into its own structure, and main reads the results only after pthread_join. The best synchronisation is the one you do not need: split the work so that the threads share as little as possible.

The loop-variable trap

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

#define N 4

static void *travail(void *arg)
{
    int num = *(int *)arg;
    printf("I am thread %d\n", num);
    return NULL;
}

int main(void)
{
    pthread_t fil[N];
    for (int i = 0; i < N; i++)
        pthread_create(&fil[i], NULL, travail, &i);   /* WRONG */
    for (int i = 0; i < N; i++)
        pthread_join(fil[i], NULL);
    return 0;
}

$ ./boucle
I am thread 2
I am thread 3
I am thread 4
I am thread 4

The four threads receive the same address, that of i. Each reads i when it starts, that is, at any time: the loop may have moved on in the meantime, or even be over (hence the 4). Worse, once the loop has ended, i no longer exists, and its address may be reused for something else. The result changes on every run.

Conclusion

As soon as several tasks share data and at least one of them modifies it, synchronisation is needed. To remember:

• a line of C is not atomic; without protection, updates get lost, and not always, from one run to the next;
• a critical section is protected by a lock; a state is waited for with a condition, always in a while loop; semaphores count resources;
• deadlock is avoided by always taking locks in the same order;
• and above all, share as little as possible: each thread works on its own data, and only the results are pooled.

What makes concurrency hard is not the code, which stays short: it is that it cannot be tested. A correct concurrent program is proved, by reasoning about all possible interleavings, as we did for Peterson.