RSS

Automatyczna gospodarka pamięcią operacyjną

Liczba odsłon: 34

Od lat trwa wojna pomiędzy zwolennikami ręcznej i automatycznej gospodarki pamięcią operacyjną. Początkowo automatyczna gospodarka pamięcią – pozbawiona dobrej polskiej nazwy i określana po angielsku jako garbage collection – ustępowała rozwiązaniom wymagającym samodzielnego alokowania i zwalniania pamięci pod każdym względem — poza łatwością użycia. Postęp, jaki dokonał się jednak w dziedzinie automatyki zarządzania pamięcią nakazuje po raz kolejny dokładnie przyjrzeć się zaletom i wadom tego rozwiązania.

We wszystkich klasycznych językach programowania istnieją trzy sposoby rezerowowania bloku pamięci do długotrwałego lub tymczasowego użycia:

  1. W segmencie danych. Rozwiązanie stosowane szczególnie często w programach pisanych w asemblerze, cieszące się jednak mniejszą popularnością wśród programistów korzystających z języków wysokiego poziomu. Mimo to zmienne globalne są zazwyczaj umieszczane własnie w segmentach danych, ponieważ istnieją przez cały czas działania programu. Oznacza to, że nie istnieje potrzeba alokowania pamięci na ich potrzeby, ani zwalniania tej pamięci: segment danych zostanie automatycznie zniszczony w całości po zakończeniu działania programu.
  2. Na stosie. Choć stos ma ograniczoną pojemność, rozwiązanie takie ma dwie podstawowe zalety. Przede wszystkim zaalokowanie pamięci trwa dosłownie moment, gdyż stos jest zawsze gotowy do wykorzystania: wystarczy zwiększyć odpowiednio wskaźnik stosu, co realizuje się jedną instrukcją maszynową. Również zwolnienie bloku pamięci wymaga jedynie zrealizowania instrukcji odejmującej określoną liczbę bajtów lub słów od wskaźnika stosu. Druga zaleta wynika z wykorzystania struktury dynamicznej, jaką jest stos: wielokrotne, rekurencyjne wywoływanie tej samej procedury pozwala w prosty sposób korzystać z odrębnych kopii danych dostępnych w zmiennych o tej samej nazwie, co jest podstawowym warunkiem rekurencji. Z tej samej cechy wynika i wada: blok pamięci zaalokowany na stosie jest dostępny dla programu tylko na czas działania jednego podprogramu (jest prywatny dla podprogramu).
  3. Na stercie. Rozwiązanie najbardziej elastyczne, gdyż umożliwia alokowanie bloków pamięci o rozmiarze ograniczonym tylko przestrzenią adresową i możliwościami systemu operacyjnego oraz w pełni dynamiczne zarządzanie nimi niezależnie od biegu programu. Nowy blok można przygotować do pracy w dowolnym momencie i zwolnić, gdy będzie niepotrzebny — niezależnie od przebiegu wywołań podprogramów po drodze. O ile jednak w dwóch poprzednich przypadkach obowiązek zwolnienia pamięci brał na siebie system operacyjny (segment danych) lub kompilator (stos), tutaj zwolnienie pamięci następuje dopiero na wyraźny rozkaz programisty. W efekcie istnieje ryzyko przedwczesnego zwolnienia bloku pamięci (co doprowadzi do błędnego działania programu lub jego awarii), zbyt późnego zwolnienia bloku pamięci (co doprowadzi do niepotrzebnego zwiększenia użycia zasobów przez program) lub niezwolnienia bloku pamięci (co lawinowo zwiększa stopień użycia zasobów i może doprowadzić do awarii programu, innych programów lub całego systemu operacyjnego).

Ponieważ o błędy związane ze zwalnianiem bloków pamięci nietrudno, postanowiono całkowicie zautomatyzować gospodarkę pamięcią. Zrzucenie odpowiedzialności za powtórne wykorzystanie zbędnych już programowi obszarów pamięci umieszczonych na stercie na sam komputer teoretycznie mogło doprowadzić do drastycznej redukcji liczby błędów w programach (a więc poprawy jakości oprogramowania i zwiększenia zadowolenia użytkowników), racjonalizacji wykorzystania dostępnych zasobów (redukcja liczby operacji alokacji bloków pamięci i oddawania ich systemowi operacyjnemu oraz zwalnianie pamięci natychmiast, gdy nie jest już potrzebna) oraz zmniejszenia obciążenia programistów i uproszczenia programów (co zwiększa czytelność kodu i produktywność jego twórców).

