2 ms·

> 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

> 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.)

Kranar 5y ago
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 https://lmax-exchange.github.io/disruptor/files/Disruptor-1.0.pdf 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-why-its-so-fast.html http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-...

Kranar 5y ago

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 https://lmax-exchange.github.io/disruptor/files/Disruptor-1.0.pdf 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-why-its-so-fast.html http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-...