Lockfree or not to lockfree...

[aminer10]

Hello,

Lockfree or not to lockfree , that's the question ...

I have read here and there that lockfree algorithms are hard,
but that's not always the case, if you take a look at the following
FIFO queue that is waitfree on the push() and Lockfree on the pop()

http://pastebin.com/f72cc3cc1

You will read this:

===
public bool pop(out T state) {
      node cmp, cmptmp = m_tail;
      do {
        cmp = cmptmp;
        node next = cmp.m_next;
        if (next == null) {
          state = default(T);
          return false;
        }
        state = next.m_state;
        cmptmp = System.Threading.Interlocked.CompareExchange(ref m_tail, next, cmp);
      } while (cmp != cmptmp);
      return true;
    }
  };

===


Lockfree is easy, you will notice that between the

the "cmp = cmptmp;"

and the:

"cmptmp = System.Threading.Interlocked.CompareExchange(ref m_tail, next, cmp);"

It's as we had a critical section, cause if for example  two threads 
crossed the "cmp = cmptmp;"  , one of them will succeed and another
will retry and loop again, hence this lockfree mechanism is the same as a critical section,
but the difference between Lockfree and Lock algorithms is that
there can be no context switches inside the "cmptmp = System.Threading.Interlocked.CompareExchange(ref m_tail, next, cmp);"
but in lock algorithms you can have a context switch inside the critical section, other than that in lockfree algorithms if you have a problem with a thread and it has stopped right on "cmptmp = System.Threading.Interlocked.CompareExchange(ref m_tail, next, cmp);"
there will be still progress of the other threads , that's not the case
in Lock based algorithms , other than that Lockfree algorithms are
immune to  priority inversion, cause if a lower priority thread
is doing "System.Threading.Interlocked.CompareExchange(ref m_tail, next, cmp);" there will be no context switch , that's not the case with lock based algorithms , lock based algorithms are not immune to priority inversion, so as you have noticed Lockfree algorithms are more resiliente than Lock based algorithms, but this is not the end of the
story , Lockfree algorithms on the other hand can have too much cache-cohency traffic, much more than Lockfre based algorithms that uses scalable Locks, and more than that scalable Locks
are FIFO fair, and this is not the case with Lockfree algorithms , they
are not FIFO fair, hence they can  have starvation, so Lockfree algorithms
are not silver bullet.




Hope you have understood.



Thank you,
Amine Moulay Ramdane.

 

[aminer10]

On 10/10/2013 3:33 PM, aminer wrote:> and more than that scalable Locks
> are FIFO fair, and this is not the case with Lockfree algorithms


I mean scalable Locks such us the scalable Anderson Lock or
the scalable MCS Lock or my scalable distributed fair Lock are
FIFO fair.




Thank you,
Amine Moulay Ramdane,

[aminer10]

On 10/10/2013 3:33 PM, aminer wrote:> Lockfree algorithms on the other hand can have too much cache-cohency
> traffic, much more than Lockfre based algorithms that uses scalable Locks

I mean:

Lockfree algorithms on the other hand can have too much cache-cohence
traffic, much more than Lock based algorithms that uses scalable Locks.


Thank you,
Amine Moulay Ramdane.