Kürzester Code, der einen Deadlock erzeugt

11

Schreiben Sie den kürzesten Code, um einen Deadlock zu erstellen . Die Codeausführung muss angehalten werden, damit dies nicht funktioniert:

public class DeadlockFail extends Thread{ //Java code
    public static void main(String[]a){
        Thread t = new DeadlockFail();
        t.start();
        t.join();
    }
    //this part is an infinite loop; continues running the loop. 
    public void run(){while(true){}}
}

Es muss nicht sicher sein, dass der Code in einen Deadlock gerät , nur fast sicher (wenn Sie unendlich lange laufen, wird er einen Deadlock verursachen).

Justin
quelle
Zählt es als Deadlock, wenn ich versuche, dieselbe (nicht wiedereintretende) Sperre zweimal von demselben Thread aus zu sperren? (Entschuldigung, ich habe diese Frage im Sandkasten nicht erkannt)
John Dvorak
@JanDvorak Schafft dies eine Situation, in der die Codeausführung angehalten wird, weil ein Thread auf etwas wartet, das er nicht bekommen kann (weil ein anderer es hält und auf das wartet, was der erste Thread hat)? Oder ist es ein Thread? Wenn Sie eine solche Situation mit einem Thread erstellen können, ist dies in Ordnung. Lesen Sie den Wikepedia-Artikel über Deadlock, das erwarte ich.
Justin
2
Code execution must haltIch verstehe nicht Wie ist es ein Deadlock, wenn es anhält? Meinst du, es wird auf etwas warten, anstatt nur wie ein Arschloch zu spinnen?
Cruncher
@ Cruncher Schauen Sie sich das Beispiel an, das nicht funktioniert. Die Codeausführung wird nicht gestoppt, da die Schleife weiter ausgeführt wird. Ja, ich meine eher warten als drehen.
Justin
Wenn Sie also den UI-Thread in Dyalog APL auf sich warten lassen können, bedeutet das, dass es Hoffnung gibt, eine Javascript-Antwort zu erhalten? Obwohl ich vermute, dass diese Art des Denkens nur die Tür zu dieser Antwort öffnen würde: Javascript 6 "wait ()" ... ähm. Nein. Verwandte: Ist es möglich, dass ein Thread Deadlock selbst?
Nathan Cooper

Antworten:

11

Dyalog APL (10)

⎕TSYNC⎕TID

⎕TSYNCLässt den Thread warten, bis der angegebene Thread endet, ⎕TIDgibt den aktuellen Thread an.

Dyalog APL kann jedoch Deadlocks erkennen und reagiert daher sofort mit

DEADLOCK

Der Spaß ist, dass Sie nicht einmal zusätzliche Threads erzeugen müssen, sodass es ausreichend ist, den UI-Thread auf sich selbst warten zu lassen.

Wenn dies ein Betrug ist und tatsächlich neue Threads erforderlich sind, können Sie dies in 27 Zeichen tun:

{∇⎕TSYNC&{⎕TSYNC⎕TID+1}&0}0

F & xwird Fin einem neuen Thread für den Wert ausgeführt xund gibt die Thread-ID zurück. Damit:

  • {⎕TSYNC⎕TID+1}&0 erstellt einen Thread, der mit dem Thread synchronisiert wird, dessen ID eine höhere als seine eigene ist.
  • ⎕TSYNC& Erstellt einen neuen Thread, der mit dem vorherigen Thread synchronisiert wird und dessen ID höher ist als der gerade erstellte Thread (vorausgesetzt, nichts anderes erstellt Threads).
  • verursacht eine Endlosschleife (also erstellen wir so lange Threads, bis ein Deadlock vorliegt).

Dies wird zum Stillstand kommen, sobald der zweite Thread erstellt wird, bevor der erste ausgeführt wird. Dies ist ziemlich bald der Fall:

9:DEADLOCK
Marinus
quelle
Speichern Sie 2 Bytes mit: ⎕TSYNC 0'. ⎕TID` ist 0.
Adám
8

Geh, 42

package main
func main(){<-make(chan int)}

Entschuldigung, Downvoter, dass Sie nicht angegeben haben, wie es funktioniert. Dadurch wird ein anonymer Int-Kanal erstellt und daraus gelesen. Dadurch wird der Hauptthread angehalten, bis ein Wert über den Kanal gesendet wird. Dies geschieht offensichtlich nie, da keine anderen Threads aktiv sind, und führt daher zu einem Deadlock.

Alex Ozer
quelle
2
Wie funktioniert es?
Justin
4

Ruby, 39 Zeichen

T=Thread;t=T.current;T.new{t.join}.join

Die Idee, einen Cross-Join zu verwenden, wurde schamlos aus Johannes Kuhns Java-Antwort gestohlen .

Wir können vier Zeichen (bis 35 ) rasieren, wenn wir den Code auf eine bestimmte Umgebung abstimmen. JRubys Konsolen-IRB ist Single-Threaded:

T=Thread;T.new{T.list[0].join}.join


Dies ist meine vorherige Lösung:

Es ist einfach, einen Thread auf einen Mutex zu kleben:

m=Mutex.new;2.times{Thread.new{m.lock}}

Dies ist jedoch kein richtiger Deadlock, da der zweite Thread technisch nicht auf den ersten Thread wartet. "hold and wait" ist laut Wikipedia eine notwendige Voraussetzung für einen Deadlock. Der erste Thread wartet nicht und der zweite Thread enthält nichts.

Rubin, 97 95 Zeichen

m,n=Mutex.new,Mutex.new
2.times{o,p=(m,n=n,m)
Thread.new{loop{o.synchronize{p.synchronize{}}}}}

Dies ist ein klassischer Deadlock. Zwei Threads konkurrieren um zwei Ressourcen und versuchen es erneut, wenn sie erfolgreich sind. Normalerweise bleiben sie innerhalb einer Sekunde auf meiner Maschine stecken.

Wenn es jedoch in Ordnung ist, unendlich viele Threads zu haben (von denen keiner unendlich viel CPU verbraucht und von denen einige einen Deadlock aufweisen),

Rubin, 87 85 Zeichen

m,n=Mutex.new,Mutex.new
loop{o,p=(m,n=n,m)
Thread.new{o.synchronize{p.synchronize{}}}}

Meinem Test zufolge schlägt es fehl, nachdem die Thread-Anzahl ungefähr 4700 erreicht hat. Hoffentlich schlägt es nicht fehl, bis jeder Thread eine Chance zum Ausführen hatte (also entweder Deadlocking oder Beenden und Freigeben von Speicherplatz für einen neuen). Laut meinem Test sinkt die Thread-Anzahl nach dem Auftreten des Fehlers nicht, was bedeutet, dass während des Tests ein Deadlock aufgetreten ist. Auch IRB starb nach dem Test.

John Dvorak
quelle
Warum brauchst du die zusätzlichen o& pVariablen? Kannst du nicht einfach passen mund nfür den neuen Thread?
Johannes Kuhn
@JohannesKuhn mund nsind global. Beide Threads sehen sie in derselben Reihenfolge. ound psind threadlokal (auf die Schleifeniteration beschränkt). Die Verwendung t[...]würde wahrscheinlich teuer werden, und ich kann keinen besseren Weg sehen, Parameter an den Thread zu übergeben, als über das Schließen. Durch Hinzufügen zusätzlicher Parameter wird newder Code um zwei Zeichen verlängert.
John Dvorak
@ JohannesKuhn Ich hoffe, es macht Ihnen nichts aus, ich habe einige Ihrer Logik ausgeliehen
John Dvorak
Es macht mir nichts aus. Gut gemacht.
Johannes Kuhn
Wenn wir davon ausgehen, dass wir im Haupt-Thread sind, können wir dies auf 32 Zeichen T=Thread;T.new{T.main.join}.join
reduzieren
4

Python, 46

import threading as t
t.Semaphore(0).acquire()

(Selbststillstand)

Sneftel
quelle
1
from threading import* Semaphore(0).acquire()ist um ein Byte kürzer, denke ich
Roman Gräf
@ Roman Ja, es ist kürzer und es funktioniert. tio.run/##K6gsycjPM/r/…
mbomb007
4

Bash + GNU Coreutils, 11 Bytes

mkfifo x;<x

Erstellt ein streunendes FIFO xim aktuellen Verzeichnis (Sie müssen also keine Datei mit diesem Namen haben). FIFOs können wie normale Dateien gelöscht werden, daher sollte es nicht schwierig sein, sie zu löschen.

