Multithreading

The Argument for Threads

So you're running along in one function. You'd like to stop running, pack up, and start running some other function for a while. Easy, right? Just CALL the other function--your return address will get pushed onto the stack, and the other function will run until it's done and RET back to you.

But sometimes, CALL and RET are not good enough. Sometimes, it's nice to be able to suspend function A, run function B for a while, then switch back to A before B is finished, then switch back to where we left off inside B, and so on. In other words, sometimes you want to be able to split up a few functions into several pieces, and switch off between the execution of each of those those pieces.

This is actually a form of parallelism--it lets you get several things done at the same time.

For example, if function A is reading stuff from the network, it'll spend a lot of time just waiting for the next piece of data to arrive. That's when it would make sense to run some other function B. If B is writing stuff to disk, it'll spend time waiting for the disk to finish writing. That's when you want to switch back to A!

Just to be clear, here's what we want to have happen:

Function	A	B
Code	for (int i=0;i<3;i++) { std::cout<<"A:"<<i<<"\n"; swap from A to B }	for (int i=0;i<3;i++) { std::cout<<" B:"<<i<<"\n"; swap from B to A }

So what we want is to be able to run one iteration of A, then run one iteration of B, and so on. In a real program, of course, A and B would be doing something useful instead of just printing stuff, and they'd only switch off when they need to wait for something slow (a disk, the network, the keyboard, etc.) instead of swapping every iteration.

Implementing Threads in User Space

So you can actually write code that switches between functions A and B like above. It's actually pretty easy to do so.

You've just got to save and restore everything that's different in A and B. This includes:

The instruction pointer. This will automatically get saved to the stack if we just make "swap" a normal function.
The saved registers (ebp, ebx, esi, and edi). It's easy enough to save these on the stack in assembly.
The stack pointer. "i" is probably sitting on the stack for both functions.

So the easy part is writing the swap routine:

; Usage: swap32(old struct pointer, new struct pointer)
global swap32
swap32:
mov eax,[esp+4] ; first argument: old thread struct pointer
mov ecx,[esp+8] ; second argument: new thread struct pointer
; Save registers
push ebp
push ebx
push esi
push edi
; Save old stack
mov [eax],esp
; Load new stack
mov esp,[ecx]
; Restore registers
pop edi
pop esi
pop ebx
pop ebp
ret

Now you've just got to call the swap routine to switch from running one function to running another--and then you can switch back!

struct thread {
	void *stack_pointer; /* <- accessed from assembly */
};
/* Save this old thread's stack; and load up from this new thread's stack. */
extern "C" void swap32(thread *old,thread *new_thread);

thread A, B; /* threads to run */
void fnA(void) {
	for (int i=0;i<3;i++) {
	    std::cout<<"A:"<<i<<"\n";   
	    swap32(&A,&B);
	}
}
void fnB(void) {
	for (int i=0;i<3;i++) {
	    std::cout<<"        B:"<<i<<"\n";   
	    swap32(&B,&A);
	}
}

int foo(void) {
	/* Set up a separate stack for B (nasty, but only needed once!) */
	int Blen=8192; /* small 8KB stack */
	char *Bstack=new char[Blen];
	void **Btop=(void **)(&Bstack[Blen]); /* end of B's stack */
	*(--Btop)=(void *)fnB; /* first swap will return to start of fnB */
	for (int crap=0;crap<4;crap++)
		*(--Btop)=0; /* set new ebp, ebx, esi, and edi all to zero */
	B.stack_pointer=(void *)Btop; /* B's stack starts here */
	
	/* Just call A.  It will swap to B, which will swap to A, and so on! */
	std::cout<<"Calling fnA\n";
	fnA();
	std::cout<<"Back to foo\n";
	return 0;
}

(executable NetRun link part 1, NetRun link part 2)

Note the trickiness of setting up B's stack so that A's first call to swap32 will actually fire up function B!

This code produces:

Calling fnA
A:0
        B:0
A:1
        B:1
A:2
        B:2
Back to foo
Program complete.  Return 0 (0x0)

Flavors of Threading

