Encontrando o impasse

18

Encontrando o impasse

Ao programar um aplicativo multithreading, é necessário tomar cuidado para evitar o bloqueio dos vários encadeamentos ao acessar recursos compartilhados. Um impasse ocorre quando um encadeamento tenta acessar um recurso bloqueado em outro encadeamento ao mesmo tempo em que o outro encadeamento está tentando acessar um recurso bloqueado pelo primeiro. Este é o caso simples, mas pode ficar mais complexo com cadeias de recursos mais longas.

O desafio

Você deve escrever um programa ou função que possa detectar uma possível situação de conflito em uma lista dos recursos acessados ​​por cada encadeamento. Isso é código-golfe, então a resposta mais curta em bytes vence.

Cada encadeamento é iniciado ao mesmo tempo, mas depois disso eles podem ser executados em qualquer combinação de intercalação. Se existem 2 fios com 4 acções cada, que poderia ser executado como (em que cada número é uma medida tomada pelo fio com 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, ou qualquer outra combinação possível.

Entrada

Você receberá, via STDIN, parâmetro de função ou alternativa mais próxima, uma lista de strings. Cada string estará no formato +a -b. Cada uma dessas seqüências representa o bloqueio ( +) / desbloqueio ( -) de um recurso pelo encadeamento. Entre cada thread haverá um ---separador. É garantido que um encadeamento não tente bloquear um recurso que já bloqueou e que todos os encadeamentos desbloqueará explicitamente todos os recursos que foram bloqueados antes de sair. A seguir, é apresentado um exemplo para demonstrar:

+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

Resultado

A saída será falsa se a entrada não contiver nenhuma possibilidade de conflito e, na verdade, se houver uma possível situação de conflito. Por exemplo:

  • true
  • false
  • 1
  • 0

são todas saídas válidas, mas qualquer coisa claramente definida como verdade / falsidade será aceita.

Exemplos

+a
-a
---
+a
-a

Resultado: false


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

Resultado true

Impasse ao tentar adquirir b,arespectivamente para threads1,2


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

Resultado false


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

Resultado: true

Impasse nos threads 1,2,3 ao tentar adquirir b,c,arespectivamente.


http://pastebin.com/vMYRZxtW

Resultado false


http://pastebin.com/V5MVgNgS

Resultado true

Impasse nos tópicos 1,2,3 ao tentar adquirir, b,d,arespectivamente.


É claro que isso pode ficar muito mais complexo, com mais threads, mais recursos para cada um e assim por diante, mas acredito que esses testes abrangem o básico.

Bônus

Como é muito triste quando você encontra situações de conflito ao escrever um programa, há um bônus de -8 bytes nas respostas que saem :(e :)como verdade / falsidade, respectivamente.

rorlork
fonte
Estou apenas supondo que isso, mas seria bom esclarecer que as ações de cada thread (a partir de topo da rosca) são executados paralelamente e correspondem à mesma hora do sistema
Optimizer
1
As ações são executadas simultaneamente, mas o tempo em que todas as ações são executadas não pode ser assumido. Pode ocorrer que os encadeamentos sejam realmente executados estritamente um após o outro ou completamente intercalados. Pode ser que a primeira metade do encadeamento 1 seja executada, o encadeamento 2 seja totalmente executado e o encadeamento 1 execute a segunda metade. E assim por diante. Atualizei a pergunta para esclarecer isso.
Rorlork 23/05
1
Ah, tudo bem, então a tarefa é descobrir que, dada qualquer combinação possível de tempos de execução do encadeamento, se é possível um conflito.
Optimizer
Sim, desculpe, não achei que isso pudesse deixar dúvidas. Na verdade, no último exemplo, isso é demonstrado, pois o encadeamento 2 não tenta usar o recurso daté mais tarde.
Rorlork 23/05
1
@rcrmn você tem certeza :)que não deve ser falso e :(verdadeiro?
Tyilo 23/05

Respostas:

4

Python 2-227

Basicamente, garante que não haja loops de 'precedência'. Por exemplo, no segundo teste, o primeiro thread tem uma a(b)precedência e o segundo thread tem uma b(a)precedência.

Eu estava pensando em reescrever isso no Pyth, pois acho que funcionaria bem com todas as operações de itertools, mas converter o regex levará algum trabalho. Por enquanto, postarei isso e talvez tente convertê-lo e postar outra resposta mais 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
fonte
Respostas falsas para pastebin.com/V5MVgNgS
Tyilo
@ Tyilo Ele gera True para mim; como exatamente você está executando?
KSab # 24/15
oh, estava lendo apenas uma linha para mim. Como você deve executá-lo?
Tyilo
@Tyilo eu mudei o formato a ser uma função que leva uma seqüência de várias linhas como entrada
KSab
5

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

Níveis de indentação:

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
fonte
1
Use ;para combinar linhas recuadas para salvar caracteres. Da mesma forma, faça suas declarações um forros.
Isaacg 23/05
@isaacg e ace, obrigado! Eu acho que melhorei o máximo que pude usando suas dicas.
Tyilo 23/05
BTW, se você não se importa canalizando a entrada de um arquivo (ou pressionando Ctrl + D duas vezes), então você pode fazer for r in sys.stdinem vez defor r in sys.stdin.readlines()
user12205
@ace Não vejo nenhum comportamento diferente entre usar apenas sys.stdinou sys.stdin.readlines(), então mudei, obrigado novamente.
Tyilo 23/05
Você pode remover os espaços entre printe':)'
user12205 23/05