Dlaczego stos wywołań ma statyczny maksymalny rozmiar?

Pracując z kilkoma językami programowania, zawsze zastanawiałem się, dlaczego stos wątków ma predefiniowany maksymalny rozmiar, zamiast rozszerzać się automatycznie w razie potrzeby. 

Dla porównania, niektóre bardzo popularne struktury wysokiego poziomu (listy, mapy itp.), Które można znaleźć w większości języków programowania, są zaprojektowane tak, aby rosły w miarę potrzeb, podczas gdy dodawane są nowe elementy, których rozmiar jest ograniczony tylko dostępną pamięcią lub limitami obliczeniowymi ( np. adresowanie 32-bitowe).

Nie znam jednak żadnych języków programowania ani środowisk uruchomieniowych, w których maksymalny rozmiar stosu nie jest wstępnie ograniczony przez jakąś domyślną lub kompilatorową opcję. Właśnie dlatego zbyt duża rekurencja spowoduje bardzo szybko błąd / wyjątek przepełnienia stosu, nawet jeśli na stos zostanie wykorzystany tylko minimalny procent pamięci dostępnej dla procesu.

Dlaczego jest tak, że większość (jeśli nie wszystkie) środowiska wykonawcze ustawiają maksymalny limit rozmiaru, jaki stos może zwiększyć w czasie wykonywania?

Możliwe jest napisanie systemu operacyjnego, który nie wymaga, aby stosy były ciągłe w przestrzeni adresowej. Zasadniczo potrzebujesz dodatkowego zamieszania w konwencji wywoływania, aby upewnić się, że:

1. jeśli w bieżącym zasięgu stosu nie ma wystarczającej ilości miejsca dla funkcji, którą wywołujesz, tworzysz nowy zasięg stosu i przesuwasz wskaźnik stosu, aby wskazywał na początek w ramach wywołania.

2. po powrocie z tego połączenia wracasz do pierwotnego zakresu stosu. Najprawdopodobniej zachowujesz ten utworzony w (1) do przyszłego wykorzystania przez ten sam wątek. Zasadniczo możesz go zwolnić, ale w ten sposób leżą raczej nieefektywne przypadki, w których w pętli przeskakujesz do przodu i do tyłu, a każde połączenie wymaga alokacji pamięci.

3. setjmpi longjmp, lub jakikolwiek inny ekwiwalent systemu operacyjnego dla nielokalnego przeniesienia kontroli, bierze udział i może poprawnie wrócić do starego zakresu stosu, gdy jest to wymagane.

Mówię „konwencja wywoływania” - mówiąc konkretnie, myślę, że najlepiej jest to zrobić w prologu funkcji, a nie przez osobę wywołującą, ale moja pamięć o tym jest niejasna.

Powodem, dla którego wiele języków określa stały rozmiar stosu dla wątku, jest to, że chcą pracować przy użyciu stosu rodzimego w systemach operacyjnych, które tego nie robią. Jak mówią odpowiedzi wszystkich innych osób, przy założeniu, że każdy stos musi być ciągły w przestrzeni adresowej i nie może być przenoszony, musisz zarezerwować określony zakres adresów do wykorzystania przez każdy wątek. Oznacza to wybór rozmiaru z przodu. Nawet jeśli twoja przestrzeń adresowa jest ogromna, a rozmiar, który wybierasz, jest naprawdę duży, nadal musisz ją wybrać, jak tylko będziesz mieć dwa wątki.

„Aha”, mówisz, „jakie są te rzekome systemy operacyjne, które używają nieciągłych stosów? Założę się, że to jakiś niejasny akademicki system, który mi się nie przyda!”. Cóż, to kolejne pytanie, które na szczęście zostało już zadane i na które udzielono odpowiedzi.

Te struktury danych zwykle mają właściwości, których stos systemu operacyjnego nie ma:

• Listy połączone nie wymagają ciągłej przestrzeni adresowej. Dzięki temu mogą dodać pamięć z dowolnego miejsca, gdy tylko dorosną.

• Nawet kolekcje, które wymagają ciągłego przechowywania, takie jak wektor C ++, mają przewagę nad stosami systemu operacyjnego: mogą zadeklarować, że wszystkie wskaźniki / iteratory są nieprawidłowe, gdy rosną. Z drugiej strony stos systemu operacyjnego musi utrzymywać wskaźniki na stosie ważne, dopóki funkcja nie dołączy do ramki, do której należy cel.

Język programowania lub środowisko wykonawcze może wdrożyć własne stosy, które są nieciągłe lub ruchome, aby uniknąć ograniczeń stosów systemu operacyjnego. Golang używa takich niestandardowych stosów do obsługi bardzo dużej liczby procedur wspólnych, pierwotnie zaimplementowanych jako pamięć niesąsiadująca, a teraz poprzez ruchome stosy dzięki śledzeniu wskaźnika (patrz komentarz hobb). Python bez stosów, Lua i Erlang mogą również używać niestandardowych stosów, ale tego nie potwierdziłem.

W systemach 64-bitowych można skonfigurować stosunkowo duże stosy przy stosunkowo niskich kosztach, ponieważ przestrzeń adresowa jest duża, a pamięć fizyczna jest przydzielana tylko wtedy, gdy faktycznie z niej korzystasz.

W praktyce powiększanie stosu jest trudne (a czasem niemożliwe). Zrozumienie, dlaczego wymaga pewnego zrozumienia pamięci wirtualnej.

W Ye Olde Days aplikacji jednowątkowych i ciągłej pamięci trzy były trzema komponentami przestrzeni adresowej procesu: kodem, stertą i stosem. To, jak te trzy układano, zależało od systemu operacyjnego, ale ogólnie kod był pierwszy, poczynając od dolnej części pamięci, sterty następowały dalej i rosły w górę, a stos zaczynał się na górze pamięci i wzrastał w dół. Pewna pamięć była zarezerwowana dla systemu operacyjnego, ale możemy to zignorować. Programy w tamtych czasach miały nieco bardziej dramatyczne przepełnienia stosu: stos zawalałby się na stosie, i w zależności od tego, który zaktualizowano jako pierwszy, albo pracowałeś ze złymi danymi, albo wróciłeś z podprogramu do dowolnej części pamięci.

Zarządzanie pamięcią zmieniło nieco ten model: z perspektywy programu nadal istniały trzy komponenty mapy pamięci procesu i były one ogólnie zorganizowane w ten sam sposób, ale teraz każdy z komponentów był zarządzany jako niezależny segment, a MMU zasygnalizowałoby System operacyjny, jeśli program próbował uzyskać dostęp do pamięci poza segmentem. Gdy już dysponujesz pamięcią wirtualną, nie było potrzeby ani chęci udzielania programowi dostępu do całej jego przestrzeni adresowej. Tak więc segmentom przypisano stałe granice.

Dlaczego więc nie jest pożądane, aby dać programowi dostęp do pełnej przestrzeni adresowej? Ponieważ ta pamięć stanowi „ładunek popełnienia” przeciwko zamianie; w dowolnym momencie może być konieczne zapisanie dowolnej lub całej pamięci dla jednego programu w celu zamiany, aby zrobić miejsce dla pamięci innego programu. Jeśli każdy program może potencjalnie zużyć 2 GB swapu, musisz albo zapewnić wystarczającą ilość swapów dla wszystkich swoich programów, albo zaryzykować, że dwa programy będą potrzebowały więcej niż mogłyby.

W tym momencie, zakładając wystarczającą przestrzeń adresu wirtualnego, to mógłby rozszerzyć te segmenty, jeśli to konieczne, a segment danych (heap) ma w rzeczywistości rośnie z upływem czasu: zaczynasz z małym segmencie danych, a gdy przydzielania pamięci żąda więcej przestrzeni gdy jest to jest potrzebne. W tym momencie, przy użyciu pojedynczego stosu, fizycznie byłoby możliwe rozszerzenie segmentu stosu: system operacyjny mógłby złapać próbę wypchnięcia czegoś poza segment i dodać więcej pamięci. Ale to również nie jest szczególnie pożądane.

Wprowadź wielowątkowość. W takim przypadku każdy wątek ma niezależny segment stosu, ponownie o ustalonym rozmiarze. Ale teraz segmenty są ułożone jeden po drugim w wirtualnej przestrzeni adresowej, więc nie ma sposobu na rozwinięcie jednego segmentu bez przesunięcia drugiego - czego nie można zrobić, ponieważ program potencjalnie będzie miał wskaźniki na pamięć żyjące na stosie. Alternatywnie możesz zostawić trochę miejsca między segmentami, ale przestrzeń ta zostałaby zmarnowana w prawie wszystkich przypadkach. Lepszym rozwiązaniem było obciążenie dewelopera aplikacji: jeśli naprawdę potrzebujesz głębokich stosów, możesz to określić podczas tworzenia wątku.

Dzisiaj, dzięki 64-bitowej wirtualnej przestrzeni adresowej, moglibyśmy tworzyć efektywnie nieskończone stosy dla efektywnie nieskończonej liczby wątków. Ale znowu, nie jest to szczególnie pożądane: w prawie wszystkich przypadkach przepełnienie stosu oznacza błąd w kodzie. Zapewnienie stosu 1 GB po prostu odracza wykrycie tego błędu.

Stos mający ustalony maksymalny rozmiar nie jest wszechobecny.

Trudno jest również uzyskać właściwy poziom: głębokości stosów są zgodne z rozkładem prawa mocy, co oznacza, że ​​bez względu na to, jak mały jest rozmiar stosu, nadal będzie znaczna część funkcji z jeszcze mniejszymi stosami (więc marnujesz miejsce), i bez względu na to, jak duży będziesz to robił, nadal będą funkcje z jeszcze większymi stosami (więc wymusza się błąd przepełnienia stosu dla funkcji, które nie zawierają błędu). Innymi słowy: niezależnie od wybranego rozmiaru, zawsze będzie on jednocześnie zbyt mały i zbyt duży.

Możesz rozwiązać pierwszy problem, pozwalając, aby stosy zaczynały się od małego i rosły dynamicznie, ale nadal masz drugi problem. A jeśli i tak pozwalasz dynamicznie rosnąć stosowi, to po co nakładać na niego arbitralny limit?

Istnieją systemy, w których stosy mogą rosnąć dynamicznie i nie mają maksymalnego rozmiaru: na przykład Erlang, Go, Smalltalk i Scheme. Istnieje wiele sposobów realizacji czegoś takiego:

• ruchome stosy: gdy ciągły stos nie może już rosnąć, ponieważ jest coś innego na drodze, przenieś go w inne miejsce w pamięci, z większą ilością wolnego miejsca
• nieciągłe stosy: zamiast alokować cały stos w jednym ciągłym obszarze pamięci, przydziel go w wielu obszarach pamięci
• stosy przydzielone do stosu: zamiast mieć oddzielne obszary pamięci dla stosu i stosu, po prostu przydziel stos na stosie; jak zauważyłeś, struktury danych alokowane na stercie zwykle nie mają problemów z powiększaniem się i kurczeniem w razie potrzeby
• nie używaj stosów w ogóle: jest to również opcja, np. zamiast śledzić stan funkcji na stosie, niech funkcja przekaże kontynuację do odbiorcy

Gdy tylko masz potężne nielokalne konstrukcje sterowania przepływem, pomysł pojedynczego ciągłego stosu i tak wychodzi z okna: wznawiane wyjątki i kontynuacje, na przykład, „rozwidlają” stos, dzięki czemu faktycznie powstaje sieć stosów (np. zaimplementowane ze stosem spaghetti). Również systemy z pierwszorzędnymi modyfikowalnymi stosami, takie jak Smalltalk, prawie wymagają stosów spaghetti lub czegoś podobnego.

System operacyjny musi dać ciągły blok, gdy żądany jest stos. Jedynym sposobem, aby to zrobić, jest określenie maksymalnego rozmiaru.

Na przykład, powiedzmy, że pamięć wygląda tak podczas żądania (X reprezentuje używane, Os nieużywane):

XOOOXOOXOOOOOX

Jeśli żądanie stosu ma rozmiar 6, odpowiedź systemu operacyjnego odpowie „nie”, nawet jeśli dostępnych jest więcej niż 6. W przypadku żądania stosu o rozmiarze 3 odpowiedzią systemu operacyjnego będzie jeden z obszarów 3 pustych miejsc (OS) z rzędu.

Widać także trudność pozwalającą na wzrost, gdy jest zajęta kolejna szczelina.

Pozostałe wymienione obiekty (listy itp.) Nie wchodzą na stos, kończą na stosie w obszarach niesąsiadujących lub fragmentarycznych, więc gdy rosną, po prostu chwytają przestrzeń, nie wymagają ciągłości, ponieważ są zarządzać inaczej.

Większość systemów ustawia rozsądną wartość wielkości stosu, można ją przesłonić, gdy wątek jest konstruowany, jeśli wymagany jest większy rozmiar.

W Linuksie jest to wyłącznie limit zasobów, który istnieje, aby zabić niekontrolowane procesy, zanim zużyją szkodliwe ilości zasobów. W moim systemie Debian następujący kod

#include <sys/resource.h>
#include <stdio.h>

int main() {
    struct rlimit limits;
    getrlimit(RLIMIT_STACK, &limits);
    printf("   soft limit = 0x%016lx\n", limits.rlim_cur);
    printf("   hard limit = 0x%016lx\n", limits.rlim_max);
    printf("RLIM_INFINITY = 0x%016lx\n", RLIM_INFINITY);
}

produkuje dane wyjściowe

   soft limit = 0x0000000000800000
   hard limit = 0xffffffffffffffff
RLIM_INFINITY = 0xffffffffffffffff

Pamiętaj, że twardy limit jest ustawiony na RLIM_INFINITY: Proces może podnieść swój miękki limit do dowolnej kwoty. Jednak dopóki programista nie ma powodu, aby sądzić, że program naprawdę potrzebuje niezwykłej ilości pamięci stosu, proces zostanie zabity, gdy przekroczy rozmiar stosu ośmiu mebibajtów.

Z powodu tego limitu niekontrolowany proces (niezamierzona nieskończona rekurencja) zostaje zabity na długo, zanim zacznie zużywać tak duże ilości pamięci, że system będzie zmuszony rozpocząć zamianę. Może to zrobić różnicę między zawieszonym procesem a zawieszonym serwerem. Jednak nie ogranicza to programów z uzasadnioną potrzebą dużego stosu, wystarczy ustawić miękki limit na odpowiednią wartość.

Technicznie, stosy rosną dynamicznie: kiedy limit miękkości jest ustawiony na osiem mebibajtów, nie oznacza to, że ta ilość pamięci została jeszcze zmapowana. Byłoby to raczej marnotrawstwem, ponieważ większość programów nigdy nie zbliża się do swoich limitów miękkich. Jądro raczej wykryje dostęp poniżej stosu i po prostu zamapuje strony pamięci w razie potrzeby. Zatem jedynym prawdziwym ograniczeniem wielkości stosu jest dostępna pamięć w systemach 64-bitowych (fragmentacja przestrzeni adresowej jest raczej teoretyczna z wielkością przestrzeni adresowej 16 zebibajtów).

Maksymalny rozmiar stosu jest statyczna, ponieważ jest to definicja „maksimum” . Każde maksimum na dowolną wartość jest ustaloną, uzgodnioną wartością graniczną. Jeśli zachowuje się jak spontanicznie poruszający się cel, nie jest to maksimum.

Stosy w systemach operacyjnych z pamięcią wirtualną faktycznie rosną dynamicznie, aż do maksimum .

Mówiąc o tym, nie musi być statyczny. Może być konfigurowalny, nawet na proces lub wątek.

Jeśli pytanie brzmi „dlaczego jest maksymalny rozmiar stosu” (sztucznie narzucony, zwykle o wiele mniejszy niż dostępna pamięć)?

Jednym z powodów jest to, że większość algorytmów nie wymaga ogromnej ilości miejsca na stosie. Duży stos wskazuje na możliwą niekontrolowaną rekurencję . Dobrze jest zatrzymać niekontrolowaną rekurencję, zanim przydzieli ona całą dostępną pamięć. Problemem, który wygląda jak niekontrolowana rekurencja, jest użycie zdegenerowanego stosu, być może wywołane nieoczekiwanym przypadkiem testowym. Załóżmy na przykład, że parser dla binarnego operatora infix działa przez rekurencję na prawym operandzie: parsuj pierwszy operand, operator skanowania, parsuj resztę wyrażenia. Oznacza to, że głębokość stosu jest proporcjonalna do długości wyrażenia: a op b op c op d .... Ogromny przypadek testowy tej formy będzie wymagał ogromnego stosu. Przerwanie programu, gdy osiągnie rozsądny limit stosu, to uchwyci.

Innym powodem ustalonego maksymalnego rozmiaru stosu jest to, że przestrzeń wirtualna dla tego stosu może być zarezerwowana przez specjalny rodzaj mapowania, a tym samym zagwarantowana. Gwarantowane oznacza, że ​​miejsce nie zostanie przydzielone innemu przydziałowi, który stos zderzy się z nim przed osiągnięciem limitu. Parametr maksymalnego rozmiaru stosu jest wymagany, aby zażądać tego mapowania.

Wątki wymagają maksymalnego rozmiaru stosu z podobnego powodu. Ich stosy są tworzone dynamicznie i nie można ich przenosić, jeśli się z czymś zderzą; przestrzeń wirtualna musi być zarezerwowana z góry i dla tego przydziału wymagany jest rozmiar.