Código mais curto que cria um impasse

11

Escreva o código mais curto para criar um conflito . A execução do código deve parar, para que isso não funcione:

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

Não é necessário ter certeza de que o código entra em conflito , quase com certeza (se você executar por tempo infinito, ele entrará em conflito).

Justin
fonte
Isso conta como um impasse se eu tentar bloquear o mesmo bloqueio (não reentrante) duas vezes do mesmo encadeamento? (desculpe, eu não sabia que essa pergunta na caixa de areia)
John Dvorak
@JanDvorak Isso cria uma situação em que a execução do código é interrompida porque um thread está esperando por algo que não pode ser obtido (porque outro está segurando e aguardando o que o primeiro thread possui)? Ou é uma discussão? Se você pode criar essa situação com um thread, tudo bem. Leia o artigo da wikepedia sobre impasse, é o que eu espero.
Justin
2
Code execution must haltEu não entendo Como é um impasse se parar? Você quer dizer que estará esperando por algo em vez de apenas girar como um idiota?
Cruncher
@Cruncher Veja o exemplo que não funciona. A execução do código não para porque o loop continua em execução. Sim, quero dizer esperar, em vez de girar.
Justin
Portanto, se você pode fazer com que o thread da interface do usuário espere por si mesmo no Dyalog APL, isso significa que há alguma esperança de obter uma resposta javascript? Embora eu suspeite que esse tipo de pensamento apenas abra a porta para esta resposta: Javascript 6 "wait ()" ... ermmm. não. Relacionado: É possível um encadeamento para o próprio Deadlock?
Nathan Cooper

Respostas:

11

Dyalog APL (10)

⎕TSYNC⎕TID

⎕TSYNCfaz com que o encadeamento aguarde até que o encadeamento final termine, ⎕TIDfornece o encadeamento atual.

O Dyalog APL pode reconhecer os impasses, portanto, responde imediatamente com

DEADLOCK

O mais divertido é que você nem precisa gerar threads extras, fazendo com que o thread da interface do usuário espere por si só.

Se isso é trapaça e novos encadeamentos são realmente necessários, você pode fazê-lo em 27 caracteres:

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

F & xé executado Fem um novo encadeamento no valor xe retorna o ID do encadeamento. Então:

  • {⎕TSYNC⎕TID+1}&0 cria um encadeamento que será sincronizado com o encadeamento cujo ID é um maior que o seu,
  • ⎕TSYNC& cria um novo encadeamento que será sincronizado com o encadeamento anterior e obtém um ID um maior que o encadeamento que acabou de ser criado (assumindo que nada mais esteja criando encadeamentos).
  • causa um loop infinito (então continuamos criando threads até que haja um impasse).

Isso entrará em conflito assim que o segundo encadeamento for criado antes do início do primeiro, o que é muito breve:

9:DEADLOCK
marinus
fonte
Salve 2 bytes com: ⎕TSYNC 0'. ⎕TID` é 0.
Adám 13/01/16
8

Go, 42

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

Desculpas, downvoter, por não fornecer como ele funciona. Isso cria um canal anônimo de entradas e lê a partir dele. Isso interrompe o encadeamento principal até que um valor seja enviado pelo canal, o que obviamente nunca acontece, pois nenhum outro encadeamento está ativo e, portanto, um impasse.

Alex Ozer
fonte
2
Como funciona?
Justin
4

Ruby, 39 caracteres

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

A idéia de usar uma junção cruzada descaradamente roubada da resposta Java de Johannes Kuhn .

Podemos cortar quatro caracteres (chegando a 35 ) se ajustarmos o código para um ambiente específico. O IRB do console do JRuby é de thread único:

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


Esta é a minha solução anterior:

é fácil ficar preso em um mutex:

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

mas esse não é um conflito adequado, porque tecnicamente o segundo thread não está aguardando o primeiro thread. "espera e espera" é uma condição necessária para um impasse, de acordo com a Wikipedia. O primeiro thread não espera e o segundo thread não contém nada.

Rubi, 97 95 caracteres

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

este é um impasse clássico. Dois threads competem por dois recursos, tentando novamente se tiverem êxito. Normalmente eles ficam presos dentro de um segundo na minha máquina.

Porém, se ter infinitos encadeamentos (nenhum dos quais consome CPU infinitamente e alguns dos quais impasse) estiver OK,

Rubi, 87 85 caracteres

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

De acordo com o meu teste, ele falha após a contagem de encadeamentos atingir cerca de 4700. Esperemos que não falhe até que cada encadeamento tenha a chance de ser executado (portanto, seja um deadlock ou finalizando e liberando espaço para um novo). De acordo com o meu teste, a contagem de threads não diminui após a falha, o que significa que ocorreu um conflito durante o teste. Além disso, o IRB morreu após o teste.

