El código más corto que crea un punto muerto

11

Escribe el código más corto para crear un punto muerto . La ejecución del código debe detenerse, por lo que esto no funciona:

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

No es necesario estar seguro de que el código entra en un punto muerto , casi con seguridad (si se ejecuta por tiempo infinito, se cerrará).

Justin
fuente
¿Cuenta como un punto muerto si intento bloquear el mismo bloqueo (no reentrante) dos veces desde el mismo hilo? (lo siento, no me di cuenta de esta pregunta en el sandbox)
John Dvorak
@ JanDvorak ¿Eso crea una situación en la que la ejecución del código se detiene porque un subproceso está esperando algo que no puede obtener (porque otro lo retiene y espera lo que tiene el primer subproceso)? ¿O es un hilo? Si puede crear tal situación con un hilo, entonces está bien. Lea el artículo de wikepedia sobre punto muerto, eso es lo que espero.
Justin
2
Code execution must haltNo entiendo. ¿Cómo es un punto muerto si se detiene? ¿Quieres decir que estará esperando algo en lugar de simplemente girar como un imbécil?
Cruncher
@Cruncher Eche un vistazo al ejemplo que no funciona. La ejecución del código no se detiene porque el bucle sigue ejecutándose. Sí, me refiero a esperar en lugar de girar.
Justin
Entonces, si puede hacer que el hilo de la interfaz de usuario se espere solo en Dyalog APL, ¿eso significa que hay alguna esperanza de obtener una respuesta de JavaScript? Aunque sospecho que ese tipo de pensamiento simplemente abriría la puerta a esta respuesta: Javascript 6 "wait ()" ... ermmm. No. Relacionado: ¿Es posible que un hilo a Deadlock mismo?
Nathan Cooper el

Respuestas:

11

Dyalog APL (10)

⎕TSYNC⎕TID

⎕TSYNChace que el hilo espere hasta que termine el hilo dado, ⎕TIDda el hilo actual.

Sin embargo, Dyalog APL puede reconocer puntos muertos, por lo que responde inmediatamente con

DEADLOCK

Lo divertido es que ni siquiera necesita generar hilos adicionales, por lo que el hilo de la interfaz de usuario espera por sí solo es suficiente.

Si esto es trampa y realmente se requieren nuevos hilos, puede hacerlo en 27 caracteres:

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

F & xse ejecuta Fen un nuevo hilo en el valor xy devuelve la ID del hilo. Entonces:

  • {⎕TSYNC⎕TID+1}&0 crea un hilo que se sincronizará con el hilo cuyo ID es uno más alto que el suyo,
  • ⎕TSYNC& crea un nuevo subproceso que se sincronizará con el subproceso anterior, y que obtiene una ID más alta que el subproceso que se acaba de crear (suponiendo que nada más esté creando subprocesos).
  • provoca un bucle infinito (por lo que seguimos creando hilos hasta que hay un punto muerto).

Esto se bloqueará tan pronto como se cree el segundo subproceso antes de que comience el primero, que es bastante pronto:

9:DEADLOCK
marinus
fuente
Ahorre 2 bytes con: ⎕TSYNC 0'. ⎕TID` es 0.
Adám
8

Go, 42

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

Disculpas, downvoter, por no proporcionar cómo funciona. Esto crea un canal anónimo de entradas y lee de él. Esto detiene el subproceso principal hasta que se envía un valor por el canal, lo que obviamente nunca sucede, ya que no hay otros subprocesos activos y, por lo tanto, punto muerto.

Alex Ozer
fuente
2
¿Como funciona?
Justin
4

Ruby, 39 caracteres

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

La idea de usar una unión cruzada robada descaradamente de la respuesta Java de Johannes Kuhn .

Podemos eliminar cuatro caracteres (llegando a 35 ) si ajustamos el código a un entorno específico. La consola IRB de JRuby es de un solo subproceso:

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


Esta es mi solución anterior:

conseguir un hilo atascado en un mutex es fácil:

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

