2

Suppose you have a piece of code that is run by multiple threads. Now further suppose that each of these threads wants to lock the same set of mutexes, say 5, but not in a specific order:

Thread 1: mutex1, mutex2, mutex3, mutex4, mutex5

Thread 1: mutex3, mutex2, mutex4, mutex4, mutex1

Now how would you avoid dead- and livelocks if you were to implement a function that takes these 5 mutexes and tries to lock them?

Since deadlocks shall be avoided a simple list of locking statements is out of question. Now what I thought of was something like (pseudo-code):

while(true) {
  if(!lock(m1)) { continue; }
  if(!lock(m2)) { unlock(m1); continue; }
  ...
  if(!lock(m5)) { unlock(m1);...;unlock(m4); continue; }
  break;
}

The problem with this approach is that it will certainly lead to a livelock and consume much cpu power.

So the only solution I came up with is to equip every thread with a priority number and use this number to specify the (increasing) sleeping time at the beginning of the loop:

sleepCounter = 0;
while(true) {
  sleep(sleepCounter);
  sleepCounter += threadPriorityNumber
  // aforementioned code

What do you think about this solution? Is it a suitable approach? Which alternatives do I have? Is there any literature concerning this problem in the scientific world?

Bastian
  • 4,638
  • 6
  • 36
  • 55
  • as apparently every thread has to lock all 5 mutexes I'd just take a 6th they have to lock before locking all others. That 6th is unlocked when all 5 mutexes are unlocked again. – Theolodis May 15 '14 at 14:41
  • 4
    **but not in a specific order** Removing this would fix it. If you always lock the mutexes in a specific order (say, always lock lower-numbered mutexes first) you would solve it. Also, having a thread lock the same mutex twice (your second example locks mutex4 twice) is problematic and indicates you might benefit from some redesign. – cnicutar May 15 '14 at 14:41
  • 1
    @cnicutar I guess this is an assignment... – Theolodis May 15 '14 at 14:43
  • It is not an assignment, but University related. @cnicutar I cannot remove this constraint because the locking function shall be used like a library function so that I do not have the ability to predict what the users are going to do. – Bastian May 15 '14 at 15:06
  • Is there anything stopping you from sorting the mutexes? – Matthew G. May 15 '14 at 15:11
  • 1
    Is this a real problem, or something theoretical? If you have an application or feature you are building, you will probably be better served choosing a more robust concurrency model, using threading primitives to build that model. This kind of complex mutex sharing is rarely a good idea. – Ben May 15 '14 at 15:19
  • Do you HAVE to use mutex-locks, or can you replace them with a state-machine inside one lock that the threads call into with their locking requirements and are only allowed to proceed when they are all satisifed? Sleep/yield loops are wasteful of CPU, memory bandwidth and add latency. – Martin James May 15 '14 at 15:22
  • @MatthewG. No, would you sort them by their addresses? – Bastian May 15 '14 at 15:45
  • @Ben I am actually building some higher level sync. mechanism that is translated to mutexes. But the mentioned situation can occur there. – Bastian May 15 '14 at 15:46
  • 1
    @Bastian sorting by address will give a total order for acquisition and provide deadlock freedom; livelock is more difficult but exponential back off would likely suffice in non-pathological cases. – Matthew G. May 15 '14 at 15:51
  • @MatthewG. Exponential backoff seems to be a good idea. But the calculation of a random number in [0, 2^i-1] seems to be computationally intensive, doesn't it? – Bastian May 15 '14 at 16:05
  • 1
    Hah. Much cheaper than sorting the locks; also, exponential backoff doesn't have to be accurately random. You could always just sample the timestamp counter from the CPU () – Matthew G. May 15 '14 at 16:46
  • So you suggest busy waiting, but with exponential backoff. This approach seems to be the best so far. Maybe I can even some scientific research on that. Thank you! – Bastian May 15 '14 at 18:08
  • I have found that only having a single lock active in a thread at any one time has avoided any lock problems, dead or alive. – user3629249 May 20 '14 at 07:53

0 Answers0