Scalable lock that is FIFO fair and starvation-free version 1.28
Author: Amine Moulay Ramdane.
Description:
A node based Lock that is scalable, FIFO fair and starvation-free.
- Discovered by Amine Moulay Ramdane
- This lock is scalable
- It has the same space requirement as the scalable MCS lock
- Doesn't require a local "queue node" to be passed in as a parameter as is doing the MCS and CLH locks.
- Spins only on local locations on a cache-coherent machine
- And it's fast.
Please read this:
A bigger problem with the MCS lock is its API. It requires a second structure to be passed in addition to the address of the lock. The algorithm uses this second structure to store the information which describes the queue of threads waiting for the lock. Unfortunately, most code written using spinlocks doesn't have this extra information, so the fact that the MCS algorithm isn't a drop-in replacement to a standard spin lock is a problem.
An IBM working group found a way to improve the MCS algorithm to remove the need to pass the extra structure as a parameter. Instead, on-stack information was used instead. The result is the K42 lock algorithm:
Unfortunately, the K42 algorithm has another problem. It appears that it may be patented by IBM. Thus it cannot be used either. (Without perhaps paying royalties to IBM.)
So you have to know that my scalable MLock doesn't require a local "queue node" to be passed in as a parameter as is doing the MCS and CLH locks, my scalable MLock doesn't require any parameter to be passed, just call the Enter() and Leave() methods and that's all.
Please take a look a the test.pas Object Pascal demo inside the zipfile, compile and run it...
You can go to download the zip files by clicking on the following web link:
https://drive.google.com/drive/folders/11_gVLLHcQAVzjj8hULr1oMPgARB_jnFL?usp=sharing
Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/
Operating Systems: Windows, Mac OSX , Linux , Unix...
Required FPC switches: -O3 -Sd
-Sd for delphi mode....
Required Delphi switches: -$H+ -DDELPHI
Required Delphi XE-XE7 switches: -$H+ -DXE
{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems
{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems