Path: csiph.com!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail From: aminer Newsgroups: comp.programming.threads,comp.programming Subject: My scalable RWLocks Date: Wed, 11 Jun 2014 04:16:04 -0700 Organization: albasani.net Lines: 236 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.albasani.net 6GItxQAYIkEU2bvpwG0012gSrWBPduvq5+fHKUFB3VzAahsxZ2657l7UlMxOeBAP+gYWU0O6b9Shq3AyAEbtWAr99QEbO8LRUvhRQdxeEyVYfcXKERvG5dh583rCGgB3 NNTP-Posting-Date: Wed, 11 Jun 2014 20:16:05 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="PNmolRNEzFjMNYcV6F9tAmykUPRVfJMC9sobzFZ1KfCxEujq4GJPcGUUL52Cm+QDH01gAPa/C/5hTI+Ont20NczVunZVePysS0p1OekFfeGqf39XEtfOCbFssqPMLxFA"; mail-complaints-to="abuse@albasani.net" User-Agent: Mozilla/5.0 (Windows NT 6.0; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 Cancel-Lock: sha1:nk+Z2q8fz27Jg4uZ+IRR4451YtM= Xref: csiph.com comp.programming.threads:2484 comp.programming:4579 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.