algorytm.org

Algorytmy probabilistyczne



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytmy probabilistyczne
Ocena użytkowników:***** / 82
SłabyŚwietny 
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:
  • nie doszło do zakleszczenia
  • nie doszło do zagłodzenia żadnego z filozofów
Algorytm probabilistyczny dla tego problemu (dla każdego filozofa) przedstawia się następująco:
  1. Rzuć monetę, by wylosować lewą lub prawą stronę
  2. Czekaj aż wylosowany widelec będzie wolny i podnieś go
  3. Jeśli drugi widelec jest zajęty to odłóż podniesiony widelec i przejdź do kroku 1.
  4. Jeśli drugi widelec jest wolny to go podnieś
  5. Jedz
  6. Odłóż oba widelce
Przy takim algorytmie prawdopodobieństwo, że n filozofów podniesie ten sam widelec wynosi 1/2n i z każdą następną próbą maleje 2n krotnie.
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
Dodaj komentarz