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

Groups > comp.programming.threads > #2738 > unrolled thread

Here is my new algorithm of a scalable distributed sequential lock

Back to article view | Back to comp.programming.threads

Contents

  Here is my new algorithm of a scalable distributed sequential lock Ramine <ramine@1.1> - 2014-12-06 13:43 -0800
    Re: Here is my new algorithm of a scalable distributed sequential lock Ramine <ramine@1.1> - 2014-12-06 14:07 -0800

#2738 — Here is my new algorithm of a scalable distributed sequential lock

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.

[toc] | [next] | [standalone]

#2739

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.

> 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.
>
>
>
>

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web