pero este no es un punto muerto adecuado, porque el segundo hilo técnicamente no está esperando el primer hilo. "mantener y esperar" es una condición necesaria para un punto muerto según Wikipedia. El primer hilo no espera, y el segundo hilo no contiene nada.

Rubí, 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 es un punto muerto clásico. Dos hilos compiten por dos recursos, reintentando si tienen éxito. Normalmente se atascan en un segundo en mi máquina.

Pero, si tiene infinidad de hilos (ninguno de los cuales consume CPU infinitamente y algunos de los cuales están en punto muerto) está bien,

Rubí, 87 85 caracteres

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

Según mi prueba, falla después de que el recuento de subprocesos alcanza aproximadamente 4700. Esperemos que no falle hasta que cada subproceso tenga la oportunidad de ejecutarse (por lo tanto, bloqueo o finalización y liberación de espacio para uno nuevo). Según mi prueba, el recuento de subprocesos no disminuye después de que ocurre la falla, lo que significa que se produjo un punto muerto durante la prueba. Además, IRB murió después de la prueba.

John Dvorak
fuente
¿por qué necesita el extra oy pvariables? ¿No puedes pasar my npor el nuevo hilo?
Johannes Kuhn el
@JohannesKuhn my nson globales. Ambos hilos los ven en el mismo orden. oy pson subprocesos locales (en el ámbito de la iteración del bucle). El uso t[...]probablemente se volvería costoso, y no puedo ver una mejor manera de pasar parámetros al hilo que a través del cierre. Agregar parámetros adicionales para newalargar el código en dos caracteres.
John Dvorak
@JohannesKuhn Espero que no te importe, tomé prestada parte de tu lógica
John Dvorak
No me importa Buen trabajo.
Johannes Kuhn el
Si asumimos que estamos en el hilo principal, podemos reducir esto a 32 caracteres conT=Thread;T.new{T.main.join}.join
histocrat
4

Python, 46

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

(autobloqueo)

Sneftel
fuente
1
from threading import* Semaphore(0).acquire()es más corto por un byte, creo
Roman Gräf
@Roman Sí, es más corto y funciona. tio.run/##K6gsycjPM/r/…
mbomb007
4

Bash + GNU coreutils, 11 bytes

mkfifo x;<x

Crea una FIFO perdida xen el directorio actual (por lo que no deberá tener un archivo con ese nombre). Los FIFO se pueden eliminar de la misma manera que los archivos normales, por lo que no debería ser difícil de eliminar.

Un FIFO tiene un lado de escritura y un lado de lectura; intentar abrir un bloque hasta que otro proceso abra el otro, y esto parece haber sido diseñado intencionalmente como una primitiva de sincronización. Dado que solo hay un hilo aquí, tan pronto como intentamos abrirlo <x, nos quedamos atascados. (Puede despegar el punto muerto mediante otro proceso escrito al FIFO en cuestión).

Este es un tipo de punto muerto diferente del que hay cuando hay dos recursos, y dos hilos tienen uno y necesitan el otro; más bien, en este caso, hay cero recursos y el proceso necesita uno. Basado en las otras respuestas, creo que esto cuenta, pero puedo entender cómo un purista de punto muerto podría querer rechazar la respuesta.

Ahora que lo pienso, en realidad puedo pensar en tres situaciones de punto muerto:

  1. El punto muerto "tradicional": dos subprocesos están esperando que se libere un bloqueo, que está retenido por el otro subproceso.

  2. Un solo subproceso está esperando que se libere un bloqueo, pero retiene el bloqueo en sí (y, por lo tanto, se bloquea para que no se pueda liberar).

  3. Un solo subproceso está esperando que se libere una primitiva de sincronización, pero la primitiva de sincronización comienza en un estado bloqueado naturalmente y tiene que desbloquearse externamente, y no se ha programado nada para hacerlo.

