Napisz najkrótszy kod, aby stworzyć impas . Wykonanie kodu musi zostać zatrzymane, więc to nie działa:

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

Nie musi być pewny, że kod wejdzie w impas , prawie na pewno (jeśli uruchomisz na czas nieokreślony, nastąpi impas).

Dyalog APL (10)

⎕TSYNC⎕TID

⎕TSYNCsprawia, że ​​wątek czeka na zakończenie danego wątku, ⎕TIDpodaje bieżący wątek.

Dyalog APL rozpoznaje jednak zakleszczenia, więc natychmiast reaguje

DEADLOCK

Zabawne jest to, że nie musisz nawet odradzać żadnych dodatkowych wątków, dzięki czemu wątek interfejsu użytkownika czeka sam na siebie.

Jeśli to jest oszustwo, a nowe wątki są rzeczywiście wymagane, możesz to zrobić za pomocą 27 znaków:

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

F & xuruchamia się Fw nowym wątku według wartości xi zwraca identyfikator wątku. Więc:

• {⎕TSYNC⎕TID+1}&0 tworzy wątek, który będzie synchronizowany z wątkiem, którego identyfikator jest o jeden wyższy od swojego,
• ⎕TSYNC& tworzy nowy wątek, który zsynchronizuje się z poprzednim wątkiem, i który uzyska identyfikator o jeden wyższy niż właśnie utworzony wątek (zakładając, że nic innego nie tworzy wątków).
• ∇ powoduje nieskończoną pętlę (więc tworzymy wątki, aż do impasu).

Zakleszczy się, gdy tylko drugi wątek zostanie utworzony przed uruchomieniem pierwszego wątku, co nastąpi wkrótce:

9:DEADLOCK

Idź, 42

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

Przepraszamy, downvoter, za niedostarczenie, jak to działa. To tworzy anonimowy kanał int i czyta z niego. Powoduje to wstrzymanie głównego wątku, dopóki wartość nie zostanie wysłana kanałem, co oczywiście nigdy się nie zdarza, ponieważ żadne inne wątki nie są aktywne, a zatem impas.

Ruby, 39 znaków

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

Pomysł użycia połączenia krzyżowego bezwstydnie skradzionego z odpowiedzi Java Johana Kuhna .

Możemy ogolić cztery znaki (do 35 ), jeśli dostroimy kod do określonego środowiska. Konsola JRuby IRB jest jednowątkowa:

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

To jest moje poprzednie rozwiązanie:

utknięcie nici na muteksie jest łatwe:

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

ale to nie jest właściwy impas, ponieważ drugi wątek technicznie nie czeka na pierwszy wątek. Według Wikipedii „czekaj i czekaj” jest niezbędnym warunkiem impasu. Pierwszy wątek nie czeka, a drugi wątek nic nie zawiera.

Rubin, 97 95 znaków

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

to klasyczny impas. Dwa wątki rywalizują o dwa zasoby, ponawiając próbę, jeśli im się powiedzie. Zwykle utkną w ciągu sekundy na moim komputerze.

Ale jeśli posiadanie nieskończenie wielu wątków (z których żaden nie zużywa procesora nieskończenie, a niektóre z nich są zakleszczone) jest OK,

Rubin, 87 85 znaków

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

Według mojego testu nie powiedzie się, gdy liczba wątków osiągnie około 4700. Mam nadzieję, że nie zawiedzie, dopóki każdy wątek nie będzie miał szansy na uruchomienie (w ten sposób albo zakleszczenie, albo zakończenie i zwolnienie miejsca na nowy). Według mojego testu liczba wątków nie spada po wystąpieniu awarii, co oznacza, że ​​podczas testu wystąpił zakleszczenie. Ponadto IRB zmarł po teście.

Python, 46

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

(samo zakleszczenie)

Coreutils Bash + GNU, 11 bajtów

mkfifo x;<x

Tworzy zbłąkane FIFO xw bieżącym katalogu (więc nie musisz mieć pliku o tej nazwie). Pliki FIFO można usunąć w taki sam sposób, jak zwykłe pliki, więc ich wyczyszczenie nie powinno być trudne.

FIFO ma stronę do zapisu i stronę do odczytu; próba otwarcia jednego bloku, dopóki inny proces nie otworzy drugiego, i wydaje się, że zostało to celowo zaprojektowane jako prymityw synchronizacji. Ponieważ jest tu tylko jeden wątek, gdy tylko spróbujemy go otworzyć <x, utkniemy. (Możesz odblokować impas, pisząc do FIFO, o którym mowa, z innego procesu.)

