10
\$\begingroup\$

Write the shortest code to create a deadlock. Code execution must halt, so this doesn't work:

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){}}
}

It doesn't need to be certain that the code goes into deadlock, just almost surely (if you run for infinite time, it will deadlock).

\$\endgroup\$
  • \$\begingroup\$ Does it count as a deadlock if I try to lock the same (non-reentrant) lock twice from the same thread? (sorry I didn't realise this question in the sandbox) \$\endgroup\$ – John Dvorak Nov 28 '13 at 6:49
  • \$\begingroup\$ @JanDvorak Does that create a situation where the code execution halts because one thread is waiting for something it cannot get (because another is holding it and waiting for what the first thread has)? Or is it one thread? If you can create such a situation with one thread, then it is fine. Read the wikepedia article on deadlock, that is what I expect. \$\endgroup\$ – Justin Nov 28 '13 at 15:43
  • 2
    \$\begingroup\$ Code execution must halt I don't understand. How is it a deadlock if it halts? Do you mean it'll be waiting for something rather than just spinlocking like an asshole? \$\endgroup\$ – Cruncher Nov 28 '13 at 16:17
  • \$\begingroup\$ @Cruncher Take a look at the example that does not work. The code execution doesn't stop because the loop keeps running. Yes I mean waiting rather than spinning. \$\endgroup\$ – Justin Nov 28 '13 at 22:14
  • \$\begingroup\$ So if you can make the UI thread wait for itself in Dyalog APL, does that mean that there's some hope of getting a javascript answer? Although I suspect that sort of thinking would just open the door to this answer: Javascript 6 "wait()" ... ermmm. no. Related: Is it possible for a thread to Deadlock itself? \$\endgroup\$ – Nathan Cooper Dec 4 '13 at 11:36

16 Answers 16

11
\$\begingroup\$

Dyalog APL (10)

⎕TSYNC⎕TID

⎕TSYNC makes the thread wait until the given thread ends, ⎕TID gives the current thread.

Dyalog APL can recognize deadlocks though, so it immediately responds with

DEADLOCK

The fun thing is, you don't even need to spawn any extra threads, making the UI thread wait for itself is plenty.

If this is cheating and new threads are actually required, you can do it in 27 characters:

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

F & x runs F in a new thread on value x, and returns the thread ID. So:

  • {⎕TSYNC⎕TID+1}&0 creates a thread that will synchronize with the thread whose ID is one higher than its own,
  • ⎕TSYNC& creates a new thread that will synchronize with the previous thread, and which gets an ID one higher than the thread that was just created (assuming nothing else is creating threads).
  • causes an infinite loop (so we keep creating threads until there's a deadlock).

This will deadlock as soon as the second thread gets created before the first one starts running, which is pretty soon:

9:DEADLOCK
\$\endgroup\$
  • \$\begingroup\$ Save 2 bytes with: ⎕TSYNC 0'. ⎕TID` is 0. \$\endgroup\$ – Adám Jan 13 '16 at 14:54
8
\$\begingroup\$

Go, 42

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

Apologies, downvoter, for not providing how it works. This creates an anonymous channel of ints and reads from it. This pauses the main thread until a value gets sent down the channel, which obviously never happens since no other threads are active, and thus, deadlock.

\$\endgroup\$
  • 2
    \$\begingroup\$ How does it work? \$\endgroup\$ – Justin Dec 2 '13 at 18:03
4
\$\begingroup\$

Ruby, 39 characters

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

The idea to use a cross-join shamelessly stolen from Johannes Kuhn's Java answer.

We can shave off four characters (getting to 35) if we tune the code to a specific environment. JRuby's console IRB is single-threaded:

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


This is my previous solution:

getting a thread stuck on a mutex is easy:

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

but this isn't a proper deadlock, because the second thread is technically not waiting for the first thread. "hold and wait" is a neccessary condition for a deadlock according to Wikipedia. The first thread doesn't wait, and the second thread doesn't hold anything.

Ruby, 97 95 characters

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

this is a classic deadlock. Two threads compete for two resources, retrying if they succeed. Normally they get stuck within a second on my machine.

But, if having infinitely many threads (none of which consumes CPU infinitely and some of which deadlock) is OK,

Ruby, 87 85 characters

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

According to my test, it fails after the thread count reaches about 4700. Hopefully it doesn't fail until each thread had a chance to run (thus either deadlocking or finishing and freeing space for a new one). According to my test, the thread count doesn't drop after the failure occurs, meaning that a deadlock did occur during the test. Also, IRB died after the test.

\$\endgroup\$
  • \$\begingroup\$ why do you need the extra o & p variables? Can't you just pass m and n for the new Thread? \$\endgroup\$ – Johannes Kuhn Nov 28 '13 at 8:57
  • \$\begingroup\$ @JohannesKuhn m and n are global. Both threads see them in the same order. o and p are thread-local (scoped to the loop iteration). Using t[...] would probably get expensive, and I can see no better way of passing parameters to the thread than via closure. Adding extra parameters to new lengthens the code by two chars. \$\endgroup\$ – John Dvorak Nov 28 '13 at 9:04
  • \$\begingroup\$ @JohannesKuhn I hope you don't mind I have borrowed some of your logic \$\endgroup\$ – John Dvorak Nov 28 '13 at 9:42
  • \$\begingroup\$ I don't mind. Good job. \$\endgroup\$ – Johannes Kuhn Nov 28 '13 at 17:29
  • \$\begingroup\$ If we assume we're in the main thread, we can shave this down to 32 chars with T=Thread;T.new{T.main.join}.join \$\endgroup\$ – histocrat Nov 29 '13 at 15:41
3
\$\begingroup\$

Python, 46

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

(self-deadlock)

\$\endgroup\$
  • 1
    \$\begingroup\$ from threading import* Semaphore(0).acquire() is shorter by one byte I think \$\endgroup\$ – Roman Gräf Nov 29 '16 at 16:21
  • \$\begingroup\$ @Roman Yeah, it is shorter and it works. tio.run/##K6gsycjPM/r/… \$\endgroup\$ – mbomb007 Feb 27 '18 at 19:13
3
\$\begingroup\$

Bash + GNU coreutils, 11 bytes

mkfifo x;<x

Creates a stray FIFO x in the current directory (so you'll need to not have a file by that name). FIFOs can be deleted the same way as regular files, so it shouldn't be hard to clear up.

A FIFO has a write side and a read side; attempting to open one blocks until another process opens the other, and this seems to have been intentionally designed as a synchronization primitive. Given that there's only one thread here, as soon as we try to open it with <x, we get stuck. (You can unstick the deadlock via writing to the FIFO in question from another process.)

This is a different kind of deadlock from the one when there are two resources, and two threads each have one and needs the other; rather, in this case, there are zero resources and the process needs one. Based on the other answers, I think this counts, but I can understand how a deadlock purist might want to disallow the answer.

Come to think of it, I can actually think of three deadlock-like situations:

  1. The "traditional" deadlock: two threads are each waiting for a lock to be released, that's held by the other thread.

  2. A single thread is waiting for a lock to be released, but it holds the lock itself (and thus is blocking itself from being able to release it).

  3. A single thread is waiting for a synchronization primitive to be released, but the synchronization primitive starts in a naturally locked state and has to be unlocked externally, and nothing's been programmed to do that.

This is a deadlock of type 3, which is in a way fundamentally different from the other two: you could, in theory, write a program to unlock the synchronization primitive in question, then run it. That said, the same applies to deadlocks of type 1 and 2, given that many languages allow you to release a lock you don't own (you're not supposed to and would have no reason to do so if you had a reason to use the locks in the first place, but it works…). Also, it's worth considering a program like mkfifo x;<x;echo test>x; that program's sort-of the opposite of a type 2 deadlock (it's trying to open both ends of the FIFO, but it can't open one end until after it opens the other end), but it was made from this one via adding extra code that never runs after this one! I guess the problem is that whether a lock is deadlocked or not depends on the intention behind the use of the lock, so it's hard to define objectively (especially in a case like this where the only purpose of the lock is to produce a deadlock intentionally).

\$\endgroup\$
2
\$\begingroup\$

C#, 100

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

See: The no-lock deadlock

\$\endgroup\$
  • 1
    \$\begingroup\$ Can't you move the stuff from static C to Main? \$\endgroup\$ – Roman Gräf Nov 29 '16 at 16:18
2
\$\begingroup\$

Bash with glibc, 6 Bytes

Sorry to revive an old thread, but couldn't resist.

As root:

pldd 1

From man pldd:

BUGS
Since glibc 2.19, pldd is broken: it just hangs when executed. It is unclear if it will ever be fixed.

\$\endgroup\$
  • \$\begingroup\$ There is no problem with answering on a old tread as long as the original was not time sensitive. \$\endgroup\$ – Wheat Wizard Nov 28 '16 at 0:50
2
\$\begingroup\$

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) {
        }
    }
}