Jak działa system automatycznej gospodarki pamięcią

Nie jest celem tego artykułu dokładne omawianie sposobu realizacji mechanizmów GC (ang. garbage collection). Odpowiednie, mniej lub bardziej szczegółowe informacje można bez problemu znaleźć w Internecie (na przykład na stronach serwisu Wikipedia). Dostępne są również biblioteki automatycznie gospodarujące pamięcią operacyjną w środowiskach standardowo pozbawionych tych mechanizmów.

Alokacja pamięci

Alokacja pamięci – mimo automatyki zarządzania nią – następuje na żądanie programu.

Najbardziej ortodoksyjne systemy automatyzujące gospodarkę pamięcią wszystkie alokowane bloki pamięci rezerwują na stercie. Upraszcza to działanie mechanizmów GC, unifikując wszystkie obiekty, wiąże się jednak z wyraźnym spadkiem wydajności i fragmentacją sterty związaną z częstym alokowaniem na niej wielu niewielkich obiektów.

Bardziej wyrafinowane systemy przeprowadzają analizę lokalności zmiennych (ang. escape analysis). Proste zmienne alokowane tylko na krótką chwilę (na przykład zmienne lokalne typu liczbowego) tworzone są na stosie z pominięciem mechanizmu GC i zwalniane analogicznie, jak w klasycznym, nieautomatycznym rozwiązaniu. Unika się w ten sposób fragmentowania sterty i spowalniania całego systemu przez konieczność śledzenia odwołań do dziesiątek lub setek niewielkich bloków pamięci. Dodatkowo, ponieważ stos jest obszarem często używanym i zazwyczaj obecnym w pamięci podręcznej procesora, unika się odwoływania do niezbuforowanych części pamięci operacyjnej i dodatkowo przyspiesza działanie programu.

W porównaniu z klasycznym, nieautomatycznym systemem gospodarowania pamięcią alokacja trwa porównywalnie długo lub krócej. Szybsze działanie wynika z możliwości wprowadzenia optymalizacji: zamiast wyszukiwać najmniejszy dostępny blok o określonym rozmiarze, wystarczy przydzielać sekwencyjnie kolejne obszary pamięci przez proste przesuwanie wskaźnika w ramach dużego, wcześniej zaalokowanego bufora.

Śledzenie wykorzystania bloków pamięci

Skuteczna automatyczna gospodarka pamięcią operacyjną musi bazować na wiedzy o wykorzystaniu pamięci w każdej chwili działania programu. Mechanizm GC musi dysponować informacją który z bloków pamięci przestał być używany, by móc go powtórnie wykorzystać lub oddać systemowi operacyjnemu.

Największą popularnością cieszą się dwa systemy obserwowania wykorzystania bloków pamięci:

Śledzenie wykorzystania realizowane jest na bieżąco przez odpowiednie biblioteki kompilatora lub przez maszynę wirtualną realizującą pseudo-kod. W efekcie każda operacja przypisania realizowana na zmiennej nietrywialnej skutkuje drobnym narzutem wydajnościowym związanym ze zmniejszeniem licznika odwołań jednego obiektu (lub likwidacją połączenia w grafie) i zwiększeniem licznika odwołań drugiego obiektu (lub utworzeniem nowego połączenia w grafie).

Zwalnianie pamięci

W momencie wykrycia, że dany blok pamięci nie jest już dalej potrzebny programowi, można rozpocząć procedurę zwalniania go. Sposób jej przeprowadzenia zależny jest bezpośrednio od sposobu przeprowadzania alokacji pamięci.

