Lock Free Concurrent Queue

Question

This code snippet is from ConcurrentQueue implementation given from here.

internal bool TryPeek(out T result) 
{
    result = default(T); 
    int lowLocal = Low;
    if (lowLocal > High)
        return false;
    SpinWait spin = new SpinWait(); 
    while (m_state[lowLocal] == 0)
    { 
        spin.SpinOnce(); 
    }
    result = m_array[lowLocal]; 
    return true;
}

Is it really lock-free instead of spinning?

Answer 1

Spinning is a lock. This is stated in MSDN, Wikipedia and many other resources. It's not about word. Lock-free is a guarantee. It doesn't mean that the code shouldn't use lock statement. Algorithm is lock-free if there is guaranteed system-wide progress. I don't see any difference between this code and the code using locks. The only difference is that the spin uses busy wait and thread yielding instead of putting thread in a sleep mode. I don't see how this guarantees system-wide process, so personally I think that this is not a lock-free implementation. At least not this function.

Answer 2

Lock free means not using locks. Spinwaiting is not locking. There are a number of methods of synchronizing access to data without using locks. Performing spin waits is one (of many) options. Not all lock-free code will use spin-waits.