Support for interdependent producer linearizability

[cameron314]

The cornerstone of the entire design is that independent producers can safely put their elements in independent sub-queues, without loss of queue semantics (since depending on the overall order of elements between those queues is tantamount to a race condition). Thanks to the design based on this assumption, the queue can be very fast, but is not linearizable.

However, many people have raised concerns about this, since it turns out that producers are not always independent; often there is synchronization between them, and in such cases it's often a requirement to have a relative ordering between elements produced by one producer with respect to the other.

Example

As an example, the queue may be used for log messages; one thread may put on a message saying it's scheduling a task, then that task is executed by another thread (with a happens-after synchronization), which logs a message saying the task is complete. Obviously, the 'task scheduled' message should come out before the 'task complete' message, but it may not because the producers are presently treated as being independent.

Workaround

Currently, the only workaround is to share an explicit producer token between all interdependent producers, and lock around multi-threaded access to it (since producer tokens are not thread-safe). This somewhat negates the benefits of using a lock-free queue in the first place!

Proposed solution

I propose adding a third type of token, the InterdependentSharedProducerToken (alas, I was never very good at naming things). This token will be usable from multiple producer threads simultaneously, and will also be lock-free. Users would then be able to choose which groups of producers are interdependent and share one of these tokens among each of them. This is still more efficient than always enforcing linearizability, while still supporting it where required (at a slight increase in complexity, of course).

[cameron314]

Won't-do. I might write an entirely different queue implementation some day that is linearizable, but at this point I have no plans to extend the functionality of ConcurrentQueue.