Jeżeli alokacja przebiega identycznie, jak w środowisku pozbawionym automatycznego zarządzania pamięcią, mechanizm GC może po prostu zwolnić niewykorzystywany blok pamięci. Taki system jednak pod względem wydajności działania ustępowałby klasycznej, ręcznej gospodarce pamięcią operacyjną, upraszczając jedynie pracę programisty.

Częściej wykorzystywany jest jednak system z sekwencyjną alokacją pamięci do określonej granicy. W takim przypadku zwalnianie pojedynczych bloków pamięci nie następuje nigdy: cały bufor alokacji zwalniany jest w ramach jednej operacji. Powoduje to znaczący spadek czasu potrzebnego na alokowanie pamięci i oznaczanie pamięci jako niepotrzebnej, zwiększa jednak znacząco obciążenie pamięci operacyjnej. Chwilowe nawet wykorzystanie dużego bloku pamięci może na dłuższy czas zwiększyć ilość prywatnej pamięci procesu, intensyfikując wymianę stron pamięci z dyskiem twardym.

Defragmentacja bufora alokacji

W systemie z buforem alokacji, przydzielającym pamięć w sposób sekwencyjny, można zapobiegać potrzebie powiększania bufora lub tworzenia kolejnych buforów (i przenoszenia do nich wciąż istniejących obiektów). Aktualny bufor alokacji może okresowo podlegać defragmentacji, podczas której nieużywane bloki są scalane w większe i przenoszone na koniec bufora. Umożliwia to ciągłe korzystanie z jednego, tego samego bufora.

Aby defragmentacja była możliwa, system GC musi realizować śledzenie stopnia wykorzystania bloków danych w postaci grafu, tylko wtedy bowiem możliwe jest przechowywanie adresów komórek pamięci przechowujących wskaźniki do przenoszonych w pamięci obiektów. W systemie z licznikiem wykorzystania obiektów defragmentacja wymagałaby wprowadzenia dodatkowego stopnia pośredniego w odwołaniach, spowalniając normalny bieg programu.

Automatyczne zarządzanie pamięcią a destruktory

Obiektowe języki programowania wprowadziły pojęcie konstruktoradestruktora obiektu. Konstruktor jest wywoływany automatycznie podczas tworzenia nowego obiektu, przygotowując go do pracy lub wypełniając jego pola właściwymi (lub domyślnymi) wartościami. Destruktor z kolei ma za zadanie obsłużyć destrukcję obiektu, niszcząc elementy zależne lub zwalniając innego typu zasoby systemowe. Na przykład obiekt reprezentujący połączenie z bazą danych może nawiązywać połączenie w ramach konstruktora i rozłączać je wewnątrz destruktora. Taka technika programowania nosi nazwę techniki RAII (ang. resource acquisition iinitialization) i znacząco upraszcza proces programowania, tworząc silną więź między obiektem programowym a obiektem fizycznym.

Istnienie mechanizmu automatycznej gospodarki pamięcią operacyjną w niczym nie zmienia roli konstruktora obiektu, zachwianiu ulega natomiast pozycja destruktora.

W systemie zbliżonym do klasycznego, w którym zbędne bloki pamięci zwalniane są natychmiast po wykryciu tego faktu, funkcja destruktora może zostać zachowana. Warto jednak pamiętać, że destruktor niekoniecznie musi zostać w takim przypadku wywołany w ramach wątku, który spowodował utworzenie obiektu. Proces niszczenia obiektu może bowiem zostać zapoczątkowany przez operację realizowaną przez inny wątek programu, lub przebiegać w ramach specjalizowanego wątku mechanizmu GC. Powoduje to konieczność uważniejszego zwracania uwagę na kwestie synchronizacji wykorzystania danych pomiędzy wątkami.

W częściej stosowanym systemie GC, w którym cały bufor alokacji zwalniany jest w jednym kroku, destruktory tracą swoją rolę. Ich wywołanie może być bowiem odroczone w czasie o sekundy lub minuty, w zależności od obciążenia mechanizmu GC oraz częstotliwości automatycznych przebiegów defragmentowania bufora i zwalniania pamięci. Destruktory przestają być zatem przewidywalnym środkiem zwalniania zasobów, stając się jedynie elementem zabezpieczającym przed nieumyślnym niezwolnieniem danego zasobu. Podkreśla się to nazywając je nie destruktorami, lecz finalizatorami (ang. finalizers).

