Maszyny stanowe a wątki

24

Alan Cox powiedział kiedyś : „Komputer jest maszyną stanową. Wątki są dla osób, które nie mogą programować maszyn stanowych”.
Ponieważ bezpośrednie pytanie do Alana nie jest dla mnie pokorne, wolę zapytać tutaj: w jaki sposób można osiągnąć funkcjonalność wielowątkowości w języku wysokiego poziomu, takim jak Java, używając tylko jednego wątku i automatu stanów? Na przykład co zrobić, jeśli do wykonania są 2 działania (wykonywanie obliczeń i wykonywanie operacji we / wy) i jedno działanie może zostać zablokowane?
Czy używanie „tylko maszyny stanów” jest realną alternatywą dla wielowątkowości w językach wysokiego poziomu?

Victor Sorokin
źródło
4
Komputer jest także maszyną Turinga. Niemniej jednak niekoniecznie jest przydatne programowanie go jak maszyny Turinga. Stos w imperatywnych językach jest niezwykle użyteczną rzeczą, a programy wielowątkowe pozwalają zachować wiele stosów w pamięci jednocześnie. Robienie tego samego w maszynie stanów jest z pewnością możliwe, ale tym bardziej niechlujne.
thiton
10
Alan był programistą jądra systemu operacyjnego; to był jego domian . Dlatego jego cytat należy wziąć w tym kontekście. Programowałby „przeciwko metalowi” tam, gdzie bardziej sensowne jest użycie takiego modelu. Gdy system operacyjny wyodrębni sprzęt i jego nieodłączne cechy (to, że „komputer jest maszyną stanu ...”), masz okazję i korzyści, aby móc korzystać z innych modeli, które są bardziej sensowne w Twojej domenie . Prawie każda gra intensywnie wykorzystuje maszyny stanowe.
Steven Evers,
2
Wątek jest po prostu funkcją systemu operacyjnego do automatycznego zarządzania niektórymi przełącznikami maszyny stanów, jeśli chcesz. Oczywiście możesz stworzyć ogromną maszynę stanową, która sama zarządza wszystkim, ale jest to bardziej skomplikowane. To samo można powiedzieć o procesach. Można powiedzieć, że procesy są dla osób, które nie mogą również programować maszyn stanów. Ale abstrakcja zapewnia znacznie prostszy i mniej podatny na błędy interfejs. Moim zdaniem jest to kolejny „fajny cytat”, który należy usłyszeć, kontemplować, a następnie zignorować w rzeczywistości.
Yam Marcovic,
2
„Ale abstrakcja [wątku] zapewnia znacznie prostszy i mniej podatny na błędy interfejs”. To wydaje się fałszywe. Liczba osób, które źle zrozumiały bezpieczeństwo wątków, wskazuje, że wydaje się powodować błędy.
S.Lott,
1
Wiele komentarzy i odpowiedzi tutaj interpretuje cytat jako ogólnie przeciw wielozadaniowy; Uważam, że Alan Cox jest po prostu anty-wątkiem i opowiada się za zastosowaniem wielu procesów, aby osiągnąć wiele celów, do których ludzie używają wątków. Pamiętaj, że jest hakerem uniksowym: rozwidlenie FTW. Nie znalazłem żadnych komentarzy od niego bezpośrednio w cytacie, ale oto jeden z Larry'ego McVoya z listy mailingowej jądra Linuksa, który idzie w tym kierunku: lkml.indiana.edu/hypermail/linux/kernel/0106.2/0405.html
Martin B

Odpowiedzi:

25

Wszystko, co robi wątek, to operacje przeplatania, dzięki czemu części procesu wydają się nakładać na siebie w czasie. Jednordzeniowa maszyna z wieloma wątkami po prostu przeskakuje: wykonuje małe fragmenty kodu z jednego wątku, a następnie przełącza się na inny wątek. Prosty harmonogram decyduje, który wątek ma najwyższy priorytet i jest faktycznie wykonywany w rdzeniu.

Na komputerze z jednym rdzeniem nic się tak naprawdę nie dzieje „w tym samym czasie”. To wszystko tylko przeplatane wykonanie.

