If there is one thread A allocating memory to push a value onto the ring buffer, and another thread B popping a value off of the ring buffer, how does B free that memory back to the memory allocator without introducing a data race? Certainly there must be some kind of synchronization so that A can allocate memory and B can free that memory.
I'm tempted to say "No need to free it; next time A needs one, let it have that one that you were going to free."
In other words, claiming a slot also claims an already-allocated object.
You're right; this isn't a trivial design consideration. And I'm second-guessing myself as to whether my answer here is wrong. If you see a problem with it, definitely call it out.
(Cheers for the interesting conversation, by the way... Didn't expect it.)
Yeah for sure, at any rate I went over the LMAX Disruptor link you provided and while it doesn't use "locks", it is not a lock-free data structure. The confusion is that their use of the work "lock" means yielding to the operating system, which they don't do, but if a thread is performing a write, then all other threads will spin in a tight loop (which is basically a spin lock) until the write is committed. This is not a lock-free data structure in the typical sense of the word (guarantees at least one thread will make progress) since if the JVM pre-empts the thread currently in the process of writing, then all other writing threads are starved.
You can read more about it here in Section 4.3 on page 6 where they have the following busy waiting:
long expectedSequence = claimedSequence – 1;
while (cursor != expectedSequence) {
// busy spin
}
cursor = claimedSequence
Comments
I'm tempted to say "No need to free it; next time A needs one, let it have that one that you were going to free."
In other words, claiming a slot also claims an already-allocated object.
You're right; this isn't a trivial design consideration. And I'm second-guessing myself as to whether my answer here is wrong. If you see a problem with it, definitely call it out.
(Cheers for the interesting conversation, by the way... Didn't expect it.)
Yeah for sure, at any rate I went over the LMAX Disruptor link you provided and while it doesn't use "locks", it is not a lock-free data structure. The confusion is that their use of the work "lock" means yielding to the operating system, which they don't do, but if a thread is performing a write, then all other threads will spin in a tight loop (which is basically a spin lock) until the write is committed. This is not a lock-free data structure in the typical sense of the word (guarantees at least one thread will make progress) since if the JVM pre-empts the thread currently in the process of writing, then all other writing threads are starved.
You can read more about it here in Section 4.3 on page 6 where they have the following busy waiting:
https://lmax-exchange.github.io/disruptor/files/Disruptor-1....Some other details of the blocking are here:
http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-...