Shortest Code that creates a Deadlock

Question

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).

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

Python, 46

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

(self-deadlock)

Answer 5

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).

Answer 6

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

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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();}}

Answer 11

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.

Answer 12

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()

Answer 13

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

Answer 14

The Waterfall Model (Ratiofall), 13 bytes

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

Try it online!

Here's a fun off-the-wall answer. This is the simplest possible infinite loop in The Waterfall Model (variables in The Waterfall Model repeatedly decrement whenever nothing else is happening; this program defines a variable that increments itself whenever it decrements, so there's no way anything can ever happen).

The question asks for a deadlock, not an infinite loop. However, we can exploit the behaviour of specific implementations. At optimisation level 2 or higher (the default is 3), the interpreter Ratiofall will detect the infinite loop, and optimise it… into a deadlock! So at least if we consider languages to be defined by their implementation (which is usually the case on this site), this program does indeed define a deadlock, rather than an infinite loop.

You can see evidence of the deadlock from the time report on the Try it Online! link above:

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

The program ran for 60 seconds (until TIO automatically terminated it), but for most of that time, there was no CPU usage, no time spent by the program running, and no time spent by the kernel on behalf of the program.

To get even stronger evidence, you can run Ratiofall under a system-call-level debugger such as strace; doing this on Linux will show the interpreter blocking on a futex system call that attempts to take a lock which will never be released.

Answer 15

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.

Answer 16

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!

Answer 17

BotEngine, 3x3=9 (9 bytes)

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.

Answer 18

Perl 6, 24 bytes

Semaphore.new(0).acquire

Try it online!

Create a semaphore with zero permits and then try to acquire it.