Rozumiem, co to jest wskaźnik stosu - ale do czego służy?

Wskaźnik stosu wskazuje na górę stosu, który przechowuje dane na podstawie tak zwanej „LIFO”. Aby ukraść czyjąś analogię, to jest jak stos naczyń, w którym wkładasz i bierzesz naczynia na górze. Wskaźnik stosu, OTOH, wskazuje górne „naczynie” stosu. Przynajmniej tak jest w przypadku x86.

Ale dlaczego komputer / program „dba” o to, na co wskazuje wskaźnik stosu? Innymi słowy, jaki cel ma posiadanie wskaźnika stosu i wiedza, gdzie ma on służyć?

Będzie zrozumiałe wyjaśnienie dla programistów C.

Jakiemu celowi służy ten stos, a nie wyjaśnianiu jego struktury?

Masz wiele odpowiedzi, które dokładnie opisują strukturę danych przechowywanych na stosie, co, jak zauważam, jest przeciwieństwem zadanego pytania.

Stos, który służy stosowi : stos jest częścią powtórzenia kontynuacji w języku bez coroutines .

Rozpakujmy to.

Po prostu kontynuacja , odpowiedź na pytanie „co będzie dalej w moim programie?” Na każdym etapie każdego programu coś się wydarzy. Dwa operandy zostaną obliczone, następnie program kontynuuje obliczanie ich sumy, a następnie program kontynuuje, przypisując sumę do zmiennej, a następnie ... i tak dalej.

Reifikacja to tylko słowo falsutinowe do konkretnego wdrożenia abstrakcyjnej koncepcji. "Co się potem dzieje?" jest pojęciem abstrakcyjnym; sposób ułożenia stosu jest częścią tego, jak ta abstrakcyjna koncepcja przekształca się w prawdziwą maszynę, która naprawdę oblicza rzeczy.

Współprogram są funkcje, które można zapamiętać, gdzie byli, kontrola wydajności do innego współprogram na chwilę, a następnie wznowić gdzie skończył później, ale nie koniecznie od razu po prostu zwanych współprogram plonów. 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 zakończy się. Języki z coroutines lub podobnymi funkcjami językowymi wymagają bardziej zaawansowanych struktur danych niż stosu w celu wdrożenia kontynuacji.

W jaki sposób stos implementuje kontynuację? Inne odpowiedzi mówią jak. Stos przechowuje (1) wartości zmiennych i plików tymczasowych, których okresy istnienia nie są większe niż aktywacja bieżącej metody, oraz (2) adres kodu kontynuacji powiązany z ostatnią aktywacją metody. W językach z obsługą wyjątków stos może również przechowywać informacje o „kontynuacji błędu” - to znaczy, co program zrobi dalej, gdy wystąpi wyjątkowa sytuacja.

Pozwolę sobie skorzystać z okazji, aby zauważyć, że stos nie mówi „skąd pochodzę?” - chociaż jest często używany do debugowania. Stos informuje cię, dokąd idziesz dalej oraz jakie będą wartości zmiennych aktywacji, kiedy tam dotrzesz . Fakt, że w języku bez coroutines, do którego zmierzasz, jest prawie zawsze tam, skąd pochodzisz, ułatwia tego rodzaju debugowanie. Ale nie ma wymogu, aby kompilator przechowywał informacje o tym, skąd pochodzi kontrola, jeśli może uciec bez tego. Optymalizacje wywołania ogona na przykład niszczą informacje o tym, skąd pochodzi kontrola programu.

Dlaczego używamy stosu do implementacji kontynuacji w językach bez coroutines? Ponieważ cechą synchronicznej aktywacji metod jest to, że wzorzec „zawiesić bieżącą metodę, aktywować inną metodę, wznowić bieżącą metodę znając wynik aktywowanej metody”, gdy skomponowany sam z siebie logicznie tworzy stos aktywacji. Tworzenie struktury danych, która implementuje to zachowanie podobne do stosu, jest bardzo tanie i łatwe. Dlaczego to jest takie tanie i łatwe? Ponieważ zestawy układów są od wielu dziesięcioleci specjalnie zaprojektowane, aby ułatwić pisarzom tego typu programowanie.

Najbardziej podstawowym zastosowaniem stosu jest przechowywanie adresu zwrotnego dla funkcji:

void a(){
    sub();
}
void b(){
    sub();
}
void sub() {
    //should i got back to a() or to b()?
}

i z punktu widzenia C to wszystko. Z punktu widzenia kompilatora:

