Concurrency: an introduction

A thread's stack

what has to be private when everything else is shared

The address space

A 16KB address space, drawn as in the chapter. Code and heap are shared by every thread; each stack belongs to one thread alone.

shared
thread 1 only
thread 2 only
thread 3 only

How many threads

Every thread the program creates needs a stack of its own somewhere in the space.

Private and shared

The OS keeps one thread control block per thread, much as it keeps a process control block per process. Switching between threads of the same process leaves the address space, and so the page table, untouched.

Keyboard: ← → to step, Space to play or pause.

A context switch between threads

save into one TCB, restore from the other

The processor and the two control blocks

One set of registers, two threads that each need their own copy of it.

CPU registers

↕the OS moves register state between the CPU and the TCBs

Where the stack pointer is pointing

Each thread runs on its own stack, so the switch changes the stack pointer as well as the program counter.

Thread creation and execution paths

the same program, three legal orderings

The trace

Ordering

Only the ordering differs; the program is identical in all three. Which one happens is up to the scheduler, and it can differ from run to run on the same machine.

The program

void *mythread(void *arg) {
    printf("%s\n", (char *) arg);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    printf("main: begin\n");
    Pthread_create(&p1, NULL, mythread, "A");
    Pthread_create(&p2, NULL, mythread, "B");
    // join waits for the threads to finish
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    printf("main: end\n");
    return 0;
}

Output so far

A race condition

two threads, one shared counter

What the hardware actually does

The line counter = counter + 1 compiles into three instructions, and a thread can be interrupted between any two of them.

Interrupt thread 1

Thread 1

Thread 2

Shared memory

One counter at address 0x8049a1c, reachable by both threads because they share the address space.

counter =50

The words for it

A critical section is a piece of code that touches a shared resource, here the three instructions that update the counter.

A race condition is when the result depends on when the scheduler happens to switch. The outcome is indeterminate: correct on most runs, wrong on some.

The fix is mutual exclusion, a guarantee that only one thread is inside the critical section at a time, so the update becomes atomic. That is what locks are for, and is where the next chapters go.