Jest to inny rodzaj impasu od tego, gdy istnieją dwa zasoby, a każdy z dwóch wątków ma jeden i potrzebuje drugiego; raczej w tym przypadku zasoby są zerowe i proces ich potrzebuje. Opierając się na innych odpowiedziach, myślę, że to się liczy, ale rozumiem, jak purysta z impasu może chcieć odmówić odpowiedzi.

Pomyśl o tym, a właściwie potrafię wymyślić trzy sytuacje podobne do impasu:

1. „Tradycyjny” impas: każdy z dwóch wątków czeka na zwolnienie blokady, która jest utrzymywana przez drugi wątek.

2. Pojedynczy wątek czeka na zwolnienie blokady, ale utrzymuje samą blokadę (a zatem blokuje się przed możliwością zwolnienia).

3. Pojedynczy wątek czeka na zwolnienie operacji podstawowej synchronizacji, ale operacja podstawowa synchronizacji zaczyna się w stanie naturalnie zablokowanym i musi zostać odblokowana zewnętrznie, i nic nie zostało do tego zaprogramowane.

Jest to impas typu 3, który zasadniczo różni się od pozostałych dwóch: teoretycznie można napisać program, aby odblokować prymityw synchronizacji, a następnie uruchomić go. To samo dotyczy zakleszczeń typu 1 i 2, biorąc pod uwagę, że wiele języków pozwala zwolnić blokadę, której nie jesteś właścicielem (nie powinieneś i nie miałbyś powodu, aby to zrobić, gdybyś miał powód użyj zamków w pierwszej kolejności, ale działa…). Warto również rozważyć taki programmkfifo x;<x;echo test>x; ten program jest przeciwieństwem impasu typu 2 (próbuje otworzyć oba końce FIFO, ale nie może otworzyć jednego końca, dopóki nie otworzy drugiego końca), ale powstał z tego jednego, dodając dodatkowe kod, który nigdy nie działa po tym! Myślę, że problem polega na tym, że to, czy zamek jest zakleszczony, zależy od intencji użycia zamka, więc trudno jest obiektywnie zdefiniować (szczególnie w takim przypadku, w którym jedynym celem zamka jest celowe wywołanie zakleszczenia ).

C #, 100

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

Zobacz: Zakleszczenie bez blokady

Bash z glibc, 6 bajtów

Przepraszam, że ożywiłem stary wątek, ale nie mogłem się oprzeć.

Jako root:

pldd 1

Od man pldd :

BŁĘDY
Od wersji 2.19 glibc pldd jest zepsuty: po prostu zawiesza się po uruchomieniu. Nie jest jasne, czy zostanie to kiedykolwiek naprawione.

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

Nie golfowany:

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

Rozpoczyna nowy wątek i joinna nim (poczekaj, aż ten wątek się zakończy), podczas gdy nowy wątek robi to samo z oryginalnym wątkiem.

Tcl, 76

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

Impas.

To tworzy nowy Wątek i mówi drugiemu wątkowi, aby wysłał mój wątek wiadomość (skrypt do wykonania).

Ale wysyłanie wiadomości do innego wątku zwykle blokuje, dopóki skrypt nie zostanie wykonany. Podczas gdy blokuje, żadne wiadomości nie są przetwarzane, więc oba wątki czekają, aż drugi przetworzy wiadomość.

alternatywna Java z nadużywaniem monitorów (248 znaków)

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

Scala, 104 bajty

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

Blok inicjalizujący leniwy val zawiesza się do momentu spełnienia warunku. Ten warunek można spełnić tylko poprzez odczyt wartości lazy val x - inny wątek, który ma spełnić ten warunek, nie może tego zrobić. W ten sposób powstaje zależność cykliczna i nie można zainicjować leniwej val.

Kotlin, 35/37/55 bajtów

Temat ogólny: Thread.currentThread().join().

Wyłączając błędy JVM / bardzo wyspecjalizowany kod przeciwko temu zgłoszeniu, nigdy nie powróci, ponieważ bieżący wątek wykonania jest teraz wyłączony i czeka na śmierć.

Zła właściwość: 35 bajtów (niekonkurencyjna): 35 bajtów

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

