Кратчайший код, который создает тупик

11

Напишите кратчайший код для создания тупика . Выполнение кода должно быть остановлено, так что это не работает:

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

Не нужно быть уверенным, что код заходит в тупик , просто почти наверняка (если вы будете работать в течение бесконечного времени, он заблокируется).

Джастин
источник
Считается ли это тупиком, если я пытаюсь заблокировать одну и ту же (не входящую) блокировку дважды из одного и того же потока? (извините, я не понял этот вопрос в песочнице)
Джон Дворак
@JanDvorak Создает ли это ситуацию, когда выполнение кода останавливается, потому что один поток ожидает чего-то, чего он не может получить (потому что другой удерживает его и ожидает того, что имеет первый поток)? Или это одна нить? Если вы можете создать такую ​​ситуацию с одним потоком, то это нормально. Прочитайте статью в википедии о тупике, вот чего я ожидаю.
Джастин
2
Code execution must haltЯ не понимаю Как это тупик, если он останавливается? Ты имеешь в виду, что он будет ждать чего-то, а не просто крутится, как мудак?
Cruncher
@Cruncher Посмотрите на пример, который не работает. Выполнение кода не останавливается, потому что цикл продолжает работать. Да, я имею в виду ожидание, а не вращение.
Джастин
Так что, если вы можете заставить поток пользовательского интерфейса ждать себя в Dyalog APL, значит ли это, что есть надежда получить ответ javascript? Хотя я подозреваю, что такое мышление просто откроет дверь к этому ответу: Javascript 6 "wait ()" ... ммм. нет. Связанный: возможно ли для нити сам Deadlock?
Натан Купер

Ответы:

11

Дьялог АПЛ (10)

⎕TSYNC⎕TID

⎕TSYNCзаставляет поток ждать, пока не закончится данный поток, ⎕TIDвыдаст текущий поток.

Dyalog APL может распознавать тупики, поэтому он немедленно отвечает

DEADLOCK

Самое интересное в том, что вам даже не нужно создавать никаких дополнительных потоков, заставляя поток пользовательского интерфейса ждать себя достаточно.

Если это обман и новые темы действительно требуются, вы можете сделать это в 27 символах:

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

F & xзапускается Fв новом потоке по значению xи возвращает идентификатор потока. Так:

  • {⎕TSYNC⎕TID+1}&0 создает поток, который будет синхронизироваться с потоком, чей ID на единицу выше, чем его собственный,
  • ⎕TSYNC& создает новый поток, который будет синхронизироваться с предыдущим потоком, и который получает идентификатор на единицу выше, чем поток, который был только что создан (при условии, что больше ничего не создает потоки).
  • вызывает бесконечный цикл (поэтому мы продолжаем создавать потоки до тупика).

Это приведет к взаимоблокировке, как только второй поток будет создан до того, как начнется запуск первого, что довольно скоро:

9:DEADLOCK
Мэринус
источник
Сохранить 2 байта с помощью: ⎕TSYNC 0'. ⎕TID` is 0.
Адам
8

Go, 42

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

Извините, downvoter, за то, что не предоставил, как это работает. Это создает анонимный канал целых и читает из него. Это приостанавливает основной поток до тех пор, пока значение не будет отправлено по каналу, что, очевидно, никогда не происходит, поскольку другие потоки не активны, и, таким образом, взаимоблокировка.

Алекс Озер
источник
2
Как это работает?
Джастин
4

Рубин, 39 знаков

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

Идея использовать кросс-соединение, бесстыдно украденное из Java-ответа Йоханнеса Куна .

Мы можем сбрить четыре символа (до 35 ), если настроим код для конкретной среды. IRB консоли JRuby является однопоточным:

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


Это мое предыдущее решение:

завести поток на мьютекс легко:

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

но это не правильный тупик, потому что второй поток технически не ждет первого потока. «Держи и жди» - это необходимое условие тупика, согласно Википедии. Первый поток не ждет, а второй поток не содержит ничего.

Рубин, 97 95 персонажей

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

это классический тупик. Два потока конкурируют за два ресурса, повторяя попытку в случае успеха. Обычно они застряли в течение секунды на моей машине.

Но если с бесконечным количеством потоков (ни один из которых не потребляет ЦП бесконечно, а некоторые из которых тупик), то все в порядке,

Рубин, 87 85 символов

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

Согласно моему тесту, он терпит неудачу после того, как число потоков достигает примерно 4700. Надеемся, что оно не будет работать до тех пор, пока у каждого потока не будет возможности запустить (таким образом, либо взаимная блокировка, либо завершение и освобождение места для нового). Согласно моему тесту, количество потоков не падает после возникновения ошибки, то есть во время теста возникла взаимоблокировка. Также ИРБ умерла после теста.