Istnieje wiele sposobów osiągnięcia przeplatania. Wiele.

Załóżmy, że masz prosty proces dwu-wątkowy, który używa prostej blokady, dzięki czemu oba wątki mogą zapisywać do wspólnej zmiennej. Masz sześć bloków kodu.

  • T1-przed zamkiem
  • T1-z zamkiem
  • Blokada T1
  • T2 przed zamkiem
  • T2-z zamkiem
  • Blokada T2

[Może to być pętla lub mieć więcej blokad lub cokolwiek innego. Wszystko staje się dłuższe, a nie bardziej złożone.]

Kroki T1 muszą przebiegać w kolejności (T1-przed, T1-z, T1-po), a kroki T2 muszą przebiegać w kolejności (T2-przed, T2-z, T2-po).

Oprócz ograniczenia „w kolejności” można je przeplatać w dowolny sposób. Tak czy inaczej. Można je uruchomić zgodnie z powyższym opisem. Kolejnym ważnym zamówieniem jest (T1-przed, T2-przed, T2-zamek, T1-zamek, T2-później, T1-później). Istnieje wiele ważnych zamówień.

Czekać.

To tylko maszyna stanów z sześcioma stanami.

To niedeterministyczne automaty skończone. Kolejność stanów T1-xxx ze stanami T2-xxx jest nieokreślona i nie ma znaczenia. Są więc miejsca, w których „następnym stanem” jest rzut monetą.

Na przykład, kiedy FSM się uruchamia, zarówno T1-przed jak i T2-przedtem są legalnymi pierwszymi stanami. Rzuć monetą.

Powiedzmy, że pojawił się T1-wcześniej. Zrób to. Kiedy to zrobisz, istnieje wybór pomiędzy T1-z i T2-przed. Rzuć monetą.

Na każdym kroku w FSM będą dwie opcje (dwa wątki - dwie opcje), a rzut monetą może określić, który konkretny stan jest przestrzegany.

S.Lott
źródło
Dziękuję, miłe wytłumaczenie. A co z maszyną wielordzeniową? Myślę, że nie ma wyraźnego sposobu na wykorzystanie rdzeni w maszynie stanu Java? W tym celu trzeba polegać na systemie operacyjnym, prawda?
Victor Sorokin,
5
Maszyna wielordzeniowa sprawia, że ​​planowanie jest nieco bardziej skomplikowane. Jednak wszystkie rdzenie zapisują w jednej wspólnej pamięci, więc kolejność zapisu w pamięci między dwoma rdzeniami oznacza, że ​​- zasadniczo - wróciliśmy do przeplatanego wykonywania zapisów w pamięci. System operacyjny wykorzystuje rdzenie, a JVM wykorzystuje to. Nie musisz się nad tym zastanawiać.
S.Lott,
9

Pisanie funkcji blokujących jest przeznaczone dla osób, które nie mogą tworzyć automatów;)

Wątki są przydatne, jeśli nie można obejść blokowania. Żadna podstawowa aktywność komputera nie blokuje naprawdę, po prostu wiele z nich zostało zaimplementowanych w ten sposób, aby ułatwić obsługę. Zamiast zwracać znak lub „odczyt nieudany”, funkcja odczytu blokuje się, dopóki cały bufor nie zostanie odczytany. Zamiast sprawdzać komunikat zwrotny w kolejce i zwracać go, jeśli nie zostanie znaleziony, funkcja połączenia czeka na odpowiedź.

Nie można używać funkcji blokujących w maszynie stanów (przynajmniej takiej, której nie można „zamrozić”).

I tak, używanie automatu stanów jest realną alternatywą. W systemach czasu rzeczywistego jest to jedyna opcja - system zapewniający platformę dla maszyny. Używanie wątków i funkcji blokujących jest po prostu „łatwym wyjściem”, ponieważ zwykle jedno wywołanie funkcji blokującej zastępuje około 3-4 stany w maszynie stanów.

