Wpisany przez Michał Knasiecki,
01 sierpnia 2005 19:05
Algorytmy probabilistyczne to pewna grupa algorytmów, które wykorzystują losowanie do uzyskania rozwiązania.
Są one często stosowane w systemach współbieżnych procesów ubiegających się o współdzielone zasoby systemu komputerowego.
W wielu przypadkach nie istnieje w pełni rozproszone (tzn. bez centralnej pamięci i centralnego procesora) i symetryczne (identyczność protokołu) rozwiązanie wolne od blokady. W takich wypadkach stosuje się algorytmy probabilistyczne. W przypadku stosowania takich algorytmów nie mamy pewności, że konstruują one rozwiązania poprawne, wiemy jednak, że dają je z prawdopodobieństwem równym 1.
Przedstawimy teraz rozwiązanie Problemu pięciu filozofów z wykorzystaniem algorytmu probabilistycznego.
Najpierw jednak scharakteryzujemy Problem 5 filozofów:
Przy stole siedzi pięciu filozofów, którzy na przemian jedzą spaghetti ze wspólnej miski oraz myślą. Żeby się najeść filozof potrzebuje dwa widelce, przy czym każdy z widelców jest współdzielony z sąsiadem. Każdy z filozofów wykonuje zatem cyklicznie następujące czynności: myśli, bierze widelce, je, odkłada widelce i znowu myśli. Widelec jest używany w trybie wyłącznym, czyli tylko jeden z dwóch siedzących obok siebie filozofów może z niego korzystać. Ponad to filozof może korzystać tylko z widelców leżących bezpośrednio przy nim. Należy napisać dla filozofów taki algorytm, aby:
Wydawać może się, że takie rozwiązanie jest banalne, jednak znalazło ono zastosowanie w protokole dostępu do sieci Ethernet, w tzw. technice CSMA/CD. Technika ta wykorzystuje mechanizm detekcji kolizji: do wspólnego medium (współdzielony zasób) podłączony jest szereg stacji roboczych. Każda stacja wykonuje następujący algorytm: stacja śledzi stan medium i zaczyna nadawać, gdy medium jest wolne. Gdy dojdzie do kolizji, tzn. gdy dwie stacje jednocześnie zaczną nadawać, wszystkie stacje przerywają nadawanie i wznawiają je po losowo wybranym odcinku czasu. Takie rozwiązanie sprawdza się bardzo dobrze, lecz nie może być stosowane w systemach sztywnego czasu rzeczywistego (HRT).
Są one często stosowane w systemach współbieżnych procesów ubiegających się o współdzielone zasoby systemu komputerowego.
W wielu przypadkach nie istnieje w pełni rozproszone (tzn. bez centralnej pamięci i centralnego procesora) i symetryczne (identyczność protokołu) rozwiązanie wolne od blokady. W takich wypadkach stosuje się algorytmy probabilistyczne. W przypadku stosowania takich algorytmów nie mamy pewności, że konstruują one rozwiązania poprawne, wiemy jednak, że dają je z prawdopodobieństwem równym 1.
Przedstawimy teraz rozwiązanie Problemu pięciu filozofów z wykorzystaniem algorytmu probabilistycznego.
Najpierw jednak scharakteryzujemy Problem 5 filozofów:
Przy stole siedzi pięciu filozofów, którzy na przemian jedzą spaghetti ze wspólnej miski oraz myślą. Żeby się najeść filozof potrzebuje dwa widelce, przy czym każdy z widelców jest współdzielony z sąsiadem. Każdy z filozofów wykonuje zatem cyklicznie następujące czynności: myśli, bierze widelce, je, odkłada widelce i znowu myśli. Widelec jest używany w trybie wyłącznym, czyli tylko jeden z dwóch siedzących obok siebie filozofów może z niego korzystać. Ponad to filozof może korzystać tylko z widelców leżących bezpośrednio przy nim. Należy napisać dla filozofów taki algorytm, aby:
- nie doszło do zakleszczenia
- nie doszło do zagłodzenia żadnego z filozofów
- Rzuć monetę, by wylosować lewą lub prawą stronę
- Czekaj aż wylosowany widelec będzie wolny i podnieś go
- Jeśli drugi widelec jest zajęty to odłóż podniesiony widelec i przejdź do kroku 1.
- Jeśli drugi widelec jest wolny to go podnieś
- Jedz
- Odłóż oba widelce
Wydawać może się, że takie rozwiązanie jest banalne, jednak znalazło ono zastosowanie w protokole dostępu do sieci Ethernet, w tzw. technice CSMA/CD. Technika ta wykorzystuje mechanizm detekcji kolizji: do wspólnego medium (współdzielony zasób) podłączony jest szereg stacji roboczych. Każda stacja wykonuje następujący algorytm: stacja śledzi stan medium i zaczyna nadawać, gdy medium jest wolne. Gdy dojdzie do kolizji, tzn. gdy dwie stacje jednocześnie zaczną nadawać, wszystkie stacje przerywają nadawanie i wznawiają je po losowo wybranym odcinku czasu. Takie rozwiązanie sprawdza się bardzo dobrze, lecz nie może być stosowane w systemach sztywnego czasu rzeczywistego (HRT).
Poprawiony: 15 sierpnia 2005 23:56