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

Groups > comp.programming.threads > #2738

Here is my new algorithm of a scalable distributed sequential lock

Show all headers | View raw

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.

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

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

csiph-web