John Dvorak
fonte
por que você precisa do extra oe pvariáveis? Você não pode simplesmente passar me npara o novo segmento?
Johannes Kuhn
@JohannesKuhn me nsão globais. Ambos os threads os veem na mesma ordem. oe psão thread-local (com escopo definido para a iteração do loop). O uso t[...]provavelmente ficaria caro, e não vejo melhor maneira de passar parâmetros para o thread do que através do fechamento. A adição de parâmetros extras para newaumentar o código em dois caracteres.
John Dvorak
@JohannesKuhn Eu espero que você não se importa de eu ter emprestado um pouco da sua lógica
John Dvorak
Eu não me importo. Bom trabalho.
Johannes Kuhn
Se assumirmos que estamos no segmento principal, podemos reduzir isso para 32 caracteres com:T=Thread;T.new{T.main.join}.join
histocrat 29/11/13
4

Python, 46

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

(auto-impasse)

Sneftel
fonte
11
from threading import* Semaphore(0).acquire()é mais curto em um byte, eu acho
Roman Gräf 29/11
@ Roman Sim, é mais curto e funciona. Você pode
usar o seguinte
4

Bash + núcleo GNU, 11 bytes

mkfifo x;<x

Cria um FIFO perdido xno diretório atual (para que você não precise ter um arquivo com esse nome). Os FIFOs podem ser excluídos da mesma maneira que os arquivos comuns, portanto, não deve ser difícil esclarecer.

Um FIFO tem um lado de gravação e um lado de leitura; tentando abrir um bloco até que outro processo abra o outro, e isso parece ter sido intencionalmente projetado como um primitivo de sincronização. Dado que há apenas um segmento aqui, assim que tentamos abri-lo <x, ficamos presos. (Você pode cancelar o impasse escrevendo para o FIFO em questão de outro processo.)

Esse é um tipo de conflito diferente do quando existem dois recursos, e dois threads têm um e precisam do outro; nesse caso, existem zero recursos e o processo precisa de um. Com base nas outras respostas, acho que isso conta, mas posso entender como um purista de impasse pode querer impedir a resposta.

Pensando bem, eu posso pensar em três situações semelhantes a um impasse:

  1. O impasse "tradicional": dois encadeamentos aguardam a liberação de um bloqueio, que é mantido pelo outro encadeamento.

  2. Um único encadeamento está aguardando a liberação de um bloqueio, mas ele mantém o próprio bloqueio (e, portanto, está impedindo de liberar).

  3. Um único encadeamento está aguardando o lançamento de uma primitiva de sincronização, mas a primitiva de sincronização inicia em um estado naturalmente bloqueado e precisa ser desbloqueada externamente, e nada foi programado para fazer isso.

Esse é um impasse do tipo 3, que é fundamentalmente diferente dos outros dois: você poderia, em teoria, escrever um programa para desbloquear a primitiva de sincronização em questão e executá-la. Dito isso, o mesmo se aplica aos impasses do tipo 1 e 2, já que muitos idiomas permitem liberar um bloqueio que você não possui (você não deveria e não teria motivos para fazê-lo se tivesse um motivo para use os bloqueios em primeiro lugar, mas funciona…). Além disso, vale a pena considerar um programa comomkfifo x;<x;echo test>x; esse tipo de programa é o oposto de um deadlock do tipo 2 (ele está tentando abrir as duas extremidades do FIFO, mas não pode abrir uma extremidade até abrir a outra extremidade), mas foi feito a partir dessa via adicionando extra código que nunca é executado após este! Eu acho que o problema é que se um bloqueio é bloqueado ou não depende da intenção por trás do uso do bloqueio, por isso é difícil definir objetivamente (especialmente em um caso como este, onde o único objetivo do bloqueio é produzir um bloqueio intencionalmente )


fonte
2

C #, 100

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

Veja: O impasse sem bloqueio

Johnbot
fonte
11
Você não pode mover as coisas de static Cpara Main?
Roman Gräf 29/11
2

Bash com glibc, 6 bytes

Desculpe reviver um tópico antigo, mas não resisti.

Como raiz:

pldd 1

Do man pldd :

BUGS
Desde o glibc 2.19, o pldd está quebrado: ele apenas trava quando executado. Não está claro se algum dia será corrigido.

jasonwilkes
fonte
Não há problema em responder em uma banda de rodagem antiga, desde que o original não seja sensível ao tempo.
Ad Hoc Garf Hunter
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) {
        }
    }
}

Inicia um novo Thread e joinnele (aguarde até que esse segmento termine), enquanto o novo Thread faz o mesmo com o Thread original.

Johannes Kuhn
fonte
Você pode torná-lo mais curto jogando e pegando em Errorvez de Exception?
Mbomb007
Não. Thread.join()lança um InteruptedException, que não é uma subclasse de Error.
Johannes Kuhn,
2

Tcl, 76

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

Impasse.

Isso cria um novo thread e informa ao outro thread para enviar uma mensagem ao meu thread (script a ser executado).

Mas o envio de uma mensagem para outro Thread geralmente bloqueia até que o script seja executado. E enquanto está bloqueando, nenhuma mensagem é processada; portanto, os dois Threads aguardam o outro processar sua mensagem.

Johannes Kuhn
fonte
Como é que isso funciona?
John Dvorak
thread::sendenfileira um script que deve ser executado em outro encadeamento e aguarde a conclusão. Assim, no final temos Tópico 1 de espera para Thread 2, e linha 2 de espera para a linha 1.
Johannes Kuhn
1

