18
2
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.
Output false
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.
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 – Optimizer – 2015-05-23T20:07:38.167
1The 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. – rorlork – 2015-05-23T20:10:26.737
1Ah okay, so the task is to figure out that given any possible combination of thread run times, whether a deadlock is possible. – Optimizer – 2015-05-23T20:15:03.117
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. – rorlork – 2015-05-23T20:18:25.710Can locks/unlocks interleave in the input? E.g.
+a +b -a -b
. Your examples never contain this. – orlp – 2015-05-23T20:49:25.483Yes, they could. Sorry, I forgot to include one that had this. I'll add one now. – rorlork – 2015-05-23T20:55:04.877
1@rcrmn are you sure
:)
shouldn't be for false and:(
for true? – Tyilo – 2015-05-23T23:37:32.993Yes, you are right! fixed – rorlork – 2015-05-23T23:38:20.633