Algoritmo "maçã ruim" ou processo travar sandbox compartilhado

9

Estou procurando um algoritmo para lidar com o seguinte problema, que estou (por enquanto) chamando de algoritmo "maçã ruim".

O problema

  • Eu tenho N processos em execução em M sandboxes, onde N >> M.
  • Não é prático atribuir a cada processo sua própria caixa de proteção.
  • Pelo menos um desses processos é mal comportado e reduz a caixa de areia inteira, matando todos os outros processos na mesma caixa de areia.

Se fosse um único processo mal comportado, eu poderia usar uma simples bissecção para colocar metade dos processos em uma caixa de areia e metade em outra caixa de areia, até encontrar o mal-entendido.

A questão

Se mais de um processo é mal comportado - incluindo a possibilidade de que todos sejam mal comportados - esse algoritmo ingênuo "funciona"? É garantido que funcione dentro de alguns limites razoáveis?

Simplificações

Por uma questão de argumento, vamos supor que um processo ruim reduz sua caixa de areia instantaneamente, e um bom processo nunca ocorre.

algorithms Roger Lipscombe
fonte
Como garantido é que o processo mal-comportado vai trazer o baixo sandbox? Quero dizer - podemos assumir um tempo finito quando sabemos com certeza que a sandbox está executando apenas processos "limpos" porque não travou?
SF.
Infelizmente não: o fato de uma sandbox não travar por 5 minutos não significa que todos os processos sejam bem-comportados, mas nos dá mais confiança nesse fato.
Roger Lipscombe
... mas, para os fins desta pergunta, poderíamos aproximar-se, permitindo um tempo finito, eu acho.
Roger Lipscombe
Você precisa atomizar o que considera um processo "aprovado" e "com falha". Se durar 5 minutos sem falhar, ainda pode ser uma maçã ruim tecnicamente, mas, como o problema da interrupção, você nunca terá 100% de certeza quando passar sem fazer algumas linhas duras na areia.
Neil
Parece que você está no caminho certo. Se houver muitos processos e várias maçãs defeituosas, talvez você precise usar um grande valor de M ou grupos desiguais para poder isolar maçãs boas conhecidas, mantenha o bem conhecido em uma caixa de proteção e divida os processos desconhecidos entre suas outras caixas de areia até identificar os indivíduos. Quanto mais caixas de areia você tiver, mais rápido será. Como o @Neil apontou, este é um grande O da base logarítmica M de N, portanto o aumento de M reduzirá suas tentativas.
GlenPeterson

Respostas:

2

Se você estava encontrando uma maçã defeituosa, poderia aplicar o algoritmo:

  1. Divida N em grupos M
  2. Faça o teste em cada grupo.
  3. Se o tamanho do grupo for maior que 1, retorne à etapa 1, substituindo N pelo número de itens no grupo incorreto.

Da mesma forma, se você estava encontrando a maçã "boa", aplica-se o mesmo algoritmo, mas, em vez disso, encontra o grupo bom.

Esse algoritmo tem uma taxa de desempenho O (log_M (N)), mas depende do fato de que há apenas uma maçã defeituosa.

Se você não souber quantas maçãs boas / ruins existem, poderá usar o seguinte algoritmo:

For each M processes in N
  Test M processes

Esse é o pior cenário, mas é executado no O(N/M)tempo (ou O(N)dependendo de você considerar uma única passagem como um único teste ou como uma coleção de testes executados em paralelo). Tudo considerado, esta não é uma abordagem ruim, por qualquer meio.

Pode haver algoritmos com desempenho melhor que isso, mas exige que você saiba quantas maçãs ruins / maçãs boas existem no lote. Sem conhecer esse fator, embora eu não possa provar isso, eu estaria disposto a apostar que você não pode fazer melhor do que o último algoritmo listado acima.

Espero que ajude!

Edit : Do ponto de vista prático, entendo que algumas dessas operações não são executadas facilmente. Isso é verdade, no entanto, a realidade lamentável é que você não pode determinar estritamente a maçã podre a partir da qual os processos estavam sendo executados na caixa de areia que estava sendo executada naquele momento, sem pelo menos ativar ou desativar os processos. Se a pergunta pertence ao algoritmo, acho que respondi a isso. Se a pergunta diz respeito a como lidar com uma situação como essa, talvez a pergunta seja mais adequada ao superusuário SE.

Neil
fonte
11
Infelizmente, não posso "testar" os processos; tudo o que sei é que uma das caixas de areia caiu e foi causada por um ou mais dos processos nela.
Roger Lipscombe
11
O problema é que, depois de dividir o conjunto, as duas partições podem ter maçãs ruins. O que me faz pensar que eu preciso de mais do que uma partição simples ...
Roger Lipscombe
@RogerLipscombe Você está tentando aplicar um algoritmo a um cenário do mundo real. É claro que você não poderá testar os processos um de cada vez, e pode ser difícil testá-los em máquinas diferentes; no entanto, se você quiser chegar ao fundo disso, precisará tem que encontrar uma maneira de uma maneira ou de outra. Se você inserir variáveis ​​que não podem ser resolvidas, simplesmente não conseguirá encontrar um algoritmo que possa identificar com precisão as maçãs ruins.
Neil
OK, então por "teste", você quer dizer apenas "deixá-los funcionando por tempo suficiente para ter confiança" ...?
Roger Lipscombe
@RogerLipscombe Suponho que sim. Pode levar mais tempo, mas você é quem precisa descobrir quanto tempo esperar. Sabendo disso e seguindo esse algoritmo, você pode descobrir tecnicamente toda e qualquer má maçã. No entanto, pode ser mais rápido simplesmente olhar para o log de eventos do Windows quanto a falhas.
Neil