[boost] [interprocess] native Windows cond_var + mutex

Subject: [boost] [interprocess] native Windows cond_var + mutex
From: Dan Brown (dbrown_at_[hidden])
Date: 2011-10-27 08:24:36

Hi,

Attached is a patch to implement interprocess_condition and interprocess_mutex natively on Windows.  Following are some detailed notes. I hope this isn't too awkward of a time for a submission like this -  I realize there's a lot of 1.48 activity going on.  One more note about the patch - IIRC, some patch utils won't create directories.  This patch is intended to be applied to boost/interprocess and relies on a new directory boost/interprocess/sync/win32.

Background

I started out by looking at http://www.cs.wustl.edu/~schmidt/win32-cv-1.html.  This appears to be from the late '90s and is the basis for ACE's cond_var implementation.  The solution in section 3.4 is arguably the most correct implementation.  However, this solution relies on the atomicity of SignalObjectAndWait().  SOAW() may have been atomic for unicore systems common at the time but from what I've read is not atomic for multicore (it prevents context switches on a single core but ignores concurrent threads on other cores), and win32 documentation backs this up.  While the paper argues that this leads to unfairness, I don't think the solution is correct without this atomicity.

Wait/signal/wait problem

One problem that I came across is what I'll call the wait/signal/wait problem.  Setting the state, thread 1 is waiting on a condition and thread 2 has just completed cond_signal.  Without an atomic SOAW(), thread 1 may release the external mutex without obtaining the associated semaphore.  Another thread, thread 3, may obtain the external lock and find the cond_var signaled and behave correspondingly.  This I believe is incorrect - a waiter which obtains the external mutex after the signaler has exited signal()should not find cond_var signaled.  This situation is unlikely but it makes assumptions about the scheduler that I am not comfortable with.  If there's a flaw in my reasoning hopefully someone will point that out.

This solution

This solution is structurally somewhat similarly to the paper's solution.  One point to note is that notify_one()/signal() blocks on an event in the same manner as notify_all()/broadcast().  There may be a solution which does not block the signaler while wake-processing is occurring, but I saw additional complexity on that path and decided to forgo it for the time being.

I hope the solution is correct but have only testing to validate.   I haven't used any formal methods to back it up.  Maybe I'll construct a Petri net sometime.  That's always .. fun.  I throw this solution on the mercy of the court.

External mutex

I have yet to see production examples of cond_var use where signalers do not hold the external mutex while they signal, but this use case is allowed by POSIX.  My original solution (if it is in fact a solution) relies on some particular external mutex being held by all waiters and signalers for some particular condition variable.  I recently added two mutexes to solve that situation but I have only minimal testing experience with that recent addition.  Use of these new locks is demarcated with WIN32_POSIX_SEMANTICS.

Interprocess vs. Intraprocess

I'm not sure if there is support for process-specific synchronization objects in boost.interprocess, but if support is present or was added at some future time this could help optimize things for win32.  At the moment win32 interprocess mutexes rely on assigning random names to mutexes (only named mutexes can cross platform boundaries in win32), and all mutex operations have to look up the mutex by this name.  Interprocess seems to have been designed primarily with pthreads in mind, and things get a little awkward on Windows in this regard.

Similarly, it would be nice to be able to use the native condition variables that win32 added for Vista+, but these can't be used across processes according to the documentation, and so can't be used AFAICT for inteprocess_condition.  Correspondingly, an intraprocess_mutex would be able to forgo the win32 mutex name lookups.

Miscellaneous

Not all interprocess tests currently pass.  There are some additional variations of mutex like the upgradable/sharable, etc., that I haven't looked at in detail.  I'm hoping that this patch goes far enough that it'll have some momentum.  I'm happy to either complete this work in the future or help whoever undertakes the task, but I may not be able to justify much of my time to the task in the short term to my employer.

I realized a little too late that I didn't keep formatting entirely consistent with the existing code.  Apologies.  Hopefully it's only the opening block curlies.

Thanks.

Dan