• wszystkie argumenty funkcji są przekazywane przez rejestry procesora - jeśli nie ma wystarczającej liczby rejestrów, argumenty zostaną umieszczone na stosie
• po zakończeniu funkcji (większość) rejestrów powinny mieć te same wartości, co przed wejściem - tak więc używane rejestry są zapisywane w stosie

I z punktu widzenia systemu operacyjnego: program można przerwać w dowolnym momencie, więc po zakończeniu zadania systemowego musimy przywrócić stan procesora, więc przechowujmy wszystko na stosie

Wszystko to działa, ponieważ nie dbamy o to, ile przedmiotów jest już na stosie lub ile przedmiotów ktoś doda w przyszłości, musimy tylko wiedzieć, o ile przesunęliśmy wskaźnik stosu i przywrócimy go po zakończeniu.

LIFO vs FIFO

LIFO oznacza Last In, First Out. Podobnie jak w przypadku, ostatni element włożony do stosu to pierwszy przedmiot wyjęty ze stosu.

To, co opisałeś z analogią swoich potraw (w pierwszej wersji ), to kolejka lub FIFO, pierwsze wejście, pierwsze wyjście.

Główna różnica między nimi polega na tym, że LIFO / stos wypycha (wstawia) i wyskakuje (usuwa) z tego samego końca, a FIFO / kolejka robi to z przeciwnych końców.

// Both:

Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]

// Stack            // Queue
Pop()               Pop()
-> [a, b]           -> [b, c]

Wskaźnik stosu

Rzućmy okiem na to, co dzieje się pod maską stosu. Oto trochę pamięci, każde pole to adres:

...[ ][ ][ ][ ]...                       char* sp;
    ^- Stack Pointer (SP)

I jest wskaźnik stosu wskazujący na dole aktualnie pustego stosu (to, czy stos rośnie czy rośnie, nie jest tutaj szczególnie istotne, więc zignorujemy to, ale oczywiście w prawdziwym świecie, który określa, która operacja dodaje i który odejmuje od SP).

Więc pchnijmy a, b, and cjeszcze raz. Grafika po lewej, operacja „wysokiego poziomu” po środku, pseudo-kod C po prawej:

...[a][ ][ ][ ]...        Push('a')      *sp = 'a';
    ^- SP
...[a][ ][ ][ ]...                       ++sp;
       ^- SP

...[a][b][ ][ ]...        Push('b')      *sp = 'b';
       ^- SP
...[a][b][ ][ ]...                       ++sp;
          ^- SP

...[a][b][c][ ]...        Push('c')      *sp = 'c';
          ^- SP
...[a][b][c][ ]...                       ++sp;
             ^- SP

Jak widać, za każdym razem pushwstawia on argument w miejscu, w którym aktualnie wskazuje wskaźnik stosu, i dostosowuje wskaźnik stosu, aby wskazywał w następnym miejscu.

Teraz pop:

...[a][b][c][ ]...        Pop()          --sp;
          ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'c'
          ^- SP
...[a][b][c][ ]...        Pop()          --sp;
       ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'b'
       ^- SP

Popjest przeciwieństwem push, dostosowuje wskaźnik stosu, aby wskazywał na poprzednią lokalizację i usuwa przedmiot, który tam był (zwykle w celu zwrócenia go temu, kto zadzwonił pop).

Pewnie to zauważyłeś bi cwciąż jesteś w pamięci. Chcę was zapewnić, że to nie są literówki. Wrócimy do tego wkrótce.

Życie bez wskaźnika stosu

Zobaczmy, co się stanie, jeśli nie będziemy mieć wskaźnika stosu. Zaczynając od ponownego naciśnięcia:

...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]...        Push(a)        ? = 'a';

Eee, hmm ... jeśli nie mamy wskaźnika stosu, nie możemy przenieść czegoś na adres, na który wskazuje. Może możemy użyć wskaźnika, który wskazuje na podstawę zamiast na górę.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[a][ ][ ][ ]...        Push(a)        *bp = 'a';
    ^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]...        Push(b)        *bp = 'b';
    ^- bp

O o. Ponieważ nie możemy zmienić stałej wartości podstawy stosu, po prostu nadpisaliśmy ają, przesuwając bw to samo miejsce.

Dlaczego nie śledzimy, ile razy pchaliśmy. Będziemy także musieli śledzić czasy, w których pojawiliśmy się.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);
                                         int count = 0;

...[a][ ][ ][ ]...        Push(a)        bp[count] = 'a';
    ^- bp
