Już wcześniej chciałem przedstawić moje rozwiązanie
problemu pięciu ucztujących filozofów, ale jak zwykle ciężko znaleźć chwilkę czasu. Tak na prawdę moje rozwiązanie nie jest ostatecznym rozwiązaniem tego problemu, ale implementacją różnych możliwości uruchomienia symulacji ucztujących filozofów. Aby uruchomić symulację wystarczy uruchomić skrypt:
Run-DPP -showAll
Na ekranie uzyskamy liczby:
Status: 0 0 0 1 0
Meals: 5 2 4 3 3
Górny wiersz określa semafory o wolnych widelcach, a dolny wiersz określa ile razy dany filozof jadł. Z górnego wiersza można odczytać, że widelec przedostatni jest wolny.
Zacząłem rozwiązywać ogólny problem ucztujących n-filozofów. Poniżej przykład statusu dla 10 filozofów:
Symulacja działania filozofów jest na podstawie Jobów. Przy każdym wywołaniu skryptu następuję usunięcie job'ów:
get-job | Stop-Job
get-job | Remove-Job
Na potrzeby rozwiązania problemu, użyto dodatkowego joba, który zarządza wszystkimi filozofami - kelner obsługujący filozofów. Implementacja kelnera jest w pliku Run-Waiter.ps1.
for( $i=0; $i -lt $philosopherNumber ; $i++)
{
Start-job -FilePath $scriptPath -ArgumentList $i,$scriptLocation -Name "Philo_$i"
}
Każdy filozof prosi kelnera o widelec (request +1).
Kelner sprawdza listę próśb (request >0) i jak widelce są dostępne, podchodzi do filozofa i pozwala na wzięcie widelca (response +1).
Filozof sprawdza odpowiedz (response >0), bierze widelec i dziękuje za obsługę (request -1).
Kelner odchodzi od filozofa (response -1)
W taki sposób, filozof jest odpowiedzialny za zapis requestów, a kelner odpowiedzialnego za zapis responsów.
Dla kelnera wprowadziłem opcje randomizacji wyboru od którego filozofa za zacząć pytać czy czegoś nie potrzebuje. Częściowo rozwiązanie to rozwiązało problem nadawania priorytetu filozofom parzystym przed innymi filozofami, gdy mamy parzystą liczbę wszystkich filozofów.
W pliku DiningPhilosophersProblemHelper.ps1 są wszystkie funkcje współdzielone między kelnerem, a filozofami. PS nie ma pamięci współdzielonej pomiędzy wszystkie job'y czy procesy. Komunikację między job'ami jest zaimplementowana poprzez zmienne środowiskowe, które są dostępne z poziomu użytkownika:
[Environment]::GetEnvironmentVariable($name, [System.EnvironmentVariableTarget]::User)
Tablica określająca wolne zasoby widelców jest zapisana w zmiennej środowiskowej jako string:
function Set-ArrVariable([string]$name, [array]$arr)
{
Set-ArrVariableStr $name ($arr -join ';')
}
Zapis danych do zmiennej środowiskowej na poziomie użytkownika jest naszą sekcją krytyczną. Często można było uzyskać wielokrotne zwiększenie lub zmniejszenie wartości w tablicy:
Synchronizacja zapisu zmiennej środowiskowej jest za pomocą globalnych muteksów dostępnych przez wszystkie job'y. Przykład tworzenia globalnego muteksa jest poniżej:
$UsedForksMutex = new-object System.Threading.Mutex ($false, 'Global\UsedFork')
Wprowadziłem opcje umierania filozofów, gdy za długo czekają na sztućce (lub na obsługę kelnera).
[bool]$mayStarve = $false
Czas potrzebny dla filozofa na myślenie oraz jedzenie jest ustawiony jako zmienna losowa. Domyślnie jest to wartość jednostkowa.
W planach mam jeszcze dodatnie
- ograniczenia do parzystej liczby filozofów, którzy mogą ubiegać się o sztućce
- pozwolenie filozofom wzięcia widelców, tylko jeżeli 2 z nich są dostępne ( jak na razie filozof bierze jeden widelec, a później próbuje wziąć drugi)
- filozofowie z parzystymi numerami najpierw wybierają widelce po prawej stronie, a filozofowie z numerami nieparzystymi wybierają najpierw widelce po lewej stronie
- rozwiązanie probabilistyczne (losowe wybieranie strony pierwszego widelca, a później znów losowanie prawdopodobieństwa wzięcia drugiego widelca, w przypadku nie wzięcia tego drugiego widelca opuszcza się widelec pierwszy)
- ustalenie priorytetów wyboru widelców (przy podnoszeniu najpierw wybiera się sztućce o numerach niższych, a przy oddawaniu najpierw oddaje się sztućce o numerach wyższych)
- rozwiązanie czystych i brudnych widelców
- ustawienie pierwszeństwa w jedzeniu dla filozofa o najmniejszej ilości skonsumowanych posiłków
Co prawda implementacja problemu 5 filozofów nie jest jeszcze gotowa, ale mogę wysunąć wnioski, że dużo przyjemniej rozwiązuje się ten problem w innych językach programowania - przynajmniej nie trzeba pracować na zmiennych globalnych czy na job'ach. Dużo przyjemniejsza była by implementacją tego problemu w C# niż w PS. PS jak na razie nie ma prostych sposobów synchronizacji job'ów. Taka prosta sprawa jak wyświetlanie komunikatów też nie była prosta. Write-Host nie wyświetla komunikatów w konsoli dopóki nie pobierze się job'a. Można było zawiesić komputer za pomocą symulację dla 20 filozofów i przetrzymując wszystkie komunikaty w pamięci. Nawet jak wyjdziemy z debuggera to job'y i tak będą wykonywać się.
Cały kod źródłowy można pobrać z
github.