Starts a new Thread and join on it (wait until this thread has finished), while the new Thread does the same with the original Thread.

\$\endgroup\$
  • \$\begingroup\$ Can you make it shorter by throwing and catching Error instead of Exception? \$\endgroup\$ – mbomb007 Feb 27 '18 at 19:19
  • \$\begingroup\$ Nope. Thread.join() throws an InteruptedException, which is not a subclass of Error. \$\endgroup\$ – Johannes Kuhn Feb 27 '18 at 21:38
2
\$\begingroup\$

Tcl, 76

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

Deadlock.

This creates a new Thread, and tells the other thread to send my thread a message (script to execute).

But sending a message to an other Thread usually blocks until the script has been executed. And while it is blocking, no messages are processed, so both Threads wait for the other to process their message.

\$\endgroup\$
  • \$\begingroup\$ how does this work? \$\endgroup\$ – John Dvorak Nov 28 '13 at 8:09
  • \$\begingroup\$ thread::send queues a script that should be executed in an other thread and wait for it to complete. So at the end we have Thread 1 waiting for Thread 2, and Thread 2 waiting for Thread 1. \$\endgroup\$ – Johannes Kuhn Nov 28 '13 at 8:14
1
\$\begingroup\$

alternative java with monitor-abuse (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();}}
\$\endgroup\$
1
\$\begingroup\$

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