SF.
źródło
Błąd strony kodowej w programie do wykonywania pojedynczego kontekstu zasadniczo blokuje. Z definicji kod, który ma pojedynczy kontekst wykonania, nie może robić postępu do przodu, dopóki nie będzie dostępna kolejna porcja kodu w przepływie.
David Schwartz,
1
@David Schwartz: prawda, zasadniczo blokuje; ale to nie jest „operacja”, ponieważ nie jest to coś, co robi zablokowany kod, to coś, co się z nim dzieje.
Javier
1
Odczyt pliku nie jest zasadniczo blokowany - zawsze można go podzielić na żądanie odczytu danej lokalizacji i pozyskanie danych z buforów po spełnieniu żądania. Błąd strony jest obejściem przypadkowego / heurystycznego użycia wymiany. Stanie się tak, jeśli dany stan zostanie wprowadzony przed udostępnieniem wszystkich danych niezbędnych do jego wykonania - brak przewidywania, coś sprzecznego z koncepcją automatu stanowego. Jeśli operacje zamiany i zamiany są częścią automatu stanów, błąd strony nie wystąpi.
SF.
1
@David Schwartz: Definicja zachowania „blokującego” zawsze podlega wymogom „w czasie rzeczywistym”. Na przykład: błąd strony kodowej jest uważany za nieblokujący dla aplikacji, która potrzebuje czasu reakcji rzędu setek milisekund. Z drugiej strony, jeśli aplikacja ma ścisłe wymagania w czasie rzeczywistym, w ogóle nie używałaby pamięci wirtualnej.
MAR
1
@Mar: ... lub użyj deterministycznych algorytmów wymiany, które gwarantują pobranie wymaganych danych, zanim staną się one konieczne.
SF.
9

W jaki sposób można osiągnąć funkcjonalność wielowątkową w języku wysokiego poziomu, takim jak Java, używając tylko jednego wątku i automatu stanów? Na przykład co zrobić, jeśli do wykonania są 2 działania (wykonywanie obliczeń i wykonywanie operacji we / wy) i jedno działanie może zostać zablokowane?

To, co opisujesz, nazywa się współpracującym wielozadaniowością , w którym zadania otrzymują procesor i oczekuje się, że zrzeknie się go dobrowolnie po upływie określonego czasu lub aktywności. Zadanie, które nie współpracuje przez dalsze korzystanie z procesora lub blokowanie gumy całej pracy i brak sprzętowego timera nadzorującego, nie ma nic, co kod nadzorujący zadania może z tym zrobić.

To, co widzisz w nowoczesnych systemach, nazywa się zapobiegawczym wielozadaniowością , czyli tam, gdzie zadania nie muszą rezygnować z procesora, ponieważ superwizor robi to za nich, gdy nadejdzie przerwanie generowane przez sprzęt. Procedura usługi przerwania w superwizorze zapisuje stan procesora i przywraca go następnym razem, gdy zadanie zostanie uznane za zasługujące na wycinek czasu, a następnie przywraca stan z dowolnego zadania, które ma zostać wykonane, i wskakuje z powrotem, jakby nic się nie wydarzyło . To działanie nazywa się przełączaniem kontekstu i może być kosztowne.

Czy używanie „tylko maszyny stanów” jest realną alternatywą dla wielowątkowości w językach wysokiego poziomu?

Wykonalny? Pewnie. Rozsądny? Czasami. To, czy użyjesz nici, czy jakiejś formy domowej wielozadaniowej współpracy (np. Maszyny stanowe), zależy od kompromisów, które chcesz zrobić.

Wątki upraszczają projektowanie zadań do tego stopnia, że ​​można traktować każdy z nich jak własny program, który dzieli się przestrzenią danych z innymi. Daje to swobodę skupienia się na wykonywanym zadaniu, a nie na całym zarządzaniu i pracach domowych wymaganych do wykonania iteracji na raz. Ale ponieważ żaden dobry uczynek nie pozostaje bezkarny, płacisz za całą tę wygodę w przełącznikach kontekstowych. Posiadanie wielu wątków, które dają procesorowi minimalną pracę (dobrowolnie lub wykonując coś, co blokuje, takie jak operacje we / wy), może pochłonąć dużo czasu procesora podczas przełączania kontekstu. Jest to szczególnie ważne, jeśli operacje blokowania rzadko blokują się bardzo długo.