O ile zatem automatyczna gospodarka pamięcią zdejmuje z programisty obowiązek samodzielnego zwalniania bloków pamięci, nakłada na niego w zamian obowiązek samodzielnego zwalniania zasobów nie związanych z pamięcią. Na przykład, w klasycznych językach oprogramowania obiekt odpowiadający plikowi dyskowemu może otwierać plik wewnątrz konstruktora i zamykać go w destruktorze, dzięki czemu zlikwidowanie obiektu (automatycznie ze stosu lub ręcznie ze sterty) od razu zamyka plik. W systemie z automatyczną gospodarką pamięcią obiekt może istnieć w pamięci jeszcze długo po tym, jak przestanie być używany, programista musi zatem pamiętać o ręcznym wywołaniu metody zamykającej plik.

Niektóre języki programowania oferują konstrukcje umożliwiające wskazanie zakresu obowiązywania danej zmiennej, dzięki czemu możliwe staje się wykorzystanie finalizatorów w sposób przewidywalny. Nie da się jednak tej metody stosować skutecznie do zasobów, których zwalnianie musi następować w konkretnych momentach, niezależnie od struktury programu.

W językach programowania korzystających z mechanizmu GC odradza się wręcz korzystanie z finalizatorów, gdyż spowalniają one proces zwalniania bufora alokacji lub jego defragmentowania. System GC musi bowiem prowadzić listę elementów wymagających finalizacji i wywołać finalizator przed przeniesieniem lub skasowaniem bloku pamięci.

Automatyczna gospodarka pamięcią a obsługa sytuacji wyjątkowych

Technologia RAII znakomicie upraszcza zwalnianie zasobów w razie zgłoszenia błędu za pomocą systemu obsługi sytuacji wyjątkowych. Wyjście z bloku programu powoduje automatyczne zniszczenie wszystkich zmiennych lokalnych, a więc wywołanie ich destruktorów. Specjalnego traktowania wymagają jedynie bloki pamięci alokowane na stercie.

W przypadku środowiska z automatycznym zarządzaniem pamięcią nie istnieją destruktory, a finalizatory wykonywane są z opóźnieniem. Jeżeli nawet program zawierał odwołania do funkcji zwalniających zasoby w określonym momencie, zgłoszenie sytuacji wyjątkowej przerywa normalny jego bieg i powoduje pominięcie tych odwołań. W efekcie program po wystąpieniu błędu nie zwalnia używanych zasobów lub robi to ze znacznym opóźnieniem.

Z tego powodu w językach programowania z automatyczną gospodarką pamięcią rozbudowano klasyczną konstrukcję try/catch o element finally, wykonywany zawsze na końcu bloku niezależnie od tego, czy został on zrealizowany poprawnie, czy też przerwała go sytuacja wyjątkowa. Wewnątrz elementu finally należy zrealizować zwalnianie zasobów nie objętych automatycznym zarządzaniem.

Automatyczna gospodarka pamięcią a przewidywalny bieg programu

W środowiskach z klasyczną gospodarką pamięci programista ściśle określa moment zwolnienia bloku pamięci. W efekcie znany jest moment, w którym zamiast programu będzie realizowany kod funkcji bibliotecznych lub destruktorów niszczonych obiektów. W razie potrzeby zwalnianie pamięci można odroczyć, by wykonać jak najwięcej pracy w jednym ciągu, zasoby zwalniając dopiero w momencie obsłużenia żądania. Z kolei w innych sytuacjach, wymagających jak najmniejszego obciążenia pamięci, można wymusić zwolnienie pamięci jak najwcześniej, kontynuując program dopiero po zrealizowaniu destruktorów i oddaniu bloków pamięci we władanie systemu operacyjnego lub biblioteki zarządzania pamięcią.

