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

Groups > comp.lang.pascal.misc > #967

My scalable MLock algorithm

Show all headers | View raw

Hello...


I have invented my scalable MLock algorithm(a scalable lock)
and you have to know that it's "waitfree" on both the Enter()
and Leave() methods, so it can be used on realtime systems and
it is very efficient, and also you have to know that the Windows 
critical section uses an exponential backoff, this is why it is fast,
but its exponential backoff is not good cause it does not load
balance efficiently the CPU ressource between the threads,
this is why i have invented my scalable MLock that is
more efficient than the Windows critical section and
that is FIFO fair.



scalable MLock is 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() method and that's all.



You can download my scalable MLock from:


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




Thank you,
Amine Moulay Ramdane.

Back to comp.lang.pascal.misc | Previous | Next | Find similar

Thread

My scalable MLock algorithm Ramine <ramine@1.1> - 2014-10-21 16:29 -0700

csiph-web