Scalable distributed Lock versoin 1.1

[aminer]

Hello,


My scalable distributed Lock have been updated to version 1.1,
now it is fair when there is contention, so i think it will avoid
starvation and it reduces the cache-coherence traffic.


Authors: Amine Moulay Ramdane.


Description:

A scalable distributed Lock, it is as fast as the windows critical section and it is fair when there is contention , and it reduces the cache-coherence traffic.

I have not used a Waitfree queue to implement my Scalable Distributed Lock,  but you can use a Waitfree queue so that my Scalable Distributed Lock will be more efficient.

Please take a look a the test.pas Object Pascal demo inside the zipfile, compile and run it...


You can download my Scalable and distributed Lock from:

http://pages.videotron.com/aminer/

Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/

Operating Systems: Windows, Mac OSX , Linux , Unix...


Required FPC switches: -O3 -Sd -dFPC -dFreePascal

-Sd for delphi mode....

{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems

{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

If you have noticed my Scalable and distributed Lock uses now
a Ticket mechanism, but my Scalable distributed Lock is more
efficient than the Ticket Spinlock cause it's distributed and
hence the threads spins on local variables so it reduced the cache
misses and the cache-cohence traffic, so my scalable distributed Lock
is more efficient than the Ticket Spinlock.



Thank you,
Amine Moulay Ramdane

[BigChimp]

Still haven't found the edit button I see...

[aminer]

Hello,


We have to be very carefull, i have just benchmarked my Scalable distributed Lock
version 1.1, and i have noticed that since it uses a Ticket mechanism it
doesn't scale, the problem with the Ticket mechanism is that it has a poor performance cause in the case of a spinlock without tickets when it is unlocked() the first thread that comes first to the lock() will enter immediatly the locked section, but that's not the case with a Ticket spinlock cause if the first thread that enters the lock() first has not the ticket to enter, the other thread that have the ticket to enter and that is waiting for his turn will wait longer/more, if there is
also context switches it will wait longer,  so this is why the Ticket spinlock has a poor performance compared to a simple spinlock with a backoff, so i have decided to return back to my scalable distributed Lock
version 1.0, the version 1.0 doesn't use a ticket mechanism but it
is much fair than the Windows critical section , other than that
i have benchmarked the Windows critical section and i have noticed that
it doesn't scale well , my scalable distributed Lock scales much better , also my scalable distributed Lock spins on local variables so it reduces
the cache misses and it reduces the cache-coherence traffic, the Windows
critical section spins on a global variable so it's less efficient than
my scalable distributed Lock.




Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,


I have thought more about my scalable distributed Lock and
i have done some benchmarks and more tests, and i have found that
it has something better than the Windows critical section and better
than a Spinlock with an exponential backoff, if  the locked region
becomes bigger the backoff of the Windows critical section will
not be good cause it will allow the same thread to reenter the locked
region many many times and this is not good i think, cause i think
the Windows critical section must balance more and give each thread
a chance to run, so i think that the Windows critical section and also the Spinlock with exponential backoff are not suited for locked regions that are bigger, they are suited for small locked regions, this problem does not happen with my scalable distributed lock , cause if you take
a look at the source code, the first Spinlock(with an exponential backoff) inside the fifo queue that i am using have a small critical section so my scalable distributed Lock will balance more and give each thread a chance to run , this is where also  my scalable distributed Lock is more efficient than the Windows critical section and the Spinlock with an exponential backoff, and my scalable distributed Lock is best suited also for bigger locked regions, the Windows
critical section is not. This is why also it is very usefull and good.


Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

I have implemented an enhanced version of the Anderson array based Lock , and i have come to the conclusion that the Anderson array based Lock doesn't scale well, cause if there is more threads than the number of cores and there is context switches the thread that must enter the Lock can wait longer and this will not make the Anderson Lock scalable,
the same problem happens with the MCS queue Lock it doesn't scale well,
the Ticket Spinlock doens't scale either..


Here is my enhanced implementation of the Anderson array based Lock...
 
==============================================================================
procedure TALOCK.Enter;

var  count1,slot:long;
     
begin

repeat

count1:=LockedIncInt(count);

if count1<= FSize then break;

LockedDecInt(count);

sleep(0);

until false;

slot:=LockedIncInt(fcount2^.fcount2);
while Fcount1^[(slot-1) mod fsize].fcount1<>1
do sleep(0);

end;

//==============================================================================

procedure TALOCK.Leave;

begin
FCount1^[fcount3^.fcount3 mod fsize].FCount1 := 0;
inc(fcount3^.fcount3);
LockedDecInt(count);
FCount1^[fcount3^.fcount3  mod fsize].FCount1 := 1;

end;
end.

---



Thank you,
Amine Moulay Ramdane.

[aminer]

I will add...

I wrote:

"I have implemented an enhanced version of the Anderson array based Lock , and i have come to the conclusion that the Anderson array based Lock doesn't scale well, cause if there is more threads than the number of cores and there is context switches the thread that must enter the Lock can wait longer and this will not make the Anderson Lock scalable"

If you have noticed if there context switches the thread that must enter or that entered the the Lock must wait longer and it must wait the other threads on the same core to have cache misses, so this will be slow and this is not good , so this is why the Anderson
array based Lock is not scalable , and i have done some benchmarks on the Anderson array based Lock and it's doesn't scale when there is more threads than the number of cores, this problem doesn't happen
with my scalable distributed Lock.



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

My scalable and distributed Lock was updated to version 1.01, i have changed a little bit
the interface, now you have only to call
Enter() and Leave() methods without any paramater like for the Windows critical section.


You can download my scalable and distributed Lock from:

http://pages.videotron.com/aminer/


Thank you,
Amine Moulay Ramdane.

[aminer]

Hello again,

I have implemented another Lock that is fair using an algorithm that look like my SemaCondvar algorithm, but there is still a problem with it, if you take a look
at my SemaCondvar algorithm it uses a critical section, but this critical section defeat the purpose of fairness cause it uses a spin-wait mechanism that introduce the starvation problem, but
if i use a Semaphore instead of a Windows Critical Section the
context switches will slow a lot the algorithm, other than that
i am using three locked regions in my algorithm that uses
the same Lock, so this will higher the delay in the backoff mechanism
of the Windows critical section or the Spinlock with an exponential
backoff , so this will slow a lot the algorithm, hence those problems have defeated the purpose of fairness of my algorithm and they will make
my algorithm slow.

But my Scalable Distributed Lock is good and i advice you to use it cause it is suited even for bigger locked regions, i think the Windows critical section is not suited for bigger locked regions and i have explained
to you why.



Thank you,
Amine Moulay Ramdane,.