System automatycznego gospodarowania pamięcią wprowadza w działanie programu element przypadkowości. Jest to szczególnie widoczne w przypadku systemów z buforem alokacji, które w momencie określonym przez sposób działania programu, lecz z góry nieprzewidywalnym, uruchamiają w tle operację defragmentacji bufora lub jego przenoszenia i zwalniania. W przypadku komputerów jednoprocesorowych taka operacja przerywa normalne działanie programu, a czas trwania przerwy zależy od liczby i rozmiarów likwidowanych i przenoszonych bloków oraz od liczby i stopnia skomplikowania finalizatorów, które trzeba wywołać. Jedynie w przypadku komputerów wieloprocesorowych system GC może przyczynić się do pewnego wzrostu wydajności, realizując swoje operacje w tle (o ile program nie wykorzystuje dodatkowych procesorów lub rdzeni do własnych działań, w którym to przypadku mechanizm GC również ograniczy dostępne dla programu zasoby).

W środowisku z automatyczną gospodarką pamięcią program może przyspieszyć operację porządkowania buforów alokacji, lecz żądanie takie może zostać zignorowane przez mechanizm GC. W zależności od budowy systemu GC operacja może zostać również przeprowadzona asynchronicznie (w tle), przez co program będzie realizowany równolegle ze zwalnianiem zasobów.

Automatyczna gospodarka pamięcią a pamięć fizyczna

Produkowane obecnie procesory są tak szybkie, że nawet brak optymalizacji nie powoduje widocznego spowolnienia typowych operacji realizowanych przez oprogramowanie. Zdecydowanie większe straty wydajności wynikają z konieczności wstrzymywania pracy procesora w oczekiwaniu na dane, które mogą znajdować się w trzech miejscach:

  1. W pamięci podręcznej. Sprowadzenie danych z pamięci podręcznej pierwszego poziomu trwa niezwykle krótko, obecnie często co najwyżej jeden cykl zegarowy (dane znajdujące się na tym poziomie pamięci podręcznej można traktować jako dostępne od razu). Kolejne, głębsze poziomy mają co prawda znacznie większe pojemności, jednak i czas dostępu do danych wydłuża się do kilku lub kilkunastu cykli zegarowych.
  2. W pamięci operacyjnej. Pamięć operacyjna transmituje dane z częstotliwością sięgającą zazwyczaj kilkuset megasłów na sekundę, podczas gdy procesor jest w stanie przetwarzać dane z szybkością kilkunastu gigasłów na sekundę. Ponadto czas losowego dostępu do pamięci liczy od kilkudziesięciu do kilkuset cykli zegarowych procesora. Im więcej użytecznych danych można zatem odczytać z pamięci w ramach jednej operacji, tym szybciej działa program.
  3. W pamięci masowej. Nowoczesne mechanizmy stronicowania umożliwiają wczytywanie stron pamięci zawierających kod i dane dopiero w momencie, gdy są one niezbędne (ang. on-demand paging). Z kolei w razie zbliżania się do granicy pojemności pamięci fizycznej chwilowo niepotrzebne strony pamięci mogą zostać wymiecione z powrotem do pamięci masowej. Ponieważ pamięci masowe są setki lub tysiące razy wolniejsze od pamięci operacyjnej, zwiększanie stopnia wykorzystania pamięci przez utrzymywanie bufora alokacji ogranicza wydajność tak całego systemu operacyjnego, jak i samego programu.

Generalnie przenoszenie obiektów w ramach bufora alokacji oraz alokowanie bloków pamięci w sposób sekwencyjny wpływają negatywnie zarówno na efektywność wykorzystania pamięci podręcznej, jak i zajętość pamięci operacyjnej. Nieco poprawiają sytuację efekty okresowego konsolidowania bufora alokacji, zwiększającego stopień lokalności danych.

W czym automatyczne zarządzanie pamięcią naprawdę pomaga

Mechanizmy automatycznego zarządzania pamięcią operacyjną potrafią realnie uprościć konstrukcję programu. Programista może w pewnym zakresie podporządkować strukturę programu wybranej architekturze, zamiast dostosowywać ją do wymogów efektywnego i bezpiecznego zarządzania pamięcią.

