Finding the Deadlock

Question

Finding the Deadlock

When programming a multithreading application one must take good care to avoid deadlocking the various threads when accessing shared resources. A deadlock occurs when a thread attempts to access a resource that's locked in another thread at the same time that the other thread is trying to access a resource locked by the first. This is the simple case, but it can get more complex with longer resource chains.

The challenge

You should write a program or function that can detect a possible deadlock situation in a list of the resources accessed by each thread. This is code-golf, so shortest answer in bytes wins.

Every thread is started at the same time, but after that they can run at any combination of interleaving. If there are 2 threads with 4 actions each, it could be run as (where each number is an action taken by the thread with that id) 1,1,1,1,2,2,2,2, 2,2,2,2,1,1,1,1, 1,2,1,2,1,2,1,2, 1,1,2,2,2,2,1,1, or any other possible combination.

Input

You will receive, via STDIN, function parameter, or closest alternative, a list of strings. Each string will be in the format +a -b. Every one of this strings represents the locking(+)/unlocking(-) of a resource by the thread. Between every thread will be a --- separator. It is guaranteed that a thread won't try to lock a resource it already has locked, and that all threads will explicitly unlock all the resources they have locked before exiting. Following is an example to demonstrate:

+a    # Lock resource a
+b    # Lock resource b
-a    # Unlock resource a
-b    # Unlock resource b
---   # Thread separator
+b    # Lock resource b
-b    # Unlock resource b

Output

The output shall be falsy if the input doesn't contain any deadlock possibility, and truthy if it contains a possible deadlock situation. For example:

• true
• false
• 1
• 0

are all valid outputs, but anything clearly defined as truthy/falsy will be accepted.

Examples

+a
-a
---
+a
-a

Output: false

---

+a
+b
-b
-a
---
+b
+a
-a
-b

Output true

Deadlock when trying to acquire b,a respectively for threads 1,2

---

+a
+b
-a
-b
---
+a
+b
-b
-a

Output false

---

+a
+b
-b
-a
---
+b
+c
-c
-b
---
+c
+a
-a
-c

Output: true

Deadlock in threads 1,2,3 when trying to acquire b,c,a respectively.

---

http://pastebin.com/vMYRZxtW

Output false

---

http://pastebin.com/V5MVgNgS

Output true

Deadlock in threads 1,2,3 when trying to aquire b,d,a respectively.

---

Of course this could get a lot more complex, with more threads, more resources for each one, and so on, but I believe these tests cover the basics.

Bonus

Since it's very very sad when you find deadlock situations when writing a program, there is a -8 byte bonus to answers outputting :( and :) as truthy/falsy respectively.

Answer 1

Python - 586 539 524 501 485 bytes - 8 = 477

Indentation levels:

1: 1 space
2: 1 tab
3: 1 tab + 1 space
4: 2 tabs

--

import sys
V=set()
t=[[[]]]
for r in sys.stdin:
 r=r.strip()
 if'---'==r:t.append([[]])
 else:v=r[1:];V.add(v);l=t[-1][-1];t[-1].append(l+[v]if'+'==r[0]else filter(lambda x:x!=v,l))
s=lambda l:s(l[1:])+map(lambda x:(l[0],x),l[1:])if 1<len(l)else[]
E=reduce(set.union,map(lambda x:set(sum(map(s,x),[])),t),set())
for v in V:
 k=set();q=[v]
 while 0<len(q):
    u=q.pop(0)
    if u in k:continue
    k.add(u)
    for x,y in E:
     if u==x:
        if y in k:print':(';sys.exit()
        else:q.append(y)
print':)'

Answer 2

Python 2 - 227

Basically makes sure there are no loops of 'precedence'. For example in the second test, the first thread has a a(b) precedence and the second thread has a b(a) precedence.

I was thinking about rewriting this in Pyth as I think it would work well with all the itertools operations, but converting the regex will take some work so for now I'll post this and maybe try to convert it and post another answer later.

from itertools import*
import re
f=lambda t:any(re.search(r"(.)((.)\3)+\1",''.join(p))for i in product(*[[m.group(1)+m.group(2)for m in re.finditer(r"(\w).*(\w).*\2.*\1",e,16)]for e in t.split('---')])for p in permutations(i))