Zarządzanie pamięcią w oparciu o regiony - Region-based memory management

W informatyce , zarządzanie pamięcią regionu oparte jest rodzajem zarządzania pamięcią , w której każdy obiekt jest przypisany przydzielone do regionu . Region, zwany także zone , arena , area lub memory context , to zbiór przydzielonych obiektów, które można efektywnie ponownie przydzielić lub cofnąć jednocześnie. Podobnie jak alokacja stosu , regiony ułatwiają alokację i cofanie alokacji pamięci z niskim obciążeniem; ale są bardziej elastyczne, pozwalając obiektom żyć dłużej niż ramka stosu, w której zostały przydzielone. W typowych implementacjach wszystkie obiekty w regionie są alokowane w jednym ciągłym zakresie adresów pamięci, podobnie jak zwykle przydzielane są ramki stosu.

Przykład

Jako prosty przykład rozważmy następujący kod w języku C, który alokuje, a następnie zwalnia strukturę danych połączonej listy: 

Region *r = createRegion();
ListNode *head = NULL;
for (int i = 1; i <= 1000; i++) {
    ListNode* newNode = allocateFromRegion(r, sizeof(ListNode));
    newNode->next = head;
    head = newNode;
}
// ...
// (use list here)
// ...
destroyRegion(r);

Chociaż tworzenie połączonej listy wymagało wielu operacji, można ją szybko cofnąć w jednej operacji, niszcząc region, w którym przydzielono węzły. Nie ma potrzeby przemierzania listy.

Realizacja

Proste, jawne regiony są łatwe do zaimplementowania; poniższy opis oparty jest na Hansonie. Każdy region jest zaimplementowany jako połączona lista dużych bloków pamięci; każdy blok powinien być wystarczająco duży, aby obsłużyć wiele alokacji. Obecny blok utrzymuje wskaźnik do następnej wolnej pozycji w bloku, a jeśli blok jest wypełniony, przydzielany jest nowy i dodawany do listy. Gdy region jest zwalniany, wskaźnik następnej wolnej pozycji jest resetowany na początek pierwszego bloku, a lista bloków może być ponownie wykorzystana dla następnego przydzielonego regionu. Alternatywnie, gdy region jest zwalniany, jego lista bloków może być dołączona do globalnej wolnej listy, z której inne regiony mogą później przydzielić nowe bloki. W obu przypadkach tego prostego schematu nie jest możliwe cofnięcie alokacji poszczególnych obiektów w regionach.

Całkowity koszt na przydzielony bajt tego schematu jest bardzo niski; prawie wszystkie alokacje obejmują tylko porównanie i aktualizację wskaźnika następnej wolnej pozycji. Cofanie alokacji regionu jest operacją w czasie stałym i jest wykonywane rzadko. W przeciwieństwie do typowych systemów garbage collection , nie ma potrzeby tagowania danych ich typem.

Historia i koncepcje

Podstawowa koncepcja regionów jest bardzo stara, po raz pierwszy pojawiła się już w 1967 roku w pakiecie AED Free Storage Package autorstwa Douglasa T. Rossa, w którym pamięć została podzielona na hierarchię stref; każda strefa miała swój własny alokator, a strefę można było uwolnić na raz, dzięki czemu można było używać stref jako regionów. W 1976 roku standard PL/I obejmował typ danych AREA. W 1990 roku Hanson zademonstrował, że jawne regiony w C (które nazwał arenami) mogą osiągnąć wydajność czasową na przydzielony bajt lepszą niż nawet najszybszy znany mechanizm alokacji sterty. Jawne regiony odegrały kluczową rolę w projektowaniu niektórych wczesnych projektów oprogramowania opartych na C, w tym Apache HTTP Server , który nazywa je pulami, oraz system zarządzania bazami danych PostgreSQL , który nazywa je kontekstami pamięci. Podobnie jak tradycyjna alokacja sterty, schematy te nie zapewniają bezpieczeństwa pamięci ; programista może uzyskać dostęp do regionu po jego cofnięciu alokacji za pomocą wiszącego wskaźnika lub zapomnieć o cofnięciu alokacji regionu, co powoduje wyciek pamięci .

