Problem palaczy papierosów
Problem palaczy papierosów to problem współbieżności w informatyce , pierwotnie opisany w 1971 roku przez Suhasa Patila . Problem był krytykowany za „ograniczenia, których nie można uzasadnić względami praktycznymi”.
Opis problemu
Problem Patila obejmuje „dość arbitralne” „ograniczenie, że proces, który dostarcza składników, nie może zostać zmieniony i że nie można używać żadnych instrukcji warunkowych”.
Załóżmy, że do wytworzenia i palenia papierosa potrzebne są trzy składniki: tytoń, papier i zapałki. Przy stole siedzi trzech palaczy, z których każdy ma nieskończone zapasy jednego z trzech składników — jeden palacz ma nieskończone zapasy tytoniu, inny papier, a trzeci zapałki.
Jest też agent dla niepalących, który umożliwia palaczom zrobienie papierosów poprzez arbitralne ( niedeterministyczne ) wybranie dwóch zapasów do umieszczenia na stole. Palacz, który ma trzeci zapas, powinien zdjąć ze stołu te dwa przedmioty i użyć ich (wraz z własnym zapasem) do zrobienia papierosa, którego pali przez chwilę. Gdy palacz skończy papierosa, agent kładzie na stole dwa nowe losowe przedmioty. Ten proces trwa wiecznie.
Trzy semafory służą do reprezentowania pozycji na stole; agent zwiększa odpowiedni semafor, aby zasygnalizować, że przedmiot został umieszczony na stole, a palacze zmniejszają semafor podczas usuwania przedmiotów. Ponadto każdy palacz ma powiązany semafor, którego używa do zasygnalizowania agentowi, że dany palacz skończył palić; agent ma proces, który czeka na semafor każdego palacza, aby dać znać agentowi, że może umieścić nowe pozycje na stole.
Prosta implementacja pseudokodu palacza, który ma zapas tytoniu, może wyglądać następująco:
def tytoniu_smoker (): powtórz : papier . czekaj () pasuje . czekać () dym () tytoniu_smoker_done . sygnał ()
Może to jednak prowadzić do impasu; jeśli agent położy papier i tytoń na stole, palacz z tytoniem może usunąć papier, a palacz z zapałkami może wziąć tytoń, pozostawiając oboje niezdolnych do zrobienia papierosa. Rozwiązaniem jest zdefiniowanie dodatkowych procesów i semaforów, które zapobiegają zakleszczeniu, bez modyfikowania agenta.
Krytyka
Patil nałożył następujące ograniczenia na problem palaczy papierosów:
- Kod agenta nie podlega modyfikacji.
- Rozwiązanie nie może używać instrukcji warunkowych.
Patil użył dowodu w postaci sieci Petriego , aby stwierdzić, że rozwiązanie problemu palaczy papierosów przy użyciu prymitywów semaforowych Edsgera Dijkstry jest niemożliwe i zasugerować, że potrzebny jest silniejszy prymityw. Jednak David Parnas wykazał, że dowód Patila jest niewystarczający, jeśli używane są tablice semaforów, oferując rozwiązanie, które wykorzystuje procesy pomocnicze, które wykonują arytmetykę, aby zasygnalizować odpowiedniemu palaczowi, aby kontynuował.
Zdaniem Allena B. Downeya pierwsze ograniczenie ma sens, ponieważ jeśli agent reprezentuje system operacyjny , modyfikacja go za każdym razem, gdy pojawia się nowa aplikacja, byłaby nieracjonalna lub niemożliwa. Jednak Parnas twierdzi, że drugie ograniczenie jest nieuzasadnione:
Ograniczenia zgłoszone przez Patila są ograniczeniami jego prymitywów, ale nie są ograniczeniami prymitywów opisanych przez Dijkstrę. … Ważne jest jednak, aby takie badanie [prymitywów Dijkstry] nie badało mocy tych prymitywów pod sztucznymi ograniczeniami. Przez sztuczne rozumiemy ograniczenia, których nie można uzasadnić względami praktycznymi. Zdaniem tego autora ograniczenia zabraniające stosowania instrukcji warunkowych lub tablic semaforowych są sztuczne.
Zobacz też
| Ogólny | |
|---|---|
| Rachunek procesowy | |
| Klasyczne problemy | |
