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

Groups > comp.programming.threads > #2484

My scalable RWLocks

Cross-posted to 2 groups.

Show all headers | View raw

Hello,


I  explain my scalable LW_RWLock algorithm:

You will read this inside the RLock() method:

//==============================================================================
procedure TRWLOCK.RLock(var myid:integer);


begin

myid:=GetCurrentProcessorNumber;

repeat

while (FCount3^.fcount3 = 1)
do if mysleep=0 then sleep(0)
else sleep(1);

LockedExchangeAdd(FCount1^[myid].fcount1,1);

if (FCount3^.fcount3 = 0)
then break
else
  begin
    LockedExchangeAdd(FCount1^[myid].fcount1,-1);
  end;

until false;

end;
//==============================================================================

procedure TRWLOCK.RUnlock(myid:integer);

begin

LockedExchangeAdd(FCount1^[myid].fcount1,-1);

end;

//==============================================================================

First take a look at the source code inside the construtor you will 
notice that  the fcount1^ array is 64 byte aligned, and each element on 
the fcount1^ array resides in a cache line , so that it makes my RWLock 
scalable, and there is as much elements as the number of cores inside 
fcount1^ array .

As you have noticed i am testing with an: if (FCount3^.fcount3 = 0), to 
see if there is no writers threads that entered the WLock() method and 
incremented FCount3^.fcount3, if the thread that entered WLock() has not 
yet incremented FCount3^.fcount3 the threads on the RLock() side will 
proceed and the thread that entered WLock() will wait until all the 
FCount1^[i].fcount1 will equal to 0  so as you have noticed with my 
algorithm the writers will not be starved. And as you have noticed there 
is an:  if (FCount3^.fcount3 =  1) just after 
LockedExchangeAdd(FCount1^[myid].fcount1,-1) to test if the writer has 
entered and incremented FCount3^.fcount3 by 1, so that the readers will 
not spin by incrementing and decrementing FCount1^[myid].fcount1 by 1 , 
but they will spin on a sleep(0) until FCount3^.fcount3 will equal to 0, 
so my new algorithm is efficient.

Notice carefully that my RWLock is scalable cause each element of the 
FCount1^ array resides in a  seperate cache line , hence when i am 
incrementing (or dfecrementing) with 
LockedExchangeAdd(FCount1^[myid].fcount1,1) it's scaling, notice also 
that i am using the following: myid:=GetCurrentProcessorNumber so i am 
puting the processor number inside myid variable.

On the WLock() and WUnlock() side you will read this:

//==============================================================================

procedure TRWLOCK.WLock;

var i:integer;

begin

while not CAS(FCount2^.FCount2,0,1)
do
  begin
   if mysleep=0 then sleep(0)
   else sleep(1);
  end;

FCount3^.fcount3:=1;

for i:=0 to GetSystemThreadCount-1 do
  begin
    while (FCount1^[i].fcount1<>0)
     do
      begin
       //if mysleep=0 then sleep(0)
       //else sleep(1);
      end;
  end;

end;

//==============================================================================

procedure TRWLOCK.WUnlock;
var i:integer;
begin

FCount3^.fcount3:=0;
//switchtothread;
sleep(0);
FCount2^.FCount2:=0;
end;
end.
//==============================================================================


As you have noticed i am using a CAS() as a critical section cause only 
one thread must enter the WLock(), after that i am assigning 1 to 
FCount3^.fcount3 to block the new readers threads entering the RLock() 
method, after that i am waiting for all FCount1^[i].fcount1 to equal 0 
that means i am waiting for all the threads that entered the RLock() to 
exit with a RUnlock(), and in WUnlock() i am assigning 0 to 
FCount3^.fcount3  to unblock the readers threads and i am using also a 
sleep(0) so that to give a chance to the readers to run ,  so i think my 
algorithm is efficient and correct.

