so:elekcja [mgr Wiki]

[[so:elekcja]]
mgr Wiki

Pytanie: “Algorytmy wyboru koordynatora (tyrana, pierścieniowy)”

# Algorytmy elekcji

W wielu algorytmach rozproszonych stosuje się proces koordynujący, który wykonuje funkcje potrzebne innym procesom w systemie. Wśród funkcji tych znajdują się takie, jak:

- wymuszanie wzajemnego wykluczania,
- utrzymywanie globalnego grafu oczekiwania w celu wykrywania zakleszczenia,
- zastępowanie utraconych żetonów,
- kontrolowanie urządzeń wejścia/wyjścia w systemie.

Jeśli proces koordynujący przestaje działać z powodu awarii stanowiska, na którym przebywa, to w celu dalszej pracy system musi uruchomić nową kopię koordynatora na jakimś innym stanowisku. Algorytmy rozstrzygające, gdzie powinno nastąpić wznowienie kopii koordynatora, są nazywane algorytmami elekcji (ang. election).

W algorytmach elekcji zakłada się, że z każdym aktywnym procesem w systemie jest związany jednoznaczny numer priorytetu. W celu uproszczenia notacji założymy, że i jest numerem priorytetu procesu Pi. Dla prostoty przyjmiemy też, że istnieje wzajemnie jednoznaczna odpowiedniość miedzy procesami i stanowiskami, zatem do stanowisk będziemy się odwoływać tak jak do procesów. Koordynatorem jest zawsze proces z najwyższym numerem priorytetu. Jeśli więc koordynator ulegnie awarii, to algorytm musi wybrać ten spośród aktywnych procesów, który ma największy numer priorytetu. Numer ten musi zostać wysłany do każdego aktywnego procesu w systemie. Oprócz tego algorytm musi zawierać mechanizm umożliwiający zidentyfikowanie bieżącego koordynatora przez proces przywracany do działania.

W obu algorytmach na wykonanie elekcji potrzeba n komunikatów, przy czym n jest liczbą procesów w systemie. Zakładamy, że proces, który uległ uszkodzeniu, ma o tym informację podczas przywracania go do działania; podejmuje on zatem odpowiednie czynności (opisane dalej), aby dołączyć do zbioru procesów aktywnych.

## Algorytm tyrana

Algorytm ma zastosowanie w tych systemach, w których każdy proces może wysłać komunikat do dowolnego procesu w systemie. Przypuśćmy, że proces Pi wysyła zamówienie, które pozostaje bez odpowiedzi ze strony koordynatora przez czas T. W tej sytuacji zakłada się, że koordynator uległ awarii, a proces Pi próbuje sam siebie obrać nowym koordynatorem, posługując się następującym algorytmem.

Proces Pi wysyła komunikat o elekcji do wszystkich procesów z wyższymi numerami priorytetów. Następnie czeka przez czas T na nadejście odpowiedzi od któregokolwiek z tych procesów.

Jeśli w czasie T nie nadejdzie żadna odpowiedź, to proces Pi zakłada, że wszystkie procesy z numerami priorytetów większymi od i uległy awariom i wybiera siebie na nowego koordynatora. Proces Pi wznawia kopię koordynatora i wysyła komunikat informujący wszystkie procesy o numerach priorytetów mniejszych od i, że Pi został nowym koordynatorem.

Jeżeli jednak odpowiedź nadejdzie, to proces Pi rozpoczyna czekanie przez czas T’, aby otrzymać komunikat, że koordynatorem został obrany jakiś proces o wyższym numerze priorytetu. (Jakiś inny proces obrał się koordynatorem i powinien powiadomić o tym w czasie T’). Jeśli przez czas T’ nie nadejdzie żaden komunikat, to przyjmuje się, że proces o wyższym numerze uległ awarii i proces Pi powinien wznowić wykonywanie algorytmu.

Jeśli proces Pi nie jest koordynatorem, to w każdej chwili swojego działania może otrzymać jeden z następujących dwu komunikatów od procesu Pj

1. Pj jest nowym koordynatorem (j > i). Proces Pi odnotowuje tę informację.
2. Pj rozpoczął elekcję (j < i).

Proces Pi wysyła odpowiedź do Pj i sam rozpoczyna wykonywać algorytm elekcji, jeśli jeszcze go nie rozpoczął. Proces, który zakończy swój algorytm, ma najwyższy numer, więc zostaje koordynatorem. Wysłał on swój numer do wszystkich aktywnych procesów z mniejszymi numerami. Proces, który po awarii powraca do działania, natychmiast rozpoczyna wykonywanie tego samego algorytmu. Jeśli wśród aktywnych procesów nie ma procesów z wyższymi numerami, to wznawiający działanie proces zmusza wszystkie procesy z niższymi numerami do uznania go koordynatorem nawet wówczas, gdy istnieje wśród nich koordynator z niższym numerem. Z tego powodu algorytm ten nazwano algorytmem tyrana.

## Algorytm pierścieniowy

Algorytm znajduje zastosowanie w systemach zorganizowanych w postaci pierścienia (logicznego lub fizycznego). W algorytmie pierścieniowym (ang. ring algorithm) zakłada się, że łącza są jednokierunkowe oraz że procesy wysyłają komunikaty do swoich sąsiadów po prawej stronie. Główną strukturą danych używaną przez algorytm jest lista aktywna (ang. active list), zawierająca numery priorytetów wszystkich procesów aktywnych w systemie w chwili zakończenia algorytmu. Każdy proces utrzymuje własną listę aktywną. Przebieg algorytmu jest następujący:

1. Jeśli proces Pi wykrywa awarię koordynatora, to tworzy nową listę aktywną, która początkowo jest pusta. Następnie wysyła komunikat `elekcja(i)` do swojego sąsiada po prawej stronie i dodaje numer i do swojej listy aktywnej.
2. Jeśli Pi otrzyma komunikat elekcja(j) od procesu po lewej, to musi od powiedzieć w jeden z trzech sposobów:
   1. Jeśli jest to pierwszy komunikat elekcja, z którym ma do czynienia lub który wysłał, to Pi tworzy nową listę aktywną z numerami i i j. Wysyła wówczas komunikat `elekcja(i)` , a po nim komunikat `elekcja(j)` .
   2. Jeśli i <> j (tj. otrzymany komunikat nie zawiera numeru procesu Pi), to Pi dodaje j do swojej listy aktywnej i przekazuje ten komunikat dalej, do swojego sąsiada po prawej stronie.
   3. Jeśli i = j (tzn. Pi otrzymuje komunikat `elekcja(i)` to lista aktywna procesu Pi zawiera już numery wszystkich aktywnych procesów w systemie. Proces Pi może teraz określić największy numer na liście aktywnej, aby wskazać nowy proces koordynujący.

W algorytmie tym nie sprecyzowano, w jaki sposób proces przywracany do działania ma określić numer bieżącego koordynatora. Jednym z rozwiązań mogłoby być wymaganie, aby proces reaktywowany wysłał komunikat z zapytaniem. Komunikat taki, przekazywany naokoło pierścienia, dotarłby do bieżącego koordynatora, który w odpowiedzi wysłałby wiadomość o swoim numerze.

so/elekcja.txt · Last modified: 2006/05/22 10:22 by 213.134.172.237