Algoritmo "Bad apple" o processo si blocca nella sandbox condivisa

Question

Algoritmo "Bad apple" o processo si blocca nella sandbox condivisa

#1 da (2 voti)

9

Sto cercando un algoritmo per gestire il seguente problema, che sto (per ora) chiamando l'algoritmo "bad apple".

Il problema

Ho N processi in esecuzione in sandbox M, dove N > > M.
Non è pratico dare a ciascun processo la propria sandbox.
Almeno uno di questi processi si comporta male e sta facendo cadere l'intera sandbox, uccidendo così tutti gli altri processi nella stessa sandbox.

Se si trattasse di un singolo processo mal funzionante, potrei usare una bisezione semplice per mettere metà dei processi in una sandbox e metà in un'altra sandbox, finché non ho trovato il miscredente.

La domanda

Se più di un processo è maleducato - inclusa la possibilità che siano tutti male comportati - questo algoritmo ingenuo "funziona"? È garantito che funzioni entro limiti ragionevoli?

Semplificazioni

Per amor di argomenti, supponiamo che un processo non corretto porti giù la sua sandbox istantaneamente e che un buon processo non avvenga mai.

algorithms

posta Roger Lipscombe 30.10.2013 - 09:42

fonte

1 risposta

Leggi altre domande sui tag algorithms

Imitazione di "RBAC AuthZ" di Exchange Server nella mia applicazione ... (c'è qualcosa di simile?) Rotazione lessicografica più piccola di una stringa utilizzando matrici di suffissi in O (n)

score 2 · Answer 1

Se dovessi trovare una mela cattiva, potresti applicare l'algoritmo:

Dividi N in M gruppi
Esegui il test su ciascun gruppo.
Se la dimensione del gruppo è maggiore di 1, torna al passaggio 1, sostituendo N con il numero di elementi nel gruppo errato.

Allo stesso modo, se stai cercando l'unica mela "buona", allora si applica lo stesso algoritmo, ma piuttosto trovare il buon gruppo.

Questo algoritmo ha un tasso di prestazioni O (log_M (N)) ma dipende dal fatto che esiste solo una mela cattiva.

Se non sai quante mele buone / cattive ci sono, puoi utilizzare il seguente algoritmo:

For each M processes in N
  Test M processes

Questo è lo scenario peggiore, ma viene eseguito in O(N/M) time (o O(N) a seconda se si considera un singolo passaggio come test singolo o come raccolta di test eseguiti in parallelo). Tutto considerato, questo è non un cattivo approccio con qualsiasi mezzo.

Potrebbero esserci algoritmi che funzionano meglio di questo, ma richiede che tu sappia quante mele / mele buone sono presenti nel batch. Non conoscendo questo fattore, mentre non posso provarlo, sarei disposto a scommettere che non puoi fare meglio del secondo algoritmo sopra elencato.

Spero che ti aiuti!

Modifica : dal punto di vista pratico, comprendo che alcune di queste operazioni non sono facilmente eseguibili. È vero, tuttavia, la sfortunata realtà è che non è possibile determinare rigorosamente la mela cattiva da cui i processi erano in esecuzione sulla sandbox in esecuzione in quel momento senza essere almeno in grado di attivare o disattivare i processi. Se la domanda riguarda l'algoritmo, penso di averlo risposto. Se la domanda riguarda come affrontare una situazione come questa, allora forse la domanda sarebbe più adatta per il superuser SE.