Co i gdzie są stosy i sterty?

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?

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}

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;

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).

  

  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.

  

  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.

(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.

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.

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ą.

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ą

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.

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.

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

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.
}

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.

Co to jest stos?

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

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.

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

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.

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.

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.

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.

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.

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.

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 ()

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ć:

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.

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).

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 .

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.

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

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

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.

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.

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).

Ł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

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.

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

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?