Podstawy programowania 7

Dynamiczna alokacja pamięci

Pamięć w komputerze o architekturze x86/x86-64 zorganizowana jest w postaci ponumerowanego kolejno ciągu bajtów. Chociaż obsługa sprzętu nie jest wcale taka prosta, to system operacyjny udostępnia procesom tzw. pamięć wirtualną (ang. virtual memory), która ukrywa przed programistą szczegóły implementacji pamięci sprzętowej. Działającemu programowi wydaje się, że cała pamięć jest pusta i do jego dyspozycji.

Pamięć wirtualna przydzielana jest w postaci dwóch odrębnych zasobów – stosu i sterty (ang. stack i heap).

Stos

Stos jest podstawową strukturą danych w dzisiejszych komputerach. Umożliwia on łatwe wywoływanie funkcji – także rekurencyjne jeśli trzeba – oraz zwracanie z nich wartości.

Stos można sobie wyobrażać jako stos talerzy – dostęp mamy tylko do talerzy znajdujących się na szczycie (czy blisko szczytu).

Wywołanie funkcji wygląda następująco:
  • argumenty wywoływanej funkcji są wkładane na stos – na szczyt stosu kopiowane są dane i przesuwany jest tzw. wskaźnik stosu, który wskazuje na jego szczyt;
  • wywołana funkcja wie, gdzie szukać swoich argumentów, gdy ma dany wskaźnik stosu (dzięki temu funkcja nie musi nic wiedzieć o wywołującym ją kodzie – jedyne co ją interesuje to wskaźnik stosu i parametry znajdujące się na szczycie stosu);
  • wywoływana funkcja może robić ze stosem co jej się podoba, dopóki nie zmienia nic poniżej wskaźnika stosu (w szczególności wszystkie zmienne lokalne wywoływanej funkcji są tworzone na stosie, powyżej wskaźnika stosu);
  • w momencie gdy funkcja kończy działanie, to zwracana wartość jest zostawiana na szczycie stosu, wskaźnik stosu zostaje przywrócony do poprzedniej wartości i sterowanie powraca do funkcji wywołującej.

Jak się chwilę zastanowić, to taki mechanizm wywołania ma jedną bardzo istotną wadę – funkcja nie może na stosie stworzyć żadnego obiektu/zmiennej i zwrócić go do kodu wywołującego (np. wskaźnikiem). Wszystkie obiekty na stosie przestają istnieć w momencie gdy kończy działanie funkcja, która je stworzyła (oczywiście pamięć po takich obiektach nie jest od razu czyszczona, ale w każdym momencie może być nadpisana).

Sterta

Sterta jest drugim z zasobów pamięci dostępnej dla programów. W przeciwieństwie do stosu nie jest uporządkowana, ale nie jest też czyszczona między wywołaniami funkcji. Pamięcią na stercie zarządza sam programista.

Do przydzielania i zwalniania pamięci na stosie służą odpowiednio operatory new i delete (oraz delete[]). Do każdego new powinien być w programie gdzieś wywołany delete lub delete[].

new

Operatora new używamy razem z nazwą typu, pomyślne wywołanie alokuje potrzebną pamięć na stercie i zwraca wskaźnik jak w poniższym przykładzie:

int *p = new int;

Jeśli trzeba możemy od razu tworzyć całe dynamiczne tablice o zadanym rozmiarze:

size_t n;
cin >> n;
int *p = new int[n];

W przypadku braku potrzebnej pamięci operator new rzuci wyjątek std::bad_alloc. O wyjątkach będziemy się uczyć znacznie później, ale warto wiedzieć gdzie szukać błędu, gdy nasz program nagle kończy działanie z komunikatem mówiącym coś o bad_alloc.

Wiele współczesnych kompilatorów C++ pozwala napisać poniższy kod używający tzw. Variable Length Array:

size_t n;
cin >> n;
int t[n];

Obecny standard C++ – C++11 – nie przewiduje takiej możliwości, ale wiele kompilatorów mimo to ją wspiera. Warto nadmienić, że VLA są w opcjonalne w standardzie języka C (C11).

