Stos i sterta

Wszystko dla programistów. C++, Delphi, Java, PHP, SQL

Stos i sterta

PostŚr wrz 05, 2007 19:43

Nie moge zrozumiec po co jest stos i sterta, czym one się roznia i czy nie wystarczylby sam stos lub sterta? Na google znalazlem tylko co to sa stos i sterta, ale i tak za bardzo tego nie rozumiem. Bylbym bardzo wdzieczny za odpowiedz, zawsze wszystko zwiazane z pamiecia bylo dla mnie najtrudniejsze do zrozumienia :(.
mientos
user
Avatar użytkownika
Posty: 263
Dołączył(a): So sie 04, 2007 12:24
Lokalizacja: Legnica
Podziękował: 0 razy
Podziękowano: 0 razy
Reputacja: 1193

Spokojnie - to tylko reklama - zniknie po zalogowaniu :)

Pani Reklama
Automat
Posty:
Dołączył(a): ab aeterno
Lokalizacja: UW-Zaloga

PostŚr wrz 05, 2007 19:46

Moze nie dotyczy C++, ale mysle ze pomoze:

Kod: Zaznacz cały
http://rudy.mif.pg.gda.pl/~bogdro/dos/a_kurs02.htm
Szukam pomocy w tym temacie.
Anarki
user
Avatar użytkownika
Posty: 441
Dołączył(a): Pn lut 19, 2007 4:04
Lokalizacja: Stany Psychodelicznie Zjednoczone
Podziękował: 1 razy
Podziękowano: 0 razy
Reputacja: 1592

PostŚr wrz 05, 2007 20:02