Wnioskowanie o regionie

W 1988 roku badacze zaczęli badać, jak używać regionów do bezpiecznej alokacji pamięci, wprowadzając koncepcję wnioskowania o regionie , w której tworzenie i cofanie alokacji regionów, a także przypisywanie poszczególnych wyrażeń alokacji statycznej do poszczególnych regionów, jest wstawiane przez kompilator w czas kompilacji. Kompilator jest w stanie to zrobić w taki sposób, że może zagwarantować, że nie pojawią się zwisające wskaźniki i nie wystąpią wycieki.

We wczesnej pracy Ruggieriego i Murtagha na początku każdej funkcji tworzony jest region, a na końcu dealokowany. Następnie używają analizy przepływu danych w celu określenia okresu istnienia każdego wyrażenia alokacji statycznej i przypisania go do najmłodszego regionu, który zawiera jego cały okres istnienia.

W 1994 roku praca ta została uogólniona w przełomowej pracy Tofte i Talpina w celu wsparcia polimorfizmu typów i funkcji wyższego rzędu w Standard ML , funkcjonalnym języku programowania , przy użyciu innego algorytmu opartego na wnioskowaniu o typie i teoretycznych koncepcjach typów regionów polimorficznych i rachunek regionu . Ich praca wprowadziła rozszerzenie rachunku lambda o regiony, dodając dwie konstrukcje:

e 1 w ρ: Oblicz wynik wyrażenia e 1 i zapisz go w obszarze ρ;
letregion ρ w e 2 end: Utwórz region i powiąż go z ρ; ocenić e 2 ; następnie cofnij alokację regionu.

W związku z tym struktury składniowej, regiony są zagnieżdżone , co oznacza, że jeśli R 2 jest tworzony po R 1 , musi również być zwalniane przed R 1 ; wynikiem jest stos regionów. Ponadto regiony muszą być cofnięte w tej samej funkcji, w której zostały utworzone. Te ograniczenia zostały złagodzone przez Aikena i in.

Ten rozszerzony rachunek lambda miał służyć jako bezpieczna w pamięci pośrednia reprezentacja do kompilowania programów Standard ML do kodu maszynowego, ale budowanie translatora, który dawałby dobre wyniki w dużych programach, napotykało na szereg praktycznych ograniczeń, które musiały zostać rozwiązane za pomocą nowych analizy, w tym radzenie sobie z wywołaniami rekurencyjnymi, wywołaniami ogona i eliminowanie regionów, które zawierały tylko jedną wartość. Praca ta została ukończona w 1995 roku i zintegrowana z zestawem ML Kit, wersją ML opartą na alokacji regionów zamiast zbierania śmieci. Pozwoliło to na bezpośrednie porównanie tych dwóch w programach testowych średniej wielkości, uzyskując bardzo zróżnicowane wyniki („od 10 razy szybciej do 4 razy wolniej”) w zależności od tego, jak „przyjazny dla regionu” był program; Czasy kompilacji były jednak rzędu minut. Zestaw ML Kit został ostatecznie przeskalowany do dużych aplikacji z dwoma dodatkami: schematem oddzielnej kompilacji modułów oraz techniką hybrydową łączącą wnioskowanie o regionie ze śledzeniem zbierania śmieci.

Uogólnienie na nowe środowiska językowe