Ein FIFO hat eine Schreibseite und eine Leseseite; Der Versuch, einen Block zu öffnen, bis ein anderer Prozess den anderen öffnet, scheint absichtlich als Synchronisationsprimitiv konzipiert worden zu sein. Da es hier nur einen Thread gibt, <xbleiben wir stecken , sobald wir versuchen, ihn zu öffnen . (Sie können den Deadlock lösen, indem Sie aus einem anderen Prozess in das betreffende FIFO schreiben.)

Dies ist eine andere Art von Deadlock als bei zwei Ressourcen, und zwei Threads haben jeweils eine und benötigen die andere. In diesem Fall gibt es keine Ressourcen, und der Prozess benötigt eine. Aufgrund der anderen Antworten denke ich, dass dies zählt, aber ich kann verstehen, wie ein Deadlock-Purist die Antwort möglicherweise ablehnen möchte.

Wenn ich darüber nachdenke, kann ich mir tatsächlich drei Deadlock-ähnliche Situationen vorstellen:

  1. Der "traditionelle" Deadlock: Zwei Threads warten jeweils darauf, dass eine Sperre aufgehoben wird, die vom anderen Thread gehalten wird.

  2. Ein einzelner Thread wartet darauf, dass eine Sperre freigegeben wird, hält jedoch die Sperre selbst (und blockiert sich somit selbst, um sie freizugeben).

  3. Ein einzelner Thread wartet darauf, dass ein Synchronisationsprimitiv freigegeben wird, aber das Synchronisationsprimitiv startet in einem natürlich gesperrten Zustand und muss extern entsperrt werden, und dafür wurde nichts programmiert.

Dies ist ein Deadlock vom Typ 3, der sich grundlegend von den beiden anderen unterscheidet: Sie könnten theoretisch ein Programm schreiben, um das betreffende Synchronisationsprimitiv zu entsperren, und es dann ausführen. Wie gesagt, das gleiche gilt für Deadlocks vom Typ 1 und 2, da viele Sprachen ermöglichen es Ihnen , eine Sperre lösen Sie nicht selbst tun (du bist nicht angenommen zu und würde keinen Grund , dies zu tun , wenn Sie einen Grund hatte, benutze zuerst die Schlösser, aber es funktioniert…). Es lohnt sich auch, ein Programm wiemkfifo x;<x;echo test>x;; Dieses Programm ist das Gegenteil eines Deadlocks vom Typ 2 (es versucht, beide Enden des FIFO zu öffnen, aber es kann ein Ende erst öffnen, nachdem es das andere Ende geöffnet hat), aber es wurde aus diesem Ende durch Hinzufügen von Extra erstellt Code, der nie nach diesem läuft! Ich denke, das Problem ist, dass es von der Absicht hinter der Verwendung des Schlosses abhängt, ob ein Schloss blockiert ist oder nicht. Daher ist es schwierig, objektiv zu definieren (insbesondere in einem Fall wie diesem, in dem der einzige Zweck des Schlosses darin besteht, absichtlich einen Deadlock zu erzeugen ).


quelle
2

C #, 100

class C{static C(){var t=new System.Threading.Thread(Main);t.Start();t.Join();}static void Main(){}}

Siehe: Der No-Lock-Deadlock

Johnbot
quelle
1
Kannst du das Zeug nicht von static Cnach verschieben Main?
Roman Gräf
2

Bash mit Glibc, 6 Bytes

Es tut mir leid, einen alten Thread wiederzubeleben, aber ich konnte nicht widerstehen.

Als Wurzel:

pldd 1

Vom Mann pldd :

BUGS
Seit glibc 2.19 ist pldd kaputt: es hängt nur, wenn es ausgeführt wird. Es ist unklar, ob es jemals behoben wird.

Jasonwilkes
quelle
Es ist kein Problem, auf einem alten Profil zu antworten, solange das Original nicht zeitkritisch war.
Ad-hoc-Garf-Jäger
2

Java, 191

class B extends Thread{public static void main(String[]a)throws Exception{new B().join();}Thread d;B(){d=Thread.currentThread();start();}public void run(){try{d.join();}catch(Exception e){}}}

Ungolfed:

class B extends Thread {
    Thread d;
    public static void main(String[] args) throws Exception {
        new B().join();
    }
    B() { // constructor
        d = Thread.currentThread();
        start();
    }
    public void run() {
        try {
            d.join();
        } catch (Exception e) {
        }
    }
}

Startet einen neuen Thread und joindarauf (warten Sie, bis dieser Thread beendet ist), während der neue Thread dasselbe mit dem ursprünglichen Thread tut.

Johannes Kuhn
quelle
Kannst du es kürzer machen, indem du Errorstatt wirfst und fängst Exception?
mbomb007
Nee. Thread.join()wirft eine InteruptedException, die keine Unterklasse von ist Error.
Johannes Kuhn
2

Tcl, 76

package r Thread;thread::send [thread::create] "thread::send [thread::id] a"

Sackgasse.

Dadurch wird ein neuer Thread erstellt und der andere Thread wird angewiesen, meinem Thread eine Nachricht zu senden (Skript zum Ausführen).

Das Senden einer Nachricht an einen anderen Thread wird jedoch normalerweise blockiert, bis das Skript ausgeführt wurde. Und während es blockiert, werden keine Nachrichten verarbeitet, sodass beide Threads darauf warten, dass der andere ihre Nachricht verarbeitet.

Johannes Kuhn
quelle
wie funktioniert das?
John Dvorak
thread::sendStellt ein Skript in die Warteschlange, das in einem anderen Thread ausgeführt werden soll, und wartet, bis es abgeschlossen ist. Am Ende warten also Thread 1 auf Thread 2 und Thread 2 auf Thread 1.
Johannes Kuhn
1

Alternative Java mit Monitor-Missbrauch (248 Charas)

class A{public static void main(String args[]) throws Exception{final String a="",b="";new Thread(new Runnable(){public void run(){try {synchronized(b){b.wait();}} catch (Exception e) {}a.notify();}}).start();synchronized(a){a.wait();}b.notify();}}
masterX244
quelle
1

Scala, 104 Bytes

class A{s=>lazy val x={val t=new Thread{override def run{s.synchronized{}}};t.start;t.join;1}};new A().x

Der Lazy-Val-Initialisierungsblock wird angehalten, bis eine Bedingung erfüllt ist. Diese Bedingung kann nur durch Lesen des Werts von Lazy Val x erfüllt werden - ein anderer Thread, der diese Bedingung erfüllen soll, kann dies nicht. Somit wird eine zirkuläre Abhängigkeit gebildet, und das Lazy Val kann nicht initialisiert werden.

Martin Seeler
quelle
Wie funktioniert das?
Addison Crump
Ich habe eine Erklärung hinzugefügt.
Martin Seeler
1

Kotlin, 35/37/55 Bytes

Allgemeines Thema : Thread.currentThread().join().

Mit Ausnahme von JVM-Fehlern / sehr spezialisiertem Code gegen diese Übermittlung sollte dies niemals zurückkehren, da der aktuelle Ausführungsthread jetzt deaktiviert ist und darauf wartet, dass er selbst stirbt.


Böse Eigenschaft: 35 Bytes (nicht konkurrierend): 35 Bytes

val a=Thread.currentThread().join()

Wenn Sie dies an einer beliebigen Stelle platzieren, an der eine Eigenschaftsdeklaration gültig ist, wird derjenige blockiert, der sie initialisiert. Im Fall einer Eigenschaft der obersten Ebene ist dies der Klassenladeprogramm, das die zugeordnete JVM-Klasse für diese Datei initialisiert (standardmäßig [file name]Kt.class).

Nicht konkurrierend, weil "dies überall als Top-Level-Eigenschaft platzieren" restriktiv ist.


Funktion: 37 Bytes

fun a()=Thread.currentThread().join()


main (): 55 Bytes

fun main(a:Array<String>)=Thread.currentThread().join()

F. George
quelle
1

PowerShell, 36 28 23 Byte

gps|%{$_.waitforexit()}

Selbststillstand. Wir bekommen alle Prozesse mit Get-Processund warten dann geduldig darauf, dass jeder von ihnen beendet wird ... was ungefähr nie passieren wird, da der Prozess auf sich selbst wartet.

Bearbeiten - 5 Bytes dank Roman Gräf gespeichert

