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

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:

[code]http://rudy.mif.pg.gda.pl/~bogdro/dos/a_kurs02.htm[/code]
I'm back !
Anarki
user
Avatar użytkownika
Posty: 451
Dołączył(a): Pn lut 19, 2007 4:04
Podziękował: 4 razy
Podziękowano: 2 razy
Reputacja: 1993

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

PostCz wrz 06, 2007 0:31

[quote="mientos"]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: 501
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: 2451

PostCz wrz 06, 2007 8:31

[quote]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: 3143

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 ;>

[size=75][ Dodano: Czw Wrz 06, 2007 12:02 ][/size]
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 ;>

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

[code]
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
[/code]
[color=#0080FF]gynvael.coldwind[/color]//[color=#00FF00]vx[/color]
http://gynvael.coldwind.pl
Gynvael Coldwind
Przyjaciel
Avatar użytkownika
Posty: 1633
Dołączył(a): N lip 25, 2004 17:08
Podziękował: 53 razy
Podziękowano: 184 razy
Reputacja: 23041

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

Powrót do Programowanie

Kto przegląda forum

Użytkownicy przeglądający ten dział: Exabot [Bot] i 1 gość