"Bad Apple" -Algorithmus oder Prozessabsturz gemeinsam genutzte Sandbox

9

Ich suche nach einem Algorithmus, um das folgende Problem zu lösen, das ich (vorerst) den "Bad Apple" -Algorithmus nenne.

Das Problem

  • Ich habe N Prozesse in M ​​Sandboxen ausgeführt, wobei N >> M.
  • Es ist unpraktisch, jedem Prozess einen eigenen Sandkasten zu geben.
  • Mindestens einer dieser Prozesse verhält sich schlecht und bringt die gesamte Sandbox zum Erliegen, wodurch alle anderen Prozesse in derselben Sandbox beendet werden.

Wenn es sich um einen einzelnen Prozess mit schlechtem Verhalten handelte, konnte ich eine einfache Halbierung verwenden, um die Hälfte der Prozesse in einen Sandkasten und die Hälfte in einen anderen Sandkasten zu legen, bis ich den Schurken fand.

Die Frage

Wenn sich mehr als ein Prozess schlecht verhält - einschließlich der Möglichkeit, dass sie sich alle schlecht verhalten - "funktioniert" dieser naive Algorithmus? Funktioniert es garantiert innerhalb einiger vernünftiger Grenzen?

Vereinfachungen

Nehmen wir aus Gründen der Argumentation an, dass ein schlechter Prozess seine Sandbox sofort herunterfährt und ein guter Prozess niemals.

algorithms Roger Lipscombe
quelle
Wie garantiert ist , dass der schlecht erzogene Prozess wird die Sandbox nach unten bringen? Ich meine - können wir eine endliche Zeit annehmen, wenn wir sicher wissen, dass eine bestimmte Sandbox nur "saubere" Prozesse ausführt, weil sie nicht abgestürzt ist?
SF.
Leider nicht: Die Tatsache, dass eine Sandbox 5 Minuten lang nicht abstürzt, bedeutet nicht, dass sich alle Prozesse gut verhalten, aber es gibt uns mehr Vertrauen in diese Tatsache.
Roger Lipscombe
... aber für die Zwecke dieser Frage könnten wir uns annähern, indem wir eine endliche Zeit einräumen, denke ich.
Roger Lipscombe
Sie müssen das atomisieren, was Sie als "bestanden" und "fehlgeschlagen" betrachten. Wenn es 5 Minuten ohne Fehler läuft, könnte es technisch gesehen immer noch ein schlechter Apfel sein, aber wie beim Anhalten des Problems werden Sie nie 100% ige Sicherheit haben, wenn es vorbei geht, ohne einige harte Linien im Sand zu machen.
Neil
Klingt so, als wären Sie auf dem richtigen Weg. Wenn es viele Prozesse und mehrere schlechte Äpfel gibt, müssen Sie möglicherweise einen großen Wert von M oder ungerade Gruppen verwenden, damit Sie bekannte gute Äpfel isolieren können. Bewahren Sie dann das bekannte Gut in einer Sandbox auf und teilen Sie die unbekannten Prozesse weiter auf Ihre anderen Sandkästen, bis Sie die Personen identifiziert haben. Je mehr Sandkästen Sie haben, desto schneller geht es. Wie @Neil hervorhob, ist dies ein großes O der logarithmischen Basis M des N-Algorithmus. Wenn Sie also M erhöhen, werden Ihre Versuche abgeschnitten.
GlenPeterson

Antworten:

2

Wenn Sie einen schlechten Apfel gefunden haben, können Sie den Algorithmus anwenden:

  1. Teilen Sie N in M ​​Gruppen
  2. Führen Sie den Test für jede Gruppe durch.
  3. Wenn die Gruppengröße größer als 1 ist, kehren Sie zu Schritt 1 zurück und ersetzen Sie N durch die Anzahl der Elemente in einer fehlerhaften Gruppe.

Wenn Sie den einen "guten" Apfel gefunden haben, gilt der gleiche Algorithmus, sondern die gute Gruppe.

Dieser Algorithmus hat eine O (log_M (N)) - Leistungsrate, hängt jedoch davon ab, dass es nur einen schlechten Apfel gibt.

Wenn Sie nicht wissen, wie viele gute / schlechte Äpfel es gibt, können Sie den folgenden Algorithmus verwenden:

For each M processes in N
  Test M processes

Dies ist das Worst-Case-Szenario, das jedoch O(N/M)rechtzeitig ausgeführt wird (oder O(N)abhängig davon, ob Sie einen einzelnen Durchgang als einzelnen Test oder als Sammlung parallel durchgeführter Tests betrachten). Alles in allem ist dies keineswegs ein schlechter Ansatz.

Möglicherweise gibt es Algorithmen, die eine bessere Leistung erbringen, aber Sie müssen wissen, wie viele schlechte / gute Äpfel sich in der Charge befinden. Wenn ich diesen Faktor nicht kenne, obwohl ich ihn nicht beweisen kann, würde ich wetten, dass Sie es nicht besser machen können als den oben aufgeführten letzteren Algorithmus.

Ich hoffe, das hilft!

Bearbeiten : Aus praktischer Sicht verstehe ich, dass einige dieser Operationen nicht einfach durchzuführen sind. Die unglückliche Realität ist jedoch, dass Sie den schlechten Apfel nicht genau bestimmen können, anhand dessen Prozesse auf der Sandbox ausgeführt wurden, die zu diesem Zeitpunkt ausgeführt wurde, ohne zumindest Prozesse zu aktivieren oder zu deaktivieren. Wenn sich die Frage auf den Algorithmus bezieht, habe ich das wohl beantwortet. Wenn sich die Frage darauf bezieht, wie mit einer solchen Situation umzugehen ist, ist die Frage möglicherweise besser für den Superuser SE geeignet.

Neil
quelle
1
Leider kann ich die Prozesse nicht "testen". Ich weiß nur, dass einer der Sandkästen abgestürzt ist und dass er durch einen oder mehrere der darin enthaltenen Prozesse verursacht wurde.
Roger Lipscombe
1
Das Problem ist, dass beide Partitionen nach der Halbierung des Sets möglicherweise schlechte Äpfel enthalten. Was mich denken lässt, dass ich mehr als eine einfache Partition brauche ...
Roger Lipscombe
@RogerLipscombe Sie versuchen, einen Algorithmus auf ein reales Szenario anzuwenden. Natürlich können Sie die Prozesse nicht einzeln testen, und es kann sich als schwierig erweisen, diese Prozesse auf verschiedenen Computern zu testen. Wenn Sie dem jedoch auf den Grund gehen möchten, werden Sie es tun muss einen Weg finden auf die eine oder andere Weise. Wenn Sie Variablen einfügen, die nicht aufgelöst werden können, können Sie einfach keinen Algorithmus finden, der die fehlerhaften Äpfel genau lokalisiert.
Neil
OK, mit "Test" meinen Sie also nur "Lassen Sie sie lange genug laufen, um zuversichtlich zu sein" ...?
Roger Lipscombe
@ RogerLipscombe Ich nehme an. Es kann länger dauern, aber Sie müssen herausfinden, wie lange Sie warten müssen. Wenn Sie das wissen und diesem Algorithmus folgen, können Sie technisch alle schlechten Äpfel herausfinden. Es kann jedoch schneller sein, das Windows-Ereignisprotokoll einfach auf Abstürze zu überprüfen.
Neil