wtorek, listopada 17, 2009

Wilcze Stado

Tworząc rozproszony system obliczeniowy, w którym nie jesteśmy w stanie oszacować obciążenia całości układu w czasie, musimy rozważać różnorakie scenariusze: utrzymywanie całości sieci w stanie gotowości może wiązać się ze zbyt dużym kosztem, przydzielając sztywną ilość jednostek do danego zadania nie jesteśmy w stanie reagować na zmieniające się wymagania. Założenie, że wszystkie jednostki są identyczne, może być zbyt niewygodne, niektóre zadania wchodzące w skład procesu mogą wymagać specyficznie skonfigurowanych jednostek.

W celu uniknięcia takich problemów, by sieć była efektywna oraz odpowiednio wykorzystywała zasoby, będąc jednocześnie elastyczną i łatwą w utrzymaniu zastosujemy podejście zakładające dużą samodzielność poszczególnych jednostek. Takie podejście oraz taką sieć nazwę Wilczym Stadem. Wewnątrz stada, różnicujemy jednostki ze względu na ich stopień gotowości do wykonania zadania. Jednostki oddelegowane do wykonywania zadań stada określimy mianem wilków, jednostki wykonujące inne zadania, a mogące dołączyć do stada po otrzymaniu odpowiedniego sygnału nazwiemy wilkołakami. W przypadku, gdy utrzymywanie stanu gotowości wiąże się ze zbyt dużymi kosztami, pojedynczą jednostkę można przeprowadzić w stan uśpienia. Śpiąca jednostka może przejść w stan gotowości w reakcji na sygnał od stada. Jednostkę której zadaniem jest koordynacja stada, rozdzielanie zadań pomiędzy jednostki, nazwiemy samcem alfa lub też przywódcą.

Nadchodzące nowe zadanie wymusza na przywódcy określone zachowanie, oprócz zadania przywódca może otrzymać również podstawowe parametry budowanego stada. Zróżnicowanie zadań i obciążeń pozwala wykonywać kilka zadań wewnątrz jednej sieci. Wystarczy wydzielić kilku przywódców i każdy z nich będzie budował własne stado, pobierając jego członków ze wspólnej puli jednostek. Przywódca buduje swoje stado postępując według poniższych reguł:
  • wezwij aktywne wilki do stawienia się w stadzie
  • nie mając odpowiedniej ilości jednostek obudź śpiące wilki i powtórz wezwanie
  • nie mając odpowiedniej ilości jednostek wezwij wilkołaki do stawienia się w stadzie
  • nie mając odpowiedniej ilości jednostek obudź śpiące wilkołaki i powtórz wezwanie

Przywódca mając zbudowane całe stado rozdziela zadania pomiędzy jednostki kierując się ich specyfiką. Może dochodzić do wydzielenia mniejszych sieci, łączących jednostki ze względu na ich charakterystyki. Jednostka która zakończyła swoje zadania zgłasza ten fakt przywódcy i może otrzymać nowe zadanie, lub też zostać odłączone ze stada. W przypadku gdy któreś zadanie wymaga powiększenia sieci przywódca powiększa ją w taki sam sposób w jaki buduje sieć. Sieć może być budowana na bieżąco wraz z rozdzielaniem zadań.

W sieci w której należy liczyć się z tym, że jednostki mogą w sposób niespodziewany odłączyć się od stada wszystkie poszczególne jednostki muszą posiadać funkcję przywódcy. Przy czym przywództwo ustalane jest na zasadzie poniższego algorytmu:
  • będąc przywódcą, rozgłoś to po całym stadzie
  • nie otrzymawszy przez określony czas sygnału od przywódcy stań się pretendentem i rozgłoś ten stan po całym stadzie
  • nie otrzymawszy przez określony czas sygnału od przywódcy i będąc pretendentem uczyń się przywódcą i rozgłoś to po całym stadzie
  • będąc przywódcą i otrzymawszy sygnał od przywódcy przestań być przywódcą
  • będąc pretendentem i otrzymawszy sygnał od przywódcy przestań pretendować

Sieć taką możemy zastosować w rozproszonych systemach testujących, obliczeniowych, monitorujących. Wszędzie tam, gdzie nie mamy stałego obciążenia, obciążenie się zmienia w czasie, zapotrzebowanie na jednostki jest mocno zmienne.

1 komentarz:

Gluth pisze...

Oświeciło mnie pewnego dnia podczas spaceru. Spisałem i wrzuciłem tutaj, może komuś się przyda. Ja też to na pewno kiedyś wykorzystam. Dobre pomysły się nie marnują.

Prześlij komentarz