AdmBorkBork
quelle
(gps)|%{$_.waitforexit()}ist drei Bytes kürzer und wartet, bis alle Prozesse beendet sind.
Roman Gräf
@ RomanGräf In der Tat, aber brauche die Parens gpsin diesem Fall nicht, also insgesamt 5 Bytes gespart.
AdmBorkBork
0

C (nur Linux), 31 Bytes - Probieren Sie es online aus!

main(a){syscall(240,&a,0,a,0);}

Der Systemaufruf 240 (0xf0) ist Futex (2) oder schneller Benutzerbereich-Mutex. Die Dokumentation besagt, dass das erste Argument ein Zeiger auf den Futex ist, das zweite Argument die Operation (0 bedeutet FUTEX_WAIT, dh warten, bis ein anderer Thread den Futex entsperrt). Das dritte Argument ist der Wert, den der Futex erwartet, solange er noch gesperrt ist, und das vierte Argument ist der Zeiger auf das Zeitlimit (NULL für kein Zeitlimit).

Da es keinen anderen Thread gibt, um den Futex freizuschalten, wird er offensichtlich für immer in einem selbstverschuldeten Deadlock warten. Es kann überprüft werden (über topoder einen anderen Task-Manager), dass der Prozess keine CPU-Zeit benötigt, wie wir es von einem blockierten Thread erwarten sollten.

Diener
quelle
0

Julia 0,6 , 13 Bytes

Sprache neuer als Frage. Warten Sie auf eine Aufgabe (wie eine Go-Routine, die sich derzeit im selben Thread befindet, in zukünftigen Versionen von Julia möglicherweise in einem anderen Thread), deren Ausführung nicht geplant ist.

wait(@task +)

Probieren Sie es online aus!

gggg
quelle
0

BotEngine, 3x3 = 9 (9 Bytes)

v
lCv
> <

Schritt 5 endet damit, dass zwei Bots auf unbestimmte Zeit darauf warten, dass sie sich bewegen ... ein Bot kann sich nicht bewegen, weil er darauf wartet, dass sich der andere aus dem unteren rechten Feld herausbewegt, und der andere Bot kann sich nicht bewegen, weil er auf den wartet Erster Bot, der sich aus dem unteren mittleren Quadrat herausbewegt.

SuperJedi224
quelle
0

Das Wasserfallmodell (Ratiofall), 13 Bytes

[[2,1],[1,1]]

Probieren Sie es online aus!

Hier ist eine lustige Antwort von der Wand. Dies ist die einfachste Endlosschleife im Wasserfallmodell (Variablen im Wasserfallmodell werden wiederholt dekrementiert, wenn nichts anderes passiert; dieses Programm definiert eine Variable, die sich bei jedem Dekrementieren inkrementiert, sodass niemals etwas passieren kann).

Die Frage fragt nach einem Deadlock, nicht nach einer Endlosschleife. Wir können jedoch das Verhalten bestimmter Implementierungen ausnutzen. Bei Optimierungsstufe 2 oder höher (die Standardeinstellung ist 3) erkennt der Interpreter Ratiofall die Endlosschleife und optimiert sie… in einen Deadlock! Zumindest wenn wir Sprachen als durch ihre Implementierung definiert betrachten (was normalerweise auf dieser Site der Fall ist), definiert dieses Programm tatsächlich eher einen Deadlock als eine Endlosschleife.

Sie können Hinweise auf den Deadlock aus dem Zeitbericht auf Try it Online! Link oben:

Real time: 60.004 s
User time: 0.006 s
Sys. time: 0.003 s
CPU share: 0.01 %
Exit code: 124

Das Programm lief 60 Sekunden lang (bis TIO es automatisch beendete), aber die meiste Zeit gab es keine CPU-Auslastung, keine Zeit, die vom Programm ausgeführt wurde, und keine Zeit, die der Kernel für das Programm verbrachte.

Um noch stärkere Beweise zu erhalten, können Sie Ratiofall unter einem Debugger auf Systemaufrufebene ausführen, z strace. Wenn Sie dies unter Linux tun, wird der Interpreter bei einem futexSystemaufruf blockiert , der versucht, eine Sperre zu aktivieren, die niemals freigegeben wird.

ais523
quelle
0

Perl 6 , 24 Bytes

Semaphore.new(0).acquire

Probieren Sie es online aus!

Erstellen Sie ein Semaphor mit null Genehmigungen und versuchen Sie dann, es zu erwerben.

Donaldh
quelle