Den Deadlock finden

18

Den Deadlock finden

Beim Programmieren einer Multithreading-Anwendung muss sorgfältig darauf geachtet werden, dass die verschiedenen Threads beim Zugriff auf gemeinsam genutzte Ressourcen nicht blockieren. Ein Deadlock tritt auf, wenn ein Thread versucht, auf eine Ressource zuzugreifen, die in einem anderen Thread gesperrt ist, während der andere Thread versucht, auf eine von der ersten gesperrte Ressource zuzugreifen. Dies ist der einfache Fall, kann jedoch mit längeren Ressourcenketten komplexer werden.

Die Herausforderung

Sie sollten ein Programm oder eine Funktion schreiben, die eine mögliche Deadlock-Situation in einer Liste der Ressourcen erkennt, auf die von jedem Thread zugegriffen wird. Das ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes.

Jeder Thread wird zur gleichen Zeit gestartet, kann danach jedoch mit jeder Kombination von Interleaving ausgeführt werden. Bei 2 Fäden mit 4 Aktionen je könnte es als ausgeführt werden (wobei jede Zahl eine Aktion durch das Gewinde mit dieser ID genommen ist) 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,1oder irgendeine andere mögliche Kombination.

Eingang

Sie erhalten über STDIN, Funktionsparameter oder die nächstgelegene Alternative eine Liste von Zeichenfolgen. Jede Zeichenfolge hat das Format +a -b. Jede dieser Zeichenfolgen repräsentiert das Sperren ( +) / Entsperren ( -) einer Ressource durch den Thread. Zwischen jedem Thread befindet sich ein ---Trennzeichen. Es wird garantiert, dass ein Thread nicht versucht, eine bereits gesperrte Ressource zu sperren, und dass alle Threads alle gesperrten Ressourcen explizit entsperren, bevor sie beendet werden. Das Folgende ist ein Beispiel, um zu demonstrieren:

+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

Ausgabe

Die Ausgabe ist falsch, wenn die Eingabe keine Deadlock-Möglichkeit enthält, und wahr, wenn sie eine mögliche Deadlock-Situation enthält. Beispielsweise:

  • true
  • false
  • 1
  • 0

sind alle gültigen Ausgaben, aber alles, was klar als wahr / falsch definiert ist, wird akzeptiert.

Beispiele

+a
-a
---
+a
-a

Ausgabe: false


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

Ausgabe true

Deadlock beim Versuch, b,ajeweils für Threads zu erfassen1,2


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

Ausgabe false


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

Ausgabe: true

Deadlock in den Threads 1, 2, 3 beim Versuch, b,c,ajeweils zu erfassen .


http://pastebin.com/vMYRZxtW

Ausgabe false


http://pastebin.com/V5MVgNgS

Ausgabe true

Deadlock in den Threads 1, 2, 3 beim Versuch, b,d,ajeweils zu erwerben .


Natürlich könnte dies viel komplexer werden, mit mehr Threads, mehr Ressourcen für jeden einzelnen und so weiter, aber ich glaube, diese Tests decken die Grundlagen ab.

Bonus

Da es sehr sehr traurig ist , wenn man Deadlocksituationen finden , wenn ein Programm zu schreiben, gibt es einen -8 Byte Bonus Antworten ausgibt :(und :)als truthy / falsy sind.

rorlork
quelle
Ich gehe nur davon aus, aber es wäre schön zu klären, dass die Aktionen jedes Threads (beginnend am oberen Ende des Threads) parallel ausgeführt werden und der gleichen Systemzeit entsprechen
Optimizer
1
Die Aktionen werden gleichzeitig ausgeführt, es kann jedoch nicht davon ausgegangen werden, in welcher Zeit jede Aktion ausgeführt wird. Es kann vorkommen, dass die Threads tatsächlich streng nacheinander oder vollständig verschachtelt ablaufen. Es kann sein, dass die erste Hälfte von Thread 1 ausgeführt wird, dann wird Thread 2 vollständig ausgeführt, und Thread 1 führt die zweite Hälfte aus. Und so weiter. Ich habe die Frage aktualisiert, um das zu klären.
rorlork
1
Ah okay, also die Aufgabe ist herauszufinden, ob bei einer möglichen Kombination von Thread-Laufzeiten ein Deadlock möglich ist.
Optimierer
Ja, sorry, ich hätte nicht gedacht, dass das Zweifel aufkommen lassen könnte. Tatsächlich wird dies im letzten Beispiel demonstriert, da Thread 2 derst später versucht, die Ressource zu verwenden .
rorlork
1
@rcrmn sind Sie sicher, :)dass Sie nicht für falsch und :(für wahr sein sollten?
Tyilo

Antworten:

4

Python 2 - 227

Grundsätzlich ist darauf zu achten, dass es keine "Prioritätsschleifen" gibt. Im zweiten Test hat beispielsweise der erste Thread a(b)Vorrang und der zweite Thread b(a)Vorrang.

Ich habe darüber nachgedacht, dies in Pyth umzuschreiben, da ich denke, dass es mit allen itertools-Operationen gut funktionieren würde, aber das Konvertieren des regulären Ausdrucks wird einige Arbeit in Anspruch nehmen. Daher werde ich dies zunächst veröffentlichen und möglicherweise versuchen, es zu konvertieren und später eine andere Antwort zu veröffentlichen.

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))
KSab
quelle
Diese Antworten falsch pastebin.com/V5MVgNgS
Tyilo
@ Tyilo Es gibt True für mich aus; Wie genau läufst du es?
KSab
oh, es las nur eine Zeile für mich. Wie soll es laufen?
Tyilo
@ Tyilo Ich habe das Format geändert, um eine Funktion zu sein, die eine mehrzeilige Zeichenfolge als Eingabe verwendet
KSab
5

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

Einrückungsstufen:

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':)'
Tyilo
quelle
1
Verwenden Sie ;diese Option , um Zeilen zu kombinieren, die eingerückt sind, um Zeichen zu speichern. Ebenso machen Sie Ihre Aussagen einzeilig.
isaacg
@isaacg und Ass, danke! Ich denke, ich habe es so weit wie möglich verbessert, indem ich Ihre Tipps verwende.
Tyilo
Übrigens, wenn es Ihnen nichts ausmacht, die Eingabe aus einer Datei for r in sys.stdinfor r in sys.stdin.readlines()
weiterzuleiten
@ace Ich sehe kein unterschiedliches Verhalten zwischen der Verwendung von "nur" sys.stdinoder " sys.stdin.readlines(), daher habe ich es geändert. Nochmals vielen Dank."
Tyilo
Sie können die Leerzeichen zwischen printund entfernen':)'
user12205