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.
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,2,2,2,2,1,1, or any other possible combination.
You will receive, via STDIN, function parameter, or closest alternative, a list of strings. Each string will be in the format
-b. Every one of this strings represents the locking(
-) of a resource by the thread. Between every thread will be a
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
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:
are all valid outputs, but anything clearly defined as truthy/falsy will be accepted.
+a -a --- +a -a
+a +b -b -a --- +b +a -a -b
Deadlock when trying to acquire
b,a respectively for threads
+a +b -a -b --- +a +b -b -a
+a +b -b -a --- +b +c -c -b --- +c +a -a -c
Deadlock in threads 1,2,3 when trying to acquire
Deadlock in threads 1,2,3 when trying to aquire
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.
Since it's very very sad when you find deadlock situations when writing a program, there is a -8 byte bonus to answers outputting
:) as truthy/falsy respectively.