18
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I am just assuming this, but it would be nice to clarify that the actions of each thread (starting from top of the thread) are run parallely and correspond to the same system time \$\endgroup\$ – Optimizer May 23 '15 at 20:07
  • 1
    \$\begingroup\$ The actions are run concurrently, but the time in which every action is run can't be assumed. It could occur that the threads are actually run strictly one after the other or completely interleaved. It could be that the first half of thread 1 is run, then thread 2 is run entirely, then thread 1 runs it's second half. And so on. I've updated the question to clarify that. \$\endgroup\$ – rorlork May 23 '15 at 20:10
  • 1
    \$\begingroup\$ Ah okay, so the task is to figure out that given any possible combination of thread run times, whether a deadlock is possible. \$\endgroup\$ – Optimizer May 23 '15 at 20:15
  • \$\begingroup\$ Yes, sorry, I didn't think that could leave doubts. Actually in the last example this is demonstrated since thread 2 doesn't try to use resource d until later. \$\endgroup\$ – rorlork May 23 '15 at 20:18
  • 1
    \$\begingroup\$ @rcrmn are you sure :) shouldn't be for false and :( for true? \$\endgroup\$ – Tyilo May 23 '15 at 23:37
4
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ This answers false to pastebin.com/V5MVgNgS \$\endgroup\$ – Tyilo May 24 '15 at 2:03
  • \$\begingroup\$ @Tyilo It outputs True for me; how exactly are you running it? \$\endgroup\$ – KSab May 24 '15 at 3:39
  • \$\begingroup\$ oh it was only reading one line for me. How are you supposed to run it? \$\endgroup\$ – Tyilo May 24 '15 at 12:07
  • \$\begingroup\$ @Tyilo I changed the format to be a function which takes a multiline string as input \$\endgroup\$ – KSab May 24 '15 at 21:09
5
\$\begingroup\$

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':)'
\$\endgroup\$
  • 1
    \$\begingroup\$ Use ; to combine lines that are indented to save characters. Likewise, make your statements one liners. \$\endgroup\$ – isaacg May 23 '15 at 22:53
  • \$\begingroup\$ @isaacg and ace, Thanks! I think I improved it as much as I could using your tips. \$\endgroup\$ – Tyilo May 23 '15 at 23:09
  • \$\begingroup\$ BTW if you don't mind piping the input from a file (or pressing Ctrl+D twice) then you can do for r in sys.stdin instead of for r in sys.stdin.readlines() \$\endgroup\$ – user12205 May 23 '15 at 23:39
  • \$\begingroup\$ @ace I don't see any different behavior between using just sys.stdin or sys.stdin.readlines(), so I have changed it, thanks again. \$\endgroup\$ – Tyilo May 23 '15 at 23:51
  • \$\begingroup\$ You can remove the spaces between print and ':)' \$\endgroup\$ – user12205 May 23 '15 at 23:52

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.