Szczególnie widać to w momencie synchronizowania elementów interfejsu graficznego (na przykład okien dialogowych) z zadaniami wykonywanymi w tle. W programie pisanym w sposób klasyczny konieczne jest wprowadzenie własnego kodu opóźniającego zamknięcie okna aż do momentu zrealizowania drugoplanowej operacji (lub przerywającego tę operację) — użytkownik może bowiem znudzić się czekaniem i zamknąć okno, do którego zlecone zadanie zechce się później odwoływać. W środowisku z automatyczną gospodarką pamięcią nie jest to konieczne: choć okno zostanie zamknięte, odpowiadające mu bloki pamięci będą istniały aż do momentu zakończenia drugoplanowej operacji.

Łatwiej jest również realizować skomplikowane, skorelowane ze sobą listy o formie relacyjnej bazy danych. Klasyczny sposób programowania wymaga utrzymywania liczników stopnia wykorzystania rekordu, by niemożliwe było usunięcie obiektu, z którego korzystają inne. Przy automatycznej gospodarce pamięcią wystarczy zapisać wskaźnik do obiektu, by nie został on skasowany zbyt wcześnie.

Podsumowanie

Mocne i słabe strony najważniejszych odmian mechanizmów zarządzania pamięcią w ramach programu przedstawiłem w poniższej tabeli:

Operacja Ręczna gospodarka pamięcią Automatyczna gospodarka pamięcią Automatyczna gospodarka pamięcią z buforem alokacji
Wygoda programowania mała duża duża
Odporność na błędy związane z zarządzaniem pamięcią mała duża duża
Szybkość realizacji operacji alokowania pamięci mała mała duża
Szybkość realizacji operacji dealokowania pamięci względnie duża względnie duża duża
Realizacja konstruktorów szybka szybka szybka
Realizacja destruktorów szybka, w momencie dealokacji obiektu zależnie od implementacji długotrwała, nieprzewidywalna, w momencie porządkowania bufora
Zajętość pamięci mała, zależna od jakości programu mała, zależna od implementacji duża
Przewidywalność stopnia zajętości pamięci duża zależna od implementacji mała

Widać, że systemy z automatyczną gospodarką pamięcią operacyjną przyspieszają działanie programu zgodnie z regułą „przyspieszenie przez zwiększenie wykorzystania zasobów”. Choć same operacje alokacji i dealokacji bloków pamięci realizowane są szybciej (w przypadku systemu z buforem alokacji), wiąże się to z korzystaniem z większych bloków pamięci. Przyspieszenie operacji zwalniania pamięci (i wykonywania kodu destruktorów) również możliwe jest tylko na komputerach z wieloma procesorami.

Na pytanie „czy stosować systemy automatycznej gospodarki pamięcią operacyjną” nie ma prostej odpowiedzi. Niewątpliwie mają one swoje miejsce w prostych językach programowania, gdzie efektywność nie liczy się tak bardzo jak niezawodność i łatwość stosowania nawet przez początkujących i niedoświadczonych programistów. Trudniej podjąć decyzję w przypadku języków programowania używanych przez profesjonalistów. Przykład języków Java i C# pokazuje, że automatyczna gospodarka pamięcią daje wielkie możliwości i pozwala w prosty sposób tworzyć niezawodne i wielowątkowe oprogramowanie za cenę znacznego zwiększenia zajętości pamięci, a więc pogorszenia wydajności działania całego komputera. Mało kto stosuje też automatyczną gospodarkę pamięcią w klasycznych językach programowania, takich jak C czy C++.

Automatyczne gospodarowanie pamięcią zwiększa produktywność i kreatywność programisty, gdyż może on w krótkim czasie realizować skomplikowane algorytmy, nie wprowadzając zarazem subtelnych błędów skutkujących niezwalnianiem pamięci lub odwoływaniem się do zwolnionych już bloków pamięci. Z drugiej strony doświadczony programista może osiągnąć podobne rezulaty za cenę poświęcenia większej ilości czasu na pracę (inwestując go w doskonale przemyślane klasy obiektów automatyzujące częściowo gospodarkę pamięcią lub wprowadzając ręczne zarządzanie). Wybór należy do Ciebie.