Czym jest fragmentacja pamięci?

Czym jest fragmentacja pamięci?

Fragmentacja pamięci jest wtedy, gdy większość pamięci jest przydzielana w dużej liczbie przyległych bloków lub kawałków-pozostawiając spory procent całkowitej pamięci nieprzydzielonej, ale bezużytecznej w większości typowych scenariuszy. Powoduje to wyjątki out of memory lub błędy alokacji (np. malloc zwraca null).

Najprostszym sposobem myślenia o tym jest wyobrażenie sobie, że masz dużą pustą ścianę, którą musisz umieścić zdjęcia o różnych rozmiarach na. Każde zdjęcie ma określony rozmiar i oczywiście nie można go podzielić na mniejsze części, aby pasowało. Potrzebujesz pustego miejsca na ścianie, rozmiaru obrazu, albo nie możesz go powiesić. Teraz, jeśli zaczniesz wieszać zdjęcia na ścianie i nie będziesz uważać na to, jak je zaaranżujesz, wkrótce skończysz ze ścianą, która jest częściowo pokryta zdjęciami i nawet jeśli możesz mieć puste miejsca, większość nowych zdjęć nie zmieści się, ponieważ są większe niż dostępne miejsca. Nadal można powiesić naprawdę małe zdjęcia, ale większość z nich nie zmieści się. Więc będziesz musiał ponownie zaaranżować (zwarte) te już na ścianie, aby zrobić miejsce na więcej..

Jak mogę stwierdzić, czy fragmentacja pamięci jest problemem dla mojej aplikacji? Jaki program najbardziej ucierpi?

Znak, że możesz mieć do czynienia z fragmentacja pamięci występuje wtedy, gdy pojawia się wiele błędów alokacji, zwłaszcza gdy odsetek zużytej pamięci jest wysoki - ale nie zużyłeś jeszcze całej pamięci - więc technicznie powinieneś mieć dużo miejsca na obiekty, które próbujesz przydzielić.

Gdy pamięć jest mocno rozdrobniona, alokacja pamięci prawdopodobnie potrwa dłużej, ponieważ alokator pamięci musi wykonać więcej pracy, aby znaleźć odpowiednie miejsce dla nowego obiektu. Jeśli z kolei masz wiele alokacji pamięci (które prawdopodobnie tak, ponieważ skończyło się fragmentacji pamięci) czas alokacji może nawet powodować zauważalne opóźnienia.

Jakie są dobre wspólne sposoby radzenia sobie z fragmentacją pamięci?

Użyj dobrego algorytmu przydzielania pamięci. Zamiast przydzielać pamięć dla wielu małych obiektów, wstępnie przydzielaj pamięć dla sąsiedniej tablicy tych mniejszych obiektów. Czasami trochę marnotrawstwo przy przydzielaniu pamięci może iść na drogę dla wydajności i może zaoszczędzić kłopotu radzenie sobie z fragmentacją pamięci.

Fragmentacja pamięci jest tym samym pojęciem, co fragmentacja dysku: odnosi się do marnowania przestrzeni, ponieważ używane obszary nie są odpowiednio spakowane.

Załóżmy dla prostego przykładu Zabawki, że masz dziesięć bajtów pamięci:

 |   |   |   |   |   |   |   |   |   |   |
   0   1   2   3   4   5   6   7   8   9

Przydzielmy teraz trzy trzy bajtowe bloki, Nazwy A, B i C:

 | A | A | A | B | B | B | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Teraz Blok B:

 | A | A | A |   |   |   | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Co się stanie, jeśli spróbujemy przydzielić czterobajtowy Blok D? Mamy cztery bajty pamięci wolne, ale nie mamy czterech sąsiadujących bajtów pamięci, więc nie możemy przydzielić D! Jest to nieefektywne wykorzystanie pamięci, ponieważ powinniśmy byli być w stanie przechowywać D, ale nie byliśmy w stanie. I nie możemy przenieść C, aby zrobić miejsce, ponieważ bardzo prawdopodobne, że niektóre zmienne w naszym programie wskazują na C, i nie możemy automatycznie znaleźć i zmienić wszystkich tych wartości.

