Co i gdzie są stosy i sterty?

8099

Książki języków programowania wyjaśniają, że typy wartości są tworzone na stosie , a typy referencyjne są tworzone na stercie , bez wyjaśnienia, jakie są te dwie rzeczy. Nie przeczytałem wyraźnego wyjaśnienia tego. Rozumiem, co to jest stos . Ale,

  • Gdzie i czym one są (fizycznie w pamięci prawdziwego komputera)?
  • W jakim stopniu są one kontrolowane przez system operacyjny lub język?
  • Jaki jest ich zakres?
  • Co decyduje o wielkości każdego z nich?
  • Co przyspiesza?
mattshane
źródło
175
naprawdę dobre wytłumaczenie można znaleźć tutaj Jaka jest różnica między stosem a stertą?
Songo,
12
Również (naprawdę) dobrze: codeproject.com/Articles/76153/… (część stosu / sterty)
Ben
3
Powiązane, patrz Zderzenie stosu . Środki zaradcze stosu kolizji wpłynęły na niektóre aspekty zmiennych systemowych i zachowania, takie jak rlimit_stack. Zobacz także Red Hat Issue 1463241
jww
3
@mattshane Definicje stosu i sterty nie zależą od wartości i typów referencji. Innymi słowy, stos i stertę można w pełni zdefiniować, nawet jeśli nigdy nie istniały typy wartości i odwołania. Ponadto, gdy rozumiemy typy wartości i odniesienia, stos jest tylko szczegółem implementacji. Per Eric Lippert: Stos to szczegół implementacji, część pierwsza .
Matthew

Odpowiedzi:

5961

Stos jest pamięcią zarezerwowaną jako miejsce na zarysowania dla wątku wykonania. Po wywołaniu funkcji blok jest zarezerwowany na górze stosu dla zmiennych lokalnych i niektórych danych księgowych. Gdy funkcja ta powraca, blok staje się nieużywany i można go użyć przy następnym wywołaniu funkcji. Stos jest zawsze zarezerwowany w kolejności LIFO (od ostatniego do pierwszego); ostatnio zarezerwowany blok jest zawsze następnym blokiem do zwolnienia. To sprawia, że ​​śledzenie stosu jest naprawdę proste; uwolnienie bloku ze stosu to nic innego jak dostosowanie jednego wskaźnika.

Sterty jest pamięć zarezerwowana do alokacji dynamicznej. W przeciwieństwie do stosu nie ma wymuszonego wzorca przydziału i zwalniania bloków ze stosu; możesz przydzielić blok w dowolnym momencie i zwolnić go w dowolnym momencie. To znacznie komplikuje śledzenie, które części sterty są przydzielane lub wolne w danym momencie; dostępnych jest wiele niestandardowych alokatorów sterty, które dostosowują wydajność sterty do różnych wzorców użytkowania.

Każdy wątek otrzymuje stos, podczas gdy zazwyczaj aplikacja ma tylko jedną stertę (chociaż nierzadko jest mieć wiele stosów dla różnych rodzajów alokacji).

Aby bezpośrednio odpowiedzieć na pytania:

W jakim stopniu są one kontrolowane przez system operacyjny lub środowisko uruchomieniowe języka?

System operacyjny przydziela stos dla każdego wątku na poziomie systemu podczas tworzenia wątku. Zazwyczaj system operacyjny jest wywoływany przez środowisko wykonawcze języka w celu przydzielenia sterty dla aplikacji.

Jaki jest ich zakres?

Stos jest dołączony do wątku, więc gdy wątek wychodzi, stos jest odzyskiwany. Sterta jest zwykle przydzielana podczas uruchamiania aplikacji przez środowisko wykonawcze i jest odzyskiwana, gdy aplikacja (proces techniczny) zostanie zamknięta.

Co decyduje o wielkości każdego z nich?

Rozmiar stosu jest ustawiany podczas tworzenia wątku. Rozmiar sterty jest ustawiany podczas uruchamiania aplikacji, ale może rosnąć w miarę potrzebnego miejsca (alokator żąda więcej pamięci z systemu operacyjnego).

Co przyspiesza?

Stos jest szybszy, ponieważ wzorzec dostępu sprawia, że ​​przydzielanie i zwalnianie z niego pamięci jest trywialne (wskaźnik / liczba całkowita jest po prostu zwiększana lub zmniejszana), podczas gdy sterta ma znacznie bardziej skomplikowaną księgowość związaną z alokacją lub dezalokacją. Ponadto każdy bajt w stosie jest często bardzo często wykorzystywany, co oznacza, że ​​jest on mapowany do pamięci podręcznej procesora, co czyni go bardzo szybkim. Kolejnym uderzeniem wydajności dla sterty jest to, że sterty, będące głównie zasobem globalnym, zazwyczaj muszą być bezpieczne dla wielu wątków, tj. Każda alokacja i dezalokacja muszą - zazwyczaj - być synchronizowane z „wszystkimi” dostępami do sterty w programie.

Wyraźna demonstracja:
Źródło obrazu: vikashazrati.wordpress.com

Jeff Hill
źródło
74
Dobra odpowiedź - ale myślę, że powinieneś dodać, że chociaż stos jest przydzielany przez system operacyjny na początku procesu (zakładając istnienie systemu operacyjnego), jest on utrzymywany w linii przez program. Jest to kolejny powód, dla którego stos jest szybszy - operacje wypychania i popu są zwykle jedną instrukcją maszyny, a nowoczesne maszyny mogą wykonać co najmniej 3 z nich w jednym cyklu, podczas gdy przydzielanie lub zwalnianie sterty wymaga wywoływania w kodzie systemu operacyjnego.
sqykly
275
Schemat na końcu naprawdę mnie zagubił. Myślałem, że dostałem, dopóki nie zobaczyłem tego obrazu.
Sina Madani
10
@Anarelle procesor uruchamia instrukcje z lub bez systemu operacyjnego. Przykładem bliskim mojemu sercu jest SNES, który nie miał wywołań API, nie ma systemu operacyjnego, jaki znamy dzisiaj - ale miał stos. Przydział na stosie polega na dodawaniu i odejmowaniu w tych systemach i jest to w porządku dla zmiennych zniszczonych, gdy są one wywoływane przez powrót z funkcji, która je utworzyła, ale ogranicza to, powiedzmy, konstruktor, którego wynikiem nie może być po prostu Wyrzucony. Do tego potrzebujemy sterty, która nie jest powiązana z nawiązywaniem i zwracaniem. Większość systemów operacyjnych ma
mnóstwo
2
„stos jest pamięcią zarezerwowaną jako miejsce na zarysowania”. Fajne. Ale gdzie to właściwie jest „odłożone” pod względem struktury pamięci Java? Is it Heap memory / Non-heap memory / Other (Struktura pamięci Java zgodnie z betsol.com/2017/06/… )
Jatin Shashoo
4
Środowisko wykonawcze Java @JatinShashoo, jako interpreter kodu bajtowego, dodaje jeszcze jeden poziom wirtualizacji, więc chodzi tu tylko o punkt widzenia aplikacji Java. Z punktu widzenia systemu operacyjnego wszystko to jest tylko stertą, w której proces wykonawczy Java przydziela część swojej przestrzeni jako pamięć „bez sterty” na przetworzony kod bajtowy. Reszta sterty na poziomie systemu operacyjnego jest używana jako sterty na poziomie aplikacji, w których przechowywane są dane obiektu.
kbec
2349

Stos:

  • Przechowywane w pamięci RAM komputera podobnie jak sterty.
  • Zmienne utworzone na stosie wykroczą poza zakres i zostaną automatycznie zwolnione.
  • Znacznie szybciej alokuje w porównaniu do zmiennych na stercie.
  • Zaimplementowane z faktyczną strukturą danych stosu.
  • Przechowuje dane lokalne, adresy zwrotne, używane do przekazywania parametrów.
  • Może mieć przepełnienie stosu, gdy użyto zbyt dużej ilości stosu (głównie z nieskończonej lub zbyt głębokiej rekurencji, bardzo dużych alokacji).
  • Dane utworzone na stosie mogą być używane bez wskaźników.
  • Użyłbyś stosu, jeśli dokładnie wiesz, ile danych musisz przydzielić przed czasem kompilacji i nie jest on zbyt duży.
  • Zwykle ma maksymalny rozmiar określony już podczas uruchamiania programu.

Sterta:

  • Przechowywane w pamięci RAM komputera, podobnie jak stos.
  • W C ++ zmienne na stercie muszą zostać zniszczone ręcznie i nigdy nie wykraczają poza zakres. Dane uwalnia się z delete, delete[]lub free.
  • Wolniej przydzielać w porównaniu do zmiennych na stosie.
  • Używane na żądanie do przydzielenia bloku danych do wykorzystania przez program.
  • Może mieć fragmentację, gdy jest dużo alokacji i zwolnień.
  • W C ++ lub C dane utworzone na stercie będą wskazywane przez wskaźniki i przydzielane odpowiednio newlub malloc.
  • Może wystąpić błąd alokacji, jeśli zażąda się zbyt dużego bufora.
  • Używałbyś sterty, jeśli nie wiesz dokładnie, ile danych będziesz potrzebować w czasie wykonywania lub jeśli musisz przydzielić dużo danych.
  • Odpowiedzialny za wycieki pamięci.

Przykład:

int foo()
{
  char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
  bool b = true; // Allocated on the stack.
  if(b)
  {
    //Create 500 bytes on the stack
    char buffer[500];

    //Create 500 bytes on the heap
    pBuffer = new char[500];

   }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;
Brian R. Bondy
źródło
31
Wskaźnik pBuffer i wartość b znajdują się na stosie i najczęściej są przydzielane przy wejściu do funkcji. W zależności od kompilatora bufor może być również przydzielany przy wejściu do funkcji.
Andy,
36
Powszechnym błędem jest przekonanie, że Cjęzyk zdefiniowany w C99standardzie językowym (dostępny na open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf ) wymaga „stosu”. W rzeczywistości słowo „stos” nawet nie pojawia się w standardzie. Odpowiedzi na te stwierdzenia Cużycie stosu wrt / to jest ogólnie prawdą, ale nie jest w żaden sposób wymagane przez język. Aby uzyskać więcej informacji, zobacz knosof.co.uk/cbook/cbook.html , a w szczególności sposób Cimplementacji w architekturach nieparzystych, takich jak en.wikipedia.org/wiki/Burroughs_large_systems
johne
55
@Brian Należy wyjaśnić, dlaczego bufor [] i wskaźnik pBuffer są tworzone na stosie i dlaczego dane pBuffer są tworzone na stercie. Myślę, że niektóre ppl mogą być mylone przez twoją odpowiedź, ponieważ mogą myśleć, że program instruuje, aby pamięć była przydzielana na stosie vs stercie, ale tak nie jest. Czy dlatego, że bufor jest typem wartości, podczas gdy pBuffer jest typem referencyjnym?
Howiecamp
9
@Remover: Żaden wskaźnik nie posiada adresu i może wskazywać równo na stos lub stos. new, malloc i niektóre inne funkcje podobne do malloc przydzielają na stercie i zwracają adres przydzielonej pamięci. Dlaczego chcesz przydzielić na stosie? Aby twoja pamięć nie wyszła poza zakres i została zwolniona, dopóki tego nie chcesz.
Brian R. Bondy
35
„Odpowiedzialny za wycieki pamięci” - hałdy nie są odpowiedzialne za wycieki pamięci! Leniwi / zapominalscy / byli koderzy / koderzy, którzy nie dają gówna!
Laz
1370

Najważniejsze jest to, że sterty i stosy są ogólnymi terminami określającymi sposoby przydzielania pamięci. Można je wdrożyć na wiele różnych sposobów, a terminy dotyczą podstawowych pojęć.

  • W stosie przedmiotów, przedmioty układają się jeden na drugim w kolejności, w jakiej zostały tam umieszczone, i można usunąć tylko górną (bez przewrócenia całej rzeczy).

    Układaj jak stos papierów

    Prostota stosu polega na tym, że nie trzeba utrzymywać tabeli zawierającej zapis każdej sekcji przydzielonej pamięci; jedyne potrzebne informacje o stanie to pojedynczy wskaźnik na końcu stosu. Aby przydzielić i cofnąć przydział, wystarczy zwiększyć i zmniejszyć pojedynczy wskaźnik. Uwaga: czasami można zaimplementować stos, aby zaczynał się na górze części pamięci i rozszerzał w dół, zamiast rosnąć w górę.

  • Na stosie nie ma określonej kolejności sposobu umieszczania przedmiotów. Możesz sięgać i usuwać przedmioty w dowolnej kolejności, ponieważ nie ma wyraźnego „górnego” przedmiotu.

    Kupa jak kupa lukrecji

    Alokacja stosów wymaga prowadzenia pełnego rejestru pamięci, która jest przydzielana, a co nie, a także konserwacji narzutów w celu zmniejszenia fragmentacji, znalezienia sąsiadujących segmentów pamięci na tyle dużych, aby pasowały do ​​żądanego rozmiaru itd. Pamięć można w dowolnym momencie zwolnić, pozostawiając wolne miejsce. Czasami alokator pamięci wykonuje zadania konserwacyjne, takie jak defragmentacja pamięci poprzez przenoszenie przydzielonej pamięci lub odśmiecanie - identyfikowanie w czasie wykonywania, gdy pamięć nie jest już w zasięgu, i jej cofanie.

Te obrazy powinny całkiem dobrze opisać dwa sposoby przydzielania i zwalniania pamięci w stosie i sterty. Mniam!

  • W jakim stopniu są one kontrolowane przez system operacyjny lub środowisko uruchomieniowe języka?

    Jak wspomniano, sterty i stosy są warunkami ogólnymi i można je wdrażać na wiele sposobów. Programy komputerowe zazwyczaj mają stos nazywany stosem wywołań który przechowuje informacje istotne dla bieżącej funkcji, takie jak wskaźnik do dowolnej funkcji, z której został wywołany, oraz dowolne zmienne lokalne. Ponieważ funkcje wywołują inne funkcje, a następnie wracają, stos rośnie i kurczy się, aby przechować informacje z funkcji znajdujących się dalej na stosie wywołań. Program tak naprawdę nie ma nad nim kontroli; zależy to od języka programowania, systemu operacyjnego, a nawet architektury systemu.

    Sterta jest ogólnym terminem używanym dla każdej pamięci przydzielanej dynamicznie i losowo; tzn. nieczynny. Pamięć jest zwykle przydzielana przez system operacyjny, przy czym aplikacja wywołuje funkcje API w celu wykonania tej alokacji. Zarządzanie dynamicznie przydzielaną pamięcią wymaga dość dużego obciążenia, które zwykle jest obsługiwane przez kod środowiska wykonawczego używanego języka programowania lub środowiska.

  • Jaki jest ich zakres?

    Stos wywołań jest tak niskim poziomem koncepcji, że nie odnosi się do „zakresu” w sensie programowania. Jeśli rozłożysz jakiś kod, zobaczysz względne odwołania do stylu stosu w odniesieniu do części stosu, ale jeśli chodzi o język wyższego poziomu, język narzuca własne reguły zakresu. Jednym ważnym aspektem stosu jest jednak to, że po zwróceniu funkcji wszystko lokalne dla tej funkcji jest natychmiast usuwane ze stosu. Działa to tak, jak można by oczekiwać, biorąc pod uwagę sposób działania języków programowania. Na stercie trudno też zdefiniować. Zakres jest tym, co ujawnia system operacyjny, ale Twój język programowania prawdopodobnie dodaje swoje reguły dotyczące tego, co „zakres” znajduje się w twojej aplikacji. Architektura procesora i system operacyjny wykorzystują adresowanie wirtualne, które procesor tłumaczy na adresy fizyczne i występują błędy stron itp. Śledzą, które strony należą do których aplikacji. Nigdy tak naprawdę nie musisz się tym martwić, ponieważ po prostu używasz dowolnej metody używanej przez Twój język programowania do przydzielania i zwalniania pamięci oraz sprawdzania błędów (jeśli z jakiegokolwiek powodu przydzielanie / zwalnianie kończy się niepowodzeniem).

  • Co decyduje o wielkości każdego z nich?

    Znowu zależy to od języka, kompilatora, systemu operacyjnego i architektury. Stos jest zwykle wstępnie przydzielony, ponieważ z definicji musi to być ciągła pamięć. Kompilator języka lub system operacyjny określają jego rozmiar. Na stosie nie są przechowywane duże porcje danych, więc będą wystarczająco duże, aby nigdy nie były w pełni wykorzystane, z wyjątkiem przypadków niechcianej nieskończonej rekurencji (stąd „przepełnienia stosu”) lub innych nietypowych decyzji programowych.

    Sterta to ogólny termin określający wszystko, co można dynamicznie przydzielić. W zależności od tego, jak na to patrzysz, stale zmienia rozmiar. W nowoczesnych procesorach i systemach operacyjnych dokładny sposób działania jest zresztą bardzo abstrakcyjny, więc zwykle nie musisz martwić się o to, jak działa głęboko, z wyjątkiem tego (w językach, w których pozwala), nie możesz używać pamięci, która jeszcze nie przydzieliłeś ani uwolnionej pamięci.

  • Co przyspiesza?

    Stos jest szybszy, ponieważ cała wolna pamięć jest zawsze ciągła. Nie trzeba utrzymywać listy wszystkich segmentów wolnej pamięci, wystarczy pojedynczy wskaźnik do bieżącego wierzchołka stosu. Kompilatory zwykle przechowują ten wskaźnik w specjalnym, szybkim rejestrze do tego celu. Co więcej, kolejne operacje na stosie są zwykle skoncentrowane w bardzo bliskich obszarach pamięci, co przy bardzo niskim poziomie jest dobre do optymalizacji przez pamięci podręczne procesora.

thomasrutter
źródło
20
David Nie zgadzam się z tym, że to dobry obraz lub że „push-down stack” to dobry termin na zilustrowanie tej koncepcji. Kiedy dodajesz coś do stosu, pozostała zawartość stosu nie jest zepchnięta w dół, pozostaje na miejscu.
thomasrutter,
8
Ta odpowiedź zawiera duży błąd. Zmienne statyczne nie są przydzielane na stosie. Zobacz moją odpowiedź [link] stackoverflow.com/a/13326916/1763801 w celu uzyskania wyjaśnień.
porównujesz
13
Mówisz konkretnie: „statycznie przydzielone zmienne lokalne” są przydzielane na stosie. W rzeczywistości są one alokowane w segmencie danych. Na stosie są przydzielane tylko automatycznie przydzielane zmienne (które obejmują większość, ale nie wszystkie zmienne lokalne, a także rzeczy takie jak parametry funkcji przekazywane raczej przez wartość niż przez odniesienie).
davec
9
Właśnie zdałem sobie sprawę, że masz rację - w C alokacja statyczna jest osobną rzeczą, a nie terminem na wszystko, co nie jest dynamiczne . Zredagowałem swoją odpowiedź, dzięki.
thomasrutter,
5
To nie tylko C. Java, Pascal, Python i wiele innych mają pojęcia alokacji statycznej kontra automatycznej kontra dynamicznej. Powiedzenie „przydział statyczny” oznacza to samo prawie wszędzie. W żadnym języku przypisanie statyczne nie oznacza „niedynamicznego”. Chcesz termin „automatyczny” przydział do tego, co opisujesz (tj. Rzeczy na stosie).
davec
727

(Przesunąłem tę odpowiedź z innego pytania, które było mniej więcej duplikatem tego).

Odpowiedź na twoje pytanie zależy od implementacji i może się różnić w zależności od kompilatora i architektury procesora. Oto jednak uproszczone wyjaśnienie.

  • Zarówno stos, jak i sterty są obszarami pamięci przydzielonymi z podstawowego systemu operacyjnego (często pamięć wirtualna, która jest mapowana na pamięć fizyczną na żądanie).
  • W środowisku wielowątkowym każdy wątek będzie miał swój całkowicie niezależny stos, ale będzie współdzielił stertę. Jednoczesny dostęp musi być kontrolowany na stosie i nie jest możliwy na stosie.

Kupa

  • Sterta zawiera połączoną listę używanych i wolnych bloków. Nowe przydziały na stercie (przez newlub malloc) są spełnione przez utworzenie odpowiedniego bloku z jednego z wolnych bloków. Wymaga to aktualizacji listy bloków na stercie. Te meta informacje o blokach na stercie są również przechowywane na stercie często na małym obszarze tuż przed każdym blokiem.
  • W miarę wzrostu stosu nowe bloki są często przydzielane od niższych adresów do wyższych adresów. Dlatego możesz myśleć o stercie jako o stercie bloków pamięci, które powiększają się wraz z przydzielaniem pamięci. Jeśli sterta jest zbyt mała do alokacji, rozmiar można często zwiększyć, uzyskując więcej pamięci z podstawowego systemu operacyjnego.
  • Przydzielanie i zwalnianie wielu małych bloków może pozostawić stertę w stanie, w którym istnieje wiele małych wolnych bloków rozproszonych między wykorzystanymi blokami. Żądanie alokacji dużego bloku może się nie powieść, ponieważ żaden z wolnych bloków nie jest wystarczająco duży, aby spełnić żądanie alokacji, mimo że łączny rozmiar wolnych bloków może być wystarczająco duży. Nazywa się to fragmentacją sterty .
  • Gdy zwolniony zostaje wykorzystany blok, który sąsiaduje z wolnym blokiem, nowy wolny blok może zostać połączony z sąsiednim wolnym blokiem w celu utworzenia większego wolnego bloku, skutecznie zmniejszając fragmentację stosu.

Kupa

Stos

  • Stos często działa w ścisłym tandemie ze specjalnym rejestrem w CPU o nazwie wskaźnik stosu . Początkowo wskaźnik stosu wskazuje na górę stosu (najwyższy adres na stosie).
  • CPU ma specjalne instrukcje dotyczące wypychania wartości na stos i wyrzucania ich z powrotem ze stosu. Każde wypychanie przechowuje wartość w bieżącej lokalizacji wskaźnika stosu i zmniejsza wskaźnik stosu. A pop Pobiera wartość wskazywanego przez wskaźnik stosu, a następnie zwiększa wskaźnik stosu (nie mylić z faktu, że dodawanie wartości do stosu maleje wskaźnik stosu i usuwania wartości zwiększa ją. Pamiętaj, że stos rośnie do dół). Wartości przechowywane i pobierane są wartościami rejestrów CPU.
  • Gdy funkcja jest wywoływana, CPU używa specjalnych instrukcji, które przesuwają wskaźnik bieżącej instrukcji , tj. Adres kodu wykonującego się na stosie. Następnie CPU przeskakuje do funkcji, ustawiając wskaźnik instrukcji na adres wywoływanej funkcji. Później, gdy funkcja wraca, stary wskaźnik instrukcji jest wyskakujący ze stosu i wykonywanie jest wznawiane przy kodzie tuż po wywołaniu funkcji.
  • Po wprowadzeniu funkcji wskaźnik stosu jest zmniejszany, aby przydzielić więcej miejsca na stosie dla zmiennych lokalnych (automatycznych). Jeśli funkcja ma jedną lokalną 32-bitową zmienną, cztery bajty są odkładane na stosie. Kiedy funkcja powraca, wskaźnik stosu jest cofany, aby zwolnić przydzielony obszar.
  • Jeśli funkcja ma parametry, są one wypychane na stos przed wywołaniem funkcji. Kod w funkcji może następnie nawigować w górę stosu od bieżącego wskaźnika stosu, aby zlokalizować te wartości.
  • Zagnieżdżanie wywołań funkcji działa jak urok. Każde nowe wywołanie przydzieli parametry funkcji, adres zwrotny i przestrzeń dla zmiennych lokalnych, a te rekordy aktywacji mogą być układane w stos dla zagnieżdżonych wywołań i będą się rozwijać w prawidłowy sposób po powrocie funkcji.
  • Ponieważ stos jest ograniczonym blokiem pamięci, możesz spowodować przepełnienie stosu , wywołując zbyt wiele zagnieżdżonych funkcji i / lub przydzielając zbyt dużo miejsca dla zmiennych lokalnych. Często obszar pamięci używany dla stosu jest skonfigurowany w taki sposób, że zapis poniżej dolnej (najniższego adresu) stosu wyzwoli pułapkę lub wyjątek w CPU. Ten wyjątkowy warunek może następnie zostać przechwycony przez środowisko wykonawcze i przekształcony w pewien wyjątek przepełnienia stosu.

Stos

Czy funkcję można przypisać do stosu zamiast stosu?

Nie, rekordy aktywacji funkcji (tj. Zmiennych lokalnych lub automatycznych) są przydzielane na stosie, który służy nie tylko do przechowywania tych zmiennych, ale także do śledzenia zagnieżdżonych wywołań funkcji.

Sposób zarządzania stertą zależy od środowiska wykonawczego. Używa mallocjęzyka C i języka C ++ new, ale wiele innych języków ma funkcje wyrzucania elementów bezużytecznych.

Stos jest jednak funkcją niskiego poziomu, ściśle związaną z architekturą procesora. Zwiększanie sterty, gdy nie ma wystarczającej ilości miejsca, nie jest zbyt trudne, ponieważ można ją zaimplementować w wywołaniu biblioteki, która obsługuje stertę. Jednak zwiększenie stosu jest często niemożliwe, ponieważ przepełnienie stosu jest wykrywane tylko wtedy, gdy jest już za późno; a zamknięcie wątku wykonania jest jedyną realną opcją.

Martin Liversage
źródło
35
@Martin - Bardzo dobra odpowiedź / wyjaśnienie niż bardziej abstrakcyjna odpowiedź zaakceptowana. Przykładowy program zestawu pokazujący wskaźniki stosu / rejestry używane do wywołań funkcji byłby bardziej ilustracyjny.
Bikal Lem,
3
Każdy typ odniesienia jest kompozycją typów wartości (int, string itp.). Jak powiedziano, typy wartości są przechowywane na stosie, niż jak to działa, gdy są częścią typu odniesienia.
Nps
15
Moim zdaniem ta odpowiedź była najlepsza, ponieważ pomogła mi zrozumieć, czym tak naprawdę jest deklaracja zwrotna i jak odnosi się do tego „adresu zwrotnego”, na który natrafiam od czasu do czasu, co to znaczy wcisnąć funkcję na stos, i dlaczego funkcje są wypychane na stosy. Świetna odpowiedź!
Alex
3
Moim zdaniem jest to najlepsze, mianowicie wspomnieć, że sterta / stos są bardzo specyficzne dla implementacji. Pozostałe odpowiedzi zakładają wiele rzeczy na temat języka i środowiska / systemu operacyjnego. +1
Qix - MONICA MISTREATED
2
Co masz na myśli: „Kod w funkcji może wtedy nawigować w górę stosu od bieżącego wskaźnika stosu, aby zlokalizować te wartości”. ? Czy możesz to rozwinąć?
Koray Tugay
404

W następującym kodzie C #

public void Method1()
{
    int i = 4;
    int y = 2;
    class1 cls1 = new class1();
}

Oto jak zarządza się pamięcią

Obraz zmiennych na stosie

Local Variablesmusi to trwać tylko tak długo, jak długo wywoływana jest funkcja na stosie. Sterta jest używana dla zmiennych, których czasu życia tak naprawdę nie wiemy z góry, ale spodziewamy się, że będą trwały przez jakiś czas. W większości języków bardzo ważne jest, abyśmy w czasie kompilacji wiedzieli, jak duża jest zmienna, jeśli chcemy ją przechowywać na stosie.

Obiekty (które różnią się rozmiarem, gdy je aktualizujemy) trafiają na stos, ponieważ nie wiemy w czasie tworzenia, jak długo będą trwać. W wielu językach sterty są usuwane w celu znalezienia obiektów (takich jak obiekt cls1), które nie mają już żadnych odniesień.

W Javie większość obiektów trafia bezpośrednio na stos. W językach takich jak C / C ++ struktury i klasy często pozostają na stosie, gdy nie masz do czynienia ze wskaźnikami.

Więcej informacji można znaleźć tutaj:

Różnica między alokacją pamięci stosu i sterty «timmurphy.org

i tu:

Tworzenie obiektów na stosie i stosie

Ten artykuł jest źródłem powyższego obrazu: Sześć ważnych pojęć .NET: Stos, stos, typy wartości, typy referencyjne, boksowanie i rozpakowywanie - CodeProject

ale pamiętaj, że może zawierać pewne nieścisłości.

Snowcrash
źródło
15
To jest niepoprawne. i i cls nie są zmiennymi „statycznymi”. nazywane są zmiennymi „lokalnymi” lub „automatycznymi”. To bardzo ważne rozróżnienie. Aby uzyskać wyjaśnienia, zobacz [link] stackoverflow.com/a/13326916/1763801
davec
9
Nie powiedziałem, że to zmienne statyczne . Powiedziałem, że int i cls1 są elementami statycznymi . Ich pamięć jest przydzielana statycznie i dlatego idą na stos. Jest to przeciwieństwo obiektu, który wymaga dynamicznej alokacji pamięci, która dlatego trafia na stertę.
Snowcrash,
12
Cytuję „Przedmioty statyczne ... idź na stos”. To po prostu źle. Przedmioty statyczne trafiają do segmentu danych, przedmioty automatyczne trafiają na stos.
davec
14
Również ten, kto napisał ten artykuł dotyczący projektu kodowego, nie wie o czym mówi. Mówi na przykład, że „prymitywne potrzebują pamięci typu statycznego”, co jest całkowicie nieprawdziwe. Nic nie powstrzymuje Cię przed dynamicznym przydzielaniem prymitywów na stercie, po prostu napisz coś takiego jak „int array [] = new int [num]” i voila, prymitywy przydzielane dynamicznie w .NET. To tylko jedna z kilku nieścisłości.
davec
8
Zredagowałem twój post, ponieważ popełniłeś poważne błędy techniczne dotyczące tego, co dzieje się na stosie.
Tom Leys,
209

Stos Kiedy wywołujesz funkcję, argumenty tej funkcji plus niektóre inne koszty ogólne są umieszczane na stosie. Niektóre informacje (takie jak miejsce powrotu) są tam również przechowywane. Kiedy deklarujesz zmienną w swojej funkcji, zmienna ta jest również przydzielana na stosie.

Cofnięcie przydziału stosu jest dość proste, ponieważ zawsze zwalniasz w odwrotnej kolejności, w jakiej przydzielasz. Stosy są dodawane podczas wprowadzania funkcji, odpowiadające im dane są usuwane po wyjściu z nich. Oznacza to, że zwykle pozostajesz w niewielkim obszarze stosu, chyba że wywołasz wiele funkcji, które wywołują wiele innych funkcji (lub stworzysz rozwiązanie rekurencyjne).

Kupa Kupa to ogólna nazwa, w której umieszczasz dane, które tworzysz w locie. Jeśli nie wiesz, ile statków kosmicznych utworzy Twój program, prawdopodobnie użyjesz nowego (lub malloc lub równoważnego) operatora do utworzenia każdego statku kosmicznego. Ta alokacja pozostanie na jakiś czas, więc prawdopodobnie uwolnimy rzeczy w innej kolejności niż je stworzyliśmy.

Tak więc sterta jest o wiele bardziej złożona, ponieważ ostatecznie powstają regiony pamięci, które nie są przeplatane przeplatanymi fragmentami - pamięć ulega fragmentacji. Znalezienie wolnej pamięci o wymaganym rozmiarze jest trudnym problemem. Dlatego należy unikać sterty (choć nadal jest często używana).

Implementacja Implementacja zarówno stosu, jak i sterty zależy zwykle od środowiska wykonawczego / systemu operacyjnego. Często gry i inne aplikacje, które mają krytyczne znaczenie dla wydajności, tworzą własne rozwiązania pamięciowe, które pobierają dużą część pamięci ze sterty, a następnie rozdzielają ją wewnętrznie, aby uniknąć polegania na systemie operacyjnym pamięci.

Jest to praktyczne tylko wtedy, gdy zużycie pamięci jest zupełnie inne niż w normie - tj. W przypadku gier, w których poziom jest ładowany w jednej wielkiej operacji i może odrzucić cały los w kolejnej wielkiej operacji.

Fizyczna lokalizacja w pamięci Jest to mniej istotne niż myślisz, ponieważ technologia zwana pamięcią wirtualną sprawia, że ​​Twój program myśli, że masz dostęp do określonego adresu, na którym dane fizyczne znajdują się gdzie indziej (nawet na dysku twardym!). Adresy, które otrzymujesz dla stosu, są rosnące w miarę pogłębiania się drzewa połączeń. Adresy stosu są nieprzewidywalne (tj. Specyficzne dla implantacji) i szczerze mówiąc nieistotne.

Tom Leys
źródło
16
Zalecenie, aby unikać używania sterty, jest dość silne. Nowoczesne systemy mają dobrych menedżerów sterty, a współczesne języki dynamiczne intensywnie korzystają ze sterty (bez faktycznego martwienia się przez programistę). Powiedziałbym, żeby użyć sterty, ale z ręcznym alokatorem nie zapomnij uwolnić!
Greg Hewgill,
2
Jeśli możesz użyć stosu lub stosu, użyj stosu. Jeśli nie możesz użyć stosu, naprawdę nie masz wyboru. Używam zarówno dużo, jak i oczywiście używając std :: vector lub podobnego trafia na stos. Dla początkującego unikasz stosu, ponieważ stos jest po prostu taki łatwy !!
Tom Leys,
Jeśli twój język nie implementuje odśmiecania, inteligentne wskaźniki (osobno przydzielone obiekty, które owijają się wokół wskaźnika, które liczą referencje dla dynamicznie przydzielanych fragmentów pamięci) są ściśle powiązane z odśmiecaniem i są dobrym sposobem zarządzania stertą w sejfie i sposób bez wycieków. Są one wdrażane w różnych ramach, ale nie są również trudne do wdrożenia w przypadku własnych programów.
BenPen,
1
„Właśnie dlatego należy unikać stosu (choć nadal jest często używany)”. Nie jestem pewien, co to właściwie oznacza, zwłaszcza że pamięć jest zarządzana inaczej w wielu językach wysokiego poziomu. Ponieważ to pytanie jest oznaczone jako niezależne od języka, powiedziałbym, że ten konkretny komentarz / wiersz jest nieodpowiedni i nie dotyczy.
LintfordPickle
2
Dobra uwaga @ JonnoHampson - Podczas gdy robisz słuszny punkt, twierdzę, że jeśli pracujesz w „języku wysokiego poziomu” z GC, prawdopodobnie nie obchodzą cię mechanizmy alokacji pamięci - i tak nie należy nawet obchodzi, jaki jest stos i sterta.
Tom Leys,
194

Aby wyjaśnić, ta odpowiedź ma niepoprawne informacje ( Thomas poprawił swoją odpowiedź po komentarzach, fajnie :)). Inne odpowiedzi po prostu unikają wyjaśniania, co oznacza statyczny przydział. Wyjaśnię więc trzy główne formy alokacji i ich związek z kupką, stosem i segmentem danych poniżej. Pokażę także kilka przykładów w C / C ++ i Python, aby pomóc ludziom zrozumieć.

