Re:A threading riddle
by davidtgoldblatt on Tuesday June 30, 2015 @02:35PM
(#9807478)
Looks good to me; that's essentially the solution I had in mind (though, I think you have a race on NintBucket::waiters in modify and append_cv). Using a custom two-mutex lock class and condition_variable_any is particularly clever, I hadn't thought of that.
I just published my solution, which uses a similar strategy: http://dgoldblatt.com/a-threading-riddle-solution.html
I don't think of this as violating the N^2 primitives rule; the solution is still linear in the size of the problem its facing (it only uses K condition variables for K threads, so even if K is bigger than N^2, it's still morally in the scope of the problem).
Ah, yep I see the race. Here is a fix: https://gist.github.com/sdab/d7ba036b2b7f4b5626cd
Thanks for the puzzle, its hard to find good concurrency problems.
Edit: Looked through your solution. You are right, we thought of similar things. I started out by wanting a multi condition variable, but didnt want to implement it :). I ended up getting something similar in a roundabout way.
I believe it follows all of the requirements. There is one glaring flaw which is that it uses a condition variable per 'wait_until_equal' call, though it uses only N mutexes. So this doesn't fall under the N^2 primitives (in the case of many waits), though its unclear to me if thats an official rule.
Im happy to listen to feedback or if someone sees an error.