Алгоритм «плохое яблоко», или процесс вылетает из общей песочницы

9

Я ищу алгоритм для решения следующей проблемы, которую я (пока) называю алгоритмом «плохого яблока».

Проблема

  • У меня N процессов, запущенных в M песочницах, где N >> M.
  • Непрактично давать каждому процессу свою собственную песочницу.
  • По крайней мере, один из этих процессов ведет себя плохо и разрушает всю изолированную программную среду, тем самым убивая все остальные процессы в этой же изолированной программной среде.

Если бы это был один процесс с плохим поведением, то я мог бы использовать простое деление пополам, чтобы поместить половину процессов в одну песочницу, а половину - в другую, пока не обнаружу негодяй.

Вопрос

Если несколько процессов плохо себя ведут, включая вероятность того, что все они плохо себя ведут, «работает» ли этот наивный алгоритм? Гарантируется ли работа в разумных пределах?

Упрощения

Ради аргумента давайте предположим, что плохой процесс мгновенно разрушает свою песочницу, а хороший процесс никогда не делает.

algorithms Роджер Липскомб
источник
Как гарантировано, что плохо себя ведет процесс будет принести песочницу вниз? Я имею в виду - можем ли мы предположить конечное время, когда мы точно знаем, что данная песочница выполняет только «чистые» процессы, потому что она не вылетала?
SF.
К сожалению, нет: тот факт, что песочница не падает в течение 5 минут, не означает, что все процессы работают хорошо, но это дает нам больше уверенности в этом факте.
Роджер Липскомб
... но для целей этого вопроса, мы могли бы приблизиться, предоставив конечное время, я думаю.
Роджер Липскомб
Вы должны разбить то, что вы считаете «пройденным» и «провальным» процессом. Если он работает 5 минут без сбоев, технически он все равно может быть плохим яблоком, но, как и проблема остановки, у вас никогда не будет 100% -ной уверенности, когда он пройдет без каких-либо жестких линий на песке.
Нил
Похоже, вы на правильном пути. Если есть много процессов и много плохих яблок, то вам, возможно, придется использовать большое значение M или неравные группы, чтобы вы могли изолировать известные хорошие яблоки, а затем хранить известные хорошие в одной песочнице и делить неизвестные процессы между другие ваши песочницы, пока вы не определили людей. Чем больше у вас песочниц, тем быстрее это будет. Как указал @Neil, это большая O из логарифмической базы M из N алгоритма, поэтому увеличение M сократит ваши испытания.
ГленПетерсон

Ответы:

2

Если вы нашли одно плохое яблоко, вы можете применить алгоритм:

  1. Разделите N на M групп
  2. Выполните тест по каждой группе.
  3. Если размер группы больше 1, вернитесь к шагу 1, заменив N количеством элементов в плохой группе.

Аналогично, если вы находили одно «хорошее» яблоко, то применялся тот же алгоритм, но скорее находил хорошую группу.

Этот алгоритм имеет производительность O (log_M (N)), но это зависит от того факта, что существует только одно плохое яблоко.

Если вы не знаете, сколько хороших / плохих яблок, то вы можете использовать следующий алгоритм:

For each M processes in N
  Test M processes

Это худший сценарий, но он выполняется во O(N/M)времени (или в O(N)зависимости от того, считаете ли вы один проход одним тестом или набором тестов, выполняемых параллельно). Учитывая все обстоятельства, это не плохой подход с любой стороны.

Могут быть алгоритмы, которые работают лучше, чем это, но это требует, чтобы вы знали, сколько плохих яблок / хороших яблок в партии. Не зная этого фактора, хотя я не могу доказать это, я готов поспорить, что вы не можете добиться большего успеха, чем последний алгоритм, перечисленный выше.

Надеюсь, это поможет!

Изменить : С практической точки зрения, я понимаю, что некоторые из этих операций не так легко выполнить. Это правда, однако, к сожалению, реальность такова, что вы не можете точно определить «плохое яблоко», исходя из того, какие процессы выполнялись в «песочнице», которая работала в тот момент, без необходимости по крайней мере активировать или деактивировать процессы. Если вопрос относится к алгоритму, я думаю, что я ответил на это. Если вопрос относится к тому, как справиться с такой ситуацией, то, возможно, этот вопрос лучше подойдет для суперпользователя SE.

Нил
источник
1
К сожалению, я не могу "проверить" процессы; все, что я знаю, это то, что одна из песочниц разбилась и что она была вызвана одним или несколькими процессами в ней.
Роджер Липскомб
1
Проблема в том, что после разделения пополам на обоих разделах могут быть плохие яблоки. Что заставляет меня думать, что мне нужно больше, чем простой раздел ...
Роджер Липскомб
@RogerLipscombe Вы пытаетесь применить алгоритм к реальному сценарию. Конечно, вы не сможете протестировать процессы по одному, и может оказаться трудным тестировать эти процессы на разных машинах, однако, если вы хотите докопаться до сути, вы собираетесь надо найти путь так или иначе. Если вы вставите переменные, которые не могут быть разрешены, вы просто не сможете найти алгоритм, который может точно определить плохие яблоки.
Нил
Итак, под словом «тест» вы подразумеваете «оставить их работать достаточно долго, чтобы быть уверенными» ...?
Роджер Липскомб
@RogerLipscombe Я так полагаю. Может занять больше времени, но вы тот, кто должен выяснить, как долго ждать. Зная это и следуя этому алгоритму, вы можете технически обнаружить любые плохие яблоки. Однако может быть быстрее просто посмотреть журнал событий Windows на наличие сбоев.
Нил