Asp Forum - About reader-writer mechanisms

Ramine

3/8/2015 6:04:00 AM

Hello,

We have to be smart when thinking about reader-writer consistent
mechanism which has different kinds of characteristics... first comes
first, we have to know an important thing is how to evaluate those
reader=writer mechanisms ? i think we have to evaluate them
using the following criteria: scalability, starvation-freedom and power
efficiency..

So i will start with the following reader-writer lock, look at it
in the following webpage:

http://concurrencyfreaks.blogspot.ca/search?updated-min=2015-01-01T00:00:00%2B01:00&updated-max=2016-01-01T00:00:00%2B01:00&max...

this algorithm is using the same algorithm as the following algorithm by
Joe Duffy an architect at Microsoft:

http://joeduffyblog.com/2009/02/20/a-more-scalable-readerwriter-lock-and-a-bit-less-harsh-consideration-of...

If we judge those reader-writer locks on the criteron of
starvation-freedom, those reader-writer locks above are not
starvation-free, but my scalable RWLock called LW_RWLockX and my
scalable RWLock called RWLockX are starvation-free.

You can download my scalable RWLocks that are starvation-free from:

https://sites.google.com/site/aminer68/scala...

Now if we judge those reader-writer locks above on the power efficiency
criterion , those reader-writer above are less efficient than
my scalable RWLock called LW_RWLockX and less efficient than my
scalable RWLock called RWLockX.

So now we will evaluate those reader-writer locks above on the criterion
of scalability on multicores:

I must say that they are both innefficient when it comes to scalability
on multicores and i will explain to you why:

I must say that we have to be carefull, because i have just
read the above webpages about those more scalable reader/writer lock
by an architect at microsoft called Joe Duffy and a PhD called Pedro
Ramalhete... but you have to be carefull because those reader/writer
locks are not really scalable, and i will think as an architect and
explain to you why...

Here is the webpage, and my explanation follows...

http://joeduffyblog.com/2009/02/20/a-more-scalable-readerwriter-lock-and-a-bit-less-harsh-consideration-of...

http://concurrencyfreaks.blogspot.ca/search?updated-min=2015-01-01T00:00:00%2B01:00&updated-max=2016-01-01T00:00:00%2B01:00&max...

So look inside the EnterWriteLock() of the reader/writer above of Joe
Duffy, you will notice that it is first executing
Interlocked.Exchange(ref m_writer, 1), that means it is atomicaly making
m_writer equal 1, so that to block readers from entering the reader
section, but this is garbage, cause look after that he is doing this:

for (int i = 0; i < m_readers.Length; i++)

while (m_readers[i].m_taken != 0) sw.SpinOnce();

So after making m_writers equal 1 so that to block the readers,
he is transfering many cache-lines between cores, and this is really
expensive and it will make the serial part of the Amdahl's law bigger
and bigger when more and more cores will be used , so this will not
scale, so it is kind of garbage.

My explanation applies to the other algorithm of Pedro Ramalhete because
the Joe Duffy reader-writer lock above is the same algorithm.

But the Dmitry Vyukov distributed reader-writer mutex doesn't have this
weakness, because look at the source code here:

http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem/distributed-reader-wr...

Because he is doing this on the distr_rw_mutex_wrlock() side:

for (i = 0; i != mtx->proc_count; i += 1)
pthread_rwlock_wrlock(&mtx->cell[i].mtx);

So we have to be smart here and notice with me that as the "i" counter
variable goes from 0 to proc_count, the reader side will still be
allowed to enter and to enter again the reader section on scenarios with
more contention, so in contrast with the above reader-writer lock, this
part of the distributed lock is not counted as only a serial part of the
Amdahl's law, because it allows also the reader threads to enter
and to enter again the reader section, so this part contains a parallel
part of the Amdahl's law, and this makes this distributed reader-writer
lock to effectively scale. This is even better with my Distributed
sequential lock , because my Distributed sequential lock scales even
better than the distributed reader-writer mutex of Dmitry Vyukov.

But there is a weakness on the distributed reader-writer mutex of Dmitry
Vyukov, because the writer's side will become slower and slower when you
will add more and more cores and use more and more threads , because it
will transfers too many cache-lines and this is really expensive and
this will make the writer's side too slow and this is a real problem,
because this reader-writer mutex does effectively scale the readers but
the writer's side will become slower and slower
when there is more cores and more threads.

Now let us talk about my scalable SeqlockX algorithm that you will
find here:

https://sites.google.com/site/aminer68/scalabl...

This scalable SeqlockX is scalable reader-writer mechanism that
is really scalable on multicores and it improve on the classical Seqlock
because it eliminates completly the "livelock" of the readers when there
is many writers. I think my new scalable SeqlockX algorithm is the right
tool to use if you want to replace scalable RWLocks or to replace Dmitry
Vyukov's distributed reader-writer mutex, it can even replace RCU, it
has good characteristics: since it doesns't "livelock" the readers when
there is many writers, and since it is extremely fast
and since it is really "scalable" and more scalable and faster on more
cores than Dmitry Vyukov's distributed reader-writer mutex, so i think
you have to port it to C++ and Java and C# also.

As you have noticed, currently , I have implemented my algorithm for
Delphi and FreePascal compilers...

You can download my scalable SeqlockX and read about the algorithm from:

https://sites.google.com/site/aminer68/scalabl...

Thank you,
Amine Moulay Ramdane.

comp.programming

About reader-writer mechanisms

Ramine

x Login to ForumsZone