Encontrar el punto muerto

18

Encontrar el punto muerto

Al programar una aplicación de subprocesos múltiples, se debe tener mucho cuidado para evitar interbloquear los diversos subprocesos al acceder a recursos compartidos. Un punto muerto se produce cuando un hilo intenta acceder a un recurso que está bloqueado en otro hilo al mismo tiempo que el otro hilo intenta acceder a un recurso bloqueado por el primero. Este es el caso simple, pero puede volverse más complejo con cadenas de recursos más largas.

El reto

Debe escribir un programa o función que pueda detectar una posible situación de punto muerto en una lista de los recursos a los que accede cada subproceso. Este es el código de golf, por lo que la respuesta más corta en bytes gana.

Cada subproceso se inicia al mismo tiempo, pero después de eso pueden ejecutarse en cualquier combinación de intercalado. Si hay 2 hilos con 4 acciones cada una, que podría ser ejecutado como (donde cada número es una acción tomada por el hilo con que id) 1,1,1,1,2,2,2,2, 2,2,2,2,1,1,1,1, 1,2,1,2,1,2,1,2, 1,1,2,2,2,2,1,1, o cualquier otra combinación posible.

Entrada

Recibirá, a través de STDIN, el parámetro de función o la alternativa más cercana, una lista de cadenas. Cada cadena estará en el formato +a -b. Cada una de estas cadenas representa el bloqueo ( +) / desbloqueo ( -) de un recurso por el hilo. Entre cada hilo habrá un ---separador. Se garantiza que un hilo no intentará bloquear un recurso que ya ha bloqueado, y que todos los hilos desbloquearán explícitamente todos los recursos que han bloqueado antes de salir. El siguiente es un ejemplo para demostrar:

+a    # Lock resource a
+b    # Lock resource b
-a    # Unlock resource a
-b    # Unlock resource b
---   # Thread separator
+b    # Lock resource b
-b    # Unlock resource b

Salida

La salida será falsa si la entrada no contiene ninguna posibilidad de punto muerto, y verdadera si contiene una posible situación de punto muerto. Por ejemplo:

  • true
  • false
  • 1
  • 0

son todas las salidas válidas, pero se aceptará cualquier cosa claramente definida como verdadero / falso.

Ejemplos

+a
-a
---
+a
-a

Salida: false


+a
+b
-b
-a
---
+b
+a
-a
-b

Salida true

Punto muerto al intentar adquirir b,arespectivamente hilos1,2


+a
+b
-a
-b
---
+a
+b
-b
-a

Salida false


+a
+b
-b
-a
---
+b
+c
-c
-b
---
+c
+a
-a
-c

Salida: true

Punto muerto en hilos 1,2,3 al intentar adquirir b,c,arespectivamente.


http://pastebin.com/vMYRZxtW

Salida false


http://pastebin.com/V5MVgNgS

Salida true

Punto muerto en hilos 1,2,3 al intentar adquirir b,d,arespectivamente.


Por supuesto, esto podría ser mucho más complejo, con más hilos, más recursos para cada uno, etc., pero creo que estas pruebas cubren los conceptos básicos.

Prima

Dado que es muy muy triste cuando encuentras situaciones de punto muerto cuando escribes un programa, hay un bono de -8 bytes para las respuestas que salen :(y :)como verdadero / falso respectivamente.

rorlork
fuente
Solo estoy asumiendo esto, pero sería bueno aclarar que las acciones de cada hilo (comenzando desde la parte superior del hilo) se ejecutan en paralelo y corresponden a la misma hora del sistema
Optimizer
1
Las acciones se ejecutan simultáneamente, pero no se puede suponer el tiempo en que se ejecuta cada acción. Podría ocurrir que los hilos se ejecuten estrictamente uno después del otro o completamente intercalados. Puede ser que la primera mitad del subproceso 1 se ejecute, luego el subproceso 2 se ejecute por completo, luego el subproceso 1 ejecute su segunda mitad. Y así. He actualizado la pregunta para aclarar eso.
rorlork
1
Ah, está bien, así que la tarea es descubrir que, dada cualquier combinación posible de tiempos de ejecución de subprocesos, si es posible un punto muerto.
Optimizador
Sí, lo siento, no pensé que eso pudiera dejar dudas. En realidad, en el último ejemplo, esto se demuestra ya que el hilo 2 no intenta usar recursos dhasta más tarde.
rorlork
1
@rcrmn, ¿estás seguro de :)que no debería ser falso ni :(verdadero?
Tyilo

Respuestas:

4

Python 2 - 227

Básicamente se asegura de que no haya bucles de 'precedencia'. Por ejemplo, en la segunda prueba, el primer subproceso tiene a(b)prioridad y el segundo subproceso tiene b(a)prioridad.

Estaba pensando en reescribir esto en Pyth, ya que creo que funcionaría bien con todas las operaciones de itertools, pero convertir la expresión regular tomará algo de trabajo, por lo que por ahora publicaré esto y tal vez intente convertirlo y publique otra respuesta más tarde.

from itertools import*
import re
f=lambda t:any(re.search(r"(.)((.)\3)+\1",''.join(p))for i in product(*[[m.group(1)+m.group(2)for m in re.finditer(r"(\w).*(\w).*\2.*\1",e,16)]for e in t.split('---')])for p in permutations(i))
KSab
fuente
Esto responde falso a pastebin.com/V5MVgNgS
Tyilo
@Tyilo Produce True para mí; ¿cómo lo estás ejecutando exactamente?
KSab
oh, solo estaba leyendo una línea para mí. ¿Cómo se supone que lo ejecutes?
Tyilo
@Tyilo Cambié el formato para que sea una función que toma una cadena multilínea como entrada
KSab
5

Python - 586 539 524 501 485 bytes - 8 = 477

Niveles de sangría:

1: 1 space
2: 1 tab
3: 1 tab + 1 space
4: 2 tabs

-

import sys
V=set()
t=[[[]]]
for r in sys.stdin:
 r=r.strip()
 if'---'==r:t.append([[]])
 else:v=r[1:];V.add(v);l=t[-1][-1];t[-1].append(l+[v]if'+'==r[0]else filter(lambda x:x!=v,l))
s=lambda l:s(l[1:])+map(lambda x:(l[0],x),l[1:])if 1<len(l)else[]
E=reduce(set.union,map(lambda x:set(sum(map(s,x),[])),t),set())
for v in V:
 k=set();q=[v]
 while 0<len(q):
    u=q.pop(0)
    if u in k:continue
    k.add(u)
    for x,y in E:
     if u==x:
        if y in k:print':(';sys.exit()
        else:q.append(y)
print':)'
Tyilo
fuente
1
Se usa ;para combinar líneas con sangría para guardar caracteres. Del mismo modo, haga sus afirmaciones una línea.
isaacg
@isaacg y as, ¡Gracias! Creo que lo mejoré tanto como pude con tus consejos.
Tyilo
Por cierto, si no le importa canalizar la entrada de un archivo (o presionar Ctrl + D dos veces), puede hacerlo en for r in sys.stdinlugar defor r in sys.stdin.readlines()
user12205
@ace No veo ningún comportamiento diferente entre usar just sys.stdino sys.stdin.readlines(), así que lo he cambiado, gracias de nuevo.
Tyilo
Puede eliminar los espacios entre printy':)'
user12205