Algoritmo de "manzana defectuosa", o el proceso bloquea la caja de arena compartida

9

Estoy buscando un algoritmo para manejar el siguiente problema, que estoy llamando (por ahora) al algoritmo de "manzana podrida".

El problema

  • Tengo N procesos ejecutándose en M sandboxes, donde N >> M.
  • No es práctico dar a cada proceso su propia caja de arena.
  • Al menos uno de esos procesos se comporta mal y está haciendo caer todo el entorno limitado, matando así a todos los demás procesos en el mismo entorno limitado.

Si se tratara de un solo proceso de mal comportamiento, entonces podría usar una bisección simple para colocar la mitad de los procesos en una caja de arena, y la otra mitad en otra caja de arena, hasta que encuentre el malhechor.

La pregunta

Si más de un proceso se comporta mal, incluida la posibilidad de que todos se comporten mal, ¿este ingenuo algoritmo "funciona"? ¿Se garantiza que funcione dentro de algunos límites razonables?

Simplificaciones

En aras de la discusión, supongamos que un mal proceso derriba su caja de arena instantáneamente, y un buen proceso nunca lo hace.

algorithms Roger Lipscombe
fuente
Cómo garantizado es que el proceso se comportaron mal- será llevar la caja de arena hacia abajo? Quiero decir, ¿podemos suponer un tiempo finito cuando sabemos con certeza que dado sandbox ejecuta solo procesos "limpios" porque no se bloqueó?
SF.
Lamentablemente no: el hecho de que un sandbox no se bloquee durante 5 minutos no significa que todos los procesos se comporten bien, pero sí nos da más confianza en ese hecho.
Roger Lipscombe
... pero para los propósitos de esta pregunta, podríamos aproximarnos permitiendo un tiempo finito, supongo.
Roger Lipscombe
Debe atomizar lo que considera un proceso "aprobado" y "fallido". Si se ejecuta 5 minutos sin fallar, técnicamente podría ser una manzana podrida, pero, al igual que el problema de la detención, nunca tendrá 100% de certeza cuando pase sin hacer algunas líneas duras en la arena.
Neil
Parece que estás en el camino correcto. Si hay muchos procesos y varias manzanas podridas, entonces es posible que tenga que usar un gran valor de M, o grupos desiguales para poder aislar las manzanas buenas conocidas, luego mantenga el bien conocido en una caja de arena y siga dividiendo los procesos desconocidos entre sus otras cajas de arena hasta que haya identificado a los individuos. Cuantos más sandboxes tenga, más rápido será. Como señaló @Neil, este es un gran algoritmo O de base de registro M de N, por lo que aumentar M reducirá sus pruebas.
GlenPeterson

Respuestas:

2

Si estaba encontrando una manzana podrida, entonces podría aplicar el algoritmo:

  1. Divide N en grupos M
  2. Realice la prueba en cada grupo.
  3. Si el tamaño del grupo es mayor que 1, regrese al paso 1, reemplazando N con el número de elementos en el grupo incorrecto.

Del mismo modo, si estaba encontrando la única manzana "buena", entonces se aplica el mismo algoritmo, pero en lugar de encontrar el buen grupo.

Este algoritmo tiene una tasa de rendimiento O (log_M (N)) pero depende del hecho de que solo hay una manzana defectuosa.

Si no sabe cuántas manzanas buenas / malas hay, entonces podría usar el siguiente algoritmo:

For each M processes in N
  Test M processes

Este es el peor de los casos, pero se ejecuta a O(N/M)tiempo (o O(N)dependiendo de si considera un solo pase como una sola prueba o como una colección de pruebas realizadas en paralelo). A fin de cuentas, este no es un mal enfoque de ninguna manera.

Puede haber algoritmos que funcionen mejor que esto, pero requiere que sepa cuántas manzanas malas / buenas hay en el lote. Sin conocer este factor, aunque no puedo probarlo, estaría dispuesto a apostar que no puede hacerlo mejor que el último algoritmo mencionado anteriormente.

¡Espero que ayude!

Editar : Desde una perspectiva práctica, entiendo que algunas de estas operaciones no se realizan fácilmente. Eso es cierto, sin embargo, la desafortunada realidad es que no se puede determinar la manzana defectuosa estrictamente desde qué procesos se estaban ejecutando en el sandbox que se estaba ejecutando en ese momento sin ser al menos activar o desactivar procesos. Si la pregunta se refiere al algoritmo, creo que he respondido eso. Si la pregunta se refiere a cómo lidiar con una situación como esta, entonces tal vez la pregunta sería más adecuada para el superusuario SE.

Neil
fuente
1
Desafortunadamente, no puedo "probar" los procesos; Todo lo que sé es que uno de los sandboxes se estrelló, y que fue causado por uno o más de los procesos en él.
Roger Lipscombe
1
El problema es que, después de dividir el conjunto, ambas particiones podrían tener manzanas podridas. Lo que me hace pensar que necesito más que una simple partición ...
Roger Lipscombe
@RogerLipscombe Estás intentando aplicar un algoritmo a un escenario del mundo real. Por supuesto, no podrá probar los procesos uno a la vez, y puede resultar difícil probar estos procesos en diferentes máquinas, sin embargo, si desea llegar al fondo de esto, va a tiene que encontrar una manera de una manera u otra. Si inserta variables que no se pueden resolver, simplemente no podrá encontrar un algoritmo que pueda identificar con precisión las manzanas defectuosas.
Neil
OK, entonces, por "prueba", simplemente te refieres a "dejarlos funcionando el tiempo suficiente para tener confianza" ...?
Roger Lipscombe
@RogerLipscombe, supongo que sí. Puede tomar más tiempo, pero usted es el que tiene que calcular cuánto tiempo esperar. Sabiendo eso y siguiendo este algoritmo, técnicamente podrías descubrir todas y cada una de las manzanas podridas. Sin embargo, puede ser más rápido simplemente mirar el registro de eventos de Windows para detectar fallas.
Neil