Review: DThreads: Efficient Deterministic Multithreading

I’ve decided to try and be more pro-active about reading papers from the community. Since I tend to forget everything I read, it’s best I write down somewhere my thoughts for later reference — I’ve decided to post these reviews here in case they prove useful to others.

PDF of the paper

Overview:

This paper follows one of the latest fads in systems (NB: academics have fads just like fashionistas) — deterministic threading. The main idea behind all of these papers is to try and allow users to make use of multi-core/multi-threaded programming, but at the same time have it be deterministic. This is helpful as it ensures the behavior we see when testing is the same as what we see at runtime, and it also helps make it easier to recreate test failures.

This is a non-trivial problem, and it has a lot of work behind it already. The contribution with dthreads is that it, (a) claims high performance, and (b) provides a drop-in replacement for existing threads.

How does it work:

There’s a standard trick for d-threading, and DThreads uses it as well. It’s somewhat a kin to transactions in databases. First, split each thread into a separate world that can’t communicate with the other threads. Buffer all of the updates that would go to shared memory. Then, at a synchronization point (mutex lock, condition var, etc.), wait for all of the threads to finish their work, and then apply the shared memory changes in a deterministic fashion.

The DThreads way of handling this is to run each thread as a separate process. Whenever a commit point is reached, the processes determine which parts of memory they’ve changed, and commit them to shared memory at that time.

There are a number of things that need to be handled to make this all possible — you need to provide a deterministic malloc, you have to ensure threads are created and destroyed in a deterministic way, etc.

Why aren’t we using it today?

Two reasons, really.

Speed

DThreads is faster then previous work on the subject, but still can end up a lot slower then regular threading. This isn’t unexpected — you have to do more work, so you end up paying for it.

Correctness

DThreads, while being a drop-in replacement for pthreads, isn’t really a drop-in replacement for pthreads. Unfortunately for deterministic threading proponents, this type of code:

Thread 1:

while not done:
  sleep(0)

Thread 2:
... do some work ...
done = 1

where synchronization is handled outside the scope of the threading library is all too common in the wild. This forces the use of more expensive techniques then DThreads, which keeps determistic threading, for the moment, an academic exercise.

What did I think of the paper

It’s well written (which I expect of all SOSP papers), and presents a bunch of interesting tricks for improving performance and making things work. The fact that it requires all synchronization be performed through pthreads calls is on the face of it, reasonable, but sadly, it is far from realistic when it comes to running everyday applications.

Still, fun to read.

Leave a Reply

Your email address will not be published. Required fields are marked *