Zmienne „statyczne” (AKA statycznie przydzielone) nie są przydzielane na stosie. Nie zakładaj, że tak - wiele osób robi to tylko dlatego, że „statyczny” brzmi podobnie jak „stos”. W rzeczywistości nie istnieją ani na stosie, ani na stosie. Są częścią tak zwanego segmentu danych .

Jednak ogólnie lepiej jest rozważyć „ zakres ” i „ czas życia ” niż „stos” i „stos”.

Zakres odnosi się do tego, które części kodu mogą uzyskać dostęp do zmiennej. Generalnie myślimy o zasięgu lokalnym (może być dostępny tylko przez bieżącą funkcję) w porównaniu z zasięgiem globalnym (można uzyskać dostęp w dowolnym miejscu), chociaż zakres może być znacznie bardziej złożony.

Czas życia odnosi się do tego, kiedy zmienna jest przydzielana i zwalniana podczas wykonywania programu. Zwykle myślimy o przydziale statycznym (zmienna zachowuje się przez cały czas trwania programu, dzięki czemu jest przydatny do przechowywania tych samych informacji w kilku wywołaniach funkcji) w porównaniu do przydziału automatycznego (zmienna zachowuje się tylko podczas pojedynczego wywołania funkcji, dzięki czemu jest przydatna do przechowywanie informacji, które są używane tylko podczas działania i można je odrzucić po zakończeniu) w porównaniu z alokacją dynamiczną (zmienne, których czas trwania jest definiowany w czasie wykonywania, zamiast czasu kompilacji, takiego jak statyczny lub automatyczny).