Este es un punto muerto de tipo 3, que es fundamentalmente diferente de los otros dos: en teoría, podría escribir un programa para desbloquear la primitiva de sincronización en cuestión y luego ejecutarlo. Dicho esto, lo mismo se aplica a los puntos muertos de tipo 1 y 2, dado que muchos idiomas le permiten liberar un bloqueo que no es de su propiedad (se supone que no debe hacerlo y no tendría ninguna razón para hacerlo si tuviera una razón para hacerlo). use las cerraduras en primer lugar, pero funciona ...). Además, vale la pena considerar un programa comomkfifo x;<x;echo test>x; ese programa es más o menos lo opuesto a un punto muerto de tipo 2 (está tratando de abrir ambos extremos del FIFO, pero no puede abrir un extremo hasta después de abrir el otro extremo), pero se hizo a partir de este agregando más código que nunca se ejecuta después de este! Supongo que el problema es que si un bloqueo está bloqueado o no depende de la intención detrás del uso del bloqueo, por lo que es difícil de definir objetivamente (especialmente en un caso como este donde el único propósito del bloqueo es producir un bloqueo intencionalmente )


fuente
2

C #, 100

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

Ver: el punto muerto sin bloqueo

Johnbot
fuente
1
¿No puedes mover las cosas de static Ca Main?
Roman Gräf
2

Bash con glibc, 6 bytes

Lamento revivir un hilo viejo, pero no pude resistirme.

Como root:

pldd 1

Del hombre pldd :

ERRORES
Desde glibc 2.19, pldd está roto: simplemente se cuelga cuando se ejecuta. No está claro si alguna vez se solucionará.

jasonwilkes
fuente
No hay ningún problema con responder en una banda de rodamiento antigua siempre que el original no sea sensible al tiempo.
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){}}}

Sin golf:

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 un nuevo hilo y joinen él (espere hasta que este hilo haya terminado), mientras que el nuevo hilo hace lo mismo con el hilo original.

Johannes Kuhn
fuente
¿Puedes hacerlo más corto lanzando y atrapando en Errorlugar de Exception?
mbomb007
No Thread.join()arroja un InteruptedException, que no es una subclase de Error.
Johannes Kuhn
2

Tcl, 76

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

Punto muerto.

Esto crea un nuevo hilo y le dice al otro hilo que envíe un mensaje a mi hilo (secuencia de comandos para ejecutar).

Pero enviar un mensaje a otro subproceso generalmente bloquea hasta que se haya ejecutado el script. Y mientras se está bloqueando, no se procesan mensajes, por lo que ambos subprocesos esperan que el otro procese su mensaje.

Johannes Kuhn
fuente
¿como funciona esto?
John Dvorak
thread::sendpone en cola un script que debe ejecutarse en otro subproceso y espera a que se complete. Así que al final tenemos el Hilo 1 esperando el Hilo 2, y el Hilo 2 esperando el Hilo 1.
Johannes Kuhn
1

Java alternativo con 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
fuente
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

El bloque de inicialización val perezoso se suspende hasta que se cumpla una condición. Esta condición solo puede cumplirse leyendo el valor de lazy val x: otro hilo que se supone que completa esta condición no puede hacerlo. Por lo tanto, se forma una dependencia circular y el vago val no se puede inicializar.

Martin Seeler
fuente
¿Como funciona esto?
Addison Crump
Agregué una explicación.
Martin Seeler
1

Kotlin, 35/37/55 bytes

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

Excluyendo errores de JVM / código muy especializado en contra de esta presentación, esto nunca debería volver ya que el hilo de ejecución actual ahora está deshabilitado esperando que muera.


Propiedad malvada: 35 bytes (no competitiva): 35 bytes

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

Poner esto en cualquier lugar donde una declaración de propiedad sea válida bloqueará a quien la esté inicializando. En el caso de una propiedad de nivel superior, ese será el cargador de clases que inicializa la clase JVM asignada para ese archivo (de forma predeterminada [file name]Kt.class).