Джон дворак
источник
зачем вам дополнительные oи pпеременные? Не могли бы вы просто пройти mи nдля новой темы?
Йоханнес Кун
@JohannesKuhn mи nявляются глобальными. Оба потока видят их в одинаковом порядке. oи pявляются локальными для потока (ограничены итерацией цикла). Использование t[...], вероятно, обойдется дорого, и я не вижу лучшего способа передачи параметров потоку, чем с помощью замыкания. Добавление дополнительных параметров newудлиняет код на два символа.
Джон Дворжак
@JohannesKuhn Надеюсь, ты не возражаешь, я кое-что позаимствовал у тебя
Джон Дворжак,
Я не против Отличная работа.
Йоханнес Кун
Если мы предположим, что мы находимся в главном потоке, мы можем сократить это до 32 символов сT=Thread;T.new{T.main.join}.join
гистократ
4

Python, 46

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

(Само-взаимоблокировки)

Sneftel
источник
1
from threading import* Semaphore(0).acquire()короче на один байт, я думаю
Roman Gräf
@Roman Да, это короче, и это работает. tio.run/##K6gsycjPM/r/…
mbomb007
4

Bash + GNU coreutils, 11 байт

mkfifo x;<x

Создает случайный FIFO xв текущем каталоге (поэтому вам не нужно иметь файл с таким именем). FIFO могут быть удалены так же, как и обычные файлы, поэтому их не сложно очистить.

FIFO имеет сторону записи и сторону чтения; попытка открыть один блок до тех пор, пока другой процесс не откроет другой, и это, кажется, намеренно было разработано как примитив синхронизации. Учитывая, что здесь есть только один поток, как только мы пытаемся открыть его <x, мы застреваем. (Вы можете снять тупик, записав данные в FIFO из другого процесса.)

Этот тип тупика отличается от того, когда есть два ресурса, и каждый из двух потоков имеет один и нуждается в другом; скорее, в этом случае ресурсов нет, и процесс нуждается в них. Основываясь на других ответах, я думаю, что это имеет значение, но я могу понять, как тупиковый пурист может запретить ответ.

Если подумать, я могу подумать о трех тупиковых ситуациях:

  1. «Традиционный» тупик: два потока каждый ожидают снятия блокировки, которая удерживается другим потоком.

  2. Отдельный поток ожидает снятия блокировки, но он удерживает сам замок (и, таким образом, блокирует себя от возможности снять его).

  3. Один поток ожидает освобождения примитива синхронизации, но примитив синхронизации запускается в естественно заблокированном состоянии и должен быть разблокирован извне, и ничего для этого не запрограммировано.

Это тупик типа 3, который принципиально отличается от двух других: теоретически вы можете написать программу для разблокировки рассматриваемого примитива синхронизации, а затем запустить его. Тем не менее, то же самое относится к взаимоблокировкам типа 1 и 2, учитывая, что многие языки позволяют вам освобождать блокировку, которой вы не владеете (вы не должны и не будете иметь причины делать это, если у вас была причина в первую очередь используйте замки, но это работает…). Также стоит рассмотреть такую ​​программу, какmkfifo x;<x;echo test>x ; эта программа является своего рода противоположностью взаимоблокировке типа 2 (она пытается чтобы открыть оба конца FIFO, но он не может открыть один конец до тех пор, пока он не откроет другой конец), но он был сделан из этого путем добавления дополнительного кода, который никогда не запускается после этого! Я думаю, проблема в том, что ли блокировка заблокирована или нет, зависит от намерения за использованием блокировки, поэтому сложно определить объективно (особенно в случае, подобном этому, где единственная цель блокировки - преднамеренно создать тупик).


источник
2

C #, 100

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

Смотрите: тупик без блокировки

Johnbot
источник
1
Вы не можете переместить материал из static Cв Main?
Роман Греф
2

Баш с glibc, 6 байтов

Извините, что оживил старую ветку, но не удержался.

Как корень:

pldd 1

От человека pldd :

ОШИБКИ
Начиная с glibc 2.19, pldd не работает: он просто зависает при выполнении. Неясно, будет ли это когда-либо исправлено.

jasonwilkes
источник
Нет проблем с ответом на старом протекторе, если оригинал не чувствителен ко времени.
Ad Hoc Garf Hunter
2

Ява, 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) {
        }
    }
}

Запускает новый joinпоток и на нем (дождитесь окончания этого потока), пока новый поток делает то же самое с исходным потоком.

Йоханнес Кун
источник
Можете ли вы сделать его короче, бросая и ловя Errorвместо Exception?
mbomb007
Нет. Thread.join()бросает InteruptedException, который не является подклассом Error.
Йоханнес Кун
2

Tcl, 76

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

Тупик.

Это создаст новый поток и скажет другому потоку отправить моему потоку сообщение (скрипт для выполнения).

Но отправка сообщения в другой поток обычно блокируется до тех пор, пока скрипт не будет выполнен. И пока он блокируется, сообщения не обрабатываются, поэтому оба потока ждут, пока другой обработает их сообщение.

Йоханнес Кун
источник
как это работает?
Джон Дворак
thread::sendставит в очередь сценарий, который должен быть выполнен в другом потоке, и ожидает его завершения. Итак, в конце у нас есть Нить 1, ожидающая Нить 2, и Нить 2, ожидающая Нить 1.
Йоханнес Кун,
1