No dalej nie moge tego zrozumiec :( nie wiem czemu tak mam ale ciagle mam z tym problemy ze nie moge zrozumiec. Nie mozna tego po prostu wytlumaczyc po co stos i sterta, nie wystarczylaby sama sterta? I gdzie wogole jest stos a gdzie sterta, bo tego tez nie wiem(chodzi o to czy w np. RAMach). I po co tworzyc zmienne dynamicznie jesli mozna statycznie i ten sam efekt.

Tego nie moge zrozumiec, a z tego co wyszukalem na google to jest jakos napisane ze nie moge zrozumiec, a z tego linku co podales to tez za bardzo nie rozumiem, a jesli chodzi o assembler to tylko nazwe znam, a o nim samym to pojecia nie mam.
mientos
user
Avatar użytkownika
Posty: 263
Dołączył(a): So sie 04, 2007 12:24
Lokalizacja: Legnica
Podziękował: 0 razy
Podziękowano: 0 razy
Reputacja: 1193

PostCz wrz 06, 2007 0:31

mientos napisał(a):I po co tworzyc zmienne dynamicznie jesli mozna statycznie i ten sam efekt.
Przede wszystkim dla wygody i czytelności, sekcje gdzie deklarujesz zmienne statyczne (lepszym przykładem będzie pascal niż C) zapełniasz tym co potrzeba w całym kodzie ale jeżeli w jednej pętli która pojawi się nagle (nie uwzględniłeś jej przy projektowaniu) nie możesz użyć żadnej z istniejących już zmiennych (np. pętla jest zagnieżdżona w innej już pętli i nie masz zmiennej indeksującej) to deklarujesz prostą zmienną dynamiczną, która potem zostaje zwolniona i już nie przeszkadza.
Dlaczego?
NeooeN
user
 
Posty: 499
Dołączył(a): Pt maja 27, 2005 19:26
Lokalizacja: Północne południe troche bardziej na wschodni zachód
Podziękował: 4 razy
Podziękowano: 4 razy
Reputacja: 2274

PostCz wrz 06, 2007 8:31

I po co tworzyc zmienne dynamicznie jesli mozna statycznie i ten sam efekt.

Dynamicznie mozesz tworzyc podczas pracy programu... Jeśli potrzebne Ci mniej miejsca to alokujesz miejsce na tyle co CI potrzeba ...
Jeśli np. pobierasz dane z standardowego wejscia to mozesz sprawdzic jaka dlugosc ma okreslony string i utworzyc odpowiednia ilosc miejsca dla tego, mozesz takze zwiekszac ilosc zarezerwowanego miejsca itd ...
A statycznie to jak statycznie .... masz to co masz i kropka ...
Statycznie tez nie mozesz zrobić np. takiej struktury jak lista jedno lub dwu kierunkowa( tzn mozesz, ale nie bedziesz mogl dodawac itd. ) ...
Dobra mysle ze chyba dość jasno to wytłumaczyłęm
JacuS
user
Avatar użytkownika
Posty: 1089
Dołączył(a): Cz maja 17, 2007 21:20
Lokalizacja: Ostrołęka/Warszawa
Podziękował: 0 razy
Podziękowano: 1 razy
Reputacja: 2965

PostCz wrz 06, 2007 10:38

Dobra, to podsumuje to co ludzie wyżej napisali i dorzucę coś od siebie ;>

(to co piszę dotyczy trybu chronionego, czyli tego na którym obecne systemy operacyjne pracują)

Więc tak, mamy pamięć wirtualną, która zazwyczaj korzysta z pamięci RAM (a jak zabraknie RAMu to też i z dysku twardego). Czyli pamięci wirtualnej mamy tyle ile RAMu lub więcej, w zależności od potrzeb.

I teraz pamięć wirtualną procesu (uruchomionego programu) można logicznie podzielić na kilka innych pamięci. I teraz żeby to było jasne. Ten podział jest tylko i wyłącznie logiczny, to znaczy że niezależnie od tego czy jest to stos, sterta, czy pamięć tzw statycznie zaalokowana, to to i tak leży w tej samej pamięci wirtualnej. Po prostu podział logiczny wynika z różnego stosowania różnych fragmentów tej samej pamięci wirtualnej.

OK, i teraz tak. Zacznijmy od pamięci statycznie zaalokowanej.
Dla programisty C/C++ są to wszystkie zmienne globalne oraz zmienne statyczne - czyli tzw dane. Dodatkowo, pamięć w której przechowywany jest binarny kod wykonywalny programu również jest statycznie zaalokowana, i to zazwyczaj gdzieś w okolicy danych ;>
Pamięć statyczna jest alokowana w momencie uruchomienia procesu (potem niby można doalokować jeszcze, ale nie mieszajmy).
Pamięć statyczna charakteryzuje się tym że zawsze jest alokowana w tym samym miejscu (powiedzmy pod Windowsem takim defaultowym adresem początku pamięci statycznej jest 0x400000 lub 0x10000000). Od tego "zawsze" są wyjątki, ale nie mieszajmy ;>
Skąd system operacyjny wie gdzie i ile pamięci zaalokować ? W pliku wykonywalnym (np PE .exe) jest to zapisane (jeśli by ktoś chciał wgłębić to pola ImageBase i SizeOfImage w Optional Header, oraz nagłówki poszczególnych sekcji).
Jako że pamięć statyczna jest zawsze w tym samym miejscu, to w kodzie assemblera odwołania do danych z tej pamięci korzystają ze stałych adresów, np:
MOV EAX, [0x404012] (czyli przenieś do EAX int'a z adresu 0x404012)

Jeśli chodzi o stos, to jest on alokowany w momencie tworzenia wątku (przykładowo główny wątek procesu jest tworzony w momencie uruchomienia procesu).
Stos np na Viscie dla głównego wątku ma adres około 0x27E000 i wielkość 0x2000 w momencie tworzenia. Dla każdego nowego wątku (threada) tworzony jest nowy oddzielny stos.
I teraz tak, ze stosem jest bezpośrednio związanych kilka instrukcji procesora:
PUSH XXX - umieść XXX na stosie
POP XXX - zdejmij wartość ze stosu i umieść w XXX
CALL XXX - skocz na adres XXX po czym powróć, adres powrotu zapisz na stosie
RET - powróć do adresu zapisanego na stosie
(jeszcze kilka innych, PUSHA, POPA, PUSHF, POPF, LEAVE, ENTER, etc)
Dodatkowo, ze stosem związany jest rejestr procesora ESP (Stack Pointer) który pokazuje ostatni umieszczony na stosie element.
Można go używać do adresowania innych elementów na stosie, np ESP+4 to poprzedni wrzucony na stos element, etc.
I teraz kilka informacji:
- stos należy traktować jako tablicę zmiennych 32 bitowych (na prockach 32 bitowych), np int stos[1024]
- pierwszy element jest wrzucony na koniec stosu, czyli na poczatku ESP = &stos[1024] (przy czym w momencie wrzucenia jest robione stos[--ESP] = cos)
- na niektorych systemach (np winda) w momencie gdy stos sie skonczy, to alokowana jest dodatkowa pamiec na stos.. jest jakies gorne ograniczenie, ale nie pamietam wiec klamac nie bede... (w trybie jadra pod winda stos ma ograniczenie do kilku/kilkunastu kilobajtow ;p, natomiast w trybie uzytkownika do kilku mega o ile sie nie myle)
I teraz tak. Stos jest często używany. W związku z czym część stosu jest na pewno trzymana w L1/L2 procesora (cache'u), dzięki czemu działa bardzo szybko, czyli zmienne lokalne w tym wypadku mogą być szybsze niż zmienne globalne.
I tak, zmienne lokalne alokowane są właśnie na stosie. Taka alokacja jest bardzo szybka, po prostu przesuwa się ESP (odejmuje interesującą nas ilość bajtów od ESP, np ESP-=16 to alokacja 16 bajtów na stosie). To jest tylko i wyłącznie alokacja logiczna, jako że pamięć stosu i tak istnieje cały czas ;>
Na stosie program przechowuje:
- zmienne lokalne
- parametry funkcji
- adresy powrotu w momencie wywolania innych funkcji
- inne zapasowe rzeczy
Do stosu kod assemblera odwołuje się poprzez rejestr ESP adresowaniem pośrednim (lub czasami EBP jeśli wartosc ESP została do EBP kiedyś zapisana)
np. MOV EAX, [ESP+4] --- wrzuć do EAX inta spod adresu ESP+4 (czyli przedostatni element wrzucony na stos)
(każdy element na stosie ma dokładnie 4ry bajty, a jeśli miał by nie mieć to jest dopełniany zerami... dodatkowo większe elementy można tworzyć z kilku elementów stosu, np long long zajmuje 2 elementy na stosie, ofc to i tak jest normalna pamięć, więc podział na elementy jest logiczny a nie fizyczny)

OK, I ostatnia rzecz, czyli sterta (heap).
Sterta to również fragment pamięci, zaalokowanej zazwyczaj w momencie uruchomienia, z tym że często kolejna pamięć jest doalokowywana. Tak na prawdę sterta dzieli się zazwyczaj na dwie części:
- pierwsza - prealokowana - np w momecie uruchomienia procesu jest alokowane 16kb - i z tej części przydzielana jest pamięć dla małych alokacji, np malloc(sizeof(int)), etc
- druga - która alokowana jest dopiero w momencie żądania alokacji i która jest używana gdy user chce zaalokować np 16mb pamięci (malloc(16*1024*1024)) - wtedy funkcje operujące stertą proszą system o 16mb i zwracają jej adres użytkownikowi
W pierwszym przypadku w tej pamięci oprócz danych użytkownika, znajduje się również struktura opisująca gdzie są poszczególne fragmenty sterty, które są wolne etc (zazwyczaj to jakaś lista list albo lista stert, albo lista drzew, takie cosie). W drugim przypadku zazwyczaj znajdzie się tam jakaś mała strukturka która mówi co to za pamięć i ile jej jest.
I teraz tak, o ile stosem na dobrą sprawę zarządzał bezpośrednio procesor (ESP, PUSH, etc, to bezpośrednie instrukcje procesora), to sterta jest wytworem systemu operacyjnego, i to system operacyjny LUB/ORAZ biblioteki run-time danego języka nią zarządzają. W przypadku systemu Windows są to takie funkcje jak HeapAlloc czy HeapFree, po za tym malloc, new, etc. To wszystko są dość skomplikowane funkcje które muszą zadecydować czy mogą jakąś prealokowaną pamięć przydzielić userowi, czy może muszą zaalokować pamięć dedykowaną dla większej ilości danych, czy może im się pamięć kończy i muszą doalokować. W związku z czym alokacja na stercie nie należy do szybkich.
Do pamięci na stercie w assemblerze odwołujemy się za pomocą zapamiętanych wcześniej adresów, czyli np:
PUSH 1024
CALL malloc ; wywołaj malloc(1024), czyli zaalokuj 1024 bajty na stercie
MOV [ESP+8], EAX ; zapisz adres pamięci na stercie do zmiennej lokalnej na stosie
...
MOV EDX, [ESP+8]; wrzuć do rejestru EDX zapamiętany adres sterty
MOV EAX, [EDX] ; przenieś do EAX inta ze pamięci na stercie

Jeśli chodzi o różnicę:
- pamięć statyczna jest alokowana RAZ - przy uruchomieniu procesu. Dostęp do niej jest równie szybki jak do pamięci na stercie, ale może być odrobinę wolniejszy (to zależy od kilku czynników) niż do zmiennych lokalnych na stosie. Pamięci statycznej jest STAŁA ilość, jest jej dokładnie tyle ile kompilator wywnioskował z kodu programu że będzie potrzebne (dla dociekliwych: z wyrównaniem do strony oczywiście)... standardowo pamięć statyczna przeznaczana jest dla zmiennych GLOBALNYCH oraz STATYCZNYCH (przedrostek static w c/c++)
- stos jest alokowany w momencie tworzenia WĄTKU i jest oddzielny dla każdego wątku (tzn ESP każdego wątku chodzi po własnym stosie)... stos ma górne ograniczenie, więc alokuje się na nim MAŁE ILOŚCI danych, takie jak ZMIENNE LOKALNE, czy ARGUMENTY FUNKCJI (proszę zauważyć że argumenty funkcji mają również swój fragment pamięci, więc można je traktować jak zmienne lokalne na dobrą sprawę)... każde wejście i wyjście z funkcji to alokacja i dealokacja danych na stosie, która jest zasadniczo bardzo szybka (proste dodawanie i odejmowanie)
- sterta jest tworzona na początku procesu, ale jej wielkość zmienia się w zależności od potrzeb... ograniczenie wielkości sterty wynika jedynie z ograniczenia ilości RAMu lub przestrzeni adresowej (np na 32-bitowym windowsie proces usera przy standardowych ustawieniach może używać max 2GB pamięci na raz, lub 3GB przy przeniesieniu systemu w górne partie pamięci)... Alokacja pamięci na stercie jest WOLNIEJSZA niż alokacja na stosie, ale i można z niej korzystać bardziej dowolnie (w sensie malloc i już mamy pamięć która będzie istnieć do momentu jej uwolnienia bądź zakończenia procesu).

Mniej więcej tak to wygląda ;>
Jak coś to pytaj ;>

[ Dodano: Czw Wrz 06, 2007 12:02 ]
Ps, dodam jeszcze że czasami zdarzają się i inne rodzaje pamięci, takie jak np TLS (Thread Local Storage).
Dodatkowo, proces może mieć kilka stert, kilka stosów, i kilka pamięci statycznych (np. .exe i do tego pamiec statyczna dla kernel32.dll i ntdll.dll)
Nyo ;>

[ Dodano: Czw Wrz 06, 2007 12:08 ]
ps. 2. dorzucę jeszcze mapę pamięci dla hello world pod windą ;>

Kod: Zaznacz cały
Address    Size       Owner      Section    Contains      Type
00010000   00010000                                       Map
00079000   00007000                                       Priv
0027D000   00001000                                       Priv
0027E000   00002000                         stack of mai  Priv - Stos głównego wątku
00280000   00004000                                       Map  - Jakiś zmapowany plik
002C0000   00004000                                       Priv
00400000   00001000   hello                 PE header     Imag \
00401000   00001000   hello      .text      code          Imag |
00402000   00001000   hello      .data      data          Imag |
00403000   00001000   hello      .rdata                   Imag  > Pamięć statyczna hello.exe
00404000   00001000   hello      .bss                     Imag |
00405000   00001000   hello      .idata     imports       Imag /
00430000   00007000                                       Priv
00530000   0037E000                                       Map  - Jakiś zmapowany plik
00990000   00003000                                       Priv - Sterta procesu
75530000   0004A000                                       Imag
75630000   00009000                                       Imag
75640000   00045000                                       Imag
75CA0000   00001000   kernel32              PE header     Imag \
75CB0000   000C1000   kernel32   .text      code,imports  Imag |
75D80000   00003000   kernel32   .data      data          Imag  > Pamięć statyczna kernel32.dll
75D90000   00001000   kernel32   .rsrc      resources     Imag |
75DA0000   0000A000   kernel32   .reloc     relocations   Imag /
76400000   00001000   msvcrt                PE header     Imag \
76401000   0009D000   msvcrt     .text      code,imports  Imag |
7649E000   00007000   msvcrt     .data      data          Imag  > Pamięć statyczna msvcrl.dll
764A5000   00001000   msvcrt     .rsrc      resources     Imag |
764A6000   00004000   msvcrt     .reloc     relocations   Imag /
77300000   0017A000                                       Imag
774B0000   00001000   ntdll                 PE header     Imag \
774C0000   000C0000   ntdll      .text      code,exports  Imag |
77580000   00001000   ntdll      RT                       Imag |
77590000   0000B000   ntdll      .data      data          Imag  > Pamięć statyczna ntdll.dll
775A0000   00049000   ntdll      .rsrc      resources     Imag |
775F0000   00005000   ntdll      .reloc     relocations   Imag /
7EFB0000   00023000                                       Map
7EFDB000   00002000                                       Priv
7EFDD000   00001000                         data block o  Priv - Tzw data block głównego wątku
7EFDE000   00001000                                       Priv
7EFDF000   00001000                                       Priv
7EFE0000   00006000                                       Map
7FFE0000   00001000                                       Priv
gynvael.coldwind//vx
http://gynvael.coldwind.pl
Gynvael Coldwind
Przyjaciel
Avatar użytkownika
Posty: 1631
Dołączył(a): N lip 25, 2004 17:08
Podziękował: 53 razy
Podziękowano: 179 razy
Reputacja: 22358

PostCz wrz 06, 2007 15:41

Ok Wielkie Dzieki za wysilek i napisanie takiego duzego tekstu :P. Juz bardziej rozumiem ta pamiec(teraz na tyle mi wystarczy :D), moze z wiekiem juz zrozumiem to calkiem, jak zrozumialem c++ dopiero na te wakacje(1 - 2 klasa gimnazjum).

PS.
Nie wiem czy dac wam wszystkim pochwaly, ale Gynvael'owi napewno sie nalezy.
mientos
user
Avatar użytkownika
Posty: 263
Dołączył(a): So sie 04, 2007 12:24
Lokalizacja: Legnica
Podziękował: 0 razy
Podziękowano: 0 razy
Reputacja: 1193

Powrót do Programowanie

Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość