Algorytm „złego jabłka” lub proces powoduje awarię współużytkowanej piaskownicy

9

Szukam algorytmu do obsługi następującego problemu, który nazywam (na razie) algorytmem „złego jabłka”.

Problem

  • Mam N procesów działających w M piaskownicach, gdzie N >> M.
  • Niepraktyczne jest nadawanie każdemu procesowi własnej piaskownicy.
  • Co najmniej jeden z tych procesów jest źle zachowywany i sprowadza cały obszar izolowany, tym samym zabijając wszystkie pozostałe procesy w tym samym obszarze izolowanym.

Jeśli byłby to jeden źle zachowany proces, mógłbym użyć prostej bisekcji, aby umieścić połowę procesów w jednej piaskownicy, a połowę w innej piaskownicy, dopóki nie znajdę złego.

Pytanie

Jeśli źle zachowuje się więcej niż jeden proces - w tym możliwość, że wszystkie są źle zachowane - czy ten naiwny algorytm „działa”? Czy na pewno działa w rozsądnych granicach?

Uproszczenia

Dla celów argumentu załóżmy, że zły proces natychmiast sprowadza piaskownicę, a dobry proces nigdy tego nie robi.

algorithms Roger Lipscombe
źródło
Jak zagwarantować, że proces jest źle wychowane będzie wnieść w dół piaskownicy? Mam na myśli - czy możemy założyć skończony czas, kiedy wiemy na pewno, że dana piaskownica działa tylko „czyste” procesy, ponieważ się nie zawiesiła?
SF.
Niestety nie: fakt, że piaskownica nie ulega awarii przez 5 minut, nie oznacza, że ​​wszystkie procesy przebiegają prawidłowo, ale daje nam większą pewność tego faktu.
Roger Lipscombe
... ale dla celów tego pytania moglibyśmy dokonać przybliżenia, przyznając, że skończony czas.
Roger Lipscombe
Musisz rozpylić to, co uważasz za proces „pozytywny” i „nieudany”. Jeśli działa bezawaryjnie przez 5 minut, nadal może być złym jabłkiem, ale podobnie jak w przypadku problemu z zatrzymaniem, nigdy nie będziesz mieć 100% pewności, gdy mija bez robienia twardych linii na piasku.
Neil
Wygląda na to, że jesteś na dobrej drodze. Jeśli istnieje wiele procesów i wiele złych jabłek, może być konieczne użycie dużej wartości M lub nierównych grup, aby można było wyodrębnić znane dobre jabłka, a następnie przechowywać znane dobre w jednym piaskownicy i dzieląc nieznane procesy między inne piaskownice, dopóki nie zidentyfikujesz osób. Im więcej masz piaskownic, tym szybciej to pójdzie. Jak zauważył @Neil, jest to duża liczba O logarytmu M bazowego algorytmu N, więc zwiększenie M ograniczy twoje próby.
GlenPeterson

Odpowiedzi:

2

Jeśli znalazłeś jedno złe jabłko, możesz zastosować algorytm:

  1. Podziel N na M grup
  2. Wykonaj test dla każdej grupy.
  3. Jeśli wielkość grupy jest większa niż 1, wróć do kroku 1, zastępując N liczbą elementów w złej grupie.

Podobnie, jeśli znajdujesz jedno „dobre” jabłko, wówczas stosuje się ten sam algorytm, ale raczej znajdujesz dobrą grupę.

Ten algorytm ma współczynnik wydajności O (log_M (N)), ale zależy to od faktu, że jest tylko jedno złe jabłko.

Jeśli nie wiesz, ile jest dobrych / złych jabłek, możesz użyć następującego algorytmu:

For each M processes in N
  Test M processes

Jest to najgorszy scenariusz, ale działa on w O(N/M)czasie (lub w O(N)zależności od tego, czy rozważasz pojedyncze przejście jako pojedynczy test czy jako zbiór testów przeprowadzanych równolegle). Biorąc wszystko pod uwagę, nie jest to wcale złe podejście.

Mogą istnieć algorytmy, które działają lepiej niż to, ale wymaga to znajomości liczby złych jabłek / dobrych jabłek w partii. Nie znając tego czynnika, chociaż nie mogę tego udowodnić, chciałbym się założyć, że nie da się lepiej niż ten drugi algorytm wymieniony powyżej.

Mam nadzieję, że to pomaga!

Edycja : Z praktycznego punktu widzenia rozumiem, że niektóre z tych operacji nie są łatwe do wykonania. To prawda, jednak niefortunną rzeczywistością jest to, że nie można dokładnie określić złego jabłka, z którego procesy działały na piaskownicy, która działała w tym momencie, bez konieczności przynajmniej aktywacji lub dezaktywacji procesów. Jeśli pytanie dotyczy algorytmu, myślę, że na to odpowiedziałem. Jeśli pytanie dotyczy tego, jak poradzić sobie z taką sytuacją, być może pytanie to byłoby lepiej dostosowane do superużytkownika SE.

Neil
źródło
1
Niestety nie mogę „przetestować” procesów; wszystko, co wiem, to to, że jedna z piaskownic uległa awarii i że została spowodowana przez jeden lub więcej procesów w niej zawartych.
Roger Lipscombe
1
Problem polega na tym, że po podzieleniu zestawu obie partycje mogą mieć w sobie złe jabłka. Co sprawia, że ​​uważam, że potrzebuję czegoś więcej niż zwykłej partycji ...
Roger Lipscombe,
@RogerLipscombe Próbujesz zastosować algorytm do scenariusza z prawdziwego świata. Oczywiście nie będziesz w stanie przetestować procesów pojedynczo i może to być trudne do przetestowania na różnych komputerach, jednak jeśli chcesz przejść do sedna, musisz muszę znaleźć sposób w ten czy inny sposób. Jeśli wstawisz zmienne, których nie można rozwiązać, po prostu nie będziesz w stanie znaleźć algorytmu, który mógłby dokładnie wskazać złe jabłko (jabłka).
Neil
OK, więc przez „test” masz na myśli po prostu „zostawić je uruchomione na tyle długo, aby mieć pewność siebie” ...?
Roger Lipscombe
@RogerLipscombe Chyba tak. Może to zająć więcej czasu, ale to ty musisz dowiedzieć się, jak długo czekać. Wiedząc o tym i postępując zgodnie z tym algorytmem, możesz technicznie znaleźć wszystkie złe jabłka. Jednak szybsze może być po prostu sprawdzenie dziennika zdarzeń systemu Windows pod kątem awarii.
Neil