Concurrency

Concurrency using processes: processes created with fork can be used for concurrency, but processes are a heavyweight abstratction requiring significant resources.

They require:

• address space data structures
• open file table
• process context data

Scheduling a process requires switching address spaces (possibly losing useful context built up in caches and TLB).

Threads are a mechanism for concurrency within a single process/addresss space. It is a "virtual CPU" (program counter and registers). Each thread can be executing a different stream of instructions.

• Compared to processes, threads are lightweight, requiring only context (memory in which to save register values when thread is suspended), a stack, thread-local storage (for per-thread variables).

Thread

Pthread = "POSIX threads" The standard API for using threads on Unix-like systems.

They allow:

• creating threads and waiting for them to complete
• synchronizing threads (more on this soon)

Can be used for both concurrency and parallelism (on multicore machine, threads can be executed in parallel)

Some basic concepts: pthread_t: the thread id data type, each running thread has a distinct thread id

Thread attributes: runtime characteristics of a thread. Many programs will create thread using default attributes.

Attached vs Detached: a thread is attached if the program will explicitly call pthread_join to wait for a thread to finish.

Creating a Thread

pthread_create creates a new thread.

#include <pthread.h>
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);

Thread id is stored in variable pointed-to by thread parameter. The attr parameter specifies attribute (which will be NULL for default attributes).

The created thread executes the start_routine function, which is passed arg as its parameter.

Returns 0 if successful.

Waiting for Thread

pthread_join waits for a specified thread to finish.

#include <pthread.h>
int pthread_join(pthread_t thread, void **retval);

Only attached threads can be waited for. Value returned by exited threadis stored in the variable pointed to be retval

Find Thread ID

pthread_self allows a thread to find out its own thread id

#include <pthread.h>
pthread_t pthread_self(void)

Detach Thread

pthread_detach changes the specified thread to be detached, so that its resources can be freed without another thread explicitly calling pthread_join.

#include <pthread.h>
int pthread_detach(pthread_t thread);

• Typically called on itself. A child thread initially created as an attached thread can detach itself. This is done with the parent thread no longer needs the child thread(s).

Application

Multithreaded Web Server You can make a multithreaded web server so that many clients can interact with a single server. Its features include

• Server creates a thread for each client
• Created threads that are detached. The server doesn't need to wait for them to complete.
• No limit on the number of threads that can be created. Not really a good idea, because there is a maximum load, so that the server does not become unresponsive.
• Only the main function differs from previous non-threaded version.

ConnInfo

We create struct ConnInfo to represet a client connection.

struct ConnInfo {
	int clientfd;
	const char *webroot;
}

It's useful to pass an object containing data about the task the thread has been assigned to the thread's start function.

Worker Function

The worker function (executed by client connection threads)

void *worker(void *arg) {
	struct ConnInfo *info = arg;
	pthread_detach(pthread_self());
	
	server_chat_with_client(info->clientfd, info->webroot);
	close(info->clientfd);
	free(info);
	
	return NULL;
}

A created thread detaches itself, handles the client request, closes the client socket, frees its ConnInfo object, and then returns.

Main Loop

while (1) {
	int clientfd = Accept(serverfd, NULL, NULL);
	if (clientfd < 0) {
		fatal("Error accepting client connection");
	}
	
	struct ConnInfo *info = malloc(sizeof(struct ConnInfo));
	info->clientfd = clientfd;
	info->webroot = webroot;
	
	pthread_t thr_id;
	if (pthread_create(&thr_id, NULL, worker, info) != 0) {
		fatal("pthread_create failed");
	}
}

Multithreaded Programming

Shared Memory

The problem with writing multithreaded programs is that the thread executes in the same address space, so they share memory. This means one variable written by one thread may be read by another.

• Useful for communicating between threads
• Dangerous

Reentrancy

Reentrancy describes that a function can have as many on going calls, and they will not interfere with each other. It means they are safe to call from multiple threads and in recurison. In other words, a function can be safely "reentered" before a currently-executing call to the same function completes.

On the other hand, some functions are designed to use global variables (internally), so they are hard to guarantee that they are going to be safe and correct when there are many threads. These functions are not reentrant. Some examples are

• strtok (for tokenizing C character strings, retains state between calls). Instead, use strtok_r, which makes the progress variable explicit by taking a pointer to it as a parameter.
• gethostbyname returns pointer to global struct hostent object.

