Czy struktura stosu jest używana w procesach asynchronicznych?

To pytanie ma doskonałą odpowiedź Erica Lipperta opisującą, do czego służy ten stos. Przez lata wiedziałem - ogólnie mówiąc - co to jest stos i jak jest używany, ale niektóre jego odpowiedzi sprawiają, że zastanawiam się, czy ta struktura stosu jest dziś mniej używana, gdy programowanie asynchroniczne jest normą.

Z jego odpowiedzi:

stos jest częścią potwierdzania kontynuacji w języku bez coroutines.

W szczególności zastanawiam się nad tym , że część bez coroutines .

Wyjaśnia nieco więcej tutaj:

Korynty są funkcjami, które mogą pamiętać, gdzie były, poddać kontroli przez pewien czas kolejnej korowinie, a następnie wznowić tam, gdzie ją przerwały, ale niekoniecznie natychmiast po tym, jak tak zwane korowody się wydadzą. Pomyśl o „zwrocie zysków” lub „czekaniu” w C #, który musi pamiętać, gdzie się znajdowali, gdy żądany jest następny element lub operacja asynchroniczna została zakończona. Języki z coroutines lub podobnymi funkcjami językowymi wymagają bardziej zaawansowanych struktur danych niż stosu w celu wdrożenia kontynuacji.

Jest to doskonałe w odniesieniu do stosu, ale pozostawia mi bez odpowiedzi pytanie, jaka struktura jest używana, gdy stos jest zbyt prosty do obsługi tych funkcji językowych, które wymagają bardziej zaawansowanych struktur danych?

Czy stos zmienia się wraz z postępem technologii? Co to zastępuje? Czy to hybryda? (np. czy mój program .NET używa stosu, dopóki nie trafi w wywołanie asynchroniczne, a następnie przełącza się na inną strukturę aż do ukończenia, w którym momencie stos jest rozwijany z powrotem do stanu, w którym może być pewien kolejnych elementów itp.? )

To, że te scenariusze są zbyt zaawansowane dla stosu, ma sens, ale co zastępuje stos? Kiedy dowiedziałem się o tym lata temu, stos był tam, ponieważ był błyskawiczny i lekki, kawałek pamięci przydzielonej przy aplikacji poza stertą, ponieważ wspierał bardzo wydajne zarządzanie dla bieżącego zadania (zamierzona gra słów?). Co się zmieniło

Czy to hybryda? (np. czy mój program .NET używa stosu, dopóki nie trafi w wywołanie asynchroniczne, a następnie przełącza się na inną strukturę aż do ukończenia, w którym momencie stos jest rozwijany z powrotem do stanu, w którym może być pewien kolejnych elementów itp.? )

Zasadniczo tak.

Załóżmy, że mamy

async void MyButton_OnClick() { await Foo(); Bar(); }
async Task Foo() { await Task.Delay(123); Blah(); }

Oto niezwykle uproszczone wyjaśnienie, w jaki sposób kontynuowane są kontynuacje. Rzeczywisty kod jest znacznie bardziej złożony, ale ten pomysł przenika.

Kliknij przycisk. Wiadomość jest w kolejce. Pętla komunikatów przetwarza wiadomość i wywołuje moduł obsługi kliknięć, umieszczając na stosie adres zwrotny kolejki komunikatów. Oznacza to, że po zakończeniu procedury obsługi pętla komunikatów musi nadal działać. Tak więc kontynuacją programu obsługi jest pętla.

Moduł obsługi kliknięć wywołuje Foo (), umieszczając adres zwrotny na stosie. Oznacza to, że kontynuacja Foo jest pozostałą częścią procedury obsługi kliknięć.

Foo wywołuje Task.Delay, umieszczając swój adres zwrotny na stosie.

Task.Delay robi wszystko, co trzeba, aby natychmiast zwrócić zadanie. Stos jest wyskakujący i wróciliśmy do Foo.

Foo sprawdza zwrócone zadanie, aby sprawdzić, czy zostało zakończone. Nie jest. Kontynuacja tego czekają na to, aby zadzwonić Blah (), więc Foo tworzy delegata, który wywołuje Blah (), a sygnały, że delegować się jako kontynuacja zadania. (Właśnie popełniłem małe nieporozumienie; złapałeś go? Jeśli nie, ujawnimy to za chwilę.)

Następnie Foo tworzy własny obiekt Task, oznacza go jako niekompletny i zwraca go stosowi do programu obsługi kliknięć.

Moduł obsługi kliknięć sprawdza zadanie Foo i odkrywa, że ​​jest ono niekompletne. Kontynuacją oczekiwania w module obsługi jest wywołanie Bar (), więc moduł obsługi kliknięć tworzy delegata, który wywołuje Bar () i ustawia go jako kontynuację zadania zwróconego przez Foo (). Następnie zwraca stos do pętli komunikatów.

Pętla komunikatów przetwarza wiadomości. Ostatecznie magia timera utworzona przez zadanie opóźnienia robi swoje i wysyła komunikat do kolejki, informujący, że kontynuacja zadania opóźnienia może być teraz wykonana. Pętla komunikatów wywołuje więc kontynuację zadania, jak zwykle umieszczając się na stosie. Ten delegat nazywa Blah (). Blah () robi to, co robi i zwraca stos.

Co się teraz stanie? Oto trudny kawałek. Kontynuacja zadania opóźnienia nie tylko wywołuje Blah (). Musi także wywołać wywołanie Bar () , ale to zadanie nie wie o Bar!

Foo rzeczywiście stworzył delegata, że (1) wywołuje Blah () i (2) wywołuje kontynuację zadania, które Foo stworzył i oddał do obsługi zdarzeń. W ten sposób nazywamy delegata, który wywołuje Bar ().

A teraz zrobiliśmy wszystko, co musieliśmy zrobić, we właściwej kolejności. Ale nigdy nie przestawaliśmy przetwarzać wiadomości w pętli komunikatów na bardzo długo, więc aplikacja pozostała responsywna.

To, że te scenariusze są zbyt zaawansowane dla stosu, ma sens, ale co zastępuje stos?

Wykres obiektów zadań zawierający odniesienia do siebie za pośrednictwem klas zamknięcia delegatów. Te klasy zamknięcia są automatami państwowymi, które śledzą pozycję ostatnio wykonywanego czekania i wartości miejscowych. Dodatkowo w podanym przykładzie kolejka działań globalnych realizowana przez system operacyjny oraz pętla komunikatów, która wykonuje te akcje.

Ćwiczenie: jak myślisz, jak to wszystko działa w świecie bez pętli wiadomości? Na przykład aplikacje konsolowe. Oczekiwanie w aplikacji na konsolę jest zupełnie inne; czy możesz wywnioskować, jak to działa na podstawie tego, co wiesz do tej pory?

Kiedy dowiedziałem się o tym lata temu, stos był tam, ponieważ był błyskawiczny i lekki, kawałek pamięci przydzielonej przy aplikacji z dala od sterty, ponieważ wspierał wysoce wydajne zarządzanie dla danego zadania (zamierzona gra słów?). Co się zmieniło

Stosy są użyteczną strukturą danych, gdy czasy życia aktywacji metod tworzą stos, ale w moim przykładzie aktywacje modułu obsługi kliknięć, Foo, Bar i Blah nie tworzą stosu. Dlatego struktura danych reprezentująca ten przepływ pracy nie może być stosem; raczej jest to wykres zadań przydzielonych do sterty i delegatów, który reprezentuje przepływ pracy. Oczekiwania to punkty w przepływie pracy, w których nie można poczynić dalszych postępów w przepływie pracy, dopóki prace rozpoczęte wcześniej nie zostaną zakończone; podczas gdy czekamy, możemy wykonać inną pracę, która nie zależy od zakończenia tych konkretnych rozpoczętych zadań.

Stos to po prostu tablica ramek, w których ramki zawierają (1) wskaźniki do środka funkcji (gdzie nastąpiło wywołanie) i (2) wartości zmiennych lokalnych i temps. Kontynuacja zadań jest taka sama: delegat jest wskaźnikiem do funkcji i ma stan, który odwołuje się do określonego punktu na środku funkcji (gdzie nastąpiło oczekiwanie), a zamknięcie zawiera pola dla każdej zmiennej lokalnej lub tymczasowej . Ramki po prostu nie tworzą już ładnej, uporządkowanej tablicy, ale wszystkie informacje są takie same.

Appel napisał, że zbieranie starych śmieci papierowych może być szybsze niż przydzielanie stosu . Przeczytaj także jego książkę Kompilowanie z kontynuacjami i podręcznik usuwania śmieci . Niektóre techniki GC są (nieumyślnie) bardzo wydajne. Kontynuacja przechodzącą styl określa kanoniczną całego programu transformacji (CPS transformacji ), aby pozbyć się stosów (koncepcyjnie zastępujących ramek połączeń z sterty przydzielone zamknięć , innymi słowy „reifikacji” pojedynczych klatek zadzwonić jako indywidualnych „wartości” lub „obiektów” ).

Ale stos wywołań jest nadal bardzo szeroko stosowany, a obecne procesory mają dedykowany sprzęt (rejestr stosu, maszynę pamięci podręcznej itp.) Przeznaczony do stosów wywołań (i dzieje się tak, ponieważ większość języków programowania niskiego poziomu, zwłaszcza C, jest łatwiejsza do implement ze stosem wywołań). Zauważ też, że stosy są przyjazne dla pamięci podręcznej (i to ma duże znaczenie dla wydajności).

Praktycznie mówiąc, stosy połączeń są nadal dostępne. Ale mamy teraz wiele z nich, a czasami stos wywołań jest podzielony na wiele mniejszych segmentów (np. Po kilka stron o wielkości 4 KB każdy), które czasem są zbierane na śmieci lub przydzielane do stosu. Te segmenty stosu mogą być zorganizowane na jakiejś połączonej liście (lub w bardziej złożonej strukturze danych, gdy jest to potrzebne). Na przykład, GCC kompilatory mają takie -fsplit-stackmożliwości (szczególnie przydatnych dla Go, a jej „goroutines” i jego „procesów asynchronicznych”). Dzięki podzielonym stosom możesz mieć wiele tysięcy stosów (a procedury wspólne stają się łatwiejsze do wdrożenia) wykonanych z milionów segmentów małych stosów, a „odwijanie” stosu może być szybsze (lub co najmniej prawie tak szybkie, jak w przypadku pojedynczej porcji stos).

^{(innymi słowy, rozróżnienie między stosem a stertą jest rozmyte, ale może wymagać transformacji całego programu lub niezgodnej zmiany konwencji wywoływania i kompilatora)}

Zobacz także to i tamto oraz wiele artykułów (np. To ) omawiających transformację CPS. Przeczytaj także o ASLR i call / cc . Przeczytaj (i STFW) więcej o kontynuacjach .

Implementacje .CLR i .NET mogą nie mieć najnowocześniejszej transformacji GC i CPS z wielu pragmatycznych powodów. Jest to kompromis związany z transformacjami całych programów (i łatwością korzystania z niskopoziomowych procedur C i posiadania środowiska wykonawczego zakodowanego w C lub C ++).

Chicken Scheme używa stosu maszynowego (lub C) w niekonwencjonalny sposób z transformacją CPS: każda alokacja odbywa się na stosie, a gdy staje się zbyt duża, generacyjny etap kopiowania i przesyłania GC zdarza się, aby przenieść ostatnie przydzielone wartości stosu (i prawdopodobnie bieżąca kontynuacja) do stosu, a następnie stos jest drastycznie zmniejszany za pomocą dużego setjmp.

Przeczytaj także SICP , Pragmatyka języka programowania , Dragon Book , Lisp In Small Pieces .