Wyjaśnij pojęcie ramy stosu w pigułce


200

Wygląda na to, że mam pomysł na stos wywołań w projektowaniu języka programowania. Ale nie mogę znaleźć (prawdopodobnie po prostu nie szukam wystarczająco mocno) żadnego przyzwoitego wyjaśnienia, czym jest rama stosu .

Chciałbym więc poprosić kogoś o wyjaśnienie mi tego w kilku słowach.

Odpowiedzi:


195

Ramka stosu to ramka danych, która jest wypychana na stos. W przypadku stosu wywołań ramka stosu reprezentowałaby wywołanie funkcji i dane argumentu.

Jeśli dobrze pamiętam, adres zwrotny funkcji jest najpierw wypychany na stos, a następnie argumenty i miejsce na zmienne lokalne. Razem tworzą „ramkę”, chociaż prawdopodobnie zależy to od architektury. Procesor wie, ile bajtów jest w każdej ramce i odpowiednio przesuwa wskaźnik stosu, gdy ramki są wypychane i wyskakiwane ze stosu.

EDYTOWAĆ:

Istnieje duża różnica między stosami wywołań wyższego poziomu a stosami wywołań procesora.

Kiedy mówimy o stosie wywołań procesora, mówimy o pracy z adresami i wartościami na poziomie bajtów / słów w asemblerze lub kodzie maszynowym. Podczas mówienia o językach wyższego poziomu występują „stosy połączeń”, ale są one narzędziem do debugowania / środowiska wykonawczego zarządzanym przez środowisko wykonawcze, dzięki czemu można rejestrować, co poszło nie tak z twoim programem (na wysokim poziomie). Na tym poziomie często znane są numery linii, nazwy metod i klas. Zanim procesor otrzyma kod, nie ma absolutnie żadnego pojęcia o tych rzeczach.


6
„Procesor wie, ile bajtów jest w każdej ramce i odpowiednio przesuwa wskaźnik stosu, gdy ramki są wypychane i wyskakiwane ze stosu”. - Wątpię, aby procesor wiedział coś o stosie, ponieważ manipulujemy nim poprzez subbing (alokację), wypychanie i popping. Oto konwencje wywoływania, które wyjaśniają, w jaki sposób powinniśmy używać stosu.
Victor Polevoy,

78

Jeśli rozumiesz stos bardzo dobrze, zrozumiesz, jak pamięć działa w programie, a jeśli zrozumiesz, jak pamięć działa w programie, zrozumiesz, jak przechowuje funkcje w programie, a jeśli zrozumiesz, jak przechowuje funkcje w programie, zrozumiesz, jak działa funkcja rekurencyjna, a jeśli zrozumiesz, jak działa funkcja rekurencyjna, zrozumiesz, jak działa kompilator, a jeśli zrozumiesz, jak działa kompilator, twój umysł będzie działał jako kompilator i bardzo łatwo debugujesz dowolny program

Pozwól mi wyjaśnić, jak działa stos:

Najpierw musisz wiedzieć, jak funkcje są reprezentowane na stosie:

Sterta przechowuje dynamicznie przydzielane wartości.
Stos przechowuje wartości automatycznego przydzielania i usuwania.

wprowadź opis zdjęcia tutaj

Rozumiemy na przykładzie:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(4)

Teraz zrozum części tego programu:

wprowadź opis zdjęcia tutaj

Zobaczmy teraz, co to jest stos, a jakie części stosu:

wprowadź opis zdjęcia tutaj

Przydział stosu:

Pamiętaj o jednej rzeczy: jeśli warunek powrotu dowolnej funkcji zostanie spełniony, bez względu na to, czy załadował zmienne lokalne, czy nie, natychmiast powróci ze stosu z ramką stosu. Oznacza to, że za każdym razem, gdy jakakolwiek funkcja rekurencyjna zostanie spełniona warunek podstawowy, a my wstawimy znak powrotu po warunku podstawowym, warunek podstawowy nie będzie czekał na załadowanie zmiennych lokalnych, które znajdują się w części „else” programu. Natychmiast zwróci bieżącą ramkę ze stosu, po której następna ramka znajduje się teraz w rekordzie aktywacji.

Zobacz to w praktyce:

wprowadź opis zdjęcia tutaj

Zwolnienie bloku:

Tak więc teraz, gdy funkcja napotka instrukcję return, usuwa bieżącą ramkę ze stosu.

Podczas powrotu ze stosu wartości będą zwracane w odwrotnej kolejności niż pierwotna kolejność, w jakiej zostały przydzielone w stosie.

wprowadź opis zdjęcia tutaj


3
stos rośnie w dół, a stos rośnie w górę, masz je odwrócone na schemacie. POPRAWNY SCHEMAT TUTAJ
Rafael

