Concurrency: An Introduction

In a multi-threaded process, each thread runs independently and of course may call into various routines to do whatever work it is doing. Instead of a single stack in the address space, there will be one per thread. Let’s say we have a multi-threaded process that has two threads in it; the resulting address space looks different.

Why Use Threads?

There are at least two major reasons you should use threads. The first is simple: parallelism. The task of transforming your standard single-threaded program into a program that does this sort of work on multiple CPUs is called parallelization, and using a thread per CPU to do this work is a natural and typical way to make programs run faster on modern hardware.

The second reason is a bit more subtle: to avoid blocking program progress due to slow I/O. Threading enables overlap of I/O with other activities within a single program, much like multiprogramming did for processes across programs.

The Heart Of The Problem: Uncontrolled Scheduling

A race condition (or, more specifically, a data race) occurs when the results depend on the timing execution of the code. With some bad luck (i.e., context switches that occur at untimely points in the execution), we get the wrong result. In fact, we may get a different result each time; thus, instead of a nice deterministic computation (which we are used to from computers), we call this result indeterminate, where it is not known what the output will be and it is indeed likely to be different across runs.

Because multiple threads executing this code can result in a race condition, we call this code a critical section. A critical section is a piece of code that accesses a shared variable (or more generally, a shared resource) and must not be concurrently executed by more than one thread. What we really want for this code is what we call mutual exclusion. This property guarantees that if one thread is executing within the critical section, the others will be prevented from doing so.

To avoid these problems, threads should use some kind of mutual exclusion primitives; doing so guarantees that only a single thread ever enters a critical section, thus avoiding races, and resulting in deterministic program outputs.

Thread API

Create a thread

man 3 pthread_create

#include <pthread.h>

int
pthread_create(pthread_t *thread, 
								const pthread_attr_t *attr, 
								void *(*start_routine)(void *), 
								void *arg);

Why do we need these void pointers? Well, the answer is quite simple: having a void pointer as an argument to the function start routine allows us to pass in any type of argument; having it as a return value allows the thread to return any type of result.

Complete a thread

#include <pthread.h>

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

The pthread_join() function suspends execution of the calling thread until the target thread terminates unless the target thread has already terminated.

value_ptr stores the return value of the executed thread.

! Use malloc to store the return value, do not allocate it on stack

Locks

Beyond thread creation and join, probably the next most useful set of functions provided by the POSIX threads library are those for providing mutual exclusion to a critical section via locks. The most basic pair of routines to use for this purpose is provided by the following.

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

Wrap lock and unlock ops around your critical section like below

pthread_mutex_t lock;
pthread_mutex_lock(&lock);
x = x + 1; // or whatever your critical section is
pthread_mutex_unlock(&lock);

Unfortunately, this code is broken, in two important ways. The first problem is a lack of proper initialization. With POSIX threads, there are two ways to initialize locks. One way to do this is to use PTHREAD MUTEX INITIALIZER, as follows:

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

The dynamic way to do it (i.e., at run time) is to make a call to pthread mutex init(), as follows:

int rc = pthread_mutex_init(&lock, NULL);
assert(rc == 0); // always check success!

Either way works, but we usually use the dynamic (latter) method. Note that a corresponding call to pthread_mutex_destroy() should also be made when you are done with the lock.

The second problem with the code above is that it fails to check error codes when calling lock and unlock. Just like virtually any library routine you call in a UNIX system, these routines can also fail!

// Keeps code clean; only use if exit() OK upon failure
void Pthread_mutex_lock(pthread_mutex_t *mutex) {
int rc = pthread_mutex_lock(mutex);
assert(rc == 0);
}

Condition Variables

Condition variables are useful when some kind of signaling must take place between threads if one thread is waiting for another to do something before it can continue.

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cond);

wait for certain condition (has mutex as second arg because wait will release the lock)

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
Pthread_mutex_lock(&lock);
while (ready == 0)
Pthread_cond_wait(&cond, &lock);
Pthread_mutex_unlock(&lock);

wake

Pthread_mutex_lock(&lock);
ready = 1;
Pthread_cond_signal(&cond);
Pthread_mutex_unlock(&lock);

use man -k pthread to find out more system interface

Best Practice

• Keep critical section as simple as possible.
• Minimize thread interactions.
• Initialize locks and condition variables.
• Check your return codes.
• Always use condition variables to signal between threads. While it is often tempting to use a simple flag, don’t do it.

Locks

A lock is just a variable, and thus to use one, you must declare a lock variable of some kind (such as mutex above). This lock variable (or just ‘lock’ for short) holds the state of the lock at any instant in time.

It is either available (or unlocked or free) and thus no thread holds the lock, or acquired (or locked or held), and thus exactly one thread holds the lock and presumably is in a critical section. We could store other information in the data type as well, such as which thread holds the lock or a queue for ordering lock acquisition, but information like that is hidden from the user of the lock.

Based on hardware support, we can build a spin lock using hardware primitives like test-and-set or compare-and-swap.

typedef struct {
    int flag;
} lock_t;

void init(lock_t *lock) {
    // 0: lock is available, 1: lock is held
    lock->flag = 0;
}

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ; // spin-wait (do nothing)
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

Avoid spinning (CPU-consuming) :

• Just Yield, Baby: A thread can be in one of three states (running, ready, or blocked); yield is simply a system call that moves the caller from the running state to the ready state, and thus promotes another thread to running. Thus, the yielding thread essentially deschedules itself.
• Using Queues: Sleeping Instead Of Spinning. park() to put a calling thread to sleep, and unpark(threadID) to wake a particular thread as designated by threadID.