So if you have noticed in the "writers" side , each writer verifies if 
all the  FCount1^[i].fcount1 equal to zero , so you will say that my 
algorithm have a weakness in the writer side since every writer must 
transfer many cache lines so it will be slow, but be smart please and 
imagine that we have 100 cores, and you have to start 100 threads , so 
when a writer will enter the RWlock() method it will set all the 
FCount1^[i].fcount1 to zero  in its corresponding core,  and since every 
FCount1^[i].fcount1 resides in a core , so i think as soon a writer will 
finish to verify the  first or the second  FCount1^[i].fcount1 many 
other FCount1^[i].fcount1 may have been decremented to zero , so this 
will make the writer side faster , so i think my algorithm will still be 
fast on both the reader and the writer  and it will be scalable. Other 
than that if you have 100 cores you can start fewer than 100  threads 
and make also my algorithm faster in the "writers" side , so this will 
also make my algorithm faster on both the readers and the writers and my 
algorithm will be scalable,
but you have to know that the reader side is scalable , but even
though the writer side is more expensive than the reader side, my 
scalable RWLocks are used in scenarios of frequent reads and infrequant 
writes, so even if the writer side is more expensive my
scalable RWLocks will scale even at 3% of writes.

And you have to know also that even if we are in a scenario with many 
more writes than 3% of writes and my scalable LW_RWLockX don't scale 
globally in the timing you have to know that LW_RWLockX will still be 
useful , cause even if it doen't scale globally in the timing ,  you 
have to understand that if from the time t1 to the time t2 there is 
writes and reads and from the time t2 to time t3 there is only reads, so 
even if the time from t1 to t2 will add more to the overall time cause 
there is writes threads, the perceived throughput from time t2 to t3 
will be higher and the waiting time from t2 to t3 will be lower cause 
all my RWLocks will be scalable from t2 to t3 and this will make all my 
scalable RWLocks useful cause for example the database clients from 
internet or intranet waiting from t2 to t3 will be served more quickly 
and this is still useful and this will make my scalable RWLocks still 
useful even if it doesn't scale above 3% of writes.

Other than that, look at my scalable RWLock here:

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

You have to know that the Omnithread MREW synchronization don't scale 
either cause it uses an expensive atomic operation on the reader side, 
that's the same for the pthread reader-writer Lock, read this:

https://www.efficios.com/pub/rcu/urcu-main.pdf

I have read the following IEEE paper about RCU (Read-Copy Update), and 
as you will notice they are testing this RCU implementation against the 
pthread reader-writer lock, and as you have noticed the pthread 
reader-writer lock doesn't scale well cause the reader side of the 
pthread reader-writer lock is expensive...

Here is the paper:

https://www.efficios.com/pub/rcu/urcu-main.pdf

But as you will notice that the quiescent-state based reclamation (QSBR) 
and RCU scales very well cause there reader side functions scale very 
well, but don't worry , you don't need the RCU, cause my scalable 
RWLocks are also scaling very well on read-mostly scenarios, why my 
scalable RWLocks are scaling very well ? Cause read the following about 
my LW_RWLock algorithm:

"Notice carefully that my RWLock is scalable cause each element of the 
FCount1^ array resides in a seperate cache line , hence when i am 
incrementing with LockedExchangeAdd(FCount1^[myid].fcount1,1) it's 
scaling, notice also that i am using the following: 
myid:=GetCurrentProcessorNumber so i am puting the processor number 
inside myid variable."

Read this:

http://pages.videotron.com/aminer/rwlock1.html

So as you have noticed in my algorithm, the threads that have the same 
"myid" will have and will increment the "FCount1^[myid].fcount1" in the 
same local cache, so there will be no cache-lines transfers between the 
cores on the reader side of my scalable RWlocks algorithms, this is why 
my RWLock algorithms are scaling very well on read-mostly scenarios.

I think that my scalable RWLocks algorithms that i have invented are as 
good and as scalable as both quiescent-state based reclamation (QSBR) 
and RCU (Read-Copy Update) on the above IEEE paper..

And optimistic synchronization with hardware or software Transactional 
memory will not outperform my scalable RWLocks algorithms, cause my 
scalable RWLocks algorithms are used in scenarios of frequent reads and 
infrequent writes, so my scalable RWLocks algorithms are still very good 
and useful.

So hope that you will be happy with my RWLocks algorithms...

You can download my scalable RWLocks from:

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


I have also implemented scalable RWLocks that are starvation-free,
i will explained them to you next time...

You can download my scalable RWLocks:

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


Thank you,
Amine Moulay Ramdane.

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

Thread

My scalable RWLocks aminer <aminer@toto.net> - 2014-06-11 04:16 -0700

csiph-web