Writing your own assembly code to switch between threads is called "user-level threading", or "coroutines". There are several other ways to implement the same thing, like using the builtin OS routines setjmp/longjmp, makecontext/swapcontext, or Windows Fibers.

You can also get the OS itself to do the swapping whenever it likes; threads created and managed by the OS are called "kernel threads" or just plain "threads". You can create OS threads with pthread_create (on UNIX-like systems) or CreateThread (on Windows). You'll learn more about creating kernel threads in CS 321 next semester.

The big advantage of kernel threads is that the kernel knows when an I/O will block (for example, when you're reading a file), and can thus automatically swap out that thread with another thread. The big advantage of user-level threads is that you know exactly when every thead switch will occur (because you're explicitly calling the "swap" function!), so it's pretty rare for a thread switch to happen at "exactly the wrong instant" and hence screw up your program.

My friend Gengbin and I wrote a decent paper on the tradeoffs between user-level and kernel threads for parallel programming. Generally, user-level threads have less overhead (25ns per context switch for the implementation above); while kernel threads can run better (the kernel swaps its threads out if one blocks for I/O, and they naturally take advantage of multiple CPUs).

Simple Kernel Threads

So far, we've built threads and switched between them on our own. But you can actually get the OS kernel to do the hard work of creating threads, which are then called "kernel threads". On UNIX systems, you create a new kernel thread by calling "pthread_create", which is in "#include <pthread.h>" and the "-lpthread" library. You just pass pthread_create the function to run in the thread, and the kernel will then run that function, switching back and forth between threads at basically random times (100 or 1000 times per second, usually).

#include <pthread.h>

void doWork(const char *caller) {
	std::cout<<caller<<"\n";
	for (int delay=0;delay<1*1000*1000;delay++) {}
}
void *fnA(void *arg) {
	for (int i=0;i<10;i++) doWork("A");
	return 0;
}
void *fnB(void *arg) {
	for (int i=0;i<10;i++) doWork("    B");
	return 0;
}
int foo(void) {
	pthread_t B; 
	pthread_create(&B,0,fnB,0); 
	fnA(0); 
	void *Bret;
	pthread_join(B,&Bret); 
	return 0;
}

(executable NetRun link)

To illustrate the way the kernel randomly switches between these functions, run this thing several times--here's what I got on several different runs on my (uniprocessor) laptop:

A
A
A
B
B
B

AB

AB

AB

B
B
B
A
A
A

AB
A
A

B
B

AB

B
B
A
A

That is, the kernel runs A for a while, then B for a while, then back to A. You can't tell when a switch is going to happen. Note that the kernel sometimes switches to B between when A prints the letter 'A' and when it prints the newline immediately after it in the string "A\n"!

The danger of threads

So basically a kernel thread is just a fancy way to run one of your subroutines simultaniously with all the other subroutines. A kernel thread can still call other functions, access your global variables, or use anything it can find that belongs to other threads.

This shared access to common variables immediately introduces the many problems of "thread safety". For example, consider a piece of code like this:

int shared=0;
void inc(void) {
	int i=shared;
	i++;
	shared=i;
}

If two threads try to call "inc" repeatedly, the two executions might interleave like this:

Thread A	Thread B
int i=shared; // i==0 i++; // i==1 // hit interrupt. switch to B shared=i; // i is still 1, so shared==1!	int i=shared; // i==0 (again) i++; //i==1 shared=i; // shared==1 int i=shared; // i==1 i++; //i==2 shared=i; // shared==2 int i=shared; // i==2 i++; //i==3 shared=i; // shared==3 // hit interrupt, switch back to A

Uh oh! When we switch back to thread A, the value stored in "i" isn't right anymore. It's an older copy of a shared global variable, stored in thread A's stack or registers. So thread A will happily overwrite the shared variable with its old version, causing all of B's work to be lost!

Here's an executable example of this problem. Both threads are trying to increment "sum". They each do this 10 million times, so "sum" should be 20 million at the end. But with optimization on, they both store a copy of "sum" in a register, so one guy overwrites the other guy's work when they write the modified value back to "sum", and you (usually!) end up with the totally-wrong value 10 million (or so):

