11. Concurrency and Threads

Concurrency and Threads#

Concurrency means multiple computations make progress during overlapping periods of time. They do not need to execute at the same instant. Parallelism means multiple computations literally execute simultaneously, which normally requires multiple CPU cores or other processing units.

flowchart TB
    C["Concurrency on one core<br/>A → B → A → B"]
    P["Parallelism on two cores<br/>Core 1: A | Core 2: B"]
    C ~~~ P

A concurrent program may become parallel when the OS schedules its work across cores, but concurrency is primarily about program structure and overlapping progress.

Flynn's Taxonomy#

Flynn's taxonomy classifies computation by the number of instruction and data streams:

This is a vocabulary for kinds of parallel hardware and computation. It is separate from the concurrency/parallelism distinction: a program can be concurrent while taking turns on one SISD core.

Processes or Threads?#

Processes can run concurrently and provide strong isolation, but each process has its own address space. Communicating through Pipes and File Redirection or another IPC mechanism requires explicit work.

Threads provide concurrency within one process. Threads in the same process share:

• program code;
• global and static variables;
• heap allocations;
• open file descriptors;
• environment variables and current working directory.

Each thread has its own:

• registers and program counter;
• stack;
• thread ID;
• thread-local state such as errno.

flowchart TB
    subgraph Process["One process"]
        CODE["shared code"]
        GLOBAL["shared globals"]
        HEAP["shared heap"]
        FD["shared file descriptors"]
        T1["Thread 1<br/>registers + stack"]
        T2["Thread 2<br/>registers + stack"]
        T3["Thread 3<br/>registers + stack"]
    end

Although each thread has its own stack, the stacks occupy the shared address space. One thread can technically access another thread's stack through a pointer. The problem is not access permission; it is ensuring that the pointed-to object still exists.

Creating a POSIX Thread#

POSIX threads, or pthreads, are declared in <pthread.h>. Compilation commonly needs -pthread:

dcc -pthread program.c -o program

A thread starts in a function with this exact shape:

void *worker(void *argument);

pthread_create() launches it:

int pthread_create(
	pthread_t *thread,
	const pthread_attr_t *attributes,
	void *(*start_routine)(void *),
	void *argument
);

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

void *worker(void *argument) {
	char *name = argument;
	printf("hello from %s\n", name);
	return NULL;
}

int main(void) {
	pthread_t thread;
	int error = pthread_create(&thread, NULL, worker, "the worker");
	if (error != 0) {
		fprintf(stderr, "pthread_create failed: %d\n", error);
		return 1;
	}

	error = pthread_join(thread, NULL);
	if (error != 0) {
		fprintf(stderr, "pthread_join failed: %d\n", error);
		return 1;
	}

	return 0;
}

Like posix_spawn(), pthread functions usually return an error number directly rather than setting errno.

Joining Threads#

int pthread_join(pthread_t thread, void **result);

Joining waits until the chosen thread finishes and optionally collects its return pointer. If main() returns, the process terminates and all other threads disappear, whether or not they finished. A process must therefore join threads whose work it needs.

A worker can finish by returning from its start routine or by calling pthread_exit(result). Returning is usually clearer. The result pointer follows the same lifetime rules either way.

void *worker(void *unused) {
	long *answer = malloc(sizeof *answer);
	if (answer == NULL) {
		return NULL;
	}
	*answer = 42;
	return answer;
}

// Later in main:
void *result;
int error = pthread_join(thread, &result);
if (error != 0) {
	fprintf(stderr, "pthread_join failed: %d\n", error);
	return 1;
}

long *answer = result;
if (answer != NULL) {
	printf("%ld\n", *answer);
	free(answer);
}

Never return a pointer to a worker's local variable. Its stack frame ceases to exist when the thread returns.

Passing Data Safely#

pthread_create() passes one void *, so a structure is useful for multiple values:

struct task {
	const int *values;
	size_t start;
	size_t end;
	long result;
};

void *sum_range(void *raw) {
	struct task *task = raw;
	task->result = 0;
	for (size_t i = task->start; i < task->end; i++) {
		task->result += task->values[i];
	}
	return NULL;
}

The pointed-to task must remain alive until the worker has finished. Safe choices include:

• storage in main() when main() joins all workers before returning;
• a heap allocation freed after the join;
• static storage, when sharing that lifetime and access pattern is intentional.

A classic bug passes the address of one loop variable to every worker:

for (int i = 0; i < THREADS; i++) {
	pthread_create(&threads[i], NULL, worker, &i); // broken
}

All workers receive the same address. By the time they read it, the loop may have changed i or ended. Store one stable argument object per thread.

struct task tasks[THREADS];

for (size_t i = 0; i < THREADS; i++) {
	tasks[i].values = values;
	tasks[i].start = starts[i];
	tasks[i].end = ends[i];
	pthread_create(&threads[i], NULL, sum_range, &tasks[i]);
}

// Keep tasks alive and unchanged until the corresponding joins complete.

When Threads Help#

Threads can improve a program when:

• independent CPU-heavy work can run on several cores;
• one thread can make progress while another blocks on I/O;
• a user interface must remain responsive during background work;
• shared-memory communication is cheaper than process IPC.

They do not automatically make code faster. Thread creation, scheduling, cache traffic and synchronisation all have costs. If the task is tiny, sequential code can be quicker. A calculation with unavoidable sequential dependencies cannot be divided arbitrarily.

Data Races#

A data race occurs when threads access the same memory concurrently, at least one access writes it, and the accesses are not properly synchronised.

int bank_account = 0;

void *deposit(void *unused) {
	bank_account++;
	return NULL;
}

bank_account++ looks like one C expression, but at machine level it is a read-modify-write sequence:

load bank_account
add 1
store bank_account

Two threads can both load 42, both calculate 43, and both store 43. One increment is lost.

sequenceDiagram
    participant A as Thread A
    participant M as bank_account
    participant B as Thread B
    A->>M: load 42
    B->>M: load 42
    Note over A: calculate 43
    Note over B: calculate 43
    A->>M: store 43
    B->>M: store 43
    Note over M: expected 44, got 43

In C, a data race is undefined behaviour. It is not merely a rare arithmetic error. The compiler and CPU are allowed to make assumptions which can produce outcomes more surprising than an occasional lost update.

Critical Sections and Mutexes#

A critical section accesses shared state which must not be manipulated by multiple threads at once. A mutex establishes mutual exclusion: only the thread which successfully locks it enters the protected region; another thread trying to lock it waits.

int bank_account = 0;
pthread_mutex_t bank_lock = PTHREAD_MUTEX_INITIALIZER;

void *deposit_many(void *unused) {
	for (int i = 0; i < 100000; i++) {
		pthread_mutex_lock(&bank_lock);
		bank_account++;
		pthread_mutex_unlock(&bank_lock);
	}
	return NULL;
}

The mutex protects a rule about data, not just a line of code. Every access participating in that rule must use the same mutex. Locking only the writers while readers access the variable unsynchronised is still broken.

Keep critical sections as small as correctness permits, but not smaller. If two fields must change together to preserve an invariant, protect the whole multi-step update.

Deadlock#

A deadlock occurs when threads wait forever for one another. Consider two locks:

Thread 1: lock A -> lock B -> work -> unlock B -> unlock A
Thread 2: lock B -> lock A -> work -> unlock A -> unlock B

If Thread 1 owns A while Thread 2 owns B, each waits for a lock which the other cannot release.

flowchart TB
    T1["Thread 1<br/>holds Lock A"] -->|"waits for"| LB["Lock B"]
    LB -->|"held by"| T2["Thread 2<br/>holds Lock B"]
    T2 -->|"waits for"| LA["Lock A"]
    LA -->|"held by"| T1

A powerful prevention rule is to enforce a strict global lock acquisition hierarchy. If every thread acquires Lock A before Lock B, circular waiting cannot occur. Releasing locks in reverse order of acquisition is standard practice.

Atomics#

For simple shared values, C atomic types can make individual operations indivisible:

#include <stdatomic.h>

atomic_int bank_account = 0;

void *deposit_many(void *unused) {
	for (int i = 0; i < 100000; i++) {
		bank_account += 1;
	}
	return NULL;
}

Atomic compound operations such as ++, +=, -=, |=, &= and ^= perform an atomic read-modify-write on an atomic object. Explicit functions are also available:

int old_value = atomic_fetch_add(&bank_account, 1);

However:

bank_account = bank_account + 1;

is an atomic load followed by a separate atomic store. Another thread can intervene between them, so the whole increment is not atomic.

Atomics are not a universal mutex replacement. If correctness depends on a relationship between several variables or several operations, one atomic operation may not protect the invariant. Memory ordering also becomes subtle beyond COMP1521's scope.

Mutex or Atomic?#

A mutex is easier to reason about for compound state. Atomics can be cheaper and cannot themselves form a lock-order deadlock, but lock-free does not mean mistake-free.

Common Mistakes#

• Assuming concurrency always means parallel execution.
• Passing a pointer whose object expires before the worker reads it.
• Passing the same loop-variable address to every thread.
• Returning from main() before workers are joined.
• Treating x++ on an ordinary shared int as atomic.
• Protecting writes but leaving reads unsynchronised.
• Locking different mutexes around accesses to the same invariant.
• Acquiring several mutexes in inconsistent orders.
• Putting one mutex around an entire program and eliminating all useful parallelism.
• Assuming atomic_x = atomic_x + 1 is one atomic update.

Practice#

1. What resources are shared among threads of the same process, and what is private to each thread?
2. Why is counter++ not thread-safe without synchronisation?
3. What is a data race, and what condition makes it undefined behaviour?
4. How can deadlock be prevented when threads must acquire multiple mutex locks?
5. Why is pthread_join() necessary before main() exits?