Po opracowaniu ML Kit regiony zaczęły być uogólniane na inne środowiska językowe:

  • Różne rozszerzenia języka programowania C:
    • Bezpieczny dialekt języka C Cyclone , który oprócz wielu innych funkcji dodaje obsługę wyraźnych regionów i ocenia wpływ migracji istniejących aplikacji C w celu ich użycia.
    • Zaimplementowano rozszerzenie języka C o nazwie RC, które używa regionów zarządzanych jawnie, ale używa również zliczania odwołań w regionach, aby zagwarantować bezpieczeństwo pamięci, zapewniając, że żaden region nie zostanie przedwcześnie zwolniony. Regiony zmniejszają obciążenie związane z liczeniem referencji, ponieważ referencje wewnętrzne do regionów nie wymagają aktualizacji liczników po ich modyfikacji. RC zawiera jawny statyczny system typów dla regionów, który umożliwia eliminację niektórych aktualizacji liczby odwołań.
    • Ograniczenie języka C o nazwie Control-C ogranicza programy do używania regionów (i tylko jednego regionu na raz), jako części jego projektu, aby statycznie zapewnić bezpieczeństwo pamięci.
  • Regiony zostały zaimplementowane dla podzbioru Javy i stały się kluczowym elementem zarządzania pamięcią w Javie w czasie rzeczywistym , która łączy je z typami własności, aby zademonstrować enkapsulację obiektów i wyeliminować kontrole w czasie wykonywania przy delokalizacji regionu. Niedawno zaproponowano półautomatyczny system do wnioskowania o regionach we wbudowanych aplikacjach Java działających w czasie rzeczywistym, łączący analizę statyczną w czasie kompilacji, politykę alokacji regionów w czasie wykonywania oraz wskazówki dla programistów. Regiony dobrze nadają się do przetwarzania w czasie rzeczywistym, ponieważ ich narzut czasowy jest statycznie przewidywalny, bez złożoności przyrostowego wyrzucania elementów bezużytecznych.
  • Zostały one zaimplementowane dla logicznych języków programowania Prolog i Mercury poprzez rozszerzenie modelu wnioskowania o regionie Tofte'a i Talpina o obsługę nawrotów i cięć.
  • Zarządzanie pamięcią masową oparte na regionach jest używane w całym równoległym języku programowania ParaSail . Ze względu na brak wyraźnych wskaźników w ParaSail, nie ma potrzeby liczenia referencji.

Niedogodności

Systemy korzystające z regionów mogą napotkać problemy, w których regiony stają się bardzo duże przed cofnięciem ich alokacji i zawierają dużą część martwych danych; są one powszechnie nazywane „przeciekami” (chociaż ostatecznie zostają uwolnione). Wyeliminowanie przecieków może wiązać się z restrukturyzacją programu, zazwyczaj poprzez wprowadzenie nowych, krótszych regionów. Debugowanie tego typu problemu jest szczególnie trudne w systemach korzystających z wnioskowania o regionie, w których programista musi zrozumieć podstawowy algorytm wnioskowania lub zbadać szczegółową reprezentację pośrednią, aby zdiagnozować problem. Tracing garbage collectors są bardziej efektywne w usuwaniu tego typu danych w odpowiednim czasie bez zmian w programie; było to jedno z uzasadnień dla hybrydowych systemów region/GC. Z drugiej strony, śledzące odśmiecacze mogą również wykazywać subtelne przecieki, jeśli zachowane są odniesienia do danych, które nigdy nie zostaną ponownie użyte.

Zarządzanie pamięcią oparte na regionach działa najlepiej, gdy liczba regionów jest stosunkowo niewielka i każdy zawiera wiele obiektów; programy, które zawierają wiele rzadkich regionów, będą wykazywać wewnętrzną fragmentację , prowadzącą do marnowania pamięci i narzutu czasu na zarządzanie regionami. Ponownie, w obecności wnioskowania o regionie problem ten może być trudniejszy do zdiagnozowania.

Metody hybrydowe

Jak wspomniano powyżej, RC używa hybrydy regionów i zliczania referencji , ograniczając obciążenie związane z liczeniem referencji, ponieważ referencje wewnętrzne dla regionów nie wymagają aktualizacji liczników, gdy są modyfikowane. Podobnie, niektóre metody hybrydowe znacznik-region łączą śledzenie wyrzucania elementów bezużytecznych z regionami; działają one poprzez podzielenie sterty na regiony, wykonanie przejścia znakowania, w którym wszystkie regiony zawierające żywe obiekty są oznaczane, a następnie uwalnianie wszelkich nieoznaczonych regionów. Wymagają one ciągłej defragmentacji, aby zachować skuteczność.

Bibliografia