Introduction

The two key primitives used as building blocks for (blocking) concurrent algorithms are mutexes and condition variables, showing up in C++ as std::mutex and std::condition_variable.

In this post, I'll describe a pair of functions that can be simply described, but whose implementation requires a tricky use of these primitives.

The problem

Suppose we have an array of N ints. There are two functions we want to implement:

• void modify(size_t index, int value); This changes the element at position index to equal value.

• void wait_until_equal(size_t index1, size_t index2); This blocks until the elements at positions index1 and index2 of the array are equal.

The question is: how do we implement modify and wait_until_equal?

The rules

Without further requirements, the problem is trivial: just have a single lock guarding the array, together with a single condition variable that all readers wait on. But this severely limits concurrency: calls to modify that operate on different indices block one another. It's also wasteful of the waiter time; every waiter must wake up, acquire the lock, and re-check the values of its indices on every modification to the array, even if the indices it's interested in weren't modified. This motivates the first rule:

• Calls to one of the functions should not block waiting on a call to another one of the functions unless the two calls have one of their index arguments equal.

We'll relax the problem a little bit, to make it easier, to get a second rule that deals with races between modify calls.

• If a call to wait_until_equal(index1, index2) occurs, and the elements at indices index1 and index2 become equal only briefly, it's okay for the wait_until_equal call not to return; it can "miss" situations that don't exist for long enough.

We don't want this rule to be abused though (e.g. with a wait_until_equal call that never returns), so we'll add one final rule.

• If the elements at the indices passed to a wait_until_equal call become and remain equal, the wait_until_equal call will eventually return.

Finally, we want to make sure we don't waste too much CPU time; we'll have a no-spinning requirement

• The internals of wait_until_equal shouldn't busy-wait by spinning until their conditions become true. Similarly, loops like while (!check_condition()) { std::this_thread::sleep_for(std::chrono::milliseconds(15)) } are cheating. The wait_until_equal function shouldn't use CPU time that's not proportional to the number of modify operations that are used on its arguments.

These rules are really just to try to prevent "clever" solutions that dodge the real concurrency issues that are present. I promise that there's a reasonable solution to this that doesn't involve waiting forever, calling exit(0), or other trickery. The only concurrency primitives you need are mutexes and condition variables, and you don't need an unreasonable number of them (e.g. having N**2 variables is unnecessary).

Discussion

This problem is pretty abstracted, and the API presented to users is unrealistic in several ways:

• There's no way to read the values from the array, only to set them and compare them for equality
• Once you know two values are equal, they won't necessarily remain equal after the call to wait_until_equal returns, so you can't rely on their equality.

But these problems are easy to remedy, once a solution to this simplified problem is found, and solving only the simplification gets to the heart of the matter. There are real-world problems that require techniques similar to this one.

I'll post a solution sometime in the next couple of weeks. I'll keep it in a separate post to avoid spoiling it for anyone reading this one.