- About reader-writer mechanisms - 1 Update
- cmsg cancel <mdge54$bnl$2@dont-email.me> - 1 Update
| Ramine <ramine@1.1>: Mar 07 10:03PM -0800 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-results=7 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-the-idea/ 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/scalable-rwlock 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-the-idea/ http://concurrencyfreaks.blogspot.ca/search?updated-min=2015-01-01T00:00:00%2B01:00&updated-max=2016-01-01T00:00:00%2B01:00&max-results=7 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-writer-mutex 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/scalable-seqlockx 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/scalable-seqlockx Thank you, Amine Moulay Ramdane. |
| bleachbot <bleachbot@httrack.com>: Mar 08 04:03AM +0100 |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.programming.threads+unsubscribe@googlegroups.com. |
No comments:
Post a Comment