альтернативный java с нарушением монитора (248 чар)

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
источник
1

Scala, 104 байта

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

Блок инициализации lazy val приостанавливается, пока не будет выполнено условие. Это условие может быть выполнено только путем чтения значения lazy val x - другой поток, который должен выполнить это условие, не может этого сделать. Таким образом, формируется круговая зависимость, и ленивый val не может быть инициализирован.

Мартин Зилер
источник
Как это работает?
Эддисон Крамп
Я добавил объяснение.
Мартин Зилер,
1

Котлин, 35/37/55 байт

Общая тема: Thread.currentThread().join() .

Исключая ошибки JVM / очень специализированный код для этой отправки, этот шоуд никогда не вернется, поскольку текущий поток выполнения теперь отключен, ожидая своей смерти.


Злое свойство: 35 байт (не конкурирует): 35 байт

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

Размещение этого значения в любом месте, в котором объявление свойства является действительным, приведет к взаимоблокировке того, кто его инициализирует. В случае свойства верхнего уровня это будет загрузчик классов, инициализирующий сопоставленный класс JVM для этого файла (по умолчанию[file name]Kt.class ).

Не конкурирует, потому что «помещать это как свойство верхнего уровня в любом месте» является ограничительным.


Функция: 37 байт

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


main (): 55 байт

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

Ф. Джордж
источник
1

PowerShell, 36 28 23 байта

gps|%{$_.waitforexit()}

Self-тупиковый. Мы получаем все процессы сGet-Process и затем терпеливо ожидаем завершения каждого из них ... что произойдет примерно никогда, поскольку процесс будет ждать сам по себе.

Редактировать - 5 байтов сохранено благодаря Роману Грэфу

AdmBorkBork
источник
(gps)|%{$_.waitforexit()}на три байта короче и ожидает завершения всех процессов.
Роман Греф
@ RomanGräf Действительно, но gpsв этом случае паренсы не нужны , так что сэкономлено 5 байт.
AdmBorkBork
0

C (только для Linux), 31 байт - попробуйте онлайн!

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

Системный вызов 240 (0xf0) - это futex (2) или быстрый мьютекс пространства пользователя. В документации говорится, что первый аргумент - это указатель на futex, второй аргумент - это операция (0 означает FUTEX_WAIT, то есть дождитесь, пока другой поток разблокирует futex). Третий аргумент - это значение, которое, как вы ожидаете, будет иметь futex, пока он еще заблокирован, а четвертый - указатель на тайм-аут (NULL для без тайм-аута).

Очевидно, что, поскольку нет другого потока, чтобы разблокировать futex, он будет ждать вечно в самопричиненном тупике. Можно проверить (с помощью topили другого диспетчера задач), что процесс не использует процессорное время, как мы должны ожидать от заблокированного потока.

maservant
источник
0

Юлия 0,6 , 13 байт

Язык новее, чем вопрос. Ожидание задачи (как подпрограмма go, в настоящее время будет в том же потоке, в будущих версиях Julia это может быть в другом потоке), выполнение которого не запланировано.

wait(@task +)

Попробуйте онлайн!

GGGG
источник
0

BotEngine, 3x3 = 9 (9 байт)

v
lCv
> <

Шаг 5 заканчивается двумя ботами, которые бесконечно ждут друг друга для перемещения ... один бот не может двигаться, потому что он ждет, пока другой выйдет из нижнего правого квадрата, а другой бот не может двигаться, потому что он ждет Первый бот, чтобы выйти из нижней центральной площади.

SuperJedi224
источник
0

Модель водопада (Ratiofall), 13 байт

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

Попробуйте онлайн!

Вот забавный ответ со стены. Это самый простой бесконечный цикл в модели «Водопад» (переменные в модели «Водопад» многократно уменьшаются, когда ничего не происходит; эта программа определяет переменную, которая увеличивает себя всякий раз, когда она уменьшается, поэтому нет ничего, что могло бы случиться).

Вопрос требует тупика, а не бесконечного цикла. Однако мы можем использовать поведение конкретных реализаций. На уровне оптимизации 2 или выше (по умолчанию 3) интерпретатор Ratiofall обнаружит бесконечный цикл и оптимизирует его ... в тупик! Поэтому, по крайней мере, если мы считаем, что языки определяются их реализацией (что обычно имеет место на этом сайте), эта программа действительно определяет тупик, а не бесконечный цикл.

Вы можете увидеть свидетельство тупика из отчета о времени на сайте Try it Online! ссылка выше:

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

Программа работала в течение 60 секунд (до тех пор, пока TIO автоматически ее не завершил), но большую часть этого времени не было использования ЦП, времени, затраченного на запуск программы, и времени, затраченного ядром от имени программы.

Чтобы получить еще более веские доказательства, вы можете запустить Ratiofall в отладчике уровня системных вызовов, например strace; выполнение этого в Linux покажет блокировку интерпретатора при futexсистемном вызове, который пытается получить блокировку, которая никогда не будет снята.

ais523
источник