Hi Howard, thank you for your code - I'll try it out. How about add your implementation to boost-1.35.0? best regards, Oliver
Here's the reference implementation for N2447:
// Copyright Howard Hinnant 2007. Distributed under the Boost // Software License, Version 1.0. (see http://www.boost.org/LICENSE_1_0.txt)
// returns index of failed lock or -1 on success template <class L1, class L2> int try_lock(L1& l1, L2& l2) { unique_lock<L1> u(l1, try_to_lock); if (u.owns_lock()) { if (l2.try_lock()) { u.release(); return -1; } return 1; } return 0; }
template <class L1, class L2, class ...L3> int try_lock(L1& l1, L2& l2, L3& l3...) { unsigned r = 0; unique_lock<L1> u(l1, try_to_lock); if (u.owns_lock()) { r = try_lock(l2, l3...); if (r == -1) u.release(); else ++r; } return r; }
template <class L1, class L2> void lock(L1& l1, L2& l2) { while (true) { { unique_lock<L1> __u1(l1); if (l2.try_lock()) { __u1.release(); break; } } std::this_thread::yield(); { unique_lock<L2> __u2(l2); if (l1.try_lock()) { __u2.release(); break; } } std::this_thread::yield(); } }
template <class L1, class L2, class ...L3> void __lock_first(int __i, L1& l1, L2& l2, L3& l3...) { while (true) { switch (__i) { case 0: { unique_lock<L1> __u1(l1); __i = try_lock(l2, l3...); if (__i == -1) { __u1.release(); return; } } ++__i; std::this_thread::yield(); break; case 1: { unique_lock<L2> __u2(l2); __i = try_lock(l3..., l1); if (__i == -1) { __u2.release(); return; } } if (__i == sizeof...(L3)) __i = 0; else __i += 2; std::this_thread::yield(); break; default: __lock_first(__i - 2, l3..., l1, l2); return; } } }
template <class L1, class L2, class ...L3> inline void lock(L1& l1, L2& l2, L3& l3...) { __lock_first(0, l1, l2, l3...); }
Notes:
1. It doesn't require Lock::mutex().
2. It is *much* faster than the lock-in-order algorithm.
3. The yields are absolutely necessary to get the high performance mentioned in the previous note.
4. I've beat the heck out of this code (with extremely high contention tests). Live-lock just doesn't happen. Neither does thread starvation. The above code is very "fair".
5. Lock-in-order can result in thread starvation (experimentally determined under high contention tests).
6. These algorithms have the strong exception safety guarantee for a throwing lock() or try_lock(). If one of these throws, nothing is locked. unlock() must not throw.
7. Anthony's previous post:
A better version of try-and-back-off is to lock the first mutex unconditionally, and then try to lock the others in turn. If a lock fails, then unlock ALL the mutexes and start again, but this time with a blocking lock on the failed mutex. This means that you're waiting for the mutex that you couldn't get last time, but without holding any others, so you won't deadlock with another thread.
is a good description of the above algorithms.
8. The above algorithms can painstakenly be converted to not use variadic templates for a fixed number of locks (I've done up to 4 before the hair loss became too great ;-)).
-Howard
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost