Thread Safety

CS 321 Lecture, Dr. Lawlor, 2006/02/08

Silberschatz chapter 4 describes threads in some detail. Chapter 6 describes synchronization primitives, and the critical section problem.

Thread Safety: The Problem

As discussed in the previous lecture, it's dangerous for multiple threads to update the same variable:

struct number_range {
        int lo, hi;
};

int total_count=0;

int count_range(number_range *n) {
        for (int i=n->lo;i<n->hi;i++) 
                if ((i%2)==0)
                        total_count++; /* i is even-- add it to the count */
}

On my machine, this takes about 20 milliseconds to search 10 million integers, or 2 ns per integer.

On a real SMP machine, two threads running this routine will overwrite each others' updates to total_count, resulting in a sum that differs each run!

Total count: 2947116
Total count: 3285076
Total count: 3192229

You can see this effect on a uniprocessor by splitting the increment into several instructions.

Thread Safety by Privatization

We can fix this problem by just giving a separate copy of the shared variable to each thread (called "privatizing" the shared variable):

struct number_range {
	int lo, hi;
	int count;
};

void count_range(number_range *n) {
	for (int i=n->lo;i<n->hi;i++) 
		if ((i%2)==0) {
			n->count++; /* i is even-- add it to the count */
		}
}

This is by far the best solution--it's easy to get the right answer this way. One performance warning: different threads' "number_range" structures must be more than one cache line apart in memory, or they'll "thrash" back and forth between processors at runtime, which is really slow. See an example of this padding. With proper padding, multiple threads are fastest when using privatized variables.

Thread Safety by Atomic Access

If what we're sharing between threads is a single "int", and we're doing increments, decrements, or additions to the int, we can make our code threadsafe by using an atomic (or indivisible) instruction to update the shared variable. A small subset of x86 instructions can be made atomic (even on an SMP) using the "lock" instruction prefix. Note that using "lock" prefix slows down execution slightly, plus you've lost portability by using assembly language.

Thread Safety via a Lock

We can make access to any shared variable atomic by wrapping a lock around the access:

/* Describes a range of numbers to count */
struct number_range {
	int lo, hi;
};

int total_count=0;
porlock lk; /* protects the "total_count" variable */

void count_range(number_range *n) {
	for (int i=n->lo;i<n->hi;i++) 
		if ((i%2)==0) {
			lk.lock();
			total_count++; /* i is even-- add it to the count */
			lk.unlock();
		}
}

Locks are a very common way to make code threadsafe. But in addition to serializing access, they're pretty slow on their own--just grabbing and releasing a lock takes at least 100ns, as it involves two round trips to memory. Plus, it's easy to forget to release the lock or incorrectly access the data without using the lock, resulting in all sorts of headaches.

Thread Safety via a serialization thread

For low-occurrence operations, it's sometimes convenient to pass them off to a single thread (a "serializer", "worker thread", "coordinator", etc.) to be merged. Coordinating access to the single thread is sometimes tricky, and there may be a performance impact from having the additional thread around.

Download all above examples together with a portable Linux/Windows thread library (Directory, Zip, Tar-gzip)