Re: [boost] [thread] best practice to lock multiple mutexes

From: Kowalke Oliver (QD IT PA AS) (Oliver.Kowalke_at_[hidden])
Date: 2008-02-04 06:32:34

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
>