Maszyny stanowe a wątki

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?

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.

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.

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ą.

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 (alan@lxorguk.ukuu.org.uk)
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)

• 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ź.

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ą.

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.

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.

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ć.

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.