The lazy val initialization block suspends until a condition is fulfilled. This condition can only be fulfilled by reading the value of lazy val x - another thread that is supposed to complete this condition cannot do so. Thus, a circular dependency is formed, and the lazy val cannot be initialized.

\$\endgroup\$
  • \$\begingroup\$ How does this work? \$\endgroup\$ – Addison Crump Oct 29 '15 at 13:42
  • \$\begingroup\$ I added an explanation. \$\endgroup\$ – Martin Seeler Oct 29 '15 at 13:45
1
\$\begingroup\$

Kotlin, 35/37/55 bytes

General theme: Thread.currentThread().join().

Excluding JVM bugs / very specialized code against this submission this shoud never return as the current execution thread is now disabled waiting for itself to die.


Evil property: 35 bytes (non-competing): 35 bytes

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

Putting this anywhere a property declaration is valid will deadlock whoever is initializing it. In the case of a top-level property, that will be the classloader initializing the mapped JVM class for that file (by default [file name]Kt.class).

Non-competing because "put this as a top level property anywhere" is restrictive.


Function: 37 bytes

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


main(): 55 bytes

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

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 36 28 23 bytes

gps|%{$_.waitforexit()}

Self-deadlock. We get all processes with Get-Process and then wait patiently for each of them to exit ... which will happen approximately never, since the process will be waiting on itself.

Edit - Saved 5 bytes thanks to Roman Gräf

\$\endgroup\$
  • \$\begingroup\$ (gps)|%{$_.waitforexit()} is three bytes shorter and waits for all processes to exit. \$\endgroup\$ – Roman Gräf Nov 28 '16 at 10:29
  • \$\begingroup\$ @RomanGräf Indeed, but don't need the parens around gps in that case, so saved 5 bytes total. \$\endgroup\$ – AdmBorkBork Nov 29 '16 at 15:57
0
\$\begingroup\$

C (Linux only), 31 Bytes -- Try it online!

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

System call 240 (0xf0) is futex(2), or fast userspace mutex. The documentation states that the first argument is a pointer to the futex, the second argument is the operation (0 means FUTEX_WAIT, that is, wait until another thread unlocks the futex). The third argument is the value you expect the futex to have while still locked, and the fourth is the pointer to the timeout (NULL for no timeout).

Obviously, since there's no other thread to unlock the futex, it will wait forever in self-inflicted deadlock. It can be verified (via top or other task manager) that the process uses no CPU time, as we should expect from a deadlocked thread.

\$\endgroup\$
0
\$\begingroup\$

BotEngine, 3x3=9

Noncompeting, laguage postdates the question.

v
lCv
> <

Step 5 ends with two bots waiting indefinitely for each other to move... one bot can't move because it's waiting for the other to move out of the bottom right square, and the other bot can't move because it's waiting for the first bot to move out of the bottom center square.

\$\endgroup\$
0
\$\begingroup\$

Julia 0.6, 13 bytes

Language newer than question. Wait on a task (like a go-routine, will currently be on the same thread, in future versions of Julia it may be on another thread) which is not scheduled to run.

wait(@task +)

Try it online!

\$\endgroup\$

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.