Chociaż większość kompilatorów i interpreterów implementuje to zachowanie w podobny sposób, jeśli chodzi o stosowanie stosów, hałd itp., Kompilator może czasami złamać te konwencje, jeśli chce, o ile zachowanie jest prawidłowe. Na przykład ze względu na optymalizację zmienna lokalna może istnieć tylko w rejestrze lub zostać całkowicie usunięta, mimo że większość zmiennych lokalnych istnieje w stosie. Jak wskazano w kilku komentarzach, możesz swobodnie wdrożyć kompilator, który nawet nie używa stosu lub sterty, ale zamiast tego niektóre inne mechanizmy przechowywania (rzadko wykonywane, ponieważ stosy i sterty są do tego świetne).

Przedstawię prosty kod C z adnotacjami, aby zilustrować to wszystko. Najlepszym sposobem na naukę jest uruchomienie programu w debuggerze i obserwowanie zachowania. Jeśli wolisz czytać Pythona, przejdź do końca odpowiedzi :)

// Statically allocated in the data segment when the program/DLL is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in the code
int someGlobalVariable;

// Statically allocated in the data segment when the program is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in this particular code file
static int someStaticVariable;

// "someArgument" is allocated on the stack each time MyFunction is called
// "someArgument" is deallocated when MyFunction returns
// scope - can be accessed only within MyFunction()
void MyFunction(int someArgument) {

    // Statically allocated in the data segment when the program is first loaded
    // Deallocated when the program/DLL exits
    // scope - can be accessed only within MyFunction()
    static int someLocalStaticVariable;

    // Allocated on the stack each time MyFunction is called
    // Deallocated when MyFunction returns
    // scope - can be accessed only within MyFunction()
    int someLocalVariable;

    // A *pointer* is allocated on the stack each time MyFunction is called
    // This pointer is deallocated when MyFunction returns
    // scope - the pointer can be accessed only within MyFunction()
    int* someDynamicVariable;

    // This line causes space for an integer to be allocated in the heap
    // when this line is executed. Note this is not at the beginning of
    // the call to MyFunction(), like the automatic variables
    // scope - only code within MyFunction() can access this space
    // *through this particular variable*.
    // However, if you pass the address somewhere else, that code
    // can access it too
    someDynamicVariable = new int;


    // This line deallocates the space for the integer in the heap.
    // If we did not write it, the memory would be "leaked".
    // Note a fundamental difference between the stack and heap
    // the heap must be managed. The stack is managed for us.
    delete someDynamicVariable;

    // In other cases, instead of deallocating this heap space you
    // might store the address somewhere more permanent to use later.
    // Some languages even take care of deallocation for you... but
    // always it needs to be taken care of at runtime by some mechanism.

    // When the function returns, someArgument, someLocalVariable
    // and the pointer someDynamicVariable are deallocated.
    // The space pointed to by someDynamicVariable was already
    // deallocated prior to returning.
    return;
}

// Note that someGlobalVariable, someStaticVariable and
// someLocalStaticVariable continue to exist, and are not
// deallocated until the program exits.

Szczególnie przejmującym przykładem tego, dlaczego ważne jest rozróżnienie czasu życia i zakresu, jest to, że zmienna może mieć zasięg lokalny, ale czas życia statyczny - na przykład „someLocalStaticVariable” w powyższym przykładzie kodu. Takie zmienne mogą sprawić, że nasze powszechne, ale nieformalne nawyki nazywania będą bardzo mylące. Na przykład, gdy mówimy „ lokalnie ”, zwykle mamy na myśli „ lokalnie przydzieloną zmienną przydzielaną automatycznie ”, a gdy mówimy globalnie, zwykle mamy na myśli „ globalnie ustaloną zmienną przydzielaną statycznie ”. Niestety, jeśli chodzi o takie rzeczy, jak „ statycznie przydzielane zmienne o zasięgu pliku ”, wiele osób mówi po prostu… „ huh ??? ”.

Niektóre opcje składni w C / C ++ zaostrzają ten problem - na przykład wiele osób uważa, że ​​zmienne globalne nie są „statyczne” z powodu składni pokazanej poniżej.

int var1; // Has global scope and static allocation
static int var2; // Has file scope and static allocation

