[thread] upgrading read lock to write lock
I'm struggling to find the correct incantation to upgrade a (conceptual) read lock to a write lock. Here's my best guess at what I think should work, but it deadlocks at the highlighted point: #include <iostream> #include <iomanip> #include <boost/thread/shared_mutex.hpp> #include <boost/thread/locks.hpp> int main() { using namespace boost; shared_mutex m; shared_lock<shared_mutex> readlock(m); // reads go here // ... // Ah, need to write actually. // Upgrade to a write lock now. upgrade_lock<shared_mutex> uglock(m); std::cout << __LINE__ << std::endl; upgrade_to_unique_lock<shared_mutex> writelock(uglock); // <-- deadlock? std::cout << __LINE__ << std::endl; return 0; } I've been trying this with various combinations of msvc 9, msvc 10, mingw 4.3, boost 1.39 and boost 1.45, but always with the same results. Could someone kindly put me out of my misery? :) Kind regards, Edd
On Feb 6, 2011, at 3:11 PM, Edd Dawson wrote:
I'm struggling to find the correct incantation to upgrade a (conceptual) read lock to a write lock.
Here's my best guess at what I think should work, but it deadlocks at the highlighted point:
#include <iostream> #include <iomanip> #include <boost/thread/shared_mutex.hpp> #include <boost/thread/locks.hpp>
int main() { using namespace boost;
shared_mutex m; shared_lock<shared_mutex> readlock(m); // reads go here // ...
// Ah, need to write actually. // Upgrade to a write lock now. upgrade_lock<shared_mutex> uglock(m); std::cout << __LINE__ << std::endl; upgrade_to_unique_lock<shared_mutex> writelock(uglock); // <-- deadlock? std::cout << __LINE__ << std::endl;
return 0; }
I've been trying this with various combinations of msvc 9, msvc 10, mingw 4.3, boost 1.39 and boost 1.45, but always with the same results.
Could someone kindly put me out of my misery? :)
My implementation of shared/upgrade mutexes and locks is here: http://home.roadrunner.com/~hinnant/mutexes/shared_mutex and using that, the following works: #include <shared_mutex> #include <mutex> #include <iostream> #include <iomanip> int main() { ting::upgrade_mutex m; ting::upgrade_lock<ting::upgrade_mutex> readlock(m); // reads go here // ... // Ah, need to write actually. // Upgrade to a write lock now. std::cout << __LINE__ << std::endl; std::unique_lock<ting::upgrade_mutex> writelock(std::move(readlock)); std::cout << __LINE__ << std::endl; return 0; } What I have is similar to boost and I believe you can use this as an example to get your code working with the boost version. There is an explanation at the link above as to how my implementation is supposed to work. It is open source and please feel free to use it if that works better for you. -Howard
Howard Hinnant wrote: ...
int main() {
ting::upgrade_mutex m; ting::upgrade_lock<ting::upgrade_mutex> readlock(m); // reads go here
The problem is that only one thread can do this at a time, and I suspect that in the original problems, there are many such readers, some of which need to then write, but only occasionally. This is one way to do it: take read lock; int v = data.version_; // reads go here drop read lock; if( need to write ) { take write lock; if( v != data.version_ ) { retry reads; } if( still need to write ) { ++data.version_; // writes go here } drop write lock; } Note that no upgrade locks are needed.
On Feb 6, 2011, at 5:10 PM, Peter Dimov wrote:
Howard Hinnant wrote: ...
int main() {
ting::upgrade_mutex m; ting::upgrade_lock<ting::upgrade_mutex> readlock(m); // reads go here
The problem is that only one thread can do this at a time, and I suspect that in the original problems, there are many such readers, some of which need to then write, but only occasionally. This is one way to do it:
take read lock; int v = data.version_; // reads go here drop read lock;
if( need to write ) { take write lock;
if( v != data.version_ ) { retry reads; }
if( still need to write ) { ++data.version_; // writes go here }
drop write lock; }
Note that no upgrade locks are needed.
Yes, there are several tools in the tool box here. And none of them are the right tool for all situations. The upgradable lock tends to be most needed when the read is expensive enough that you want to put extra effort into not repeating it. -Howard
On 2/6/2011 11:51 PM, Howard Hinnant wrote:
On Feb 6, 2011, at 5:10 PM, Peter Dimov wrote:
Howard Hinnant wrote: ...
int main() {
ting::upgrade_mutex m; ting::upgrade_lock<ting::upgrade_mutex> readlock(m); // reads go here
The problem is that only one thread can do this at a time, and I suspect that in the original problems, there are many such readers, some of which need to then write, but only occasionally.
What I'm trying to achieve is to be able to turn a read lock in to a write lock without forfeiting my 'turn'. Specifically, I'm implementing a kind of thread-local storage. In order to do so, I have a map whose keys are thread::ids. I'd like to take a read lock while looking to see if there's something in the map for the current thread and if so, return the associated value. Otherwise, I want to upgrade to a write lock so I can fill in a value for the current thread before returning it. I guess I'd like to know: 1. Is this a realistic thing to expect to be able to achieve? I'm under the impression that this is the purpose of an upgradable locking facility. Perhaps this isn't the case, though? 2. The boost-centric code that I posted was my attempt at doing this. What makes it wrong?
Yes, there are several tools in the tool box here. And none of them are the right tool for all situations. The upgradable lock tends to be most needed when the read is expensive enough that you want to put extra effort into not repeating it.
It may be the case that my approach to the problem will result in an inefficient solution, but I'd like to at least understand the correctness problems, before continuing much further. And Howard, thanks for sharing your ting implementation elsewhere in the thread. For what it's worth I approve of the separate upgrade_mutex and may consider using this instead, in the end. Thanks for sharing! Kind regards, Edd
On Feb 6, 2011, at 7:04 PM, Edd Dawson wrote:
What I'm trying to achieve is to be able to turn a read lock in to a write lock without forfeiting my 'turn'.
Specifically, I'm implementing a kind of thread-local storage. In order to do so, I have a map whose keys are thread::ids. I'd like to take a read lock while looking to see if there's something in the map for the current thread and if so, return the associated value. Otherwise, I want to upgrade to a write lock so I can fill in a value for the current thread before returning it.
I guess I'd like to know:
1. Is this a realistic thing to expect to be able to achieve? I'm under the impression that this is the purpose of an upgradable locking facility. Perhaps this isn't the case, though?
I'm not positive if upgradable locks fit your use case or not, mainly because I don't know enough about your use case. If *every* thread follows the algorithm you describe, then it probably won't work (except maybe as described below). The problem is that if you have more than one thread holding a shared lock, you can only promise one of those threads that they can upgrade to a unique lock without forfeiting their shared lock. Otherwise you get deadlock when two of the threads holding shared locks each wait for the other to release their shared lock so that they can upgrade to unique ownership. The way the upgrade_lock is meant to work is that a bunch of threads are able to obtain a shared_lock, and at the same time *one* thread obtains an upgrade_lock, which shares ownership with the other threads holding a shared_lock. Then if and when the thread with the upgrade_lock wants unique ownership, then he converts the upgrade_lock to a unique_lock. This operation blocks until all of the threads with the shared_locks give up their ownership. And then the conversion from upgrade to unique completes. A compromise solution (which boost doesn't support, but http://home.roadrunner.com/~hinnant/mutexes/locking.html does), is for a bunch of threads to hold shared_locks, and they can *all* /try/ to convert their shared_locks to either upgrade_locks or unique_locks. The conversion to upgrade_lock can succeed for only one thread. The conversion to unique_lock will succeed only if no other threads are currently holding a shared_lock (or upgrade_lock), and no thread is already blocked waiting for a unique_lock. In this scenario, the logic has to have something to do if the attempted conversion from shared fails. Simply turning around and trying again is simply going to implement an expensive spin lock at best, and deadlock at worst. Bringing this back to your problem, upgradeable locks will only work if there are some threads which need read access and don't ever want to upgrade to write access, or can at least choose to do something else if a try-conversion fails. A thread with an upgrade_lock can share threads holding shared_locks. But a thread with an upgrade_lock can not share with another thread needing an upgrade_lock.
2. The boost-centric code that I posted was my attempt at doing this. What makes it wrong?
int main() { using namespace boost; shared_mutex m; shared_lock<shared_mutex> readlock(m); // reads go here // ... // Ah, need to write actually. // Upgrade to a write lock now. upgrade_lock<shared_mutex> uglock(m); ---- You have called m.lock_shared() followed by m.lock_upgrade(). I haven't even thought about what this does to a mutex, but it can't be good. It is like calling m.lock() twice on a non-recursive mutex. It is going to put it into an undefined state. There is no unconditional conversion from shared_lock to upgrade_lock (in either implementation), though in my implementation their are try- and timed-versions of this conversion. But it would be done with this syntax: // use upgrade_mutex everywhere, shared_mutex can't change ownership modes ... // Ah, need to write actually. // Upgrade to a write lock now. upgrade_lock<upgrade_mutex> uglock(std::move(readlock), std::try_to_lock); if (uglock.owns_lock()) { // has upgrade ownership // this shares with other shared ownerships, but not with other upgrade or unique ownerships unique_lock<upgrade_mutex> writelock(std::move(uglock)); // blocks until all shared_locks are unlocked // has unique access now } else // unable to convert to upgrade ownership, still has shared ownership -Howard
On 2/7/2011 3:34 AM, Howard Hinnant wrote:
On Feb 6, 2011, at 7:04 PM, Edd Dawson wrote:
What I'm trying to achieve is to be able to turn a read lock in to a write lock without forfeiting my 'turn'. 1. Is this a realistic thing to expect to be able to achieve? I'm under the impression that this is the purpose of an upgradable locking facility. Perhaps this isn't the case, though?
I'm not positive if upgradable locks fit your use case or not, mainly because I don't know enough about your use case. If *every* thread follows the algorithm you describe, then it probably won't work (except maybe as described below).
I had imagined that I might be able to write the code such that every thread would be running the same code without any try-locking involved. I'm now seeing that this goal is probably unrealistic.
The way the upgrade_lock is meant to work is that a bunch of threads are able to obtain a shared_lock, and at the same time *one* thread obtains an upgrade_lock, which shares ownership with the other threads holding a shared_lock. Then if and when the thread with the upgrade_lock wants unique ownership, then he converts the upgrade_lock to a unique_lock. This operation blocks until all of the threads with the shared_locks give up their ownership. And then the conversion from upgrade to unique completes.
This is the root of my problem. It's not at all what I imagined upgrade_lock would be for. Entirely my fault for making such a big and silly assumption. But as a side comment, IMVHO the Boost.Threads documentation would benefit massively from an analogue to your web page, or even some updated examples.
A compromise solution (which boost doesn't support, but http://home.roadrunner.com/~hinnant/mutexes/locking.html does), is for a bunch of threads to hold shared_locks, and they can *all* /try/ to convert their shared_locks to either upgrade_locks or unique_locks. [...]
Bringing this back to your problem, upgradeable locks will only work if there are some threads which need read access and don't ever want to upgrade to write access, or can at least choose to do something else if a try-conversion fails. A thread with an upgrade_lock can share threads holding shared_locks. But a thread with an upgrade_lock can not share with another thread needing an upgrade_lock.
Right. I think I'm just going to abandon this idea of holding on to my turn if I need to write, now that I know the API wasn't designed for that in the first place! So I sincerely hope I'm correct in saying that if each thread does the following, I should be ok from a correctness point of view at the very least: T &thread_local::data_for_current_thread() { // scope for lock lifetime on shared_mutex, m. { shared_lock<shared_mutex> readlock(m); iterator f = tlcache.find(current_thread_id); if (f != tlcache.end()) return f->second; // else, we need to write } unique_lock<shared_mutex> writelock(m); return tlcache[current_thread_id] = T(); } Thanks very much Howard for all the effort you've put in to providing sample code and generally making all this clear to me! Kind regards, Edd
participants (3)
-
Edd Dawson -
Howard Hinnant -
Peter Dimov