java alternativo com abuso de monitor (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
fonte
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

O bloco de inicialização do val preguiçoso suspende até que uma condição seja atendida. Essa condição só pode ser atendida com a leitura do valor de lazy val x - outro encadeamento que deve concluir essa condição não pode fazê-lo. Assim, uma dependência circular é formada e o val preguiçoso não pode ser inicializado.

Martin Seeler
fonte
Como é que isso funciona?
Addison Crump
Eu adicionei uma explicação.
Martin Seeler
1

Kotlin, 35/37/55 bytes

Tema geral: Thread.currentThread().join().

Excluindo bugs da JVM / código muito especializado contra esse envio, esse shoud nunca retorna, pois o encadeamento de execução atual agora está desativado, aguardando sua morte.


Propriedade inválida: 35 bytes (não concorrente): 35 bytes

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

Colocar isso em qualquer lugar onde uma declaração de propriedade é válida trará um impasse para quem a está inicializando. No caso de uma propriedade de nível superior, esse será o carregador de classes que inicializa a classe da JVM mapeada para esse arquivo (por padrão [file name]Kt.class).

Não concorrente porque "coloque isso como uma propriedade de nível superior em qualquer lugar" é restritivo.


Função: 37 bytes

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


main (): 55 bytes

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

F. George
fonte
1

PowerShell, 36 28 23 bytes

gps|%{$_.waitforexit()}

Auto-impasse. Recebemos todos os processos Get-Processe esperamos pacientemente que cada um deles saia ... o que acontecerá quase nunca, pois o processo estará esperando por si mesmo.

Editar - salvou 5 bytes graças a Roman Gräf

AdmBorkBork
fonte
(gps)|%{$_.waitforexit()}é três bytes mais curto e aguarda a saída de todos os processos.
Roman Gräf 28/11
@ RomanGräf De fato, mas não precisa de parênteses gpsnesse caso, então economizei 5 bytes no total.
AdmBorkBork 29/11
0

C (apenas Linux), 31 bytes - Experimente online!

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

A chamada do sistema 240 (0xf0) é futex (2) ou mutex de espaço de usuário rápido. A documentação afirma que o primeiro argumento é um ponteiro para o futex, o segundo argumento é a operação (0 significa FUTEX_WAIT, ou seja, aguarde até que outro thread desbloqueie o futex). O terceiro argumento é o valor que você espera que o futex tenha enquanto ainda está bloqueado, e o quarto é o ponteiro para o tempo limite (NULL sem tempo limite).

Obviamente, como não há outro segmento para desbloquear o futex, ele esperará para sempre em um impasse auto-infligido. Pode-se verificar (via topou outro gerenciador de tarefas) que o processo não utiliza tempo de CPU, como seria de esperar de um encadeamento em conflito.

servente
fonte
0

Julia 0.6 , 13 bytes

Idioma mais recente que a pergunta. Aguarde uma tarefa (como uma rotina de início), no momento, esteja no mesmo encadeamento; em versões futuras do Julia, pode estar em outro encadeamento) que não esteja agendado para execução.

wait(@task +)

Experimente online!

gggg
fonte
0

BotEngine, 3x3 = 9 (9 bytes)

v
lCv
> <

A etapa 5 termina com dois bots esperando indefinidamente um pelo outro se mover ... um bot não pode se mover porque está esperando o outro sair do quadrado inferior direito e o outro bot não pode se mover porque está esperando o botão primeiro bot a sair do quadrado central inferior.

SuperJedi224
fonte
0

O modelo em cascata (Ratiofall), 13 bytes

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

Experimente online!

Aqui está uma resposta divertida e inusitada. Esse é o loop infinito mais simples possível no modelo Waterfall (as variáveis ​​no modelo Waterfall diminuem repetidamente sempre que nada mais está acontecendo; esse programa define uma variável que se incrementa sempre que diminui, para que não ocorra nada).

A pergunta pede um impasse, não um loop infinito. No entanto, podemos explorar o comportamento de implementações específicas. No nível de otimização 2 ou superior (o padrão é 3), o intérprete Ratiofall detectará o loop infinito e o otimizará… em um impasse! Portanto, pelo menos se considerarmos as linguagens a serem definidas por sua implementação (que geralmente é o caso neste site), esse programa realmente define um impasse, em vez de um loop infinito.

Você pode ver evidências do impasse no relatório de tempo no Try it Online! link acima:

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

O programa foi executado por 60 segundos (até que o TIO o encerrasse automaticamente), mas na maior parte do tempo, não havia uso da CPU, tempo gasto pelo programa em execução e tempo gasto pelo kernel em nome do programa.

Para obter evidências ainda mais fortes, você pode executar o Ratiofall em um depurador no nível de chamada do sistema, como strace; fazer isso no Linux mostrará o intérprete bloqueado em uma futexchamada do sistema que tenta bloquear um bloqueio que nunca será liberado.

ais523
fonte
0

Perl 6 , 24 bytes

Semaphore.new(0).acquire

Experimente online!

Crie um semáforo com zero de permissão e tente adquiri-lo.

donaldh
fonte