int main() {return 0;}

Zauważ, że umieszczenie słowa kluczowego „static” w powyższej deklaracji zapobiega globalnemu zasięgowi var2. Niemniej globalny var1 ma statyczny przydział. To nie jest intuicyjne! Z tego powodu staram się nigdy nie używać słowa „statyczny” przy opisywaniu zakresu, a zamiast tego mówię coś w rodzaju zakresu „plik” lub „ograniczenie pliku”. Jednak wiele osób używa wyrażenia „statyczny” lub „zakres statyczny”, aby opisać zmienną, do której można uzyskać dostęp tylko z jednego pliku kodu. W kontekście czasu życia „statyczny” zawsze oznacza, że ​​zmienna jest przydzielana na początku programu i zwalniana po wyjściu z programu.

Niektóre osoby myślą o tych pojęciach jako specyficznych dla C / C ++. Oni nie są. Na przykład poniższy przykład Pythona ilustruje wszystkie trzy typy alokacji (możliwe są pewne subtelne różnice w interpretowanych językach, których nie będę tutaj wchodził).

from datetime import datetime

class Animal:
    _FavoriteFood = 'Undefined' # _FavoriteFood is statically allocated

    def PetAnimal(self):
        curTime = datetime.time(datetime.now()) # curTime is automatically allocatedion
        print("Thank you for petting me. But it's " + str(curTime) + ", you should feed me. My favorite food is " + self._FavoriteFood)

class Cat(Animal):
    _FavoriteFood = 'tuna' # Note since we override, Cat class has its own statically allocated _FavoriteFood variable, different from Animal's

class Dog(Animal):
    _FavoriteFood = 'steak' # Likewise, the Dog class gets its own static variable. Important to note - this one static variable is shared among all instances of Dog, hence it is not dynamic!


if __name__ == "__main__":
    whiskers = Cat() # Dynamically allocated
    fido = Dog() # Dynamically allocated
    rinTinTin = Dog() # Dynamically allocated

    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

    Dog._FavoriteFood = 'milkbones'
    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

# Output is:
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is milkbones
# Thank you for petting me. But it's 13:05:02.256000, you should feed me. My favorite food is milkbones
davec
źródło
Odniosłbym się do zmiennej statycznej zadeklarowanej w funkcji jako posiadającej jedynie lokalną dostępność , ale ogólnie nie używałbym z nią terminu „zakres”. Warto również zauważyć, że aspekt jednego stosu / sterty, przy którym języki mają zasadniczo zerową elastyczność: język, który zapisuje kontekst wykonania na stosie, nie może używać tego samego stosu do przechowywania rzeczy, które będą musiały przeżyć konteksty, w których zostały utworzone . Niektóre języki, na przykład, PostScriptmają wiele stosów, ale mają „stertę”, która bardziej przypomina stos.
supercat
@ superupat To wszystko ma sens. Zdefiniowałem zakres jako „jakie części kodu mogą uzyskać dostęp do zmiennej” (i uważam, że jest to najbardziej standardowa definicja), więc myślę, że się zgadzamy :)
davec
Uważałbym, że „zakres” zmiennej jest ograniczony zarówno czasem, jak i przestrzenią. Zmienna w zakresie klasy-obiektu jest wymagana do utrzymania jej wartości tak długo, jak długo istnieje obiekt. Zmienna w zakresie kontekstu wykonania jest wymagana do zachowania swojej wartości, dopóki wykonanie pozostaje w tym kontekście. Deklaracja zmiennej statycznej tworzy identyfikator, którego zakres jest ograniczony do bieżącego bloku, który jest dołączany do zmiennej, której zakres jest nieograniczony.
supercat
@ superupat Dlatego używam słowa „czas życia”, czyli tak nazywam zakres czasu. Zmniejsza to potrzebę przeciążania słowa „zakres” tak wieloma znaczeniami. O ile mi wiadomo, nawet wśród źródeł kanonicznych nie wydaje się, że istnieje ścisła zgodność co do dokładnych definicji. Moja terminologia pochodzi częściowo z K&R, a częściowo z powszechnego użycia na pierwszym wydziale CS, na którym studiowałem / uczyłem. Zawsze dobrze słyszeć inny świadomy widok.
davec
1
chyba żartujesz. czy naprawdę możesz zdefiniować zmienną statyczną wewnątrz funkcji?
Zaeem Sattar
168

Inni dość dobrze odpowiedzieli na szerokie pociągnięcia, więc przedstawię kilka szczegółów.

  1. Stos i stos nie muszą być pojedynczymi. Częstą sytuacją, w której masz więcej niż jeden stos, jest to, że masz więcej niż jeden wątek w procesie. W tym przypadku każdy wątek ma swój własny stos. Możesz także mieć więcej niż jedną stertę, na przykład niektóre konfiguracje bibliotek DLL mogą powodować przydzielanie różnych bibliotek DLL z różnych stert, dlatego generalnie złym pomysłem jest zwolnienie pamięci przydzielonej przez inną bibliotekę.

  2. W C można uzyskać korzyść z alokacji o zmiennej długości za pomocą alokacji , która alokuje na stosie, w przeciwieństwie do alokacji, która alokuje na stosie. Ta pamięć nie przetrwa instrukcji return, ale jest użyteczna dla bufora scratch.

  3. Tworzenie ogromnego bufora tymczasowego w systemie Windows, z którego nie korzystasz dużo, nie jest darmowe. Wynika to z faktu, że kompilator generuje pętlę sondy stosu, która jest wywoływana za każdym razem, gdy twoja funkcja jest wprowadzana, aby upewnić się, że stos istnieje (ponieważ system Windows używa pojedynczej strony ochronnej na końcu stosu, aby wykryć, kiedy trzeba zwiększyć stos. Jeśli uzyskasz dostęp do pamięci więcej niż jednej strony na końcu stosu, nastąpi awaria). Przykład:

void myfunction()
{
   char big[10000000];
   // Do something that only uses for first 1K of big 99% of the time.
}
Don Neufeld
źródło
Re: „w przeciwieństwie do przydziału”: Czy masz na myśli „w przeciwieństwie do malloc”?
Peter Mortensen
Jak przenośny jest alloca?
Peter Mortensen
@PeterMortensen nie jest POSIX, przenośność nie jest gwarantowana.
Don Neufeld,
135

Inni bezpośrednio odpowiedzieli na twoje pytanie, ale próbując zrozumieć stos i stertę, myślę, że warto rozważyć układ pamięci tradycyjnego procesu UNIX (bez wątków i mmap()bazujących na alokatorach). Memory Zarządzanie Słowniczek strona internetowa posiada schemat tego układu pamięci.

Stos i sterta są tradycyjnie umieszczone na przeciwległych końcach wirtualnej przestrzeni adresowej procesu. Stos rośnie automatycznie po uzyskaniu dostępu do wielkości ustawionej przez jądro (którą można regulować setrlimit(RLIMIT_STACK, ...)). Sterta rośnie, gdy alokator pamięci wywołuje wywołanie systemowe brk()lub sbrk()systemowe, mapując więcej stron pamięci fizycznej w wirtualnej przestrzeni adresowej procesu.

W systemach bez pamięci wirtualnej, takich jak niektóre systemy osadzone, często stosuje się ten sam podstawowy układ, z wyjątkiem tego, że rozmiar stosu i sterty jest stały. Jednak w innych systemach wbudowanych (takich jak te oparte na mikrokontrolerach Microchip PIC) stos programów jest oddzielnym blokiem pamięci, który nie jest adresowany przez instrukcje przenoszenia danych i może być modyfikowany lub odczytywany pośrednio poprzez instrukcje przepływu programu (wywołanie, zwrot itp.). Inne architektury, takie jak procesory Intel Itanium, mają wiele stosów . W tym sensie stos jest elementem architektury procesora.

bk1e
źródło
117

Co to jest stos?

Stos to stos przedmiotów, zwykle starannie ułożony.

Wpisz opis zdjęcia tutaj

Stosy w architekturach obliczeniowych to regiony pamięci, w których dane są dodawane lub usuwane w sposób ostatni na wejściu.
W aplikacji wielowątkowej każdy wątek będzie miał własny stos.

Co to jest kupa?

Kupa jest nieporządnym zbiorem rzeczy ułożonych przypadkowo.

Wpisz opis zdjęcia tutaj

W architekturach obliczeniowych sterta jest obszarem dynamicznie alokowanej pamięci, która jest automatycznie zarządzana przez system operacyjny lub bibliotekę menedżera pamięci.
Pamięć na stercie jest przydzielana, zwalniana i zmieniana regularnie podczas wykonywania programu, co może prowadzić do problemu zwanego fragmentacją.
Fragmentacja występuje, gdy obiekty pamięci są przydzielane z małymi odstępami, które są zbyt małe, aby pomieścić dodatkowe obiekty pamięci.
Wynik netto to procent przestrzeni sterty, która nie nadaje się do dalszego przydzielania pamięci.

Oba razem

W aplikacji wielowątkowej każdy wątek będzie miał własny stos. Ale wszystkie różne wątki będą dzielić stos.
Ponieważ różne wątki współużytkują stertę w aplikacji wielowątkowej, oznacza to również, że musi istnieć pewna koordynacja między wątkami, aby nie próbowały one uzyskiwać dostępu i manipulować tym samym fragmentem pamięci w stercie w o tym samym czasie.

Który jest szybszy - stos czy stos? I dlaczego?

Stos jest znacznie szybszy niż stos.
Wynika to ze sposobu przydzielania pamięci na stosie.
Przydział pamięci na stosie jest tak prosty, jak przesunięcie wskaźnika stosu w górę.

Dla osób początkujących w programowaniu prawdopodobnie dobrym pomysłem jest użycie stosu, ponieważ jest łatwiejsze.
Ponieważ stos jest mały, powinieneś go użyć, gdy dokładnie wiesz, ile pamięci potrzebujesz na dane lub jeśli wiesz, że rozmiar danych jest bardzo mały.
Lepiej jest użyć sterty, gdy wiesz, że będziesz potrzebować dużo pamięci na swoje dane lub po prostu nie jesteś pewien, ile pamięci będziesz potrzebować (jak w przypadku dynamicznej tablicy).

Model pamięci Java

Wpisz opis zdjęcia tutaj