@Rafael przepraszam za zamieszanie, mówiłem o kierunku wzrostu, nie mówiłem o kierunku wzrostu stosu. Istnieją różnice między kierunkiem wzrostu a kierunkiem wzrostu stosu. Zobacz tutaj stackoverflow.com/questions/1677415/…
Aaditya Ura,

2
Rafael ma rację. Również pierwsze zdjęcie jest nieprawidłowe. Zamień go na coś innego (wyszukaj w Google obrazki „stos stosów”).
Nikos

Więc jeśli dobrze rozumiem, na twoim trzecim diagramie są 3 ramki stosu, ponieważ hello()wywołały rekurencyjnie, hello()które następnie (ponownie) wywołały rekurencyjnie hello(), a ramka globalna jest oryginalną funkcją, która wywołała pierwszą hello()?
Andy J

1
Dokąd prowadzą nas linki? Ze względów bezpieczeństwa linki te należy usunąć jak najszybciej.
Shivanshu

45

Szybkie zakończenie. Może ktoś ma lepsze wytłumaczenie.

Stos wywołań składa się z 1 lub wielu kilku ramek stosu. Każda ramka stosu odpowiada wywołaniu funkcji lub procedury, które jeszcze nie zakończyło się zwrotem.

Aby użyć ramki stosu, wątek zachowuje dwa wskaźniki, jeden nazywany jest wskaźnikiem stosu (SP), a drugi wskaźnikiem ramki (FP). SP zawsze wskazuje na „górę” stosu, a FP zawsze wskazuje na „górę” ramki. Ponadto wątek utrzymuje również licznik programów (PC), który wskazuje następną instrukcję do wykonania.

Na stosie są przechowywane: zmienne lokalne i wartości tymczasowe, rzeczywiste parametry bieżącej instrukcji (procedura, funkcja itp.)

Istnieją różne konwencje wywoływania dotyczące czyszczenia stosu.


7
Nie zapominaj, że adres zwrotny podprogramu znajduje się na stosie.
Tony R

4
Wskaźnik ramki jest również wskaźnikiem podstawowym w kategoriach x86
peterchaula,

1
Chciałbym podkreślić, że wskaźnik ramki wskazuje początek ramki stosu dla aktualnie aktywnego wcielenia procedury.
Serwer Chałiłow

13

„Stos wywołań składa się z ramek stosów ...” -  Wikipedia

Rama stosu to rzecz, którą umieszczasz na stosie. Są to struktury danych, które zawierają informacje o podprogramach do wywołania.


Przepraszam, nie mam pojęcia, jak to przegapiłem na wiki. Dzięki. Czy rozumiem poprawnie, że w dynamicznych językach rozmiar ramki nie jest wartością stałą, ponieważ lokale funkcji nie są dokładnie znane?
ikostia,

Rozmiar i charakter ramki w dużym stopniu zależy od architektury maszyny. W rzeczywistości sam paradygmat stosu wywołań jest specyficzny dla architektury. O ile wiem, zawsze jest zmienna, ponieważ różne wywołania funkcji będą miały różne ilości danych argumentów.
Tony R

Zauważ, że rozmiar ramki stosu musi być znany procesorowi podczas manipulacji. Gdy tak się dzieje, rozmiar danych jest już określony. Języki dynamiczne są kompilowane do kodu maszynowego, podobnie jak języki statyczne, ale często są wykonywane dokładnie na czas, dzięki czemu kompilator może utrzymać dynamikę, a procesor może pracować ze „znanymi” rozmiarami ramek. Nie należy mylić języków wyższego poziomu z kodem maszynowym / asemblerem, czyli tam, gdzie to się dzieje.
Tony R

Cóż, ale języki dynamiczne również mają stosy połączeń, prawda? Mam na myśli, jeśli powiedzmy, że Python chce wykonać jakąś procedurę, dane o tej procedurze są przechowywane w strukturze jakiegoś interpretera Pythona, czy mam rację? Mam na myśli, że stos wywołań jest obecny nie tylko na niskim poziomie.
ikostia,

Po przeczytaniu trochę tego artykułu z Wikipedii, poprawiam się (trochę). Rozmiar ramki stosu może pozostać nieznany w czasie kompilacji . Ale zanim procesor będzie pracował ze wskaźnikami stosu + ramki, musi wiedzieć, jakie są rozmiary. Rozmiar może być zmienny, ale procesor zna rozmiar, to właśnie próbowałem powiedzieć.
Tony R

5

Programiści mogą mieć pytania dotyczące ramek stosu nie w szerokim znaczeniu (że jest to pojedyncza jednostka w stosie, która obsługuje tylko jedno wywołanie funkcji i zachowuje adres zwrotny, argumenty i zmienne lokalne), ale w wąskim znaczeniu - gdy termin stack framesjest wymieniony w kontekst opcji kompilatora.

Czy autor pytania miał na myśli, czy nie, ale koncepcja ramki stosu w aspekcie opcji kompilatora jest bardzo ważnym zagadnieniem, nieuwzględnionym w innych odpowiedziach tutaj.

Na przykład kompilator Microsoft Visual Studio 2015 C / C ++ ma następującą opcję związaną z stack frames:

  • / Oy (pominięcie wskaźnika ramki)

GCC mają następujące elementy:

  • -fomit-frame-pointer (Nie przechowuj wskaźnika ramki w rejestrze dla funkcji, które go nie potrzebują. Pozwala to uniknąć instrukcji zapisywania, konfigurowania i przywracania wskaźników ramki; udostępnia również dodatkowy rejestr dla wielu funkcji )

Kompilator Intel C ++ ma następujące funkcje:

  • -fomit-frame-pointer (Określa, czy EBP jest używany jako rejestr ogólnego przeznaczenia w optymalizacjach)

który ma następujący alias:

  • / Oy

Delphi ma następującą opcję wiersza polecenia:

  • - $ W + (Generuj ramki stosu)

W tym konkretnym sensie, z perspektywy kompilatora, ramka stosu to tylko kod wejścia i wyjścia dla procedury , która przesuwa kotwicę do stosu - która może być również używana do debugowania i obsługi wyjątków. Narzędzia do debugowania mogą skanować dane stosu i używać tych kotwic do śledzenia wstecznego, podczas lokalizowania call sitesw stosie, tj. Do wyświetlania nazw funkcji w kolejności, w jakiej zostały one nazwane hierarchicznie. W przypadku architektury Intel jest to push ebp; mov ebp, esplub enterdo wejścia i mov esp, ebp; pop ebplub leavedo wyjścia.

Dlatego bardzo ważne jest, aby zrozumieć dla programisty, w jakiej ramce jest stos, jeśli chodzi o opcje kompilatora - ponieważ kompilator może kontrolować, czy wygenerować ten kod, czy nie.

W niektórych przypadkach kompilator może pominąć ramkę stosu (kod wejścia i wyjścia dla procedury), a do zmiennych można uzyskać bezpośredni dostęp za pomocą wskaźnika stosu (SP / ESP / RSP) zamiast wygodnego wskaźnika bazowego (BP / ESP / RSP). Warunki pominięcia ramy stosu, na przykład:

  • funkcja jest funkcją liścia (tj. bytem końcowym, który nie wywołuje innych funkcji);
  • nie ma żadnych prób / wreszcie lub prób / wyjątków lub podobnych konstrukcji, tzn. nie są stosowane wyjątki;
  • nie są wywoływane żadne procedury z parametrami wychodzącymi na stosie;
  • funkcja nie ma parametrów;
  • funkcja nie ma wbudowanego kodu asemblera;
  • itp...

Pominięcie ramek stosu (kod wejścia i wyjścia dla procedury) może sprawić, że kod będzie mniejszy i szybszy, ale może również negatywnie wpłynąć na zdolność debuggerów do śledzenia danych w stosie i wyświetlania ich programistom. Są to opcje kompilatora, które określają, w jakich warunkach funkcja powinna mieć kod wejścia i wyjścia, na przykład: (a) zawsze, (b) nigdy, (c) w razie potrzeby (określając warunki).


-1

Ramka stosu to spakowana informacja związana z wywołaniem funkcji. Informacje te ogólnie obejmują argumenty przekazane do funkcji th, zmienne lokalne i miejsce, do którego należy wrócić po zakończeniu. Rekord aktywacji to inna nazwa ramki stosu. Układ ramki stosu jest określany w ABI przez producenta i każdy kompilator obsługujący ISA musi być zgodny z tym standardem, jednak schemat układu może być zależny od kompilatora. Ogólnie rozmiar ramki stosu nie jest ograniczony, ale istnieje koncepcja zwana „czerwoną / chronioną strefą”, która umożliwia wykonywanie wywołań systemowych ... itd. Bez ingerencji w ramkę stosu.

Zawsze występuje SP, ale na niektórych ABI (na przykład ARM i PowerPC) FP jest opcjonalny. Argumenty, które musiały zostać umieszczone na stosie, można skompensować tylko za pomocą SP. To, czy ramka stosu jest generowana dla wywołania funkcji, zależy od typu i liczby argumentów, zmiennych lokalnych oraz ogólnego sposobu dostępu do zmiennych lokalnych. W większości ISA, po pierwsze, używane są rejestry i jeśli jest więcej argumentów niż rejestry dedykowane do przekazywania argumentów, są one umieszczane na stosie (na przykład x86 ABI ma 6 rejestrów do przekazywania argumentów liczb całkowitych). Dlatego czasami niektóre funkcje nie wymagają umieszczenia ramki stosu na stosie, tylko adres zwrotny jest wypychany na stos.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.