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

Groups > comp.programming > #3920

Again to lockfree or not to lockfree ...

Cross-posted to 2 groups.

Show all headers | View raw

Hello,

I have thought more about those lockfree algorithms
and i think they are not good, cause they are not FIFO fair
and in contention scenarios they can higher the cache-coherence traffic
much much more than when you use scalable Lock that are FIFO fair
such as the Anderson Lock or the MCS Lock, so what is the solution then?
you can try to invente a waitfree algorithm and satisfy the fairness and 
minimize the cache-coherence traffic, but i have thought more
and i think i have found an alternative for a bounded FIFO queue
that is better than lockfree FIFO queue algorithms, this alternative is 
to use a Ticket mechanism with a proportional backoff to lower the 
cache-coherence traffic, this proportional backoff is efficient cause the
time to run a  CAS is constant, so now follow with me please i will give 
you an example, if you look inside the source code of my scalable
distributed fair Lock, you will read inside the file lockfree_mpmc.pas
this:

==

function TLockfree_MPMC.push(tm : tNodeQueue):boolean;
var lasttail,newtemp:long;
i,j,k:integer;
begin

  if getlength >= fsize
   then
       begin
           result:=false;
           exit;
       end;
result:=true;

newTemp:=LockedIncLong(temp);

lastTail:=newTemp-1;
//asm mfence end;
setObject(lastTail,tm);

k:=1;
repeat

  if CAS(tail,lasttail,newtemp)
    then
       begin
        sleep(0);
        exit;
       end;
if k=1 then j:=(lasttail-tail);
if k=1
then
  begin
   j:=j*20;
   k:=0;
   for i:=0 to j do asm pause end;
  end;
sleep(0);
  until false;
end;

===


So as you have noticed the tail and lasttail are used as a Ticket 
mechanism , this is better than to use a Ticket spinlock mechanism
cause as you have noticed this algorithm is less sensitive to context
switches, cause if the thread is inside the lock compxch(the CAS) there
will be no context switches i think, so this is better than to use
a Ticket spinlock mechanism cause with the Ticket spinlock mechanism
if the thread is inside the critical section there can be context 
swithes, other than that this FIFO queue algorithm with a Ticket 
mechanism satisfy many
requirements that the lockfree algorithm doesn't satisfy, the first
requirement is FIFO fairness, so it's FIFO fair , hence it avoids 
starvation, the lockfree algorithm doesn't satisfy this requirement ,
other than that it satisfy another requirement: it minimizes the 
cache-coherence
traffic much much better than the lockfree algorithm cause it uses a 
proportional
backoff , and about the resiliency, since it is a bounded queue
and since we are not using the hardisk nor allocating memory so
the algorithm is more resiliente, so what i need now is to add
a ticket mechanism for the pop() method that will look like the push() 
method, and that's easy to do.




Thank you,
Amine Moulay Ramdane.

Back to comp.programming | Previous | Next | Find similar | Unroll thread

Thread

Again to lockfree or not to lockfree ... aminer <aminer@toto.net> - 2013-10-11 15:26 -0700

csiph-web