Istnieją sytuacje, w których trasa kooperacyjna ma większy sens. Kiedyś musiałem napisać oprogramowanie dla użytkownika dla sprzętu, który przesyłał strumieniowo wiele kanałów danych przez interfejs odwzorowany w pamięci, który wymagał odpytywania. Każdy kanał był obiektem zbudowanym w taki sposób, że mogłem pozwolić mu działać jako wątek lub wielokrotnie wykonywać pojedynczy cykl odpytywania.

Wydajność wersji wielowątkowej wcale nie była dobra z dokładnie tego powodu, który opisałem powyżej: każdy wątek wykonywał minimalną pracę, a następnie produkował procesor, więc inne kanały mogły mieć trochę czasu, powodując wiele przełączeń kontekstu. Zezwolenie na uruchamianie wątków do momentu wstrzymania pomogło w zwiększeniu przepustowości, ale spowodowało, że niektóre kanały nie były obsługiwane, zanim sprzęt nie przepełni bufora, ponieważ nie dostali wystarczająco dużo czasu.

Wersja jednowątkowa, która wykonywała nawet iteracje każdego kanału, działała jak oparzona małpa, a obciążenie systemu spadało jak kamień. Karą, którą zapłaciłem za dodatkowy występ, było to, że sam musiałem żonglować zadaniami. W tym przypadku kod do zrobienia tego był na tyle prosty, że koszt jego opracowania i utrzymania był wart poprawy wydajności. Myślę, że to naprawdę podstawa. Gdyby moje wątki były tymi, które siedziały i czekały na jakieś wywołanie systemowe, to ćwiczenie prawdopodobnie nie byłoby tego warte.

To prowadzi mnie do komentarza Coxa: wątki nie są przeznaczone wyłącznie dla osób, które nie potrafią pisać automatów państwowych. Niektórzy ludzie są w stanie to zrobić, ale decydują się na użycie puszkowanej maszyny stanów (tj. Wątku) w celu wykonania pracy wcześniej lub z mniejszą złożonością.

Blrfl
źródło
2

co zrobić, jeśli do wykonania są 2 działania (wykonywanie obliczeń i wykonywanie operacji we / wy) i jedno działanie może zostać zablokowane?

Cóż, szczerze mówiąc, nie wyobrażam sobie, jak poradzić sobie z blokowaniem wejść / wyjść bez wątków. Nazywa się to przecież blokowaniem tylko dlatego, że wywołuje go kod, który go wywołuje wait.

Po przeczytaniu oryginalnej wiadomości e-mail Coxa (poniżej) zwraca uwagę, że wątki nie skalują się dobrze. Mam na myśli, co jeśli jest 100 żądań We / Wy? 1000? 10000? Cox wskazuje, że posiadanie dużej liczby wątków może prowadzić do poważnych problemów:

Od: Alan Cox ([email protected])
Data: Pt 21 stycznia 2000 - 13:33:52 EST

artykuł IBM), że jeśli twoja aplikacja zależy od ogromnej liczby wątków, zawsze będziesz walczył z harmonogramem? wiele osób rzuca wiele wątków na problem i może to być naprawdę zły projekt.

To najmniej zmartwień. 1000 wątków to 8 MB stosów jądra i wystarczająca liczba przełączeń zadań, aby mieć pewność, że równie dobrze możesz wyłączyć większość pamięci podręcznej. Komputer jest maszyną stanu. Wątki są dla osób, które nie mogą programować automatów stanów.

Istnieje wiele przypadków, w których Linux zdecydowanie nie pomaga w sytuacji, zwłaszcza asynchroniczne blokowe operacje we / wy.

Alan

źródło: Re: Interesująca analiza wątków jądra Linuxa przez IBM (archiwa list dyskusyjnych jądra Linux)

komar
źródło
1
  • Teoretycznie to prawda. W rzeczywistości wątki są tylko wydajną abstrakcją używaną do programowania takiej maszyny stanów. Są tak wydajne, że można je również wykorzystać do programowania statystyk i sieci Petriego (tj. Zachowania równoległe, w których maszyny stanowe są w zasadzie sekwencyjne).

  • Problem z automatami stanowymi polega na eksplozji kombinatorycznej. Liczba stanów komputera z 4G RAM to 2 ^ (2 ^ 32) stany (nie licząc napędu dyskowego 2T).

  • Dla mężczyzny, którego jedynym narzędziem jest młotek, każdy problem wygląda jak gwóźdź.

mouviciel
źródło
1

Wątki są jedyną opcją w dwóch przypadkach:

  • używać wielu rdzeni bez separacji pamięci.
  • radzić sobie z zewnętrznym kodem, który blokuje.

Po drugie, większość ludzi uważa, że ​​wątki są nieuniknione przy wykonywaniu operacji we / wy lub programowania sieciowego, ale zwykle dzieje się tak, ponieważ nie wiedzą, że ich system operacyjny ma bardziej zaawansowany interfejs API (lub nie chcą z nim walczyć).

Jeśli chodzi o łatwość użycia i czytelność, zawsze istnieją pętle zdarzeń (takie jak libev lub EventMachine ), które sprawiają, że programowanie maszyny stanów jest prawie tak proste jak robienie z wątkami, a jednocześnie daje wystarczającą kontrolę, aby zapomnieć o problemach z synchronizacją.

mbq
źródło
1
Najlepsze z obu światów: małe, blokujące maszyny stanów w wątkach tworzą bardzo prosty kod aplikacji. A wątki ładnie dzielą się na rdzenie, jeśli je masz. Jeśli wszystko nie ma co najmniej dwóch rdzeni, wkrótce. tj. telefony z czterordzeniowym ramieniem w 2012 roku.
Tim Williscroft
0

Dobrym sposobem na sprawdzenie sposobu interakcji maszyn stanów i wielowątkowości jest spojrzenie na procedury obsługi zdarzeń GUI. Wiele aplikacji / frameworków GUI wykorzystuje jeden wątek GUI, który będzie sondował możliwe źródła danych wejściowych i wywoływał funkcję dla każdego otrzymanego wejścia; w zasadzie można to zapisać jako ogromny przełącznik:

while (true) {
    switch (event) {
        case ButtonPressed:
        ...
        case MachineIsBurning:
        ....
    }
}

Teraz dość szybko staje się jasne, że poziom kontroli wysokiego poziomu w tej konstrukcji nie może być wysoki: Procedura obsługi ButtonPressed musi zakończyć się bez interakcji użytkownika i powrócić do głównej pętli, ponieważ jeśli nie, żadne dalsze zdarzenia użytkownika może być przetwarzany. Jeśli ma jakiś stan do zapisania, ten stan musi być zapisany w zmiennych globalnych lub statycznych, ale nie na stosie; to znaczy normalny przepływ kontroli w języku imperatywnym jest ograniczony. Zasadniczo jesteś ograniczony do maszyny stanu.

Może to stać się dość nieuporządkowane po zagnieżdżeniu podprogramów, które muszą na przykład zapisać poziom rekurencji. Lub są w trakcie czytania pliku, ale plik jest w tej chwili niedostępny. Lub są po prostu w długim obliczeniu. We wszystkich tych przypadkach pożądane jest zapisanie stanu bieżącego wykonania i powrót do głównej pętli, a jest to wielowątkowość . Nic dodać nic ująć.

Cała sprawa stała się nieco bardziej skomplikowana wraz z wprowadzeniem zapobiegawczego wielowątkowości (tj. System operacyjny decyduje, kiedy wątki powinny dać kontrolę), i dlatego połączenie nie jest od razu jasne.

Tak więc, aby odpowiedzieć na ostatnie pytanie: Tak, automat stanowy jest alternatywą, większość GUI działa w ten sposób z wątkiem GUI. Po prostu nie pchaj maszyny stanowej za daleko, staje się ona nie do utrzymania naprawdę szybko.

Thiton
źródło
0

