Głodzenie filozofów ;-) - jak jest sprawiedliwiej?

To problem zwany Problemem ucztujących filozofów, podobno znany wszystkim, choć ja o nim usłyszałem niedawno (sam problem współdzielenia zasobów znałem, nie znałem tego przykładu - ale to tak jest jak się studiuje fizykę, a nie informatykę ;-)).

Mamy 5 filozofów, którzy siedzą przy stole na którym znajduje się we wspólnej misce ryż, a oni mają go jeść pałeczkami.

Między każdą parą filozofów jest dokładnie 1 pałeczka.

Żeby zjeść z miski filozof musi mieć w lewej dłoni jedną pałeczkę i w drugiej drugą...

Jak jeden filozof "zawłaszczy" zasób którym jest pałeczka to sąsiad nie może jej użyć.

Są różne sposoby rozwiązania tego problemu, ale ogólnie chodzi o synchronizowanie się na czymś.

Rozważyłem synchronizację na stole, tzn. filozof najpierw zaklepuje stół, jeśli mu się to uda to może zacząć zbierać pałeczki, po próbie zebrania pałeczek oddaje "zaklepanie" stołu i w razie ma obie pałeczki to próbuje zjeść ze wspólnej miski, po czym jeśli miał w ogóle jakieś pałeczki to zaklepuje stół i oddaje je...
W momencie "zaklepania" stołu może podnosić/upuszczać pałeczki tylko 1 filozof.

Drugi scenariusz jest taki, że pałeczki działają tak, że jak jeden filozof weźmie pałeczkę to sąsiad jej nie może wziąć.
Filozof działa tak, że próbuje wziąć pałeczkę z lewej, jeśli mu się uda to próbuje to z prawą. Jeśli ma dwie to je, po czym jeśli ma jakąkolwiek to oddaje.
Synchronizacja odbywa się na poziomie flagi w samej pałeczce.

Spoko.

Teraz jest pytanie, która metoda jest bardziej sprawiedliwa? A która szybsza? ;-)

Dałem filozofom dokładnie 214748364 (214 milionów, 748 tysięcy i 364) ziarenek ryżu.
Każdy z nich w momencie "uruchomienia" sprawdzał czy już można, a jeśli już było można to zaczynał próbować zagarnąć pałeczki...

Jak liczyłem "sprawiedliwość" podziału?
Jako sumę wartości bezwzględnych z różnic między tym co każdy z filozofów dostał, a tym co powinien dostać.
Najbardziej sprawiedliwy jest podział z tą wartością równą 0, najmniej sprawiedliwy z wartością 400 (jeden dostałby 100%, a reszta po 0, wtedy dla każdego wartość bezwzględna różnicy między oczekiwanymi 20% a otrzymanymi wynosiłaby 80%).

I co się okazało?

Że podział przy synchronizowaniu się na jednym i tym samym obiekcie czyli na stole zwykle daje rezultat o "sprawiedliwości" ~3.34, czyli łączna różnica między tym co ktoś dostał, a tym co mu się należało wynosiła średnio około 3.34%.
Przy podziale z synchronizacją na pałeczkach już tak fajnie nie było, bo "sprawiedliwość" wynosiła ~29.77%, często jeden z filozofów dostawał ~30% wszystkiego, a inny tylko ~10%, reszta zaś dzieliła się "sprawiedliwie" resztą.

Jednak bardziej sprawiedliwy podział miał swoją cenę, jedzenie trwało średnio prawie 2 razy dłużej niż w momencie gdy mniej sprawiedliwie dzielono posiłek.

W przypadku sprawiedliwym "regulator" wymagał by w danym momencie brał/oddawał pałeczki tylko 1 filozof przez co większość czasu wszyscy filozofowie spędzili na czekaniu na stół, tak by sami mogli spróbować zebrać pałeczki.
W drugim przypadku każdy z filozofów próbował wziąć pałeczkę niemal non-stop, jeśli mu się to udawało z lewą to próbował prawą.

Do tego w przypadku bardziej sprawiedliwego podziału pojedynczy filozof miał tylko jedną pałeczkę 3 razy częściej niż dwie pałeczki, w przypadku mniej sprawiedliwego podziału było to bliżej 2 razy częściej.

Podejście ze "sprawiedliwym" regulatorem było sprawiedliwsze, ale mniej wydajne, więcej też razy filozofowie byli blokowani przed działaniem bo ktoś inny miał drugą część potrzebnych zasobów.
Zasoby dłużej nie były wykorzystywane gdy były zajęte.
W przypadku bez regulatora podział był mniej sprawiedliwy, ale za to cały proces był bardziej wydajny, częściej filozofowie byli w stanie podejmować działanie, do tego zasoby były częściej używane gdy były w czyjejś gestii...

Co ciekawe najbardziej "wolne" podejście gdzie każdy filozof próbowałby zagarnąć obie pałeczki i nie oddawałby pałeczki póki by nie zjadł swojego ziarnka ryżu doprowadziłoby do deadlocka i wszyscy filozofowie padliby nam po jakimś czasie z głodu.... a zasoby większość czasu byłyby w posiadaniu kogoś kto nie może z nich korzystać.

Jakie są wnioski? ;-)

Takie:
- wolna amerykanka gdzie każdy próbuje zagarnąć to co mu jest potrzebne nie działa optymalnie, a zwykle w ogóle nie działa,
- synchronizacja na pojedynczym zasobie, czyli działanie tylko wtedy gdy "nam pozwolą" prowadzi do sprawiedliwszego podziału, ale podział trwa dłużej i jest mniej wydajny,
- słabsza kontrola, w której synchronizujemy się na samych zasobach i jak nie możemy ich użyć to je zwracamy działa w miarę najlepiej.

I teraz dodajmy aspekt "polityczny" ;-) i piszę to jako lewak :-)
Korwinizm to przykład pierwszy i nie działa.
Centralne planowanie/dzielenie w razie dobrego zarządcy powinno działać, ale jest nieefektywny.
Kapitalizm w którym gracze przestrzegają reguł (bo przecież któryś z filozofów mógłby nie chcieć oddać pałeczki i po chwili miałby 2 pałeczki i mógłby zjeść o wiele więcej) nie jest do końca sprawiedliwy, ale jest bardziej efektywny.

I to tyle ;-)

Jak ktoś ciekawy źródeł to są tutaj.


Podobne posty^beta
Ważne książki
Losowanie dobre
Jak sprawiedliwie przydzielić biurka?
Dobór naturalny, albo my
Czemu nie znoszę Spidermana.... ;-)