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.

Answer 3

Spinning places the CPU in a tight loop without yielding the rest of it's current slice of processor time, avoiding problems that a user-provided loop may create. This can be useful if it is known that the state change is imminent. It is rare for this to be the best option for ordinary code, and represents an alternative to locking for this specialized situation.

So yes, the code is lock-free as the term lock is used in the .NET Framework.

http://msdn.microsoft.com/en-us/library/hh228603.aspx