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

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2008-02-09 14:02:43

On Feb 8, 2008, at 6:19 PM, Phil Endecott wrote:

> If you can share the code, I'll see how it performs on my Linux  
> systems.

Thanks Phil!  Sorry for the delay.  I wanted to update my test to use  
the latest std::syntax and rerun them again.  First, here's the code:

#include <date_time>
#include <mutex>
#include <thread>
#include <iostream>

typedef std::mutex Mutex;
typedef std::unique_lock<Mutex> Lock;

Mutex cout_mutex;

unsigned random_gen(unsigned& random_next)
{
     random_next = random_next * 1103515245 + 12345;
     return (random_next >> 16) & 0x7FFF;
}

struct Chopstick
{
     Chopstick() : random_next_(1) {}
     Mutex mut_;
     unsigned random_next_;
};

unsigned eat(unsigned i)
{
     while (i)
         --i;
     return i;
}

unsigned eater(int id, Chopstick& left, Chopstick& right)
{
     {
     std::lock_guard<Mutex> _(cout_mutex);
     std::cout << "Thread " << id << " starting\n";
     }
     unsigned i = 10000000;
     unsigned u = 0;
     while (--i)
     {
         Lock l(left.mut_, std::defer_lock);
         Lock r(right.mut_, std::defer_lock);
         std::lock(l, r);
         u += eat(random_gen(left.random_next_) +  
random_gen(right.random_next_));
     }
     {
     std::lock_guard<Mutex> _(cout_mutex);
     std::cout << "Thread " << id << " ending\n";
     }
     return u;
}

int main()
{
     std::system_time t1 = std::get_system_time();
     Chopstick A, B, C, D, E;
     std::thread T1(eater, 1, std::ref(A), std::ref(B));
     std::thread T2(eater, 2, std::ref(B), std::ref(C));
     std::thread T3(eater, 3, std::ref(C), std::ref(D));
     std::thread T4(eater, 4, std::ref(D), std::ref(E));
     std::thread T5(eater, 5, std::ref(E), std::ref(A));
     T1.join();
     T2.join();
     T3.join();
     T4.join();
     T5.join();
     std::system_time t2 = std::get_system_time();
     std::cout << " time = " << (t2-t1).count() / 1.e9 << '\n';
}

If anyone sees any glaring problems with the test, please let me know,  
thanks.

Now for results just now run.

Machine:  iMac 2.16 GHz Intel Core 2 Duo, OS X 10.5.1.

Lock in order:

template <class L1, class L2>
void
lock(L1& l1, L2& l2)
{
     if (l1.mutex() < l2.mutex())
     {
         unique_lock<L1> u1(l1);
         unique_lock<L2> u2(l2);
         u1.release();
         u2.release();
     }
     else
     {
         unique_lock<L2> u2(l2);
         unique_lock<L1> u1(l1);
         u1.release();
         u2.release();
     }
}

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 1 ending
Thread 2 ending
Thread 3 ending
Thread 5 ending
Thread 4 ending
  time = 62.0437

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 1 ending
Thread 2 ending
Thread 3 ending
Thread 5 ending
Thread 4 ending
  time = 145.683

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 1 ending
Thread 2 ending
Thread 3 ending
Thread 5 ending
Thread 4 ending
  time = 157.347

Interesting side note:  During the first run my disk backup utility  
kicked in.  This extra competition for resources actually made the  
test case run faster!

Try/backoff/without yield

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();
     }
}

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 4 ending
Thread 5 ending
Thread 1 ending
Thread 2 ending
Thread 3 ending
  time = 32.3726

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 5 ending
Thread 4 ending
Thread 1 ending
Thread 3 ending
Thread 2 ending
  time = 29.4687

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 5 ending
Thread 1 ending
Thread 4 ending
Thread 3 ending
Thread 2 ending
  time = 56.226

I have no explanation for the longer time in the third run.

Try/backoff/yield

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();
     }
}

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 4 ending
Thread 5 ending
Thread 1 ending
Thread 3 ending
Thread 2 ending
  time = 11.216

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 4 ending
Thread 5 ending
Thread 1 ending
Thread 3 ending
Thread 2 ending
  time = 10.6229

$./a.out
Thread 1 starting
Thread 2 starting
Thread 3 starting
Thread 4 starting
Thread 5 starting
Thread 4 ending
Thread 5 ending
Thread 1 ending
Thread 3 ending
Thread 2 ending
  time = 11.3284

-Howard