Scalable Distributed Fair Lock 1.0

[aminer]

Hello,

Scalable Distributed Fair Lock 1.0 is here, i have put it again
on my website cause even that it uses a Ticket mechanism , the Ticket
mechanism performs well up to a number of threads 3X times the number of cores and i have benchmarked it to notice that , so the Ticket mechanism is still very useful.

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 , so it think it avoids starvation and it reduces the cache-coherence traffic. 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.

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.

Note: You have to use a number of threads not greater than 3X times the number of cores so that the Ticket mechanism will be optimal.

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

You can download Scalable Distributed Fair Lock 1.0 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,

Please read this about how the Ticket spinlock slows the
thinks when it spins on a global variable, this problem
doesn't happened with my distributed fair Lock cause my
distributed fait Lock spins on local variables so it's efficient.

Read please:

http://lwn.net/Articles/531254/



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

My scalable distributed fair Lock was updated to version 1.01,
we have to be smart and understand that the queue that
i was using was not fair, hence this queue can cause also starvation, so i have decided to change the FIFO queue by a queue that uses a Ticket mechanism on the push() side to be fair and that uses a proportional backoff to reduce the cache-coherence traffic, so now  my scalable distributed fair Lock is fair when there is contention and it avoids starvation.


You can download my scalable distributed fair Lock from:

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




Thank you,
Amine Moulay Ramdane

[aminer]

Hello again,


I have thought all the day about the Anderson array based Lock
and the Ticket Spinlock, they both have a weakness and you have
to be smart to understand this weakness, cause when i have
benchmarked the Anderson Lock i have discovered that it doesn't
scale if the number of threads are greater than the number of cores
and the answer is simple , it is due to the context switches that
are expensive , the context switched will slow a lot the Lock and they will make it none scalable, for the Spinlock with exponential backoff if
a thread leaves the locked region the first thread that wants
to enter the Lock will enter the lock immediatly , that's not
true with the Anderson lock , cause if a  thread unlock the lock
it will set the next threads and its correspondant variable to true,
but if the thread is not scheduled in its processor and other threads
are running on the same processor the context switch that we must wait for will slow the Lock, this is the weakness of the Anderson Lock
and the Ticket Lock, if there is more threads than the number
of cores they will become slow and they will not be scalable.



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello again,

I think i have implemented all types of Locks: Spinlocks with
a backoff mechanism, the array based locks, and distributed locks etc.
and i think i have understood them well: the fair Locks such as
the Ticket spinlock and the Anderson Lock and the MCS lock and
my scalable distributed Lock that is fair when there is contention and that avoid starvation all of them do not scale and become slow if the number of threads are greater than the number of cores, but the unfair locks such as the Spinlock with backoff and my scalable distributed Lock(the version that is unfair) will scale even if the number of threads are greater than the number of cores.


This is very important to understand.

I have implemented an enhanced version of the scalable Anderson Lock
and i will put it tomorrow on my website.


So be smart please...



Thank you,
Amine Moulay Ramdane.



   

[aminer]

Hello,


We have to be smart, i have come to an interresting subject,
if you want to add a backoff mechanism to the Ticket Lock ,
since the locked region can have a variable length, so it's not
easy to come with a backoff mechanism that reduces efficiently
the cache-coherence traffic, that's the same for a Spinlock
with an exponential backoff , so how can we do it  ?
if you take a look at the source code of my scalable
distributed fair lock you will notice that there is two
place where i am using a Ticket mechanism , inside
the LW_DFLOCK.pas and inside the FIFO queue inside
the source code lockfree_mpmc.pas, but for the first Ticket
mechanism that i am using inside LW_DFLOCK.pas we don't need
a backoff to reduce the cache-coherence traffic, cause it is
spinning locally on a variable inside the same core,
but for the FIFO queue we need a backoff for its Ticket mechanism
but this is not so difficult cause the locked region has 
a constant length, this is why i have added a backoff mechanism
to the Ticket mechanism inside the push() method of lockfree_mpmc.pas,
i have benchmarked it and it's giving a good performance, so this
is why my scalable distributed fair lock is better than the
Ticket spinlock and it's FIFO fair when there is contention,
so it avoids starvation also.

You can download my scalable distributed fair Lock from:

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

Thank you,
Amine Moulay Ramdane,