Stos to obszar pamięci, w którym przechowywane są zmienne lokalne (w tym parametry metody). Jeśli chodzi o zmienne obiektowe, są to jedynie odniesienia (wskaźniki) do rzeczywistych obiektów na stercie.
Za każdym razem, gdy instancja obiektu jest tworzona, część pamięci sterty jest odkładana na bok, aby przechować dane (stan) tego obiektu. Ponieważ obiekty mogą zawierać inne obiekty, niektóre z tych danych mogą faktycznie zawierać odniesienia do tych zagnieżdżonych obiektów.

Shreyos Adikari
źródło
115

Stos jest częścią pamięci, którą można manipulować za pomocą kilku instrukcji języka asemblera, takich jak „pop” (usuń i zwróć wartość ze stosu) i „push” (wypchnij wartość na stos), ale także wywołanie ( wywołać podprogram - powoduje to przesunięcie adresu w celu powrotu do stosu) i powrót (powrót z podprogramu - powoduje usunięcie adresu ze stosu i przejście do niego). Jest to obszar pamięci poniżej rejestru wskaźnika stosu, który można ustawić w razie potrzeby. Stos służy również do przekazywania argumentów do podprogramów, a także do zachowania wartości w rejestrach przed wywołaniem podprogramów.

Sterta to część pamięci, która jest przekazywana do aplikacji przez system operacyjny, zwykle poprzez systemowy wywołanie takie jak malloc. W nowoczesnych systemach operacyjnych pamięć ta jest zbiorem stron, do których dostęp ma tylko proces wywoływania.

Rozmiar stosu jest określany w czasie wykonywania i na ogół nie rośnie po uruchomieniu programu. W programie C stos musi być wystarczająco duży, aby pomieścić każdą zmienną zadeklarowaną w ramach każdej funkcji. Sterta będzie rosła dynamicznie zgodnie z potrzebami, ale system operacyjny ostatecznie wykonuje połączenie (często powiększa stertę o więcej niż wartość żądana przez malloc, tak że przynajmniej niektóre przyszłe centra handlowe nie będą musiały wracać do jądra, aby uzyskać więcej pamięci. To zachowanie można często dostosować)

Ponieważ przydzieliłeś stos przed uruchomieniem programu, nigdy nie musisz Malloc przed użyciem stosu, więc jest to niewielka zaleta. W praktyce bardzo trudno jest przewidzieć, co będzie szybkie, a co powolne w nowoczesnych systemach operacyjnych z podsystemami pamięci wirtualnej, ponieważ sposób implementacji stron i miejsca ich przechowywania jest szczegółem implementacji.

Daniel Papasian
źródło
2
Warto również wspomnieć o tym, że dane wywiadowcze znacznie optymalizują dostęp do stosu, zwłaszcza takie rzeczy, jak przewidywanie miejsca powrotu z funkcji.
Tom Leys,
113

Myślę, że wiele innych osób udzieliło ci głównie poprawnych odpowiedzi w tej sprawie.

Jednym z pominiętych szczegółów jest jednak to, że „stertę” należy prawdopodobnie nazwać „wolnym sklepem”. Powodem tego rozróżnienia jest fakt, że oryginalny darmowy magazyn został zaimplementowany ze strukturą danych znaną jako „dwumianowa kupa”. Z tego powodu alokacja od wczesnych implementacji malloc () / free () była alokacją ze sterty. Jednak w dzisiejszych czasach większość bezpłatnych sklepów jest wdrażana z bardzo rozbudowanymi strukturami danych, które nie są kupami dwumianowymi.


źródło
8
Kolejny nitpick - większość odpowiedzi (lekko) sugeruje, że Cjęzyk wymaga użycia „stosu” . Jest to powszechne nieporozumienie, choć jest to (zdecydowanie) dominujący paradygmat implementacji C99 6.2.4 automatic storage duration objects(zmiennych). W rzeczywistości słowo „stos” nawet nie pojawia się w C99standardzie językowym: open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf
johne
[@Heath] Mam mały komentarz do twojej odpowiedzi. Spójrz na przyjętą odpowiedź na to pytanie . Mówi, że darmowy sklep najprawdopodobniej jest taki sam jak kupa , choć niekoniecznie tak jest.
OmarOthman,
91

Za pomocą stosu możesz zrobić kilka interesujących rzeczy. Na przykład masz funkcje takie jak alokacja (zakładając, że możesz ominąć obfite ostrzeżenia dotyczące jego użycia), która jest formą malloc, która konkretnie używa stosu, a nie sterty, do pamięci.

To powiedziawszy, błędy pamięci oparte na stosie są jednymi z najgorszych, jakie spotkałem. Jeśli użyjesz pamięci sterty i przekroczysz granice przydzielonego bloku, masz przyzwoitą szansę na wywołanie błędu segmentu. (Nie 100%: twój blok może być przyległy do ​​innego, który wcześniej przydzieliłeś.) Ale ponieważ zmienne utworzone na stosie są zawsze przylegające do siebie, zapisywanie poza granicami może zmienić wartość innej zmiennej. Nauczyłem się, że ilekroć czuję, że mój program przestał przestrzegać praw logiki, prawdopodobnie jest to przepełnienie bufora.

Piotr
źródło
Jak przenośny jest alloca? Na przykład, czy to działa w systemie Windows? Czy dotyczy to tylko systemów operacyjnych uniksopodobnych?
Peter Mortensen
89

Po prostu stos służy do tworzenia zmiennych lokalnych. Ponadto za każdym razem, gdy wywołujesz podprogram, licznik programu (wskaźnik do następnej instrukcji maszyny) i wszelkie ważne rejestry, a czasami parametry są wypychane na stos. Następnie wszelkie lokalne zmienne wewnątrz podprogramu są wypychane na stos (i używane stamtąd). Po zakończeniu podprogramu wszystkie te rzeczy zostają usunięte ze stosu. Dane komputera i rejestru są pobierane i umieszczane z powrotem tam, gdzie były, tak, aby były popkręcone, dzięki czemu Twój program może iść wesoło.

Sterta to obszar, w którym tworzone są dynamiczne przydziały pamięci (jawne połączenia „nowe” lub „przydzielanie”). Jest to specjalna struktura danych, która może śledzić bloki pamięci o różnych rozmiarach i status ich alokacji.

W „klasycznych” systemach RAM ułożono w taki sposób, że wskaźnik stosu zaczynał się na dole pamięci, wskaźnik stosu zaczynał się na górze i rosły ku sobie. Jeśli się pokrywają, oznacza to brak pamięci RAM. Nie działa to jednak z nowoczesnymi wielowątkowymi systemami operacyjnymi. Każdy wątek musi mieć swój własny stos, który można tworzyć dynamicznie.

PRZETRZĄSAĆ
źródło
[@TED] Dlaczego powiedziałeś „czasami parametry są wypychane na stos”? Wiem tylko, że zawsze są. Czy mógłbyś prosić o bardziej szczegółowe opracowanie?
OmarOthman,
1
@OmarOthman - mówię to, ponieważ to zależy wyłącznie od autora twojego kompilatora / tłumacza, co dzieje się, gdy wywoływany jest podprogram. Klasyczne zachowanie Fortrana polega na tym, że wcale nie używa stosu. Niektóre języki obsługują egzotyczne rzeczy, takie jak pass-by-name, które w rzeczywistości zastępuje tekst.
TED,
83

Z WikiAnwser.

Stos

Gdy funkcja lub metoda wywołuje inną funkcję, która z kolei wywołuje inną funkcję itp., Wykonywanie wszystkich tych funkcji pozostaje zawieszone, dopóki ostatnia funkcja nie zwróci swojej wartości.

Ten łańcuch zawieszonych wywołań funkcji jest stosem, ponieważ elementy w stosie (wywołania funkcji) zależą od siebie.

Stos należy wziąć pod uwagę podczas obsługi wyjątków i wykonywania wątków.

Sterta

Sterta to po prostu pamięć używana przez programy do przechowywania zmiennych. Element stosu (zmienne) nie ma ze sobą żadnych zależności i zawsze można uzyskać do niego dostęp losowo w dowolnym momencie.

devXen
źródło
„Bardziej podoba mi się zaakceptowana odpowiedź, ponieważ jest ona jeszcze bardziej niska”. To źle, a nie dobrze.
Wyścigi lekkości na orbicie
54

Stos

  • Bardzo szybki dostęp
  • Nie musisz jawnie cofać alokacji zmiennych
  • Procesor skutecznie zarządza przestrzenią, pamięć nie ulegnie fragmentacji
  • Tylko zmienne lokalne
  • Limit wielkości stosu (zależny od systemu operacyjnego)
  • Zmiennych nie można zmieniać

Sterta

  • Dostęp do zmiennych można uzyskać globalnie
  • Brak limitu wielkości pamięci
  • (Relatywnie) wolniejszy dostęp
  • Brak gwarantowanego efektywnego wykorzystania przestrzeni, pamięć może z czasem ulec fragmentacji w miarę przydzielania, a następnie zwalniania bloków pamięci
  • Musisz zarządzać pamięcią (jesteś odpowiedzialny za przydzielanie i zwalnianie zmiennych)
  • Zmienną wielkość można zmienić za pomocą realloc ()
nieznany
źródło
50

OK, po prostu i krótko mówiąc, oznaczają uporządkowane, a nie uporządkowane ...!

Stos : w stosach przedmioty układają się jeden na drugim, co oznacza, że ​​będzie szybsze i bardziej wydajne w przetwarzaniu! ...

Tak więc zawsze istnieje indeks wskazujący konkretny element, również przetwarzanie będzie szybsze, istnieje również związek między przedmiotami! ...

Sterta : Brak zamówienia, przetwarzanie będzie wolniejsze, a wartości zostaną pomieszane wraz z brakiem konkretnego zamówienia lub indeksu ... są losowe i nie ma między nimi związku ... więc czas realizacji i użytkowania może być różny ...

Tworzę również poniższy obrazek, aby pokazać, jak mogą wyglądać:

wprowadź opis zdjęcia tutaj

Alireza
źródło
49

W skrócie

Stos jest używany do statycznej alokacji pamięci, a sterty do dynamicznej alokacji pamięci, obie przechowywane w pamięci RAM komputera.


Szczegółowo

Stos

