Hi,
I'm learning about lock-free and wait-free algorithms and I was asking myself whether queues could be implemented based on the wait-free Unsafe#getAndAdd method as opposed to the lock-free CAS spin. The latter can still lead to queuing effects, especially under high contention and when there are more threads than processors concurrently doing the CAS spin.
Example of a CAS spin in MpmcArrayQueue:
|
while (seq > pIndex || // another producer has moved the sequence(or +) |
|
!casProducerIndex(pIndex, pIndex + 1)); // failed to increment |
Would it be possible to restructure the algorithm to be wait-free or is that inherently impossible?
Thanks,
Felix
Hi,
I'm learning about lock-free and wait-free algorithms and I was asking myself whether queues could be implemented based on the wait-free
Unsafe#getAndAddmethod as opposed to the lock-free CAS spin. The latter can still lead to queuing effects, especially under high contention and when there are more threads than processors concurrently doing the CAS spin.Example of a CAS spin in
MpmcArrayQueue:JCTools/jctools-core/src/main/java/org/jctools/queues/MpmcArrayQueue.java
Lines 175 to 176 in 6b8feea
Would it be possible to restructure the algorithm to be wait-free or is that inherently impossible?
Thanks,
Felix