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

Groups > comp.programming.threads > #2480 > unrolled thread

My scalable MLock algorithm

Back to article view | Back to comp.programming.threads

Contents

  My scalable MLock algorithm aminer <aminer@toto.net> - 2014-06-11 03:22 -0700
    Re: My scalable MLock algorithm aminer <aminer@toto.net> - 2014-06-11 03:29 -0700
      Re: My scalable MLock algorithm aminer <aminer@toto.net> - 2014-06-11 04:27 -0700

#2480 — My scalable MLock algorithm

Hello,


So i will explain to you what is exactly my scalable MLock algorithm..

If you look the Enter() method of my scalable MLock algorithm you will
read this(that's easy to undertand the code in Object Pascal) :

You can download the source code here:

https://sites.google.com/site/aminer68/scalable-mlock


==
  procedure TMLock.Enter;
var prev,fcount1:PListEntry;
     k:integer;
     Buffer1:pointer;


begin
Buffer1 := AllocMem(SizeOf(TListEntry) + Alignment);
FCount1 := PListEntry((int(Buffer1) + Alignment - 1)
                            and not (Alignment - 1));

fcount1^.Data:=0;
fcount1^.Next:=nil;
fcount1^.mem:=buffer1;

long(prev) := LockedExchange(long(m_head), long(fcount1));

prev.next := fcount1;

if (flag=1)
then
  begin
   if (m_tail=prev)
    then
     if CAS(flag,1,0)
      then
       begin
        fcount1^.Data:=-1;
        exit;
       end;
  end;
k:=1;
repeat

if fcount1^.data=1
then
begin
freemem(fcount1^.mem);
break;
end
else if fcount1^.data=2
then
  begin
   fcount1^.Data:=-1;
   break
  end;
if (flag=1)
then
   begin
   if (m_tail.next.next=fcount1)
    then
     if CAS(flag,1,0)
     then
      begin
       fcount1^.Data:=-1;
       break;
      end;
   end;
inc(k);
if (k mod 140)=0
then
{$IFDEF FPC}
ThreadSwitch;
{$ENDIF}
{$IFDEF Delphi}
sleep(0);
{$ENDIF}
asm pause end;
until false;


end;
===


First i am allocating a Buffer1 struct and using fcount1 that is a 64 
bytes aligned record and assigning zero to fcount1^.Data cause the 
threads that enter will have to wait for there turn and
for fcount1^.Data to become 1 to enter the scalable Lock except for the
first thread that enters the lock, the first thread that enter
the lock will find the "flag" variable equal to 1 and mnotice with
me that the  CAS(flag,1,0) will suceed for the first thread that enters 
the Enter() method...


Look that i am using this:

long(prev) := LockedExchange(long(m_head), long(fcount1));


this is a waitfree queue and the push() and the pop() inside my
scalable MLock algorithm are waitfree...


So notice with me that the threads on the Enter() method will enter
a repeat-until loop waiting for there turn to enter, and notice
that the CAS will be touched rarely , i have benchmarked and colleted
some empiric statistics and i have noticed that the CAS inside the 
repeat-unil loop inside the Enter() method will be touched only 1% of 
the time, so the threads will wait 99% of the time for fcount1^.data
to become 1 or fcount1^.data to become 2 , and notice that fcount1^.data
inside the Enter() method is not generating cache-lines transfers for 
each thread waiting in the Enter() method, cause fcount1^.data is only 
touched by its correponding threads on its local cache, this is why
my MLock algorithm is scalable, cause it minimizes efficiently the 
cache-coherence traffic.


For the Leave() method it is waitfree and it is easy to prove that just 
look at the source code and you will notice that even though there is a 
repeat-until loop inside the Leave() method , my algorithm will not loop 
more than 2 times inside the Leave() method, so it makes my algorithm 
waitfree and my algorithm can be used on parallel and realtime safety 
critical systems.


And also you will notice easily that my scalable MLock is FIFO fair
so it's starvation-free.


That's all.


You can download my scalable node based Lock that is FIFO fair and 
waitfree from:

https://sites.google.com/site/aminer68/scalable-mlock



Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#2481

On 6/11/2014 3:22 AM, aminer wrote:
> Look that i am using this:
>
> long(prev) := LockedExchange(long(m_head), long(fcount1));
>
>
> this is a waitfree queue and the push() and the pop() inside my
> scalable MLock algorithm are waitfree...


I mean this is a waitfree FIFO queue.



Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#2485

An Pham wrote:
 >It is not a queue. It is a stack (last in first out)


The following part inside the Enter() method:

"long(prev) := LockedExchange(long(m_head), long(fcount1));
prev.next := fcount1;``


Is the waitfree push() , and the waitfree pop() is inside the Leave() 
method.


This is a waitfree FIFO queue.

And my scalable MLock is waitfree and FIFO fair.



Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web