Stos jest strukturą danych „LIFO” (ostatnie wejście, pierwsze wyjście), którą procesor dość dokładnie zarządza i optymalizuje. Za każdym razem, gdy funkcja deklaruje nową zmienną, jest „wypychana” na stos. Następnie przy każdym wyjściu funkcji wszystkie zmienne wypychane na stos przez tę funkcję są zwalniane (to znaczy są usuwane). Po zwolnieniu zmiennej stosu ten obszar pamięci staje się dostępny dla innych zmiennych stosu.

Zaletą używania stosu do przechowywania zmiennych jest to, że pamięć jest zarządzana za Ciebie. Nie musisz ręcznie przydzielać pamięci ani jej zwalniać, gdy już jej nie potrzebujesz. Co więcej, ponieważ procesor tak skutecznie organizuje pamięć stosu, odczytywanie i zapisywanie zmiennych stosu jest bardzo szybkie.

Więcej można znaleźć tutaj .


Kupa

Sterta to obszar pamięci komputera, który nie jest dla ciebie zarządzany automatycznie i nie jest tak ściśle zarządzany przez procesor. Jest to bardziej swobodny obszar pamięci (i jest większy). Aby przydzielić pamięć na stercie, musisz użyć malloc () lub calloc (), które są wbudowanymi funkcjami C. Po przydzieleniu pamięci na stercie jesteś odpowiedzialny za użycie free () w celu zwolnienia pamięci, gdy już jej nie potrzebujesz.

Jeśli tego nie zrobisz, w twoim programie wystąpi wyciek pamięci. Oznacza to, że pamięć na stercie nadal będzie odłożona na bok (i nie będzie dostępna dla innych procesów). Jak zobaczymy w sekcji debugowania, istnieje narzędzie o nazwie Valgrind, które może pomóc w wykryciu wycieków pamięci.

W przeciwieństwie do stosu, sterta nie ma ograniczeń wielkości zmiennych (oprócz oczywistych fizycznych ograniczeń komputera). Pamięć sterty jest nieco wolniejsza do odczytu i zapisu, ponieważ należy użyć wskaźników, aby uzyskać dostęp do pamięci na stercie. Niedługo porozmawiamy o wskaźnikach.

W przeciwieństwie do stosu, zmienne utworzone na stercie są dostępne dla dowolnej funkcji w dowolnym miejscu programu. Zmienne sterty mają zasadniczo zasięg globalny.

Więcej można znaleźć tutaj .


Zmienne przydzielone na stosie są przechowywane bezpośrednio w pamięci, a dostęp do tej pamięci jest bardzo szybki, a jej przydzielanie jest obsługiwane podczas kompilacji programu. Gdy funkcja lub metoda wywołuje inną funkcję, która z kolei wywołuje inną funkcję itp., Wykonywanie wszystkich tych funkcji pozostaje zawieszone, dopóki ostatnia funkcja nie zwróci swojej wartości. Stos jest zawsze zarezerwowany w kolejności LIFO, ostatnio zarezerwowany blok jest zawsze następnym blokiem do zwolnienia. To sprawia, że ​​śledzenie stosu jest naprawdę proste, uwolnienie bloku ze stosu to nic innego jak dostosowanie jednego wskaźnika.

Zmienne przydzielone na stercie mają przydzieloną pamięć w czasie wykonywania, a dostęp do tej pamięci jest nieco wolniejszy, ale wielkość sterty jest ograniczona tylko rozmiarem pamięci wirtualnej. Elementy stosu nie są od siebie zależne i zawsze można uzyskać do nich dostęp losowo w dowolnym momencie. Możesz przydzielić blok w dowolnym momencie i zwolnić go w dowolnym momencie. To znacznie komplikuje śledzenie, które części sterty są przydzielane lub wolne w danym momencie.

Wpisz opis zdjęcia tutaj

Możesz użyć stosu, jeśli dokładnie wiesz, ile danych musisz przydzielić przed czasem kompilacji, i nie jest on zbyt duży. Możesz użyć sterty, jeśli nie wiesz dokładnie, ile danych będziesz potrzebować w czasie wykonywania lub jeśli musisz przydzielić dużo danych.

W sytuacji wielowątkowej każdy wątek będzie miał swój własny, całkowicie niezależny stos, ale będzie dzielił stertę. Stos jest zależny od wątku, a sterta jest zależna od aplikacji. Stos należy wziąć pod uwagę podczas obsługi wyjątków i wykonywania wątków.

Każdy wątek otrzymuje stos, podczas gdy zazwyczaj aplikacja ma tylko jedną stertę (chociaż nierzadko jest mieć wiele stosów dla różnych rodzajów alokacji).

Wpisz opis zdjęcia tutaj

W czasie wykonywania, jeśli aplikacja potrzebuje więcej sterty, może przydzielić pamięć z wolnej pamięci, a jeśli stos potrzebuje pamięci, może przydzielić pamięć z wolnej pamięci przydzielonej dla aplikacji.

Nawet więcej szczegółów podano tutaj i tutaj .


Teraz przyjdź do odpowiedzi na twoje pytanie .

W jakim stopniu są one kontrolowane przez system operacyjny lub środowisko uruchomieniowe języka?

System operacyjny przydziela stos dla każdego wątku na poziomie systemu podczas tworzenia wątku. Zazwyczaj system operacyjny jest wywoływany przez środowisko wykonawcze języka w celu przydzielenia sterty dla aplikacji.

Więcej można znaleźć tutaj .

Jaki jest ich zakres?

Już podane w górę.

„Możesz użyć stosu, jeśli dokładnie wiesz, ile danych musisz przeznaczyć przed czasem kompilacji, i nie jest on zbyt duży. Możesz użyć stosu, jeśli nie wiesz dokładnie, ile danych będziesz potrzebować w czasie wykonywania lub jeśli musisz przydzielić dużo danych ”.

Więcej można znaleźć tutaj .

Co decyduje o wielkości każdego z nich?

Rozmiar stosu jest ustalany przez system operacyjny podczas tworzenia wątku. Rozmiar sterty jest ustawiany podczas uruchamiania aplikacji, ale może rosnąć w miarę potrzebnego miejsca (alokator żąda więcej pamięci z systemu operacyjnego).

Co przyspiesza?

Alokacja stosu jest znacznie szybsza, ponieważ tak naprawdę wszystko przesuwa wskaźnik stosu. Korzystając z pul pamięci, można uzyskać porównywalną wydajność dzięki alokacji sterty, ale wiąże się to z niewielką dodatkową złożonością i własnymi problemami.

Ponadto stos kontra stos to nie tylko kwestia wydajności; mówi również wiele o oczekiwanym okresie użytkowania obiektów.

Szczegóły można znaleźć tutaj .

Abrar Jahin
źródło
36

W latach osiemdziesiątych UNIX propagował się jak króliki, a duże firmy produkowały własne. Exxon miał jedną, podobnie jak dziesiątki marek utraconych w historii. Sposób rozmieszczenia pamięci zależał od wielu autorów.

Typowy program C został umieszczony płasko w pamięci z możliwością zwiększenia poprzez zmianę wartości brk (). Zwykle HEAP był tuż poniżej tej wartości brk, a zwiększenie brk zwiększyło ilość dostępnej sterty.

Pojedynczy STOSUNEK był zazwyczaj obszarem poniżej HEAP, który był obszarem pamięci nie zawierającym nic wartościowego, aż do początku następnego ustalonego bloku pamięci. Następnym blokiem był często KOD, który można było zastąpić stosem danych w jednym ze słynnych hacków swojej epoki.

Jednym z typowych bloków pamięci był BSS (blok zerowych wartości), który przypadkowo nie został wyzerowany w ofercie jednego producenta. Kolejnym były DANE zawierające zainicjowane wartości, w tym ciągi i liczby. Trzeci to KOD zawierający CRT (środowisko wykonawcze C), główne, funkcje i biblioteki.

Pojawienie się pamięci wirtualnej w systemie UNIX zmienia wiele ograniczeń. Nie ma obiektywnego powodu, dla którego bloki te muszą być ciągłe, mieć stały rozmiar lub zamówić w określony sposób teraz. Oczywiście przed UNIXem była Multics, która nie cierpiała z powodu tych ograniczeń. Oto schemat przedstawiający jeden z układów pamięci z tej epoki.

Typowy układ pamięci programu w stylu UNIX C.

Jlettvin
źródło
36

stos , stos i dane każdego procesu w pamięci wirtualnej:

stos, stos i dane statyczne

Yousha Aleayoub
źródło
26

Kilka centów: Myślę, że dobrze będzie narysować graficzną pamięć i prościej:

To moja wizja budowy pamięci procesowej z uproszczeniem dla łatwiejszego zrozumienia tego, co się dzieje


Strzałki - pokazują, gdzie rośnie stos i stos, wielkość stosu procesu ma limit zdefiniowany w systemie operacyjnym, limity wielkości stosu wątków według parametrów w wątku zwykle tworzą API. Sterty zwykle ograniczane przez proces maksymalnego rozmiaru pamięci wirtualnej, na przykład dla 32 bitów 2-4 GB.

Tak prosty sposób: sterta procesu jest ogólna dla procesu i wszystkich wątków wewnątrz, przy użyciu do alokacji pamięci w zwykłym przypadku z czymś takim jak malloc () .

Stos to szybka pamięć do przechowywania wskaźników i zmiennych zwracanych w typowym przypadku, przetwarzanych jako parametry w wywołaniu funkcji, lokalne zmienne funkcyjne.

Maxim Akristiniy
źródło
23

Ponieważ niektóre odpowiedzi poszły w dupę, mam zamiar przyczynić się do mojego roztocza.

Zaskakujące, nikt nie wspomniał, że wiele (tzn. Niezwiązanych z liczbą uruchomionych wątków na poziomie systemu operacyjnego) stosów wywołań można znaleźć nie tylko w językach egzotycznych (PostScript) lub platformach (Intel Itanium), ale także we włóknach , zielonych wątkach i niektóre implementacje coroutines .

Włókna, zielone nici i kortyny są pod wieloma względami podobne, co prowadzi do dużego zamieszania. Różnica między włóknami a zielonymi nitkami polega na tym, że te pierwsze wykorzystują wielozadaniowość kooperacyjną, podczas gdy te drugie mogą cechować się kooperatywnym lub zapobiegawczym (lub nawet jednym i drugim). Aby zobaczyć różnicę między włóknami i rogówkami, zobacz tutaj .

