Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #1895

Lockfree or not to lockfree..

Cross-posted to 2 groups.

Show all headers | View raw

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.

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar

Thread

Lockfree or not to lockfree.. aminer <aminer@toto.net> - 2013-10-10 15:33 -0700
  Re: Lockfree or not to lockfree.. aminer <aminer@toto.net> - 2013-10-10 15:45 -0700
  Re: Lockfree or not to lockfree.. aminer <aminer@toto.net> - 2013-10-10 16:09 -0700
  Re: Lockfree or not to lockfree.. "Chris M. Thomasson" <no@spam.invalid> - 2013-10-10 14:35 -0700

csiph-web