#include <pthread.h>

int sum=0;  /*<- Careful!  This variable is shared between threads! */
void doWork(void) {
	for (int i=0;i<1000*1000;i++)
		sum++;
}
void *fnA(void *arg) {
	for (int i=0;i<3;i++) doWork();
	return 0;
}
void *fnB(void *arg) {
	for (int i=0;i<3;i++) doWork();
	return 0;
}
int foo(void) {
	sum=0;
	pthread_t B; 
	pthread_create(&B,0,fnB,0); 
	fnA(0); 
	void *Bret;
	pthread_join(B,&Bret); 
	return sum;
}

(executable NetRun link)

Thread Safety with "volatile"

Sometimes, the only problem is the compiler's over-optimization of access to global variables. You can scare the compiler away from a variable by putting the keyword "volatile" in front of it. This makes the compiler fear the variable, and do exactly what you ask with it:

volatile int sum=0;  /*<- Careful!  This variable is shared between threads! */
void doWork(void) {
	for (int i=0;i<1000*1000;i++)
		sum++;
}
(executable NetRun link)

Adding "volatile" does indeed improve the thread safety of this program--in fact, on a uniprocessor machine, it now gets the right answer! This is because "sum++" becomes a single instruction ("inc dword [sum]"), and an instruction executes as one piece--if the kernel switches to another thread, it will be either before or after this instruction, and never "in the middle of an instruction".

However, on a multiprocessor machine (dual core, dual CPU, or hyperthreaded like the NetRun machine), this program STILL GIVES THE WRONG ANSWER.

The reason is curious. On a real multiprocessor, two processors might simultaneously execute the crucial "inc" instruction. Since the instruction involves reading "sum" from memory, incrementing it, and writing it back out, it can still happen that one processor overwrites the result of another processor.

One way to *really* fix this code on a multiprocessor would be to use the assembly language "lock" prefix, which causes an instruction to execute "atomically". This changes the memory access mode so that no other processor can modify that instruction's data until the instruction completes. Here's what our loop looks like using the lock prefix. "incl (sum)" is the g++ inline assembly version of "inc dword [sum]".

volatile int sum=0;  /*<- Careful!  This variable is shared between threads! */
void doWork(void) {
	for (int i=0;i<1000*1000;i++)
		__asm__ ( "lock incl (sum)" );
}

(executable NetRun link)

Now, finally, we get the right answer! However, our program is now 10x slower--"lock" is a memory operation, so now we're running at memory speed, not at cache speed.

Thread Safety With Mutexes

There's another way to make this function threadsafe that works even if you're writing pure C++ and/or have more than one assembly-instruction worth of work to do. It's called a "mutex", which is just a special object with "lock" and "unlock" operations--while you've got the mutex locked, no other thread can lock the mutex (think of the lock in a bathroom stall!). In pthreads, this looks like:

int sum=0;  /*<- Careful!  This variable is shared between threads! */
pthread_mutex_t sum_lock=PTHREAD_MUTEX_INITIALIZER;
void doWork(void) {
	pthread_mutex_lock(&sum_lock);
	for (int i=0;i<1000;i++)
		sum++;
	pthread_mutex_unlock(&sum_lock);
}
(executable NetRun link)

This supports long stretches of protected code, is guaranteed to work on all machines, and requires no ugly unportable assembly. But there are a few problems:

Mutex aquisition is kinda slow, like 60ns per lock. This means you want to lock and unlock as rarely as possible.
Nobody else can do the stuff protected by the lock while you've got it. This means you want to leave the lock locked as short a time as possible.
Everybody who uses "sum" MUST remember to use the lock, as well. If anybody ever forgets, you're right back in a race condition.
It's possible to try to re-lock a lock you've locked. This means you're waiting (forever!) for yourself to unlock it!

Thread Safety With Privatization

The ONLY way to get good performance and the right answer is to have each thread working on its own, separate copy of each variable:

int sumA=0, sumB=0; 
void doWork(int &sum) {
	for (int i=0;i<1000*1000;i++)
		sum++;
}

(executable NetRun link)

This is called "privatization".