Pytanie o to, czy użycie maszyny stanów jest wykonalne w języku wysokiego poziomu, przypomina trochę pytanie, czy pisanie w asemblerze jest realną alternatywą dla używania języka wysokiego poziomu. Oboje mają swoje miejsce w odpowiedniej sytuacji.

Abstrakcja używania wątków ułatwia wdrożenie bardziej złożonych systemów równoległych, ale ostatecznie wszystkie systemy równoległe mają te same problemy do rozwiązania. Klasyczne problemy, takie jak Deadlock / Livelock i inwersja priorytetów są tak samo możliwe w systemach opartych na automatach stanów, jak w systemach równoległych z pamięcią współużytkowaną , systemie NUMA lub nawet CSP , jeśli jest wystarczająco złożony.

Mark Booth
źródło
0

Nie sądzę, że tak - maszyny stanowe są bardzo „elegancką” koncepcją komputerową, ale, jak mówisz, są dość skomplikowane. A skomplikowane rzeczy trudno jest naprawić. A rzeczy, które są nie tak, są po prostu zepsute, więc jeśli nie jesteś geniuszem postury Alana Coxa, trzymaj się rzeczy, o których wiesz, że działają - pozostaw „sprytne kodowanie” projektom edukacyjnym.

Możesz powiedzieć, kiedy ktoś na próżno próbował to zrobić, ponieważ (zakładając, że działa dobrze), jeśli chodzi o jego utrzymanie, okazuje się, że zadanie jest prawie niemożliwe. Oryginalny „geniusz” przeszedł na dalszy plan, pozostawiając cię z trudem do zrozumienia kodu (ponieważ tego rodzaju programiści nie zostawiają zbyt wielu komentarzy, nie mówiąc już o dokumentacji technicznej).

W niektórych przypadkach lepszym wyborem jest automat stanowy - myślę teraz o typach osadzonych, w których używane są pewne wzorce automatów stanowych, które są używane wielokrotnie i w bardziej sformalizowany sposób (tj. Odpowiednia inżynieria :))

Wątek może być trudny do prawidłowego wykonania, ale istnieją wzorce, które mogą ci pomóc - głównie poprzez zmniejszenie potrzeby udostępniania danych między wątkami.

Ostatnim punktem jest to, że nowoczesne komputery i tak działają na wielu rdzeniach, więc automat stanowy tak naprawdę nie skorzysta z dostępnych zasobów. Wątkowanie może tutaj lepiej wykonać.

gbjbaanb
źródło
2
Maszyny stanowe wcale nie są skomplikowane! Złożone maszyny stanów są skomplikowane, ale wszystkie złożone systemy: o)
MaR
2
-1 dla „nie próbuj”. to najgorsza rada, jaką możesz udzielić.
Javier
1
-1 „Nie próbuj”? To po prostu głupie. Chciałbym również zakwestionować twoje twierdzenie, że maszyny stanowe są trudne. Kiedy dostaniesz się do czegoś w rodzaju Heirarchal Fuzzy State Machine ... wtedy tak, to jest trochę bardziej skomplikowane. Ale prosty automat stanowy? To dość podstawowe rzeczy, których co 2 lata uczyłem się, kiedy byłem w szkole.
Steven Evers,
pozwólcie mi sformułować fragment „nie próbuj” ...
gbjbaanb
0

Dobry przykład poprawnego użycia automatu stanów zamiast wątków: nginx vs apache2. Ogólnie można założyć, że nginx obsługuje wszystkie połączenia w jednym wątku, apache2 tworzy wątek na połączenie.

Ale dla mnie używanie automatów stanowych w porównaniu z wątkami jest całkiem podobne przy użyciu idealnie spreparowanego ręcznie asm vs java: możesz osiągnąć niewiarygodne wyniki, ale wymaga to wielu wysiłków programistów, dużej dyscypliny, sprawia, że ​​projekt jest bardziej złożony i warty tylko wtedy, gdy jest używany przez wielu innych programistów. Jeśli więc chcesz stworzyć szybki serwer sieciowy - użyj machin stanów i asynchronizuj operacje we / wy. Jeśli piszesz projekt (nie bibliotekę do użycia wszędzie) - użyj wątków.

ZeusTheTrueGod
źródło