6
\$\begingroup\$

I messed a little bit with pthreads and needed an alternative to the C++11 function std::lock (2 args are enough), and this is what I came up with:

void lock(pthread_mutex_t* m1, pthread_mutex_t* m2) {
  while(1) {
    pthread_mutex_lock(m1);

    if(pthread_mutex_trylock(m2) == 0) { // if lock succesfull
      break;
    }
    pthread_mutex_unlock(m1);
    sched_yield();
  }
}

It works fine so far. I am just not sure whether I missed some potential deadlock.

In addition, I am interested if I should do some more error checking. I am especially not that firm with C-style error checking.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Downvoter please explain! \$\endgroup\$
    – inf
    Jul 17 '15 at 15:00
7
\$\begingroup\$

It does not look like your code will deadlock.
That said, I am not very keen on the spin lock like attempt, as I can see situations where it may not be great in efficiency.

It (std::lock) guarantees that no matter what order you specify the locks in the parameter list you will not fall into a deadlock situation.

A common technique (simple enough you could use (but the standard does not specify whether this technique is used by std::lock)) is to make sure the locks are ordered in some way. This basically means that the order you lock the mutexes in must be consistent (thus independent of the order they are in the parameter list).

  • The actual order should be defined in terms of some immutable property of the underlying mutex (such as its address).
  • This also means that if a lock in the list is already locked it must be released so that the locks are acquired in the correct order (Note: not all lockables can safely call try_lock() so you can't always determine if you should unlock).

Example of deadlock occurring when locks are not acquired in order:

 Time:     Thread-1          Thread-2
           lock(g2, g1)      lock(g1, g2)


   0       lock(&g2)
   
   1                         lock(&g1)

   2       lock(&g1) // Can never succeed
   
   3                         lock(&g2) // Can never succeed

Metal deadlock.

Thread 1 is now waiting for g1 (held by thread 2), while thread 2 is waiting for g2 (held by thread 1).

\$\endgroup\$
10
  • \$\begingroup\$ Ok, thanks for the hints. Starting with your example, this is of course something I didn't think of as I didn't know that std::lock handles this, I supposed that it acts like a normal mutex::lock which gets double locked. While I can see that a proper ordering would fix the problem in the upper example, would the ordering still matter if we'd assume that the mutexs are both unlocked? I can't come up with a test which would deadlock in that case. \$\endgroup\$
    – inf
    May 21 '12 at 21:40
  • \$\begingroup\$ To be more precise - assuming that a thread doesn't try to lock a mutex again which it already owns. \$\endgroup\$
    – inf
    May 22 '12 at 4:30
  • \$\begingroup\$ @bamboon: If it already owns a lock. Then it must be release. If the locks are not acquired in the correct order you run the risk of deadlock. This is why std::lock imposes a strict ordering on lock acquisition. \$\endgroup\$ Jun 14 '12 at 15:43
  • 1
    \$\begingroup\$ I know almost 10 years have passed since this was written, but I believe this answer to be incorrect. Whether the naïve "try-and-back-off" strategy to lock multiple mutexes is good in terms of performance is debateable, but it is correct and does not generate deadlocks. It can theoretically generate live-locks and eat a lot of CPU. See: justsoftwaresolutions.co.uk/threading/… \$\endgroup\$
    – gd1
    Apr 3 at 17:41
  • 1
    \$\begingroup\$ @gd1 OK cleaned up the lanaguage a bit. \$\endgroup\$ Apr 5 at 20:43
5
+250
\$\begingroup\$

If you swap pointers to the mutexes after a failed iteration, you can get better performance than either your original code, or the ordered solution shown in the currently accepted answer.

void lock(pthread_mutex_t* m1, pthread_mutex_t* m2) {
  while(1) {
    pthread_mutex_lock(m1);

    if(pthread_mutex_trylock(m2) == 0) { // if lock succesfull
      break;
    }
    pthread_mutex_unlock(m1);
    sched_yield();
    pthread_mutex_t* tmp = m1;
    m1 = m2;
    m2 = tmp;
  }
}

Without swapping, the code works, but burns cpu cycles in highly contested situations.

The ordering solution works, doesn't burn cpu cycles, but can sometimes block on a mutex while holding the lock on another mutex. This can reduce parallel execution on a multicore platform.

By inserting the swap you eliminate both of those problems:

  1. You never hold a locked mutex while blocking on another.
  2. You don't "spin" because on all iterations but the first, you try to lock a mutex that just failed a try_lock. Thus you are likely to block (without holding a locked mutex), allowing other threads to run with both mutexes available.

I've published a paper that goes into more detail, and supplies C++ code demonstrating these algorithms.

The paper terms the original solution "Persistent". The ordered solution is called "Ordered". And with the swapping, you get "Smart & Polite".

\$\endgroup\$
5
  • \$\begingroup\$ Why do you yield at all? As you described, you unlock all and then block on locking the failed lock, so I see no need. An additional thought, why not start with the locks ordered? That should boost the chance of the first lock blocking if any do so for normal workloads. \$\endgroup\$ Apr 29 at 13:23
  • 1
    \$\begingroup\$ The paper measures the effect of the yield by testing both with and without it. The algorithm with yield has a slight but consistent performance advantage, at least on the platform, and test cases I tested. It is surmised that the yield dampens a small amount of live-lock that otherwise arises. \$\endgroup\$ Apr 29 at 13:45
  • 1
    \$\begingroup\$ I have not tested an algorithm that orders and tries-backsoff. Although the paper does compare each algorithm to a theoretical highest performance possible. The Smart & Polite algorithm matches the theoretical minimum until the test case starts requesting more CPU's than the hardware has to offer. The ordered algorithm does not come close to this ideal. \$\endgroup\$ Apr 29 at 13:49
  • \$\begingroup\$ I wonder if there would be a significant effect if the locks were passed to your algorithm already pre-ordered, instead of pre-randomised. \$\endgroup\$ Apr 30 at 12:39
  • \$\begingroup\$ The test code is in the appendix of the paper. You could try it out. Although for test results that are already at the theoretical best, I would not expect any improvement. \$\endgroup\$ Apr 30 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.