wait-free fast-pathed, bounded-time, 100% starvation-free rw-mutex...
I was wondering if the following invention of mine might be of use to Boost: http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... (please __read_all__; thank you) Here are some performance numbers wrt my algorithm versus NPTL on Linux (fedora 10), and OpenSolaris: http://groups.google.com/group/comp.programming.threads/msg/3e7531657a11baf0 My invention has some very interesting properties that simply do not exist for 99% of all the other rw-mutex algorithms I have seen to date. It's 100% starvation free and has bounded wait time for readers and writers. Heck, even the Microsoft rw-mutex algorithm in Vista does not come close to that: http://msdn.microsoft.com/en-us/library/aa904937(VS.85).aspx They clearly state that their algorithm is not fair. The algorithm I have observed in OpenSolaris does not meet this goal as well. Another nice property is that the algorithm has wait-free fast-paths. If readers hit a fast-path, then they are going to get wait-free access to the protected data-structure. The same goes for writers. The underlying operation is a single atomic fetch-and-add operation: http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... In fact, the algorithm only needs fetch-and-add; no stupid CAS-loops are required. Please take not that there are absolutely no loops in the algorithm; this is one reason why it's bounded time and starvation free. Also, it has conditional reader-to-writer upgrades and non-conditional writer-to-reader downgrade capabilities. This is something that does not exist in the Microsoft implementation, or even the OpenSolaris, or basically any Linux implementation I have observed. Same goes for OSX. Therefore, I think this particular algorithm might be of use to Boost. Any thoughts? Thank you all for you're valuable time; I really do appreciate it! :^)
on 21.08.2009 at 18:44 Chris M. Thomasson wrote :
I was wondering if the following invention of mine might be of use to Boost: http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... (please __read_all__; thank you)
do_not_automatically_unlock__very_dangerous_and_deadlock_prone__experts_only() LOOOOOOOOOOOOOOOOOOOL!!! it might be right that!!!
-- Pavel
DE wrote:
on 21.08.2009 at 18:44 Chris M. Thomasson wrote :
I was wondering if the following invention of mine might be of use to Boost: http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... (please __read_all__; thank you)
do_not_automatically_unlock__very_dangerous_and_deadlock_prone__experts_only() LOOOOOOOOOOOOOOOOOOOL!!! it might be right that!!!
Agreed. :) I think, support form moving locker guards and delayed locking is the right solution for this need. As for the initial proposal, if it really does fulfill the stated features, I'm all for including it into Boost.Thread. However, I'd like to see Anthony's opinion on this.
"Andrey Semashev" <andrey.semashev@gmail.com> wrote in message news:4A8FC4D2.6080206@gmail.com...
DE wrote:
on 21.08.2009 at 18:44 Chris M. Thomasson wrote :
I was wondering if the following invention of mine might be of use to Boost: http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... (please __read_all__; thank you)
do_not_automatically_unlock__very_dangerous_and_deadlock_prone__experts_only() LOOOOOOOOOOOOOOOOOOOL!!! it might be right that!!!
Agreed. :)
I think, support form moving locker guards and delayed locking is the right solution for this need.
I think you are right.
As for the initial proposal, if it really does fulfill the stated features, I'm all for including it into Boost.Thread.
This version does indeed fulfill all of the stated features/claims: http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... However this version: http://webpages.charter.net/appcore/misc/rwmutex_win_hpp.html will only support bounded-time starvation-free writer only contention if the underlying mutex has said properties. It still will not starve in the sense of reads to writes, or even pure reads. But pure writes are at the mercy of the underlying mutex implementation.
However, I'd like to see Anthony's opinion on this.
I hope he thinks it's worthy because IMHO Boost has no room for crappy synchronization algorithms... :^)
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h6oi3t$jds$1@ger.gmane.org... [...]
However, I'd like to see Anthony's opinion on this.
I hope he thinks it's worthy because IMHO Boost has no room for crappy synchronization algorithms...
I am awaiting approval of my subscription request for the `Boost.Thread' mailing list. I have had many conversations with Anthony over on `comp.programming.threads' and I think he might like what I have to offer. ;^)
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h6q8ii$fds$1@ger.gmane.org...
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h6oi3t$jds$1@ger.gmane.org... [...]
However, I'd like to see Anthony's opinion on this.
I hope he thinks it's worthy because IMHO Boost has no room for crappy synchronization algorithms...
I am awaiting approval of my subscription request for the `Boost.Thread' mailing list. I have had many conversations with Anthony over on `comp.programming.threads' and I think he might like what I have to offer.
;^)
I have posted a query over on the Boost threads development group. So, this conversation should be transferred over there if and when my post finally appears on the list. Sorry about not posting it there first! ;^/
Chris M. Thomasson wrote:
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h6q8ii$fds$1@ger.gmane.org...
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h6oi3t$jds$1@ger.gmane.org... [...]
However, I'd like to see Anthony's opinion on this.
I hope he thinks it's worthy because IMHO Boost has no room for crappy synchronization algorithms...
I am awaiting approval of my subscription request for the `Boost.Thread' mailing list. I have had many conversations with Anthony over on `comp.programming.threads' and I think he might like what I have to offer.
;^)
I have posted a query over on the Boost threads development group. So, this conversation should be transferred over there if and when my post finally appears on the list. Sorry about not posting it there first!
;^/
Could you point a link to that discussion? And, IMHO, this is the right place to get things into Boost, anyways...
"Andrey Semashev" <andrey.semashev@gmail.com> wrote in message news:4A912F5D.1030503@gmail.com...
Chris M. Thomasson wrote:
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h6q8ii$fds$1@ger.gmane.org...
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h6oi3t$jds$1@ger.gmane.org... [...]
However, I'd like to see Anthony's opinion on this.
I hope he thinks it's worthy because IMHO Boost has no room for crappy synchronization algorithms...
I am awaiting approval of my subscription request for the `Boost.Thread' mailing list. I have had many conversations with Anthony over on `comp.programming.threads' and I think he might like what I have to offer.
;^)
I have posted a query over on the Boost threads development group. So, this conversation should be transferred over there if and when my post finally appears on the list. Sorry about not posting it there first!
;^/
Could you point a link to that discussion?
I will as soon as it gets posted. I am using NNTP and the gmane portal/gateway to access the mailing list and the post has not shown up yet on my end.
And, IMHO, this is the right place to get things into Boost, anyways...
Okay. Well, I am new to this process (e.g., proposing new synchronization primitives to Boost) so please excuse my ignorance.
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h6mbsp$8ts$1@ger.gmane.org...
I was wondering if the following invention of mine might be of use to Boost: [...] Another nice property is that the algorithm has wait-free fast-paths. If readers hit a fast-path, then they are going to get wait-free access to the protected data-structure. The same goes for writers. The underlying operation is a single atomic fetch-and-add operation:
http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic...
In fact, the algorithm only needs fetch-and-add; no stupid CAS-loops are required.
I need to clarify a couple of points here. The following version of the algorithm: http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... does use CAS for the conditional read-to-write upgrade (e.g., `rwmutex_win::tryrdtowr()'), however it uses a constant for the comparand and is not used in a loop. Now, the upgrade functionality is simply not required aspect of the algorithm, therefore CAS is not required. One other point, there are architectures that simply do not provide fetch-and-add directly (e.g., SPARC). They instead provide CAS or LL/SC which can be used to implement fetch-and-add. So, on those architectures, the implementation will be using CAS or LL/SC loops, which will degrade the wait-free fast-path property down to lock-free. IMVHO, it's not really my algorithms fault, I instead blame the architectures that do not have native fetch-and-add instructions! ;^)
"Chris M. Thomasson" <cristom@charter.net> writes:
I was wondering if the following invention of mine might be of use to Boost:
http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... (please __read_all__; thank you)
It certainly looks interesting. The current boost::shared_mutex implementation is rather heavyweight due to timed lock support. I see that you've submitted it to TBB. Are you still in a position to submit to Boost, or do you have to assign copyright to Intel? In terms of scheduling I see that if the mutex is locked for writing then waiting readers will take precedence over waiting writers, whilst when it is locked for reading then a waiting writer will block further readers, and the writer will take precedence. This puts the mutex in control of the scheduling, and does not allow the OS to select which thread to wake based on priorities. For example, if a writer holds the lock, and one of the waiting readers is low priority then it is given the lock when the writer unlocks, even if there is a high priority writer waiting. The high priority writer is then blocked until the low priority reader has completed its task. Whether or not that's a good thing is open for discussion. I also note that there are no "try_wrlock()" or "try_rdlock()" functions. For integration with boost, it would be good if the write-lock member functions could be called "lock()" and "unlock()", whilst the read-lock member functions are called "lock_shared()" and "unlock_shared()". This would allow the existing RAII classes to be used with this new rwmutex type. Anthony -- Author of C++ Concurrency in Action | http://www.manning.com/williams just::thread C++0x thread library | http://www.stdthread.co.uk Just Software Solutions Ltd | http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
"Anthony Williams" <anthony.ajw@gmail.com> wrote in message news:87fxbh1ccf.fsf@dell.justsoftwaresolutions.co.uk...
"Chris M. Thomasson" <cristom@charter.net> writes:
I was wondering if the following invention of mine might be of use to Boost:
http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic... (please __read_all__; thank you)
It certainly looks interesting. The current boost::shared_mutex implementation is rather heavyweight due to timed lock support.
Yes, adding support for timeouts can definitely complicate things.
I see that you've submitted it to TBB.
I have not actually made a formal proposal yet.
Are you still in a position to submit to Boost, or do you have to assign copyright to Intel?
http://www.threadingbuildingblocks.org/contribution.php
In terms of scheduling I see that if the mutex is locked for writing then waiting readers will take precedence over waiting writers, whilst when it is locked for reading then a waiting writer will block further readers, and the writer will take precedence.
Yes.
This puts the mutex in control of the scheduling, and does not allow the OS to select which thread to wake based on priorities. For example, if a writer holds the lock, and one of the waiting readers is low priority then it is given the lock when the writer unlocks, even if there is a high priority writer waiting. The high priority writer is then blocked until the low priority reader has completed its task.
You are correct wrt read-to-write contention. Write-to-write contention is not bound to `SCHED_OTHER'. I could not really figure out a way to achieve all of the the claimed properties (e.g., 100% starvation-free, bounded-time) without doing the interleaving writes along with batches of reads. This does not prove anything, but I know that it can outperform several native rwmutex implementations (e.g., OpenSolaris, NPTL)...
Whether or not that's a good thing is open for discussion.
Absolutely! :^) Contention will not be good for real-time, while the fast-paths are wait-free which is perfect for real-time. Funny. Perhaps it could be useful to Boost with explicit documentation and/or even something in it's class name (e.g., `fair_rwmutex')?
I also note that there are no "try_wrlock()" or "try_rdlock()" functions.
I can do the `try_wrlock()' with something like (modulo typos): _________________________________________________________________________ bool fair_rwmutex::try_lock() throw() { assert(m_count < LONG_MAX); if (InterlockedCompareExchange(&m_mtx, 0, 1) == 1) { assert(m_count > -1); LONG count = InterlockedExchangeAdd(&m_count, -LONG_MAX); if (count < LONG_MAX) { if (InterlockedExchangeAdd(&m_rdwake, LONG_MAX - count) + LONG_MAX - count) { if (WaitForSingleObject(m_wrwset, INFINITE) != WAIT_OBJECT_0) { RWMUTEX_WIN_UNEXPECTED(); } } } return true; } return false; } _________________________________________________________________________ As for `try_rdlock()', humm, that could look like (modulo typos): _________________________________________________________________________ bool fair_rwmutex::try_lock_shared() throw() { LONG cmp1, cmp2 = m_count; do { cmp1 = cmp2; if (cmp1 < 1) { return false; } cmp2 = InterlockedCompareExchange(&m_count, cmp1 - 1, cmp1); } while (cmp1 != cmp2); if ((cmp1 - 1) < 0) { if (WaitForSingleObject(m_rdwset, INFINITE) != WAIT_OBJECT_0) { RWMUTEX_WIN_UNEXPECTED(); } } return true; } _________________________________________________________________________
For integration with boost, it would be good if the write-lock member functions could be called "lock()" and "unlock()", whilst the read-lock member functions are called "lock_shared()" and "unlock_shared()". This would allow the existing RAII classes to be used with this new rwmutex type.
Okay. I will add the try lock functions and change the function names, and re-name the class to `fair_rwmutex' to attempt to get across that it's `SCHED_OTHER'.
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h7168i$vq4$1@ger.gmane.org...
"Anthony Williams" <anthony.ajw@gmail.com> wrote in message news:87fxbh1ccf.fsf@dell.justsoftwaresolutions.co.uk... [...]
For integration with boost, it would be good if the write-lock member functions could be called "lock()" and "unlock()", whilst the read-lock member functions are called "lock_shared()" and "unlock_shared()". This would allow the existing RAII classes to be used with this new rwmutex type.
Okay. I will add the try lock functions and change the function names, and re-name the class to `fair_rwmutex' to attempt to get across that it's `SCHED_OTHER'.
Here is some preliminary code which adds some try lock functions, changes the name to `fair_mutex' and renames the `wrlock()/wrunlock()' procedures to `lock()/unlock()': http://pastebin.com/f502d0943 I still need to test drive the try lock functions in Relacy to see if I missed anything. As for the `SCHED_OTHER' issue, well, I am not sure how to get around that without sacrificing the 100% starvation free and bounded-time guarantees. Humm...
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h7ep7q$a5r$1@ger.gmane.org...
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h7168i$vq4$1@ger.gmane.org...
"Anthony Williams" <anthony.ajw@gmail.com> wrote in message news:87fxbh1ccf.fsf@dell.justsoftwaresolutions.co.uk... [...]
For integration with boost, it would be good if the write-lock member functions could be called "lock()" and "unlock()", whilst the read-lock member functions are called "lock_shared()" and "unlock_shared()". This would allow the existing RAII classes to be used with this new rwmutex type.
Okay. I will add the try lock functions and change the function names, and re-name the class to `fair_rwmutex' to attempt to get across that it's `SCHED_OTHER'.
Here is some preliminary code which adds some try lock functions, changes the name to `fair_mutex' and renames the `wrlock()/wrunlock()' procedures to `lock()/unlock()':
I still need to test drive the try lock functions in Relacy to see if I missed anything. As for the `SCHED_OTHER' issue, well, I am not sure how to get around that without sacrificing the 100% starvation free and bounded-time guarantees. Humm...
I forgot to destroy a resource in the failure case of the constructor. Here is code without the leak: http://pastebin.com/f527722e0 Here is the difference between leaky code and corrected code above: http://pastebin.com/pastebin.php?diff=f527722e0
"Chris M. Thomasson" <cristom@charter.net> writes:
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h7ep7q$a5r$1@ger.gmane.org...
"Chris M. Thomasson" <cristom@charter.net> wrote in message news:h7168i$vq4$1@ger.gmane.org...
"Anthony Williams" <anthony.ajw@gmail.com> wrote in message news:87fxbh1ccf.fsf@dell.justsoftwaresolutions.co.uk... [...]
For integration with boost, it would be good if the write-lock member functions could be called "lock()" and "unlock()", whilst the read-lock member functions are called "lock_shared()" and "unlock_shared()". This would allow the existing RAII classes to be used with this new rwmutex type.
Okay. I will add the try lock functions and change the function names, and re-name the class to `fair_rwmutex' to attempt to get across that it's `SCHED_OTHER'.
Here is some preliminary code which adds some try lock functions, changes the name to `fair_mutex' and renames the wrlock()/wrunlock()' procedures to `lock()/unlock()':
I still need to test drive the try lock functions in Relacy to see if I missed anything. As for the `SCHED_OTHER' issue, well, I am not sure how to get around that without sacrificing the 100% starvation free and bounded-time guarantees. Humm...
I forgot to destroy a resource in the failure case of the constructor. Here is code without the leak:
Thanks. Did you try it in Relacy? It looks OK at a quick glance, but I'm not sure I haven't missed anything. Anthony -- Author of C++ Concurrency in Action | http://www.manning.com/williams just::thread C++0x thread library | http://www.stdthread.co.uk Just Software Solutions Ltd | http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
"Anthony Williams" <anthony.ajw@gmail.com> wrote in message news:87d466n1qh.fsf@dell.justsoftwaresolutions.co.uk...
"Chris M. Thomasson" <cristom@charter.net> writes: [...]
I still need to test drive the try lock functions in Relacy to see if I missed anything. As for the `SCHED_OTHER' issue, well, I am not sure how to get around that without sacrificing the 100% starvation free and bounded-time guarantees. Humm...
I forgot to destroy a resource in the failure case of the constructor. Here is code without the leak:
Thanks. Did you try it in Relacy?
No yet. I am going to try and get that accomplished within next couple of days.
It looks OK at a quick glance, but I'm not sure I haven't missed anything.
;^) Humm... Perhaps I should change the name from `fair_mutex' to `fair_rwmutex'? lol. http://pastebin.com/f16881bed (*) BTW, what are you're thoughts wrt the name change to `fair_rwmutex'? IMVHO, it sort of implies that the synchronization primitive is `SCHED_OTHER'... (*) This code has fixed an issue that only showed up when one attempted to upgrade a recursively acquired read lock to a write lock. The previous version would simply deadlock: ______________________________________________________ rw.rdlock(); rw.rdlock(); if (rw.tryrdtowr()) { rw.wrunlock(); return; } rw.rdunlock(); rw.rdunlock(); ______________________________________________________ Would deadlock. While the following would not: ______________________________________________________ rw.rdlock(); if (rw.tryrdtowr()) { rw.wrunlock(); return; } rw.rdunlock(); ______________________________________________________ Now, both versions will work. The first one with recursive read access will never be able to upgrade, while the latter might be able to.
participants (4)
-
Andrey Semashev -
Anthony Williams -
Chris M. Thomasson -
DE