No competir porque "poner esto como una propiedad de nivel superior en cualquier lugar" es restrictivo.


Función: 37 bytes

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


main (): 55 bytes

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

F. George
fuente
1

PowerShell, 36 28 23 bytes

gps|%{$_.waitforexit()}

Auto-punto muerto. Recibimos todos los procesos Get-Processy luego esperamos pacientemente a que cada uno de ellos salga ... lo que sucederá aproximadamente nunca, ya que el proceso se esperará solo.

Editar - Guardado 5 bytes gracias a Roman Gräf

AdmBorkBork
fuente
(gps)|%{$_.waitforexit()}es tres bytes más corto y espera a que todos los procesos salgan.
Roman Gräf
@ RomanGräf De hecho, pero no necesito los padres gpsen ese caso, por lo que ahorró 5 bytes en total.
AdmBorkBork
0

C (solo Linux), 31 Bytes - ¡ Pruébelo en línea!

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

La llamada al sistema 240 (0xf0) es futex (2) , o mutex de espacio de usuario rápido. La documentación indica que el primer argumento es un puntero al futex, el segundo argumento es la operación (0 significa FUTEX_WAIT, es decir, espere hasta que otro hilo desbloquee el futex). El tercer argumento es el valor que espera que tenga el futex mientras está bloqueado, y el cuarto es el puntero al tiempo de espera (NULL sin tiempo de espera).

Obviamente, dado que no hay otro hilo para desbloquear el futex, esperará para siempre en un punto muerto autoinfligido. Se puede verificar (a través de topu otro administrador de tareas) que el proceso no utiliza tiempo de CPU, como deberíamos esperar de un subproceso bloqueado.

maservant
fuente
0

Julia 0.6 , 13 bytes

Idioma más nuevo que la pregunta. Espere una tarea (como una rutina de inicio, actualmente estará en el mismo hilo, en futuras versiones de Julia puede estar en otro hilo) que no está programada para ejecutarse.

wait(@task +)

Pruébalo en línea!

gggg
fuente
0

BotEngine, 3x3 = 9 (9 bytes)

v
lCv
> <

El paso 5 termina con dos bots que esperan indefinidamente que el otro se mueva ... uno no puede moverse porque está esperando que el otro salga del cuadro inferior derecho, y el otro bot no puede moverse porque está esperando primer bot que se mueve fuera del cuadrado central inferior.

SuperJedi224
fuente
0

El modelo de cascada (Ratiofall), 13 bytes

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

Pruébalo en línea!

Aquí hay una divertida respuesta extravagante. Este es el bucle infinito más simple posible en The Waterfall Model (las variables en The Waterfall Model disminuyen repetidamente cada vez que no sucede nada más; este programa define una variable que se incrementa cada vez que disminuye, por lo que no hay forma de que algo pueda suceder).

La pregunta pide un punto muerto, no un bucle infinito. Sin embargo, podemos explotar el comportamiento de implementaciones específicas. En el nivel de optimización 2 o superior (el valor predeterminado es 3), el intérprete Ratiofall detectará el bucle infinito y lo optimizará ... ¡hasta un punto muerto! Entonces, al menos si consideramos que los idiomas se definen por su implementación (que suele ser el caso en este sitio), este programa define un punto muerto, en lugar de un bucle infinito.

¡Puede ver evidencia del punto muerto en el informe de tiempo en Try it Online! enlace de arriba:

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

El programa se ejecutó durante 60 segundos (hasta que TIO lo finalizó automáticamente), pero durante la mayor parte de ese tiempo, no hubo uso de CPU, no pasó tiempo ejecutando el programa y el kernel no dedicó tiempo en nombre del programa.

Para obtener evidencia aún más sólida, puede ejecutar Ratiofall bajo un depurador de nivel de llamada del sistema como strace; Al hacer esto en Linux, se mostrará el bloqueo del intérprete en una futexllamada al sistema que intenta tomar un bloqueo que nunca se liberará.

ais523
fuente