Threads and race conditions

A thread is one path of execution inside a process. A process can have many threads, and they share the process's code, global data, heap and open files. Each thread has its own stack, registers and program counter.

A web browser uses several processes (one per site, for safety); a game uses many threads (graphics, sound, input) that share one world.

The kernel schedules kernel threads; libraries can also run user threads on top of them. Linux and Windows use the one-to-one model: each user thread is a kernel thread.

Shared memory is dangerous

On UNIX, threads come from the pthreads library:

int count = 0;                       /* shared by both threads */
void *work(void *arg) {
    for (int i = 0; i < 1000000; i++) count++;
    return NULL;
}
int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("%d\n", count);           /* should be 2000000, usually is not */
}

count++ looks like one step, but the CPU does it in three: load count into a register, add 1, store the register back. The scheduler can switch threads between any two of them. If both threads load before either stores, one update is lost. A result that depends on the exact timing of threads is a race condition.

Be the scheduler: run A, B, A, B, A, B and the count ends at 1. Run all of A first and it ends at 2. Races are hard to find because the bad order happens rarely, and never while you are watching with a debugger.

#include <stdio.h>

int count = 0;          /* shared by threads A and B */

int main(void) {
    int reg_a, reg_b;   /* each thread's own CPU register */

    /* Both threads run count = count + 1, switched like this: */
    reg_a = count;      /* A: load  */
    reg_b = count;      /* B: load  (the scheduler switched to B) */
    reg_a = reg_a + 1;  /* A: add   */
    reg_b = reg_b + 1;  /* B: add   */
    count = reg_a;      /* A: store */
    count = reg_b;      /* B: store, over A's update */

    printf("count = %d after two increments\n", count);
    return 0;
}

The example fixes one bad order in plain C: reg_a and reg_b play the two threads' registers. The code that touches shared data (here, the load, add and store) is a critical section. Only one thread may be inside it at a time; the next lesson shows how to make sure of that.

Mark lesson complete