Rozwiązanie to ma swoje wady – tablica jest niszczona w momencie, gdy kończy działanie funkcja, która taką tablicę stworzyła, ponadto nasz kod nie jest już zgodny ze standardem języka. Za to nie trzeba pamiętać o wywołaniu delete[].

delete

Zaalokowaną pamięć trzeba zwolnić, służy do tego operator delete. Do tego operatora przekazujemy wskaźnik zainicjowany uprzednio przez new:

int *p = new int;
...
delete p;

Jeżeli alokowaliśmy tablicę, to należy użyć delete[]:

int *t = new int[5];
...
delete[] t;

Do delete można przekazać tylko wskaźnik do pamięci przydzielonej przez new, próba przekazania innego wskaźnika skończy się z reguły natychmiastową katastrofą. Dla przykładu można sobie uruchomić następujący program:

int main() {
    int i;
    int *p = &i;
    delete p;
    return 0;
}

Wycieki pamięci

Zapomnienie o wywołaniu delete powoduje, że pamięć nie jest zwracana do sytemu operacyjnego. Systemowi operacyjnemu wydaje się więc, że nasz program cały czas jej używa. Kolejne wywołania new przydzielają nową pamięć, więc z biegiem czasu nasz program zaczyna potrzebować coraz więcej pamięci co prowadzi do katastrofy – czasem całego systemu.

Angielska Wikipedia ma bardzo dobry przykład, który tutaj przedstawię. Wyobraźmy sobie, że program obsługujący naciśnięcie przycisku piętra w windzie wygląda tak:

Po naciśnięciu przycisku:
  Przydziel trochę pamięci na numer piętra na które mamy się udać
  Wpisz numer piętra docelowego do pamięci
  Czy jesteśmy już na piętrze docelowym?
    Jeżeli tak, to koniec
    Jeżeli nie, to
      Poczekaj aż drzwi będą zamknięte
      Udaj się na zapamiętane piętro docelowe
      Zwolnij pamięć, w której był zapamiętany numer piętra

Program nie zwalnia przydzielonej pamięci, gdy nacisnąć przycisk piętra na którym winda się akurat znajduje. Winda tak mogłaby przejść wszystkie testy i jeździć latami – aż skończy się pamięć i np. zablokuje kogoś w środku. Technik prawdopodobnie by ją wyłączył, a po włączeniu działałaby dalej – restart programu spowoduje zwolnienie całej pamięci i proces zacznie się od nowa.

W C++ wyciek pamięci mógłby wyglądać jak poniższy program, jest on tylko do celów ilustracyjnych, nie należy go uruchamiać:

int main() {
    while (true) {
        int *p = new int;
    }
    return 0;
}

Program ten cały czas żąda od systemu kolejnych kawałków pamięci a nie zwalnia tego co już ma. Po wyczerpaniu całej pamięci dostępnej w systemie (także pamięci wymiany), system operacyjny zabije prawdopodobnie nasz proces, ratując tym samym resztę systemu (tak przynajmniej jest pod Linuksem – do akcji wkracza proces o groźnej nazwie Out-of-Memory Killer).

Oczywiście problem jest najpoważniejszy, gdy nie ujawni się tak od razu. Aplikacja „puchnie” wtedy wraz z jej używaniem (swego czasu Firefox tak robił), aż do wyłączenia jej lub systemu. A znalezienie źródła tego problemu może być bardzo trudne.

Poprawne zarządzanie pamięcią w przypadku dużych programów jest bardzo trudne. Biblioteka standardowa zawiera wiele rozwiązań, które mają w tym pomóc, tutaj jednak nie będziemy ich omawiać.

Niektóre języki programowania zarządzają pamięcią automatycznie (np. Java, C#, języki skryptowe), tzn. nieużywane obiekty są usuwane ze sterty bez interwencji programisty. Jednak wszystko ma swoją cenę – programy napisane w tych językach są z reguły nieco wolniejsze a i sam mechanizm zarządzania pamięcią zajmuje trochę pamięci.