W każdym razie celem zarówno włókien, zielonych nici, jak i koronek jest jednoczesne wykonywanie wielu funkcji, ale nie równolegle (patrz rozróżnienie w tym pytaniu SO ) w ramach jednego wątku na poziomie systemu operacyjnego, przenosząc kontrolę między sobą w zorganizowany sposób.

Kiedy używasz włókien, zielonych nici lub coroutines, zwykle masz oddzielny stos dla każdej funkcji. (Technicznie nie jest to tylko stos, ale cały kontekst wykonania jest zależny od funkcji. Co najważniejsze, rejestruje procesor.) Dla każdego wątku jest tyle stosów, ile jest jednocześnie uruchomionych funkcji, a wątek przełącza się między wykonaniem każdej funkcji zgodnie z logiką twojego programu. Gdy funkcja dobiega końca, stos jest niszczony. Tak więc liczba i czas życia stosów jest dynamiczna i nie zależy od liczby wątków na poziomie systemu operacyjnego!

Zauważ, że powiedziałem: „ zwykle mają osobny stos dla każdej funkcji”. Istnieją zarówno stosy, jak i stosy implementacji kurtyn. Najbardziej zauważalną stackful C ++ implementacje są Boost.Coroutine i Microsoft PPL s” async/await. (Jednak funkcje C ++ do wznowienia (aka " asynciawait "), które zostały zaproponowane do C ++ 17, prawdopodobnie współprogram użycie Stackless).

Wkrótce pojawi się propozycja Fibers do standardowej biblioteki C ++. Są też biblioteki stron trzecich . Zielone wątki są niezwykle popularne w językach takich jak Python i Ruby.

Shakurov
źródło
19

Mam coś do podzielenia się, chociaż najważniejsze kwestie zostały już omówione.

Stos

  • Bardzo szybki dostęp.
  • Przechowywane w pamięci RAM.
  • Wczytywane są tutaj wywołania funkcji wraz z przekazywanymi zmiennymi lokalnymi i parametrami funkcji.
  • Miejsce jest zwalniane automatycznie, gdy program wykracza poza zakres.
  • Przechowywane w pamięci sekwencyjnej.

Sterta

  • Powolny dostęp w porównaniu do stosu.
  • Przechowywane w pamięci RAM.
  • Tutaj przechowywane są dynamicznie tworzone zmienne, które później wymagają zwolnienia przydzielonej pamięci po użyciu.
  • Przechowywane wszędzie tam, gdzie dokonywana jest alokacja pamięci, zawsze dostępne za pomocą wskaźnika.

Ciekawa uwaga:

  • Gdyby wywołania funkcji były przechowywane w stercie, spowodowałyby 2 nieporządne punkty:
    1. Ze względu na sekwencyjne przechowywanie w stosie wykonywanie jest szybsze. Przechowywanie w stosie spowodowałoby ogromne zużycie czasu, dzięki czemu cały program działałby wolniej.
    2. Gdyby funkcje były przechowywane na stercie (bałagan w pamięci wskazywany przez wskaźnik), nie byłoby sposobu powrotu do adresu dzwoniącego z powrotem (który stos daje z powodu sekwencyjnego przechowywania w pamięci).
Pankaj Kumar Thapa
źródło
1
zwięzłe i czyste. miło :)
ingconti
13

Łał! Tak wiele odpowiedzi i nie sądzę, żeby jedna z nich dobrze zrozumiała ...

1) Gdzie i czym one są (fizycznie w pamięci prawdziwego komputera)?

Stos to pamięć, która zaczyna się jako najwyższy adres pamięci przydzielony obrazowi programu, a następnie maleje od tego momentu. Jest zarezerwowany dla wywoływanych parametrów funkcji i dla wszystkich zmiennych tymczasowych używanych w funkcjach.

Istnieją dwa hałdy: publiczny i prywatny.

Prywatna sterta zaczyna się od 16-bajtowej granicy (dla programów 64-bitowych) lub 8-bajtowej granicy (dla programów 32-bitowych) po ostatnim bajcie kodu w programie, a następnie zwiększa wartość od tego miejsca. Jest również nazywany stertą domyślną.

Jeśli stos prywatny staje się zbyt duży, nakłada się na obszar stosu, podobnie jak stos nakłada się na stos, jeśli staje się zbyt duży. Ponieważ stos zaczyna się od wyższego adresu i działa w dół na niższy adres, przy odpowiednim włamaniu można uzyskać tak duży stos, że będzie on przekraczał prywatny obszar sterty i nakładał się na obszar kodu. Sztuczka polega zatem na nałożeniu wystarczającej części obszaru kodu, aby można było podpiąć się do kodu. Jest to trochę trudne i ryzykujesz awarię programu, ale jest to łatwe i bardzo skuteczne.

Sterty publiczne znajdują się we własnej przestrzeni pamięci poza obszarem obrazu programu. To pamięć zostanie zassana na dysk twardy, jeśli zasoby pamięci będą ograniczone.

2) W jakim stopniu są kontrolowane przez system operacyjny lub środowisko uruchomieniowe?

Stos jest kontrolowany przez programistę, sterta prywatna jest zarządzana przez system operacyjny, a sterta publiczna nie jest kontrolowana przez nikogo, ponieważ jest to usługa systemu operacyjnego - wysyłasz żądania i albo są one przyjmowane, albo odrzucane.

2b) Jaki jest ich zakres?

Wszystkie są globalne dla programu, ale ich zawartość może być prywatna, publiczna lub globalna.

2c) Co decyduje o wielkości każdego z nich?

Rozmiar stosu i stosu prywatnego są określane przez opcje środowiska wykonawczego kompilatora. Sterta publiczna jest inicjowana w czasie wykonywania przy użyciu parametru rozmiaru.

2d) Co przyspiesza?

Nie są zaprojektowane tak, aby były szybkie, ale są użyteczne. Sposób, w jaki programista je wykorzystuje, określa, czy są one „szybkie” czy „wolne”

REF:

https://norasandler.com/2019/02/18/Write-a-Compiler-10.html

https://docs.microsoft.com/en-us/windows/desktop/api/heapapi/nf-heapapi-getprocessheap

https://docs.microsoft.com/en-us/windows/desktop/api/heapapi/nf-heapapi-heapcreate

ar18
źródło
8

Wiele odpowiedzi jest poprawnych jako koncepcje, ale musimy zauważyć, że sprzęt jest potrzebny stos (tj. Mikroprocesor), aby umożliwić wywoływanie podprogramów (CALL w języku asemblera ...). (Chłopaki OOP nazywają to metodami )

Na stosie zapisujesz adresy zwrotne i dzwonisz → push / ret → pop jest zarządzany bezpośrednio sprzętowo.

Możesz użyć stosu do przekazania parametrów ... nawet jeśli jest on wolniejszy niż przy użyciu rejestrów (powiedziałby guru z mikroprocesora lub dobra książka BIOS z lat 80. XX wieku ...)

  • Bez stosu nr mikroprocesor może działać. (nie możemy sobie wyobrazić programu, nawet w języku asemblera, bez podprogramów / funkcji)
  • Bez stosu może. (Program języka asemblerowego może działać bez, ponieważ sterta jest koncepcją systemu operacyjnego, tak jak malloc, czyli wywołanie OS / Lib.

Użycie stosu jest szybsze, ponieważ:

  • Jest sprzętem, a nawet push / pop są bardzo wydajne.
  • malloc wymaga przejścia w tryb jądra, użycia blokady / semafora (lub innych operacji podstawowych synchronizacji), wykonania kodu i zarządzania niektórymi strukturami potrzebnymi do śledzenia alokacji.
ingconti
źródło
Co to jest OPP? Masz na myśli OOP (programowanie obiektowe )?
Peter Mortensen
Czy chcesz powiedzieć, że mallocjest to wywołanie jądra?
Peter Mortensen
1) tak, przepraszam .. OOP ... 2) malloc: Piszę krótko, przepraszam ... malloc jest w przestrzeni użytkownika .. ale może wywoływać inne połączenia .... chodzi o to, że korzystanie ze sterty MOŻE być bardzo wolne ...
ingconti
Wiele odpowiedzi jest poprawnych jako koncepcje, ale musimy zauważyć, że sprzęt jest potrzebny stos (tj. Mikroprocesor), aby umożliwić wywoływanie podprogramów (CALL w asemblerze…) ”. Mylisz stos procesora (jeśli taki był we współczesnym procesorze) i stosy języka wykonawczego (jeden na wątek). Gdy programiści mówią o stosie, jest to stos wykonawczy wątków środowiska wykonawczego, np. Stos wątków NET), nie mówimy o stosie procesora.
min
1

Stos jest zasadniczo łatwo dostępną pamięcią, która po prostu zarządza swoimi przedmiotami jako - dobrze - stos. Tylko przedmioty, dla których znany jest rozmiar, mogą zostać umieszczone na stosie . Dotyczy to liczb, ciągów znaków, boolanów.

Sterty jest pamięć przedmiotów z których nie można przesądza dokładny rozmiar i strukturę . Ponieważ obiekty i tablice można mutować i zmieniać w czasie wykonywania, muszą one wejść na stos.

Źródło: Academind

NattyC
źródło
0

Dziękuję za naprawdę dobrą dyskusję, ale jako prawdziwy noob zastanawiam się, gdzie przechowywane są instrukcje? W POCZĄTKU naukowcy decydowali między dwiema architekturami (von NEUMANN, gdzie wszystko uważa się za DANE, i HARVARD, gdzie obszar pamięci był zarezerwowany na instrukcje, a drugi na dane). Ostatecznie zdecydowaliśmy się na projekt von Neumanna i teraz wszystko jest uważane za „takie samo”. Utrudniało mi to, kiedy uczyłem się montażu https://www.cs.virginia.edu/~evans/cs216/guides/x86.html ponieważ mówią o rejestrach i wskaźnikach stosu.

Wszystko powyżej mówi o danych. Domyślam się, że ponieważ instrukcja jest zdefiniowaną rzeczą o konkretnym rozmiarze pamięci, trafiłaby na stos, a więc wszystkie rejestry omówione w asemblerze znajdują się na stosie. Oczywiście pojawiło się programowanie obiektowe z instrukcjami i danymi wchodzącymi w strukturę, która była dynamiczna, więc teraz instrukcje będą również przechowywane na stosie?

aquagremlin
źródło