Twój komputer ma więcej niż tylko pamięć o dostępie swobodnym (RAM). To chaotyczny, pofragmentowany i ciągle zmieniający się krajobraz pamięci, który procesor udaje, że jest nieskończony. Taka jest rzeczywistość dynamicznych struktur danych działających na nowoczesnym sprzęcie.
Typowa stacja robocza ma obecnie 16–64 megabajty fizycznej pamięci RAM. Ale nie dajcie się zwieść tym małym liczbom. Dzięki technologii zwanej pamięcią wirtualną system wymienia dane pomiędzy tą pamięcią RAM a dyskiem twardym. Procesor widzi iluzję. Wydaje mu się, że ma 200-500 megabajtów ciągłej przestrzeni. Ta iluzja działa. Kod jest wykonywany. Kiedy jednak system operacyjny musi uzyskać dostęp do dysku twardego, aby załadować stronę pamięci, wszystko zwalnia. Czujesz to w postaci opóźnień. Odczuwa się to po wzroście prędkości wentylatora. Pomimo spadku wydajności, pamięć wirtualna jest niedrogim sposobem na „zwiększenie” pojemności pamięci RAM. Jest to niezbędny środek kompromisowy.
Powiedzmy, że mamy pustą kartę. Całkowita pojemność pamięci wynosi 50 megabajtów. Więcej nie. Nie mniej. To jest nasz budżet.
System operacyjny jest właścicielem tego 50-megabajtowego bloku. Ona dzieli się tym ciastem. Nierówno. Nigdy równomiernie.
Najpierw przychodzi kod. Wykonywalne instrukcje dla wszystkich uruchomionych aplikacji, a także jądra samego systemu operacyjnego. Ta sekcja jest statyczna. Nie zmienia się w trakcie działania programu. Następnie przychodzą zmienne globalne. Są to stałe ogólne i flagi stanu, do których można uzyskać dostęp z dowolnej części aplikacji. Znajdują się one w pamięci od momentu uruchomienia aplikacji aż do jej zakończenia.
Następny jest stos.
Stos ma sztywną konstrukcję. Rośnie i kurczy się synchronicznie z wywołaniami funkcji. Kiedy wywołujesz funkcję, jej zmienne lokalne i parametry są wypychane na stos. Po zakończeniu funkcji są one usuwane ze stosu. Stos pamięta kolejność wywołań. Daje pewność, że wrócisz we właściwe miejsce. Ale ma maksymalny rozmiar. Nie można poprosić stosu o przydzielenie większej ilości pamięci podczas wykonywania. Jeśli spróbujesz to zrobić, nastąpi przepełnienie stosu. Program ulegnie awarii.
Kiedy program kończy działanie, system operacyjny go rozładowuje. Kod, zmienne globalne, miejsce na stosie – wszystko to zostaje usunięte. Ta pamięć jest przetwarzana. Jest gotowa na następny program.
Ale tu jest problem. W dowolnym momencie około 50 procent tej 50-megabajtowej przestrzeni może być niewykorzystane. Dlaczego? Ponieważ stos zawiera tylko to, co jest aktualnie wykonywane. Kod zawiera jedynie instrukcje. Nieprzetworzone fragmenty pamięci są rozproszone. To są dziury.
System operacyjny zbiera te dziury razem. Nazywa tę pulę stertą.
W tym miejscu następuje dynamiczna alokacja pamięci. Sterta to jedyne miejsce w pamięci, w którym program może zażądać dokładnej ilości miejsca dokładnie w tym momencie, w którym jest potrzebna. W czasie kompilacji nie deklarujesz tablicy zawierającej 1000 liczb całkowitych. Nie wiesz, czy będziesz potrzebować 1000 czy 100 000 elementów. czekasz. Uruchamiasz kod. Ty decydujesz, że potrzebujesz tej przestrzeni. Następnie wywołujesz „malloc”.
„malloc” oznacza alokację pamięci. Pobiera blok ze sterty. Zwraca wskaźnik. Używasz tego wskaźnika. Kiedy skończysz, zadzwonisz „za darmo”. Blok wraca do puli.
Na tym polega podstawowa różnica między pamięcią statyczną a dynamiczną. Stos jest automatyczny. Jest ograniczony zakresem. Stos jest ręczny. Jest to powiązane z intencją.
Dlaczego ma to dla Ciebie znaczenie? Ponieważ większość błędów w złożonym oprogramowaniu nie jest spowodowana złą logiką. Występują z powodu złego zarządzania pamięcią. Jeśli przydzielisz pamięć na stercie i zapomnisz ją zwolnić, nastąpi wyciek pamięci. Dostępny rozmiar sterty zmniejsza się. W końcu w systemie zabraknie miejsca. Programy zawieszają się. System operacyjny wymusza zakończenie procesów. Tracisz niezapisane dane.
I odwrotnie, jeśli spróbujesz przydzielić zbyt dużo pamięci na stosie, przekroczysz limit stosu. Program ulega awarii.
Sterta zapewnia elastyczność. Pozwala tworzyć struktury danych, które mogą się rozwijać. Połączone listy. Drzewa. Wykresy. Żadnej z tych struktur nie można określić w czasie kompilacji przy stałym rozmiarze. Muszą być tworzone na bieżąco. Muszą żyć w kupie.
Czy sterta jest idealna? Nie. Jest fragmentaryczne. W miarę przydzielania i uwalniania bloków o różnych rozmiarach stos staje się łamigłówką z brakującymi elementami. Wyszukiwanie ciągłego bloku wolnej pamięci może być powolne. Dlatego też „malloc” może czasami zająć zauważalną ilość czasu. Musi szukać. Musi poskładać elementy w całość. Musi ogarnąć ten chaos.
Ale bez sterty współczesne komputery ulegną upadkowi.
