Ostep-Threads

Threads

So far the processes we've described have been single-threaded, and we now introduce the idea of a multi-threaded process. Threads are almost like separate processes, but they get to share data.

• Each thread gets its own registers and program counters, and thus requires a context switch; however unlike with processes, the page table can stay the same, since the threads share a virtual address space.
• Similar to PCBs (Process Control Blocks), now each process needs to track TCBs (Thread Control Blocks)
• A multi-threaded program needs multiple stacks! So the simple address space of [Heap -> ... <- Stack] no longer holds.
  • We refer to the stack relevant to a given thread as its thread-local storage.

Motivation

The motivation for threads is simply a better utilization of resources, whether from parallelization or allowing some progress to be made while waiting on I/O, etc. The motivation over processes is that we get to share data, which is generally not possible (communication between processes is extremely limited in comparison).

Problems

Nondeterminism

Due to uncontrolled scheduling, if we fork threads to print "hello" and "world", we have no guarantee of which one runs first.

Race conditions

When it comes to shared data, naive mutation from various threads will result in race conditions and indeterminate behavior. In general, we need atomicity guarantees for some actions. E.g x = x + 1 generates three instructions:

mov 0xaddr, %eax # load value into register
add $0x1, %eax   # increment the register
mov %eax, 0xaddr # store the value from register

and if multiple threads run this line of code, the scheduler may switch threads between the execution of these instructions! This leads to data races and unexpected outcomes.

• A critical section is a piece of code that access a shared resource, like a variable.
• Mutual exclusion primitives are used to ensure that only one thread is running a critical section at a time, avoiding race conditions.

API

Specifically, the core pieces of the POSIX thread API:

Thread create

// NULL can be used for default attrs or unnecessary args.
// Intermediary types can be used for multiple arg functions.
int pthread_create(
	pthread_t * thread,
	const pthread_attr_t * attr,
	void * (*start_routine) (void*),
	void * arg
);

Thread complete

// Double pointer necessary because the join call changes the value with the result of the thread
int pthread_join(
	pthread_t thread,
	void ** value_ptr
);

Simple example of create/complete

int main(int argc, char *argv[]) {
	pthread_t p;
	int rc, m;
	rc = pthread_create(&p, NULL, mythread, (void *) 100);
	assert(rc == 0);
	rc = pthread_join(p, (void **) &m);
	assert(rc == 0);
}

void *mythread(void *arg) {
	int m = (int) arg;
	return (void *) (arg + 1);
}

Locks

These are useful to ensure atomicity, and that threads have mutually exclusive access to run critical sections.

// Pass the pointer to the mutex around to ensure that only one thread holds the lock, finish a critical section, then release the lock. Then no more than one thread is in a critical section at a time!
// Remember to assert that return is 0!
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

// Alternatively, non-blocking requests for the lock
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_timedlock(pthread_mutex_t *mutex, struct timespec *abs_timeout);

Condition Variables

These are useful for efficiency, to put threads to "sleep" and let others "wake" them up when they're ready for work.

// A lock must be held to use _either_ of these routines.
int pthread_cond_wait(
	pthread_cond_t *cond,
	pthread_mutex_t *mutex,
);
int pthread_cond_signal(
	pthread_cond_t *cond,
);

Example

// We must first initialize the mutex and condition:
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int rc = pthread_mutex_lock(&lock);
assert(rc == 0);

// Important! Check the condition for whether this is ready. Some schedulers may arbitrarily switch threads, even without a signal being raised.
// USE CONDITIONS; don't just spin cycles with `while (ready == 0) {}`
while (ready == 0) {
	int rc = pthread_cond_wait(&cond, &lock);
	assert(rc == 0);
}
int rc = pthread_mutex_unlock(&lock);
assert(rc == 0);

// In some other thread, we signal that the other thread is ready to go
int rc = pthread_mutex_lock(&lock);
assert(rc == 0);
ready = 1;
int rc = pthread_cond_signal(&cond);
assert(rc == 0);
int rc = pthread_mutex_unlock(&lock);
assert(rc == 0);