Umieszczenie tego w dowolnym miejscu, w którym deklaracja własności jest ważna, spowoduje zakleszczenie tego, kto ją inicjuje. W przypadku właściwości najwyższego poziomu będzie to moduł ładujący inicjujący odwzorowaną klasę JVM dla tego pliku (domyślnie [file name]Kt.class).

Niekonkurencyjny, ponieważ „umieszczenie tego jako właściwości najwyższego poziomu w dowolnym miejscu” jest restrykcyjne.

Funkcja: 37 bajtów

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

main (): 55 bajtów

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

PowerShell, 36 28 23 bajtów

gps|%{$_.waitforexit()}

Zakleszczenie. Otrzymujemy wszystkie procesy, Get-Processa następnie cierpliwie czekamy na zakończenie każdego z nich ... co stanie się w przybliżeniu nigdy, ponieważ proces będzie czekał na siebie.

Edycja - Oszczędność 5 bajtów dzięki Romanowi Gräfowi

C (tylko Linux), 31 bajtów - Wypróbuj online!

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

Wywołanie systemowe 240 (0xf0) to futex (2) lub szybki muteks przestrzeni użytkownika. Dokumentacja stwierdza, że ​​pierwszy argument jest wskaźnikiem do futeksu, drugi argument jest operacją (0 oznacza FUTEX_WAIT, to znaczy poczekaj, aż inny wątek odblokuje futex). Trzeci argument to wartość, jakiej spodziewasz się, gdy futex będzie nadal zamknięty, a czwarty to wskaźnik przekroczenia limitu czasu (NULL dla braku limitu czasu).

Oczywiście, ponieważ nie ma innego wątku, aby odblokować futex, będzie on czekał wiecznie w samookaleczającym się impasie. Można zweryfikować (za pomocą toplub innego menedżera zadań), że proces nie zużywa czasu procesora, jak należy się spodziewać po zakleszczonym wątku.

Julia 0.6 , 13 bajtów

Język nowszy niż pytanie. Poczekaj na zadanie (jak rutynowa procedura, będzie aktualnie w tym samym wątku, w przyszłych wersjach Julii może być w innym wątku), którego uruchomienie nie jest zaplanowane.

wait(@task +)

Wypróbuj online!

BotEngine, 3x3 = 9 (9 bajtów)

v
lCv
> <

Krok 5 kończy się na tym, że dwa boty czekają w nieskończoność na ruch ... jeden bot nie może się ruszyć, ponieważ czeka na inny ruch z prawego dolnego kwadratu, a drugi bot nie może się ruszyć, ponieważ czeka na pierwszy bot wyszedł z dolnego środkowego kwadratu.

Model wodospadu (Ratiofall), 13 bajtów

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

Wypróbuj online!

Oto zabawna odpowiedź od ściany. Jest to najprostsza możliwa nieskończona pętla w Modelu Wodospadu (zmienne w Modelu Wodospadu wielokrotnie zmniejszają się za każdym razem, gdy nic innego się nie dzieje; ten program definiuje zmienną, która zwiększa się za każdym razem, gdy maleje, więc nie ma mowy, aby cokolwiek się wydarzyło).

Pytanie wymaga impasu, a nie nieskończonej pętli. Możemy jednak wykorzystać zachowanie określonych implementacji. Na poziomie optymalizacji 2 lub wyższym (domyślnie 3) interpreter Ratiofall wykryje nieskończoną pętlę i zoptymalizuje ją… w impasie! Tak więc przynajmniej jeśli weźmiemy pod uwagę języki definiowane przez ich implementację (co zwykle ma miejsce na tej stronie), program ten rzeczywiście określa impas, a nie nieskończoną pętlę.

Możesz zobaczyć dowody impasu z raportu czasowego w Try it Online! link powyżej:

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

Program działał przez 60 sekund (aż TIO automatycznie go zakończył), ale przez większość tego czasu nie było użycia procesora, czasu spędzonego przez uruchomiony program i czasu jądra w imieniu programu.

Aby uzyskać jeszcze silniejsze dowody, możesz uruchomić Ratiofall w debuggerze na poziomie systemowym, takim jak strace; zrobienie tego w Linuksie pokaże, że interpreter blokuje futexwywołanie systemowe, które próbuje uzyskać blokadę, która nigdy nie zostanie zwolniona.

Perl 6 , 24 bajtów

Semaphore.new(0).acquire

Wypróbuj online!

Utwórz semafor z zerowymi pozwoleniami, a następnie spróbuj go uzyskać.