1

If I have empirical data on what locks were acquired in what orders by which thread and line of code, how can I then use that data to determine if locking order has deadlock potential?

l = lock u = unlock

e.g.: these are in conflict and might deadlock

thread 1: l1, l2, u2, u1
thread 2: l2, l1, u1, u2

Or even this single thread is in conflict with itself since I don't really know that the second half of the sequence wouldn't be run on a separate thread in a different use case.

thread 1: l1, l2, u2, u1, l2, l1, u1, u2

Is there a suitable algorithm that can be used to determine that from the data?

Note I am asking not what to find (different lock aquisition orders), but what algorithm or data structure to use to find them given a set of empirical data.

idij
  • 750
  • 9
  • 19

2 Answers2

2

You need to build a lock ordering graph, and check for cycles.

Whenever a lock is acquired while another is held, add an edge from the held lock to the acquired lock.

Your example:

thread A: lock 1, lock 2, unlock 2, unlock 1
thread B: lock 2, lock 1, unlock 1, unlock 2

Because thread A locks 2 while holding 1, and thread B locks 1 while holding 2, you have these edges:

1 -> 2
2 -> 1

Making this graph:

Graph rendering

Which has cycles, so there are potential deadlocks.

See: directed cycle detection algorithm

Caveat

Technically, cycles that are made entirely out of edges that all come from one thread can't cause deadlocks (since you're probably using re-entrant locks). So those cycles aren't really deadlocks... they're time bombs. Some apparently innocent change to threading in the future will set them off, turning them into a deadlock, and ruin your day.

You can refine this algorithm to avoid that case, but I'm not going to bother because what you'd be ignoring is also bad.

Community
  • 1
  • 1
Craig Gidney
  • 17,763
  • 5
  • 68
  • 136
1

If I understand your problem correctly, you have just run into the classic lock-ordering deadlock problem.

A program will be free of lock-ordering deadlocks if all threads acquire the locks they need in a fixed global order. (from Java Concurrency in Practice)

If you detect in your data that different threads acquired the same locks in different order, then your program can potentially suffer a lock-ordering deadlock with unlucky timing. So that's the pattern to look for in your data; it's that simple.

UPDATE: Here is an algorithm how I would do it. I don't know whether it has a name.

For each lock event li from the left to right:

  • find its corresponding unlock event (or use the end of the sequence if it is never released)

  • add all enclosed lock events as pairs (i,j) where j is an enclosed lock event

  • then go to the next lock event and repeat.

An example follows.

enter image description here

For example, for the first event lA it means scanning through the sequence to find the first occurrence of uA. This gives us the subsequence: lA lB uA. For each lock event in this subsequence add a pair into a set. In this case, save (A,B) in the set. (If we had another lock event in this subsequence, say
lA lB lD uA, we would add the pair (A,D) as well to the set.)

Now let's prepare the next subsequence. For the next lock event in the orgininal sequence, that is lB, find the first uB following it. This gives the subsequence is lB uA lC uB and the only pair that needs to be saved in the set is (B,C).

For the third subsequence, for the lC event there is no pair to be saved as there is no lock event in the lC uB subsequence.

The set of thread 1 contains the pairs (A,B) and (B,C). I would simple create another set containing the reversed pairs (B,A) and (C,B); let's call it the forbidden set.

I would repeat this procedure for thread 2, prepare the container with the pairs telling which locks were acquired in what order by thread 2. Now, if the set intersection of this set and the forbidden set of thread 1 is not empty, then we have detected a potential lock-ordering deadlock.

Hope this helps.

Ali
  • 56,466
  • 29
  • 168
  • 265
  • Well, I haven't run into it, I want to know if I have the potential to run into it. My question was how to look for the ordering with an algorithm. I can see it with my eyes, but am unsure how to process the data. – idij Jun 25 '14 at 15:41
  • @idij It is not quite clear what you are asking. Do you want me to write some pseudo-code to find patterns where locks were acquired in different global order? – Ali Jun 25 '14 at 15:43
  • Well, the name of a suitable algorithm I can read up on would also be suitable. Apologies if the question was unclear, but I do not want to ask what pattern to look for (different ordering of lock acquisition), but *how* to look for it. – idij Jun 25 '14 at 15:49
  • 1
    @idij You could probably solve it with an [order-maintaince](http://en.wikipedia.org/wiki/Order-maintenance_problem) data structure as well. However, I think what I write in my answer is simple and efficient enough. It is also easy to figure out where exactly can deadlocks happen. With an order-maintenance data structure, it would not be that easy. – Ali Jun 25 '14 at 17:23
  • @idij You can also regard my answer as a recipe to get the directed edges in Strilac's answer. (Well, sort of.) – Ali Jun 25 '14 at 20:54
  • I've picked Strilac's answer (updated following your feedback) because I can see more clearly how I can apply it, though I will use elements from your answer also. I have learned a lot from your answer and comments and wanted to acknowledge that. Very much appreciated. Thank you. – idij Jun 26 '14 at 20:19
  • @idij Okay. Yes, the true answer is somewhere in between, the mix of the two as his answer doesn't tell you how to find the edges. In any case, I am glad my answer was helpful. – Ali Jun 26 '14 at 22:17