Lab 9: Concurrency 1

Outline & Preparation#

In this week’s lab, you will:

• Learn the basics of pthreads and their use in writing concurrent applications.
• Learn how to use pthread locks to synchronise between threads.
• Learn about condition variables and using them to implement shared data between threads.

Clone the lab pack 4 repo from here.

Introduction to POSIX Threads#

POSIX Threads (hereafter referred to as “pthreads”) are a standard interface for using threads in C programs. A thread is a “logical flow that runs in the context of a process”. They are a way of writing concurrent programs in C.

The code you are given to work on this week may feel trivial and not the sort of programs that demonstrate the practical benefits of concurrency. This is because the lab is mostly focused on introducing you to the basics of using pthreads. In our next (and final) lab we will put these concepts together to create something more substantial.

Creating Threads#

A pthread is created by calling the pthread_create function:

#include <pthread.h>

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

This will launch a new thread in the calling process. The “thread id” of this new thread will be stored at the location pointed to by the first argument thread. The newly-created thread will start executing the function pointed to by the start_routine argument, which which takes a single void * as an argument. We will often refer to this start_routine function as the thread’s “top level function”. The attr argument is used to define certain attributes of the thread (this will often just be left NULL).

Thread Routines#

The start_routine argument provided to pthread_create is a pointer to a function that returns a “void pointer” and accepts a void pointer as its sole argument. While it may seem prohibitive to only allow one argument to be passed to a thread routine, remember that a void pointer in C represents a “generic pointer” to an unknown type (e.g. the return type of malloc). If you need to pass multiple arguments to a thread routine you can pass a pointer to a struct type with all the necessary data in it.

Joining Threads#

What happens to the thread created by a call to pthread_create when it returns from the given start_routine? Unlike a child process created with fork, it will not continue following the same logical control flow as its “parent”. Instead, a thread that returns from its top level function it will terminate. The operating system kernel will handle reclaiming certain resources created for the thread, but only after the another thread in the process has indicated it is ok to do so by called a specific function — pthread_join:

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

This function waits for the thread specified by thread to terminate. If that thread has already terminated, then pthread_join returns immediately. Otherwise the caller will block until has done so. The retval argument is a pointer to a void pointer, which if non-NULL will be used to store the return value of the terminated thread.

Note that returning from a top-level function isn’t the only way a thread can terminate, though it is the way we will be relying on for the first part of this lab.

Exercise 1: Creating & Joining Threads#

Your first task is to look at a very simple (and broken) usage of the functions we described above. If you open the simple-pthreads.c file in your repository, you will see a program that will launch a number of threads that each run the following thread_func function:

void *thread_func(void *arg) {
  size_t thread_num = *((size_t *)arg);
  printf("[Thread #%lu] ", thread_num);
  printf("Hello from %s %lu!\n", "thread number", thread_num);
  printf("[Thread #%lu] ", thread_num);
  printf("Has finished executing, %s\n", "and will return now.");
  return NULL;
}

Each thread created will print two messages to stdout, both of which are tagged with their “thread number”.

The creation (and eventual joining) of these threads happens in the create_threads function:

printf("[Main Thread] launching %ld threads.\n", num_threads);
for (idx = 0; idx < num_threads; idx++)
  pthread_create(&tids[idx], NULL, thread_func, &idx);

If you run the program without specifying a number of threads, it will default to launching 2. If you run ./simple-pthreads you may see output that looks like the following correct behaviour:

[Main Thread] Creating 2 threads.
[Thread #0] Hello from thread number 0!
[Thread #1] Hello from thread number 1!
[Thread #1] Has finished executing, and will return now.
[Thread #0] Has finished executing, and will return now.
[Main Thread] has created all threads. Joining threads now.
[Main Thread] joined thread 0
[Main Thread] joined thread 1
[Main Thread] Joined all threads. Exiting now.

Or you may instead see something more garbled:

[Main Thread] Creating 2 threads.
[Thread #1] [Thread #2] Hello from thread number 2!
[Thread #2] Has finished executing, and will return now.
[Main Thread] has created all threads. Joining threads now.
Hello from thread number 1!
[Thread #1] Has finished executing, and will return now.
[Main Thread] joined thread 0
[Main Thread] joined thread 1
[Main Thread] Joined all threads. Exiting now.

If you re-run the program many times, you will probably see different kinds of unexpected output.

Exercise 2: Locking and Synchronisation#

Using Mutexes#

The lectures on concurrency have covered the use of semaphores as a way of performing synchronisation between threads already. While they are an important concept to learn about, we will not be using them in these labs.¹ Instead, we will focus on a closely related concept - the mutexes provided as part of the pthread API. There are a different types of mutexes that are made available, but for now we will start by focusing on “the standard” mutex (pthread_mutex_t). This mutex allows only one thread to access the resource at any given time.

The following functions are used to initialise, use and destroy mutexes:

// Initialise `mutex`
int pthread_mutex_init(pthread_mutex_t *mutex, pthread_mutexattr_t *attr);

// Free any resources used by `mutex`
int pthread_mutex_destroy(pthread_mutex_t *mutex);

// Attempt to lock the mutex. If it is already locked, calling this function
// will block the thread until it is free.
int pthread_mutex_lock(pthread_mutex_t *mutex);

// Unlock the mutex. If there are any threads waiting to lock this mutex, they
// may have a chance to acquire the lock.
int pthread_mutex_unlock(pthread_mutex_t *mutex); 

// Similar to pthread_mutex_lock, but an already-locked mutex will not cause the
// calling thread to block.
int pthread_mutex_trylock(pthread_mutex_t *mutex);

Understanding the Problem#

Your second exercise will get you to practice working with this interface for creating and managing mutexes. In counting.c you have been provided with some template code that creates two threads, each of which increment a shared counter variable a set number of times.

Hopefully you are starting to develop an intuition for the cause of these sorts of issues. In this case, it is because both threads will be reading from and writing to the same location in memory concurrently. Each of these updates requires loading the value of counter that is currently stored in memory, incrementing it by 1, and storing that updating value back. In pseudo-x86 assembly, this would look something like the following three instructions:

I1. movq counter(%rip), %rax 
I2. addq $1, %rax
I3. movq %rax, counter(%rip)

You may wish to lay your ideas out in table form:

Fixing the Problem (With Mutexes!)#

Exercise 3: Producer-Consumer Threads#

The concept of shared buffers and the Producer/Consumer Problem has already been covered in the lectures already, so you may already be familiar. If not, the idea of the “Producer-Consumer” pattern is to designate certain threads as producer threads and others as consumer threads. The role of a producer is to perform some form of computation and/or I/O to produce data needed by other parts of the program. In this scenario the “other parts of the program” are one or more consumer threads. The consumer will use data produced by a consumer thread in some way.

This exercise will look at an example of a very simple Producer-Consumer pattern, with a Producer feeding data read from standard input to a Consumer performing computations on that data. The producer-consumer pattern will usually have multiple producers and/or consumers, but for simplicities sake we will focus on this small example to start with.

Shared Buffers#

How does a producer send data to a consumer? We use a shared data structure for producers to insert items into and consumers to remove items from. This shared data structure will need to be carefully managed to ensure that only one producer or consumer is accessing it at any given time. This shared data structure often takes the form of a queue.

A shared buffer will need:

• To keep track of its total capacity, and how many items it currently contains. This is to ensure producers don’t cause a buffer overflow by inserting more items than there is allocator space for.
• A locking mechanism to ensure that producers and consumers don’t attempt to modify the contents of the shared buffer concurrently.
• A way for producer threads to indicate to a waiting consumer thread that they have inserting a new item, and the buffer is no longer empty.
• A way for consumer threads to indicate to a waiting producer thread that they have removed an item from the buffer, and there is now room for the insertion of more data.

You have seen an implementation of a shared buffer in the lectures already, that used semaphores to indicate to producers and consumers when they could add/remove new data:

typedef struct {
    int *buf;          /* Buffer array */         
    int n;             /* Maximum number of slots */
    int front;         /* buf[(front+1)%n] is first item */
    int rear;          /* buf[rear%n] is last item */
    sem_t mutex;       /* Protects accesses to buf */
    sem_t slots;       /* Counts available slots */
    sem_t items;       /* Counts available items */
} sbuf_t;

You can view the full sbuf.c and sbuf.h files to help you understand the idea behind a shared buffer more.

Bad Idea: Shared Buffer With No Synchronisation#

Open the producer-consumer.c file in your repository and inspect the code provided. The program will create two threads — one of which is a producer and the a consumer. The producer thread will read integer values entered into standard input by calling scanf. Whenever it reads a new integer, it checks whether there is room in the buffer (shared_buffer) before inserting this value. The consumer will wait until it sees that there is an item in the shared buffer to consume. It will add the value of the item in the buffer to a running total.

./producer-consumer < numbers.input

Currently this program suffers from a similar problem to those we have looked at already. The sbuf_cond_t structure definition has all the components we need to implement proper sharing between the producer and consumer:

typedef struct shared_buffer {
  pthread_mutex_t lock;       // Lock for all updates to to our buffer/
  pthread_cond_t empty, full; // Condition variables for signalling.
  int count;                  // Number of items currently in the shared buffer.
  int data;                   // Our shared buffer only has room for one integer.
} sbuf_cond_t;

Rather than using semaphores like the above, we’re relying on “condition variables” to signal the current status of the buffer to the different threads.

Condition Variables#

The pthreads API also includes a useful tool for facilitating communication between different threads — condition variables.

The idea of condition variables is simple. They exist to allow for threads to signal to other threads that certain conditions have been met, or allow for threads to wait for another thread to tell it certain conditions have been met.

The main functions of relevance are:

int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *attr);

int pthread_cond_destroy(pthread_cond_t *cond);

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

int pthread_cond_signal(pthread_cond_t *cond); 

At this point, the init and destroy functions should be intuitive. The cond_wait function is a bit more involved, however:

The pthread_cond_wait function atomically blocks the current thread
waiting on the condition variable specified by cond, and releases the mutex
specified by mutex. The waiting thread unblocks only after another thread
calls pthread_cond_signal, or pthread_cond_broadcast with the same
condition variable, and the current thread reacquires the lock on mutex.

In general, typical usage of a condition variable will look like the following:

int some_cond;
pthread_cond_t cond;
pthread_mutex_t lock;

// Run by thread 1
void foo() {
  pthread_mutex_lock(&lock); 
  // --- Critical Region Begins ---
  while (some_cond == 0)
    pthread_cond_wait(&cond, &lock); // Wait for another thread to signal change in condition.
                                     // Temporarily releases the lock.
  // At this point, some_cond is 'true' and the condition has been signalled.
  // The caller has also regained control of the lock, so we are still in a 
  // critical region.
  ... /* perform some work that relied on 'some_cond' being true */ ...
  pthread_mutex_unlock(&lock); 
  // --- Critical Region Ends ---
}

// Run by thread 2
void bar() {
  pthread_mutex_lock(&lock); 
  // --- Critical Region Begins ---

  ... /* perform some work which allows `some_cond` to become true */...

  some_cond = 1;
  pthread_cond_signal(&cond); // Signal change in condition
  pthread_mutex_unlock(&lock); 
} // --- Critical Region Ends ---

Adding Locks and Condition Variables#

Extension 1: Supporting More Items#

Extension 2: Supporting More Threads#

More Locking: Read/Write Locks#

As noted in the lectures, when sharing resources between multiple threads, it is often safe to allow multiple readers to access the resource simultaneously as they would not alter any data, but only one writer should be allowed to access the resource at any given time.

The standard mutex, pthread_mutex_t, allows only one thread to access the resource, irrespective of whether the thread is a reader or writer. This behaviour is safe, but not very efficient, as the readers are made to wait even though they are not going to modify the data.

The pthread API offers support for a variation of the standard mutex described above that allows for multiple readers to access a resource at the same time.

The pthread_rwlock_t which is a read-write lock allows multiple readers to access the resource, but allows only one writer at any given time.

pthread_rwlock_t rwlock;

We can initialize rwlock as follows,

pthread_rwlock_init(&rwlock,NULL);

We can destroy the lock to avoid memory leaks as follows,

pthread_rwlock_destroy(&rwlock);

Next, we can apply a read or a write lock depending on the scenario as follows,

pthread_rwlock_rdlock(&rwlock);
pthread_rwlock_wrlock(&rwlock);