...[a][ ][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Push(a)        bp[count] = 'b';
    ^- bp
...[a][b][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Pop()          --count;
    ^- bp
...[a][b][ ][ ]...                       return bp[count]; //returns b
    ^- bp

Cóż, działa, ale w rzeczywistości jest dość podobny do wcześniejszego, z wyjątkiem tego, że *pointerjest tańszy niż pointer[offset](bez dodatkowej arytmetyki), nie wspominając już o mniejszym pisaniu. Wydaje mi się to stratą.

Spróbujmy ponownie. Zamiast używać stylu łańcucha Pascal do znajdowania końca kolekcji opartej na tablicy (śledzenie liczby elementów w kolekcji), spróbujmy stylu łańcucha C (skanowanie od początku do końca):

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[ ][ ][ ][ ]...        Push(a)        char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       *top = 'a';
    ^- bp    ^- top

...[ ][ ][ ][ ]...        Pop()          char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       --top;
    ^- bp       ^- top                   return *top; // returns '('

Być może odgadłeś już tutaj problem. Niezainicjowana pamięć nie ma gwarancji, że wynosi 0. Więc kiedy szukamy góry do miejsca a, w końcu pomijamy kilka nieużywanych lokalizacji pamięci, które zawierają losowe śmieci. Podobnie, gdy skanujemy do góry, kończymy przeskakiwanie daleko poza to, aco właśnie popchnęliśmy, aż w końcu znajdujemy inną lokalizację pamięci, która akurat się znajduje 0, i cofamy się i zwracamy losowe śmieci tuż przed tym.

Łatwo to naprawić, musimy tylko dodać operacje Pushi Popupewnić się, że góra stosu jest zawsze aktualizowana, aby oznaczać ją 0, i musimy zainicjować stos za pomocą takiego terminatora. Oczywiście oznacza to również, że nie możemy mieć 0(lub jakiejkolwiek wartości, którą wybieramy jako terminator) jako rzeczywistej wartości na stosie.

Ponadto zmieniliśmy również operacje O (1) na operacje O (n).

TL; DR

Wskaźnik stosu śledzi górę stosu, w którym zachodzi cała akcja. Istnieją sposoby, aby się go pozbyć ( bp[count]i topzasadniczo nadal są wskaźnikiem stosu), ale oba są bardziej skomplikowane i wolniejsze niż zwykły wskaźnik stosu. I nie wiedząc, gdzie jest góra stosu, oznacza, że ​​nie możesz użyć stosu.

Uwaga: Wskaźnik stosu wskazujący na „dół” stosu wykonawczego w x86 może być nieporozumieniem związanym z odwróceniem całego stosu wykonawczego. Innymi słowy, podstawa stosu jest umieszczona pod wysokim adresem pamięci, a wierzchołek stosu rośnie do niższych adresów pamięci. Wskaźnik stosu robi punkt na czubku stosu gdzie występuje cała akcja, tylko, że końcówka jest na adres pamięci niższej niż podstawy stosu.

Wskaźnik stosu jest używany (wraz ze wskaźnikiem ramki) do stosu wywołań (kliknij link do wikipedii, gdzie jest dobre zdjęcie).

Stos wywołań zawiera ramki wywołań, które zawierają adres zwrotny, zmienne lokalne i inne dane lokalne (w szczególności rozlaną zawartość rejestrów; formale).

Przeczytaj także o wywołaniach ogona (niektóre wywołania rekurencyjne ogona nie wymagają żadnej ramki wywołania), obsłudze wyjątków (takich jak setjmp i longjmp , mogą obejmować popping wielu ramek stosu jednocześnie), sygnałów i przerwań oraz kontynuacji . Zobacz także konwencje wywoływania i interfejsy binarne aplikacji (ABI), w szczególności ABI x86-64 (która określa, że ​​rejestry przekazują niektóre formalne argumenty).

Również zakoduj kilka prostych funkcji w C, a następnie użyj gcc -Wall -O -S -fverbose-asm do ich skompilowania i przejrzenia wygenerowanego .s pliku asemblera.

Appel napisał stary artykuł z 1986 r., Twierdząc, że zbieranie śmieci może być szybsze niż przydzielanie stosu (przy użyciu stylu kompilacji kontynuacji-przejścia ), ale prawdopodobnie jest to nieprawda w dzisiejszych procesorach x86 (zwłaszcza z powodu efektów pamięci podręcznej).

Zauważ, że konwencje wywoływania, ABI i układ stosu są różne dla 32-bitowych i686 i 64-bitowych x86-64. Również konwencje wywoływania (i kto jest odpowiedzialny za przydzielanie lub usuwanie ramki wywołania) mogą być różne w różnych językach (np. C, Pascal, Ocaml, SBCL Common Lisp mają różne konwencje wywoływania ....)

BTW, ostatnie rozszerzenia x86, takie jak AVX, nakładają coraz większe ograniczenia wyrównania na wskaźnik stosu (IIRC, ramka wywołania na x86-64 chce być wyrównana do 16 bajtów, tj. Dwóch słów lub wskaźników).

Mówiąc prościej, program dba o to, ponieważ wykorzystuje te dane i musi śledzić, gdzie je znaleźć.

Jeśli deklarujesz zmienne lokalne w funkcji, stos jest tam, gdzie są przechowywane. Ponadto, jeśli wywołasz inną funkcję, stos będzie tam, gdzie przechowuje adres zwrotny, aby mógł wrócić do funkcji, w której byłeś, kiedy ta, do której zadzwoniłeś, została zakończona i odebrać tam, gdzie została przerwana.

Bez SP programowanie strukturalne, jakie znamy, byłoby w zasadzie niemożliwe. (Możesz obejść się bez niego, ale wymagałoby to implementacji własnej wersji, więc nie jest to duża różnica).

Dla stosu procesorów w procesorze x86 analogia stosu naczyń jest naprawdę niedokładna.
Z różnych powodów (głównie historycznych) stos procesorów rośnie od góry pamięci do dołu pamięci, więc lepszą analogią byłby łańcuch ogniw zwisających z sufitu. Kiedy wpychasz coś na stos, do najniższego ogniwa dodaje się ogniwo łańcucha.

Wskaźnik stosu odnosi się do najniższego ogniwa łańcucha i jest wykorzystywany przez procesor do „zobaczenia”, gdzie znajduje się to najniższe ogniwo, dzięki czemu ogniwa można dodawać lub usuwać bez konieczności przemieszczania całego łańcucha od sufitu w dół.

W pewnym sensie, w procesorze x86, stos jest odwrócony do góry nogami, ale używa się normalnej terminologii stosu stosu, tak że najniższe łącze jest określane jako szczyt stosu.

Łącza łańcuchowe, o których wspomniałem powyżej, są w rzeczywistości komórkami pamięci w komputerze i przyzwyczajają się do przechowywania zmiennych lokalnych oraz niektórych pośrednich wyników obliczeń. Programy komputerowe dbają o to, gdzie jest góra stosu (tj. Gdzie zawiesza się to najniższe łącze), ponieważ znaczna większość zmiennych, do których funkcja musi uzyskać dostęp, istnieje blisko miejsca, do którego odnosi się wskaźnik stosu, i pożądany jest szybki dostęp do nich.

Odpowiedź ta dotyczy w szczególności na wskaźnik stosu obecnego gwintu (realizacji) .

W proceduralnych językach programowania wątek zazwyczaj ma dostęp do stosu ¹ w następujących celach:

• Przepływ sterowania, a mianowicie „stos wywołań”.
  • Gdy jedna funkcja wywołuje inną funkcję, stos wywołań zapamiętuje, do którego miejsca powrócić.
  • Stos wywołań jest konieczny, ponieważ chcemy, aby zachowało się „wywołanie funkcji” - „aby odebrać od miejsca, w którym zostało przerwane” .
  • Istnieją inne style programowania, w których nie ma wywołań funkcji w trakcie wykonywania (np. Dozwolone jest określenie następnej funkcji po osiągnięciu końca bieżącej funkcji) lub w ogóle nie mają wywołań funkcji (tylko przy użyciu goto i skoków warunkowych ). Te style programowania mogą nie wymagać stosu wywołań.
• Parametry wywołania funkcji.
  • Gdy funkcja wywołuje inną funkcję, parametry mogą być wypychane na stos.
  • Konieczne jest, aby osoba dzwoniąca i osoba odbierająca postępowała zgodnie z tą samą konwencją, co do tego, kto jest odpowiedzialny za usunięcie parametrów ze stosu, gdy połączenie się zakończy.
• Zmienne lokalne, które żyją w wywołaniu funkcji.
  • Zauważ, że zmienna lokalna należąca do osoby wywołującej może zostać udostępniona odbiorcy poprzez przekazanie wskaźnika do tej zmiennej lokalnej do odbiorcy.

Uwaga ¹ : poświęcona użyciu wątku, chociaż jego zawartość jest całkowicie czytelna - i może zostać zniszczona - przez inne wątki.

W programowaniu asemblacyjnym, C i C ++, wszystkie trzy cele mogą być spełnione przez ten sam stos. W niektórych innych językach niektóre cele mogą być realizowane przez osobne stosy lub pamięć przydzielaną dynamicznie.

Oto celowo uproszczona wersja tego, do czego służy stos.

Wyobraź sobie stos kart indeksu. Wskaźnik stosu wskazuje na górną kartę.

Po wywołaniu funkcji:

• Adres kodu zapisujesz bezpośrednio po wierszu, który wywołał funkcję na karcie, i umieszczasz ją na stosie. (Tzn. Zwiększasz wskaźnik stosu o jeden i zapisujesz adres, na który wskazuje)
• Następnie zapisujesz wartości zawarte w rejestrach na niektórych kartach i umieszczasz je na stosie. (tzn. zwiększasz wskaźnik stosu o liczbę rejestrów i kopiujesz zawartość rejestru do miejsca, na które wskazuje)
• Następnie odkładasz kartę znacznika na stos. (tzn. oszczędzasz bieżący wskaźnik stosu).
• Następnie zapisujesz wartość każdego parametru, za pomocą którego wywoływana jest funkcja, jeden na kartę i umieszczasz go na stosie. (tzn. zwiększasz wskaźnik stosu o liczbę parametrów i zapisujesz parametry w miejscu, do którego wskazuje wskaźnik stosu).
• Następnie dodajesz kartę dla każdej zmiennej lokalnej, potencjalnie zapisując na niej wartość początkową. (tzn. zwiększasz wskaźnik stosu o liczbę zmiennych lokalnych).

W tym momencie uruchamia się kod w funkcji. Kod jest kompilowany, aby wiedzieć, gdzie każda karta jest względem góry. Wie więc, że zmienna xjest trzecią kartą od góry (tzn. Wskaźnikiem stosu - 3) i że parametrem yjest szósta karta od góry (tj. Wskaźnikiem stosu - 6.)

Ta metoda oznacza, że ​​adres każdej lokalnej zmiennej lub parametru nie musi być wprowadzany do kodu. Zamiast tego wszystkie te elementy danych są adresowane względem wskaźnika stosu.

Kiedy funkcja powraca, operacja odwrotna jest po prostu:

• Poszukaj karty znacznika i wyrzuć wszystkie karty nad nią. (tzn. ustaw wskaźnik stosu na zapisany adres).
• Przywróć rejestry z wcześniej zapisanych kart i wyrzuć je. (tj. odejmij stałą wartość od wskaźnika stosu)
• Zacznij uruchamiać kod od adresu na karcie na górze, a następnie wyrzuć go. (tzn. odejmij 1 od wskaźnika stosu).

Stos powrócił do stanu sprzed wywołania funkcji.

Rozważając to, zwróć uwagę na dwie rzeczy: przydzielanie i zwalnianie miejscowych jest niezwykle szybką operacją, ponieważ polega tylko na dodawaniu lub odejmowaniu liczby od wskaźnika stosu. Zauważ też, jak naturalnie działa to z rekurencją.

Jest to nadmiernie uproszczone do celów wyjaśniających. W praktyce parametry i parametry lokalne mogą być wprowadzane do rejestrów jako optymalizacja, a wskaźnik stosu będzie na ogół zwiększany i zmniejszany o wielkość słowa maszyny, a nie o jeden. (Aby wymienić kilka rzeczy.)

Nowoczesne języki programowania, jak dobrze wiesz, obsługują koncepcję wywołań podprogramów (najczęściej nazywanych „wywołaniami funkcji”). To znaczy że:

1. W środku jakiegoś kodu możesz wywołać inną funkcję w swoim programie;
2. Ta funkcja nie wie wprost, skąd została wywołana;
3. Niemniej jednak, kiedy jego praca zostanie zakończona return, kontrola wraca do dokładnego punktu, w którym wywołanie zostało zainicjowane, przy czym wszystkie wartości zmiennych lokalnych obowiązują tak, jak w momencie inicjowania połączenia.

W jaki sposób komputer to śledzi? Prowadzi ciągły rejestr, które funkcje czekają na które połączenia powrócą. Ten rekord jest stosem, a ponieważ jest to taki ważny, zwykle nazywają ją stos.

A ponieważ ten wzorzec wywoływania / zwracania jest tak ważny, procesory od dawna zostały zaprojektowane w celu zapewnienia specjalnego wsparcia sprzętowego. Wskaźnik stosu jest funkcją sprzętową procesorów - rejestr, który jest przeznaczony wyłącznie do śledzenia górnej części stosu i jest wykorzystywany w instrukcjach procesora do rozgałęziania się do podprogramu i powrotu z niego.