Here is my new algorithm of a scalable distributed sequential lock

[Ramine]

Hello,

As i have promised, here is my newer algorithm versoin 1.1 of a scalable
distributed sequential lock that is competitive with RCU,
and that beats Seqlock on some characteristics because it
doesn't starve and it doesn't livelock when a greater percentage of
writers are used, please take a look at the source code , the RLock()
and RUnlock methods have changed, what i am doing on RLock() is that
i am taking a copy of "FCount6^.fcount6" counter that is incremented on
the writer side, and i am taking the modulo of the "number of cores"
of this counter and when this modulo is equal to 0, i am switching
to a distributed algorithm on the reader side, and on RUnlock() method
i am testing if the FCount6^.fcount6 is equal to the old copy of
FCount6^.fcount6 that had the modulo equal to 0, so if they are
equal, i will exit by unlocking the distributed reader-writer lock, if
it's not, i will stay in the Seqlock mode. My newer algorithm
has allowed me to avoid memory barriers and atomics on the reader side,
so it has become competitive with RCU , so i think it can replace RCU,
and it beats RCU on some characteristics such as it doesn't starve or
livelock when there is a greater percentage of writers.


About the sequential consistency of my scalable distributed sequential
lock, my algorithm works on x86 architecture and i think my algorithm is
correct cause look at the source code of the WLock() method, since i am
using a Ticket spinlock with a proportional backoff on the writer side,
the Ticket spinlock is using a "lock add" assembler instruction to
increment a counter in the Enter() method of the ticket spinlock , and
this "lock add" assembler instruction is a barrier for stores and loads
on x86, so the WLock() method is sequential consistent and correct, now
look at the WUnlock() , we don't need an "sfence" cause stores are not
reordered with stores on x86 , so WUnlock() method is sequential
consistent and correct, now look at the RLock() method, the loads inside
RLock() method are not reordered with the loads of the reader section ,
and on RUnlock(), the loads of RUnlock() are not reordered with older
loads of the critical section , so all in all my algorithm i think my
algorithm is sequential consistent and correct on x86. So be confident
cause i have reasoned correctly and i think my algorithm is correct and
it is a powerful synchronization mechanism that can replace RCU and that
can replace Seqlock cause it beats Seqlock.



You can download my scalable distributed sequential lock version 1.1 from:

https://sites.google.com/site/aminer68/scalable-distributed-sequential-lock


Thank you,
Amien Moulay Ramdane.

[Ramine]

On 12/6/2014 1:43 PM, Ramine wrote:
> Hello,
>
> As i have promised, here is my newer algorithm versoin 1.1 of a scalable
> distributed sequential lock that is competitive with RCU,
> and that beats Seqlock on some characteristics because it
> doesn't starve and it doesn't livelock when a greater percentage of
> writers are used, please take a look at the source code , the RLock()
> and RUnlock methods have changed, what i am doing on RLock() is that
> i am taking a copy of "FCount6^.fcount6" counter that is incremented on
> the writer side, and i am taking the modulo of the "number of cores"
> of this counter and when this modulo is equal to 0, i am switching
> to a distributed algorithm on the reader side, and on RUnlock() method
> i am testing if the FCount6^.fcount6 is equal to the old copy of
> FCount6^.fcount6 that had the modulo equal to 0, so if they are
> equal, i will exit by unlocking the distributed reader-writer lock, if
> it's not, i will stay in the Seqlock mode. My newer algorithm
> has allowed me to avoid memory barriers and atomics on the reader side,
> so it has become competitive with RCU , so i think it can replace RCU,
> and it beats RCU on some characteristics such as it doesn't starve or

I mean it beats Seqlock.