To write reentrant functions:

• don't use global variables
• memory used by a reentrant function should be limited to local variables (on stack), or heap buffers not being used by other threads.
• good idea to have functions receive explicit pointers to memory they should use.

The Linux manual for API functions has a section that tells you if a function is safe to call from multiple threads.

Synchronization

For many (not all) multithreaded programs, it's useful to have explicit communications/interactions between threads.

Concurrently-executed threads can use shared data structures to communicate. However, concurrent modification of shared data is likely to lead to violated data structure invariants, corrupted program state, etc.

Synchronization mechanisms allow multiple threads to access shared data cooperatively. (queues are awesome)

Parallel Computation

Can be used to speed up

Mandelbrot set

Assume C is a complext number, and $Z_0 = 0 + 0i$.

C is in the Mandelbrot set if and only if $Z_{n+1} = Z_n^2 + C$ Can be iterated an infinite number of times and $Z$ never reaches 2.

To solve this problem for some region of the complex plane, we must sample points and determine whether they are in the Mandelbrot set. We assume C is in the set if the equation can be iterated at large number of times without the magnitude of Z reaching 2. For those that are not in the set, we can set it to a color based on the number of iterations before Z reaches 2.v

This is an embarassingly parallel problem because the computation for each point in the complex plane is completely independent. This means we can speed up the computation by doing the computation for different points in parallel on multiple CPU cores.

Apprroach:

• use an array to store the iteration count (one per complex number)
• create a fixed number of computation threads
• assign a subset of the array elements for each computation thread
• when all the threads have finished, use iteration counts to render the image.

Computation

We represent complex numbers with a struct Complex and implement its operations:

typedef struct { double real, imag; } Complex;

static inline Complex complex_add(Complex left, Complex right) {
	Complex sum = { left.real+right.real, left.imag+right.imag };
	return sum;
}

static inline Complex complex_mul(Complex left, Complex right) {
	double a = left.real, b = left.imag, c = right.real, d = right.imag;
	Complex prod = { a*c - b*d, b*c + a*d };
	return prod;
}

static inline double complex_mag(Complex c) {
	return sqrt(c.real*c.real + c.imag*c.imag);
}

The computation itself is done with:

int mandel_num_iters(Complex c) {
	Complex z = { 0.0, 0.0 };
	int num_iters = 0;
	while (complex_mag(z) < 2.0 && num_iters < MAX_ITERS) {
		z = complex_add(complex_mul(z, z), c);
		num_iters++;
	}
	
	return num_iters;
}

The core of the sequential Mandelbrot computation:

int *iters = malloc(sizeof(int) * NROWS * NCOLS);
for (int i = 0; i < NROWS; i++) {
	mandel_compute_row(iters, NROWS, NCOLS, xmin, xmax, ymin, ymax, i);
}

The mandel_compute_row function computes iteration counts for a row of complex numbers, storing them in the iters array.

Threads

Fork/join: task struct, start func

typedef struct {
	double xmin, xmax, ymin, ymax;
	int *iters;
	int start_row, skip;
} Work;

void *worker(void *arg) {
	Work *work = arg;
	for (int i = work->start_row; i < NROWS; i += work->skip) {
		mandel_compute_row(work->iters, NROWS, NCOLS, work->xmin, work->xmax, work->ymin, work->ymax, i); 
	}
	return NULL;
}

Fork/join: parallel computation

/* master work assignment */
Work master = { xmin, xmax, ymin, ymax, iters, 0, NUM_THREADS };

/* start threads */
pthread_t threads[NUM_THREADS];
Work work[NUM_THREADS];
for (int i = 0; i < NUM_THREADS; i++) {
	work[i] = master;
	work[i].start_row = i; /* each thread has different start row */
	pthread_create(&threads[i], NULL, worker, &work[i]);
}

/* wait for threads to complete */
for (int i = 0; i < NUM_THREADS; i++) {
	pthread_join(threads[i], NULL);
}

Running sequential vs 4 threads:

$ time ./mandelbrot -1.286667 -1.066667 -0.413333 -0.193333
real    0m2.020s
user    0m2.012s
sys     0m0.008s

$ time ./mandelbrot_par -1.286667 -1.066667 -0.413333 -0.193333
real    0m0.815s
user    0m3.054s
sys     0m0.000s