I recently grew an interest in lock free queues and during my research noticed some confusion concerning blocking, lock-free, and wait-free queues. There are quite a few claimed implementations that do not meet the requirements. This is my attempt to alleviate some confusion. I define an interrupt safe queue as one that will succeed at some point within a single queue or dequeue call from a uniprocessor interrupt function.
A blocking queue has the effect where an active thread is able to lock the queue and attempted locks by other threads will ‘block’ and yield their scheduled CPU time to the system. Blocking queues can be inefficient in multi-processor systems where it takes longer for the thread to be rescheduled than it would have taken to ‘spin for success’. By ‘spin for success’ I mean retry the operation until it succeeds. That is the basis for spin locks and lock free queues.
Conversely, a non-blocking queue is one where a thread will never voluntarily give up its allotted time-slice. Lock-free and wait-free queues are both non-blocking.
A lock-free queue implementation guarantees system-wide progress but does not guarantee per thread progress. Lock free queues often use atomic compare-exchange primitives where if the atomic call fails that means another thread has already made a change and it is time to retry or ‘spin’ until it works. Threads may ‘starve’ because there is no guarantee of progress. One example of starvation is that a thread may keep ‘retrying’ and worse case, under the heaviest of loads, may be continually delayed by other higher priority threads.
A wait free queue is a lock-free queue with guaranteed per thread progress. This means that every operation is guaranteed to be completed within a maximum number of steps. It appears a true wait free algorithm would also be interrupt safe. The primary difference between lock-free and wait-free is that the possible delays via lock-free methods are bounded, if not removed.
In a uniprocessor system an interrupt function can quite literally interrupt the code flow anywhere. This requires a fairly complex algorithm that lets the interrupt function succeed in either a queue or dequeue no matter the current state of the other threads. This requirement may all but completely fade as the future appears to be parallel processing… yet at the moment I still work with uniprocessor systems!
Interest in queue theories are growing because of parallel processing. Most commercial code right now is sufficient for the single and handful of cores that comprise most basic consumer systems. Most algorithms currently in use are extremely inefficient when scaled to thousands, hundreds, or even dozens of cores.
I suspect the holy grail of wait-free queues will be extremely slow compared to others until actually utilizing a large number of processors.
Queue theory is big right now. We have basically witnessed the advent of generic multi-core hardware within the last few years and are already facing huge scaling problems as we head into the future. The solutions will be very interesting.