Scalable Distributed Fair Lock 1.03

aminer10 — Sat, 26 Oct 2013 03:29:43 GMT

Hello,

Scalable Distributed Fair Lock 1.03

Authors: Amine Moulay Ramdane.

Click here to download the zip file: Zip (for FreePascal and Lazarus and Delphi 7 to 2007)

Description:

A scalable distributed Lock, it is as fast as the Windows critical section and it is FIFO fair when there is contention , so i think it avoids starvation and it reduces the cache-coherence traffic. My Scalable and distributed Lock uses now a Ticket mechanism , so it's FIFO fair when there is contention, but my Scalable distributed Lock is more efficient than the Ticket Spinlock cause it's distributed and hence the threads spins locally on variables on the local caches on the same core, so it minimizes efficiently 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.

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 minimizes efficientlythe 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 places 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 Ticketmechanism 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 also starvation.

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

Click here to see the explanation of my scalable distributed Lock algorithm: Algorithm explanation

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

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

topic Scalable Distributed Fair Lock 1.03 in Intel® Moderncode for Parallel Architectures

Scalable Distributed Fair Lock 1.03