W tym przykładzie, 3 bajty nie są dużo do zmarnowania, ale rozważ bardziej patologiczny przypadek, w którym dwa przydziały po kilka bajtów są na przykład dziesięć megabajtów w pamięci i musisz przydzielić blok o wartości 1000 bajtów. rozmiar 10 megabajtów + 1 bajt. Aby to zrobić, musisz poprosić SYSTEM OPERACYJNY o ponad dziesięć megabajtów więcej pamięci wirtualnej, nawet jeśli jesteś tylko jednym bajtem, który nie ma wystarczającej ilości miejsca.

Ogólnie rzecz biorąc, im mniej przydziałów, tym mniej prawdopodobne jest, że pamięć zostanie rozdrobniona. Jednak STL radzi sobie z tym dość skutecznie. Jeśli masz ciąg znaków, który wykorzystuje cały swój bieżący przydział i dołączasz jeden znak do to, to nie po prostu przeznaczyć na jego bieżącej długości plus jeden, to podwaja jego długość. Jest to odmiana strategii "pool for frequent small allocations". Ciąg chwyta dużą część pamięci, dzięki czemu może skutecznie radzić sobie z powtarzającymi się małymi wzrostami rozmiaru bez powtarzania małych ponownych przydziałów. Wszystkie kontenery STL w rzeczywistości robią tego typu rzeczy, więc generalnie nie musisz się zbytnio martwić o fragmentację spowodowaną automatycznym ponownym przydziałem STL kontenery.

Chociaż oczywiście kontenery STL nie łączą pamięci między, więc jeśli masz zamiar utworzyć wiele małych kontenerów (a nie kilka kontenerów, które są często zmieniane), być może będziesz musiał się martwić o zapobieganie fragmentacji w taki sam sposób, jak w przypadku często tworzonych małych obiektów, STL lub nie.

• Czym jest fragmentacja pamięci?

• Jak mogę stwierdzić, czy fragmentacja pamięci jest problemem dla mojej aplikacji? Jaki program najbardziej ucierpi?

Fragmentacja pamięci jest problemem, jeśli twój program zużywa znacznie więcej pamięci systemowej niż wymagałoby tego rzeczywiste dane paylod (a wykluczyłeś wycieki pamięci).

• Czym są dobre wspólne sposoby radzenia sobie z fragmentacją pamięci?

Użyj dobrego alokatora pamięci. IIRC, ci, którzy stosują strategię "najlepiej dopasowaną", są na ogół znacznie lepsi w unikaniu fragmentacji, jeśli są trochę wolniejsi. Wykazano jednak również, że dla każdej strategii alokacji istnieją patologiczne najgorsze przypadki. Na szczęście typowe wzorce alokacji większości aplikacji są w rzeczywistości stosunkowo łagodne dla alokatorów do obsługi. Jest mnóstwo Papierów, jeśli jesteś zainteresowanych szczegółami:

Paul R. Wilson, Mark S. Johnstone, Michael Neely i David Boles. Dynamiczna alokacja pamięci masowej: ankieta i krytyczny przegląd. W 1995 International Workshop on Memory Management, Springer Verlag LNCS, 1995 Mark S. Johnstone, Paul R. Wilson. Problem Fragmentacji Pamięci: Rozwiązany? W ACM SIG-PLAN Notices, volume 34 No. 3, pages 26-36, 1999 M. R. Garey, R. L. Graham i J. D. Ullman. Analiza najgorszego przypadku pamięci algorytmy alokacji. W roku 1972, w czwartym dorocznym sympozjum ACM on the Theory of Computing, 1972

Aktualizacja:
Google TCMalloc: Thread-Caching Malloc
Stwierdzono, że jest całkiem dobry w radzeniu sobie z fragmentacją w długotrwałym procesie.

Rozwijałem aplikację serwerową, która miała problemy z fragmentacją pamięci na HP-UX 11.23/11.31 ia64.

O moim doświadczeniu. W HP-UX bardzo łatwo jest znaleźć fragmentację pamięci przy użyciu HP-UX gdb. Ustawiasz break-point i po naciśnięciu go uruchamiasz to polecenie: info heap i widzisz wszystkie alokacje pamięci dla procesu i całkowity rozmiar sterty. Następnie kontynuujesz swój program, a po jakimś czasie ponownie trafiasz w punkt przerwania. Znowu robisz info heap. Jeśli całkowita wielkość sterty jest większa, ale liczba i wielkość oddzielnych przydziały są takie same, więc prawdopodobnie masz problemy z alokacją pamięci. W razie potrzeby sprawdź to kilka razy.

Wiem, że jednym ze sposobów uniknięcia fragmentacji pamięci w HP-UX jest użycie małego alokatora bloków lub MallocNextGen. W RedHat Linux domyślny alokator zdaje się radzić sobie całkiem dobrze z przydzielaniem wielu małych bloków. W systemie Windows jest Low-fragmentation Heap i rozwiązuje problem dużej liczby małych przydziałów.

Rozumiem, że w aplikacji stl-heavy musisz najpierw zidentyfikować problemy. Alokatory pamięci (jak w libc) w rzeczywistości zajmuje się problemem wielu małych alokacji, co jest typowe dla std::string (na przykład w mojej aplikacji serwerowej jest wiele ciągów STL, ale jak widzę po uruchomieniu info heap nie powodują one żadnych problemów). Mam wrażenie, że należy unikać częstych dużych przydziałów. Niestety zdarzają się sytuacje, kiedy nie można ich uniknąć i trzeba zmienić kod. Jak mówię w moim przypadku poprawiłem sytuację po przełączeniu na std::deque. Jeśli zidentyfikujesz swoją pamięć fragmentarycznie to może być możliwe, aby mówić o tym bardziej precyzyjnie.

Fragmentacja pamięci jest najbardziej prawdopodobna, gdy przydzielasz i deallokujesz wiele obiektów o różnych rozmiarach. Załóżmy, że masz w pamięci następujący układ:

obj1 (10kb) | obj2(20kb) | obj3(5kb) | unused space (100kb)

Teraz, kiedy obj2 jest zwolniony, masz 120kb nieużywanej pamięci, ale nie możesz przydzielić pełnego bloku 120kb, ponieważ pamięć jest fragmentowana.

Typowe techniki unikania tego efektu obejmują bufory pierścieniowe i pule obiektów. W kontekście STL, metody takie jak std::vector::reserve() może pomóc.

Bardzo szczegółową odpowiedź na temat fragmentacji pamięci można znaleźć tutaj.

Http://library.softwareverify.com/memory-fragmentation-your-worst-nightmare/

Jest to kulminacja 11 lat fragmentacji pamięci odpowiedzi, które udzielam ludziom zadającym mi pytania dotyczące fragmentacji pamięci na softwareverify.com

Czym jest fragmentacja pamięci?

Gdy aplikacja korzysta z pamięci dynamicznej, przydziela i zwalnia fragmenty pamięci. Na początku cała przestrzeń pamięci aplikacji jest jednym ciągłym blokiem wolnej pamięci. Jednakże, gdy przydzielasz i uwalniasz bloki o różnej wielkości, pamięć zaczyna być rozdrobniona , tzn. zamiast dużego przylegającego wolnego bloku i kilku sąsiadujących ze sobą przydzielonych bloków, zostaną wymieszane przydzielone i wolne bloki. Od wolnego bloki mają ograniczony rozmiar, trudno je ponownie wykorzystać. Np. możesz mieć 1000 bajtów wolnej pamięci, ale nie możesz przydzielić pamięci na 100-bajtowy blok, ponieważ wszystkie wolne bloki mają maksymalnie 50 bajtów.

Innym, nieuniknionym, ale mniej problematycznym źródłem fragmentacji jest to, że w większości architektur adresy pamięci muszą być wyrównane do 2, 4, 8 itd. granice bajtów (tzn. adresy muszą być wielokrotnościami 2, 4, 8 itd.) Oznacza to, że nawet jeśli masz np. strukturę zawierając 3 pola char, twoja struktura może mieć rozmiar 12 zamiast 3, ze względu na fakt, że każde pole jest wyrównane do 4-bajtowej granicy.

Jak mogę stwierdzić, czy fragmentacja pamięci jest problemem dla mojej aplikacji? Jaki program najbardziej ucierpi?

Oczywistą odpowiedzią jest to, że dostajesz wyjątek out of memory.

Najwyraźniej nie ma dobrego przenośnego sposobu wykrywania fragmentacji pamięci w aplikacjach C++. Zobacz Ta odpowiedź aby dowiedzieć się więcej szczegóły.

Jakie są dobre wspólne sposoby radzenia sobie z fragmentacją pamięci?

Jest to trudne w C++, ponieważ używasz bezpośrednich adresów pamięci w wskaźnikach i nie masz kontroli nad tym, kto odwołuje się do określonego adresu pamięci. Przestawianie przydzielonych bloków pamięci (tak jak robi to Java garbage collector) nie wchodzi w grę.

Własny alokator może pomóc poprzez zarządzanie alokacją małych obiektów w większej części pamięci i ponowne wykorzystanie wolnych miejsc w tym kawałku.

Jest to super uproszczona wersja dla manekinów.

Gdy obiekty są tworzone w pamięci, są dodawane do końca używanej części w pamięci.

Jeśli obiekt, który nie znajduje się na końcu używanej części pamięci, zostanie usunięty, co oznacza, że ten obiekt znajdował się pomiędzy dwoma innymi obiektami, utworzy "dziurę".

To się nazywa fragmentacja.

Gdy chcesz dodać element na stercie, to komputer musi wyszukać miejsce, aby pasował do tego elementu. Dlatego dynamiczne alokacje, gdy nie są wykonywane na puli pamięci lub przy użyciu alokatora zbiorczego, mogą "spowolnić" działanie. W przypadku ciężkiej aplikacji STL, jeśli wykonujesz wielowątkowość, istnieje wersja alokatora Hoard lub TBB Intel .

Teraz, gdy pamięć jest rozdrobniona, mogą wystąpić dwie rzeczy:

1. będzie musiało być więcej poszukiwań, aby znajdź dobre miejsce na przyklejenie "dużych" przedmiotów. Oznacza to, że z wieloma małymi obiektami rozproszonymi o znalezienie ładnego przylegającego fragmentu pamięci może w pewnych warunkach być trudne(są to ekstremalne.)
Pamięć nie jest łatwo odczytaną istotą. Procesory są ograniczone do tego, ile mogą pomieścić i gdzie. Robią to poprzez zamianę stron, jeśli element, którego potrzebują, jest jednym miejscem, ale obecne adresy są inne. Jeśli ciągle musisz wymieniać strony, przetwarzanie może spowolnić (ponownie, ekstremalne scenariusze, w których wpływa to na wydajność.) Zobacz ten post na pamięci wirtualnej .

Fragmentacja pamięci występuje, ponieważ wymagane są bloki pamięci o różnych rozmiarach. Rozważmy bufor 100 bajtów. Żądasz dwóch znaków, a następnie liczby całkowitej. Teraz zwalniasz dwa znaki, następnie żądasz nowej liczby całkowitej - ale ta liczba całkowita nie może zmieścić się w przestrzeni tych dwóch znaków. Pamięć ta nie może być ponownie wykorzystana, ponieważ nie znajduje się w wystarczająco dużym sąsiednim bloku, aby ją ponownie przydzielić. Co więcej, wywołałeś wiele kosztów przydzielania dla swoich znaków.

Zasadniczo pamięć przychodzi tylko bloki o określonej wielkości w większości systemów. Po rozdzieleniu tych bloków nie można ich połączyć, dopóki cały blok nie zostanie uwolniony. Może to prowadzić do całych bloków w użyciu, gdy w rzeczywistości tylko niewielka część bloku jest w użyciu.

Podstawowym sposobem zmniejszenia fragmentacji sterty jest dokonywanie większych, rzadszych przydziałów. W skrajności można użyć sterty zarządzanej, która jest w stanie przenosić obiekty, przynajmniej w obrębie własnego kodu. To całkowicie eliminuje problem - z pamięci perspektywa. Oczywiście przenoszenie obiektów i takie ma koszt. W rzeczywistości masz problem tylko wtedy, gdy często przydzielasz bardzo małe kwoty ze sterty. Używanie sąsiadujących ze sobą kontenerów (wektor, ciąg znaków, itp.) i przydzielanie na stosie w miarę ludzkich możliwości (zawsze dobry pomysł na wydajność) jest najlepszym sposobem na zmniejszenie tego. Zwiększa to również spójność pamięci podręcznej, co sprawia, że aplikacja działa szybciej.

Należy pamiętać, że na 32-bitowym pulpicie x86, masz całe 2GB pamięci, która jest podzielona na 4KB " stron "(prawie pewien, że rozmiar strony jest taki sam we wszystkich systemach x86). Będziesz musiał wywołać fragmentację omgwtfbbq, aby mieć problem. Fragmentacja jest naprawdę kwestią przeszłości, ponieważ nowoczesne stosy są zbyt duże dla zdecydowanej większości zastosowań, a istnieje rozpowszechnienie systemów, które są w stanie to wytrzymać, takich jak zarządzane stosy.