Słyszałem termin „fragmentacja pamięci” użyty kilka razy w kontekście dynamicznej alokacji pamięci w C ++. Znalazłem kilka pytań na temat tego, jak radzić sobie z fragmentacją pamięci, ale nie mogę znaleźć bezpośredniego pytania, które sobie z tym poradzi. Więc:
- Co to jest fragmentacja pamięci?
- Jak sprawdzić, czy fragmentacja pamięci stanowi problem dla mojej aplikacji? Jaki program najbardziej ucierpi?
- Jakie są dobre powszechne sposoby radzenia sobie z fragmentacją pamięci?
Również:
- Słyszałem, że przy użyciu alokacji dynamicznych wiele może zwiększyć fragmentację pamięci. Czy to prawda? W kontekście C ++ rozumiem, że wszystkie standardowe kontenery (std :: string, std :: vector itp.) Używają dynamicznej alokacji pamięci. Jeśli są one używane w całym programie (zwłaszcza std :: string), czy fragmentacja pamięci jest bardziej prawdopodobna?
- Jak poradzić sobie z fragmentacją pamięci w aplikacji obciążonej STL?
c++
memory
heap
fragmentation
AshleysBrain
źródło
źródło
Odpowiedzi:
Wyobraź sobie, że masz „dużą” (32 bajty) przestrzeń wolnej pamięci:
Teraz przydziel część (5 alokacji):
Teraz uwolnij pierwsze cztery przydziały, ale nie piąty:
Teraz spróbuj przydzielić 16 bajtów. Ups, nie mogę, mimo że jest prawie dwa razy tyle za darmo.
W systemach z pamięcią wirtualną fragmentacja stanowi mniejszy problem, niż mogłoby się wydawać, ponieważ duże alokacje muszą być ciągłe tylko w wirtualnej przestrzeni adresowej, a nie w fizycznej przestrzeni adresowej. Tak więc w moim przykładzie, gdybym miał pamięć wirtualną o wielkości strony 2 bajty, bez problemu mógłbym dokonać alokacji 16 bajtów. Pamięć fizyczna wyglądałaby tak:
mając na uwadze, że pamięć wirtualna (znacznie większa) może wyglądać następująco:
Klasycznym objawem fragmentacji pamięci jest to, że próbujesz przydzielić duży blok i nie możesz tego zrobić, nawet jeśli wydaje się, że masz wystarczającą ilość wolnej pamięci. Inną możliwą konsekwencją jest niezdolność procesu do zwolnienia pamięci z powrotem do systemu operacyjnego (ponieważ we wszystkich blokach przydzielonych przez system operacyjny nadal jest używany obiekt, mimo że te bloki są w większości nieużywane).
Taktyki zapobiegania fragmentacji pamięci w C ++ działają poprzez przydzielanie obiektów z różnych obszarów zgodnie z ich wielkością i / lub oczekiwanym czasem życia. Więc jeśli zamierzasz stworzyć wiele obiektów i zniszczyć je wszystkie razem później, przydziel je z puli pamięci. Wszelkie inne alokacje, które dokonujesz między nimi, nie będą pochodzić z puli, a zatem nie będą znajdować się między nimi w pamięci, więc pamięć nie zostanie podzielona na fragmenty.
Zasadniczo nie musisz się tym zbytnio przejmować, chyba że twój program jest długotrwały i dużo alokuje i zwalnia. Najbardziej zagrożone są mieszanki krótko i długo żyjących obiektów, ale nawet wtedy
malloc
zrobią wszystko, co w ich mocy, aby pomóc. Zasadniczo należy go zignorować, dopóki program nie będzie miał problemów z alokacją lub nieoczekiwanie spowoduje, że w systemie zacznie brakować pamięci (najlepiej przechwyć to podczas testowania!).Standardowe biblioteki nie są gorsze od wszystkiego, co alokuje pamięć, a wszystkie standardowe pojemniki mają
Alloc
parametr szablonu, którego można użyć do dostrojenia strategii alokacji, jeśli jest to absolutnie konieczne.źródło
ffffffffffffffff
jest ciągłym przydziałem w pamięci wirtualnej, ale taki ciągły przydział nie może istnieć w pamięci fizycznej. Jeśli wolisz spojrzeć na to, że są one równo podzielone, ale przestrzeń wirtualna jest znacznie większa, możesz zamiast tego spojrzeć na nią w ten sposób. Ważną praktyczną kwestią jest to, że używanie rozległych wirtualnych przestrzeni adresowych często wystarcza, aby móc zignorować fragmentację, więc pomaga, gdy pozwala mi na 16-bajtową alokację.Fragmentacja pamięci ma miejsce, gdy większość pamięci jest przydzielana w dużej liczbie nieciągłych bloków lub porcji - pozostawiając znaczny procent całkowitej pamięci nieprzydzielony, ale nieużywalny w większości typowych scenariuszy. Powoduje to wyjątki braku pamięci lub błędy alokacji (tj. Malloc zwraca wartość null).
Najłatwiej to sobie wyobrazić, wyobrażając sobie, że masz dużą pustą ścianę, na której musisz umieścić zdjęcia o różnych rozmiarach . Każde zdjęcie zajmuje określony rozmiar i oczywiście nie można go podzielić na mniejsze części, aby dopasować. Potrzebujesz pustego miejsca na ścianie, wielkości zdjęcia, bo inaczej nie możesz go postawić. Teraz, jeśli zaczniesz wieszać zdjęcia na ścianie i nie będziesz ostrożny, jak je ułożysz, wkrótce skończysz ze ścianą częściowo pokrytą zdjęciami i chociaż możesz mieć puste miejsca, większość nowych zdjęć nie będzie pasować ponieważ są większe niż dostępne miejsca. Nadal możesz zawiesić naprawdę małe zdjęcia, ale większość nie będzie pasować. Musisz więc zmienić układ (kompaktowy) już na ścianie, aby zrobić miejsce na więcej ...
Teraz wyobraź sobie, że ściana jest twoją pamięcią (stertą), a zdjęcia to obiekty .. To fragmentacja pamięci ..
Jak sprawdzić, czy fragmentacja pamięci stanowi problem dla mojej aplikacji? Jaki program najbardziej ucierpi?
Znamiennym sygnałem, że możesz mieć do czynienia z fragmentacją pamięci jest to, że wystąpi wiele błędów alokacji, szczególnie gdy odsetek wykorzystanej pamięci jest wysoki - ale nie wykorzystałeś jeszcze całej pamięci - więc technicznie powinieneś mieć dużo miejsca dla obiektów, które próbujesz przydzielić.
Gdy pamięć jest silnie rozdrobniona, alokacja pamięci prawdopodobnie potrwa dłużej, ponieważ alokator pamięci musi wykonać więcej pracy, aby znaleźć odpowiednią przestrzeń dla nowego obiektu. Jeśli z kolei masz wiele alokacji pamięci (co prawdopodobnie robisz, odkąd skończyło się fragmentacją pamięci), czas alokacji może nawet spowodować zauważalne opóźnienia.
Jakie są dobre powszechne sposoby radzenia sobie z fragmentacją pamięci?
Użyj dobrego algorytmu do przydzielania pamięci. Zamiast alokować pamięć dla wielu małych obiektów, wstępnie przydziel pamięć dla ciągłej tablicy tych mniejszych obiektów. Czasami trochę marnotrawstwa podczas przydzielania pamięci może iść w parze z wydajnością i może zaoszczędzić kłopotów z radzeniem sobie z fragmentacją pamięci.
źródło
Fragmentacja pamięci to ta sama koncepcja, co fragmentacja dysku: odnosi się do marnowania miejsca, ponieważ używane obszary nie są wystarczająco blisko siebie upakowane.
Załóżmy, że dla prostego przykładu z zabawką masz dziesięć bajtów pamięci:
Teraz przydzielmy trzy trzy bajtowe bloki o nazwach A, B i C:
Teraz cofnij przydział bloku B:
Co się stanie, jeśli spróbujemy przydzielić czterobajtowy blok D? Cóż, mamy cztery bajty wolnej pamięci, ale nie mamy czterech sąsiadujących bajtów wolnej pamięci, więc nie możemy przydzielić D! Jest to nieefektywne wykorzystanie pamięci, ponieważ powinniśmy móc przechowywać D, ale nie byliśmy w stanie. I nie możemy przesunąć 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.
Skąd wiesz, że to problem? Cóż, największym znakiem jest to, że rozmiar pamięci wirtualnej twojego programu jest znacznie większy niż ilość pamięci, której faktycznie używasz. W prawdziwym przykładzie miałbyś dużo więcej niż dziesięć bajtów pamięci, więc D zostałby przydzielony zaczynając od bajtu 9, a bajty 3-5 pozostałyby nieużywane, chyba że później przydzielisz coś o długości trzech bajtów lub mniejszej.
W tym przykładzie 3 bajty to nie wiele do stracenia, ale rozważ bardziej patologiczny przypadek, w którym dwa przydziały pary bajtów to na przykład dziesięć megabajtów pamięci i trzeba przydzielić blok o wielkości 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 brakuje Ci już tylko jednego bajta.
Jak temu zapobiec? Najgorsze przypadki zdarzają się, gdy często tworzysz i niszczysz małe obiekty, ponieważ powoduje to efekt „szwajcarskiego sera” z wieloma małymi przedmiotami oddzielonymi przez wiele małych otworów, uniemożliwiając przydzielenie większych obiektów w tych otworach. Gdy wiesz, że zamierzasz to robić, skuteczną strategią jest wstępne przydzielenie dużego bloku pamięci jako puli dla małych obiektów, a następnie ręczne zarządzanie tworzeniem małych obiektów w tym bloku, zamiast pozwalania domyślny alokator obsługuje to.
Ogólnie rzecz biorąc, im mniej alokacji, tym mniej prawdopodobne jest rozdrobnienie pamięci. Jednak STL radzi sobie z tym dość skutecznie. Jeśli masz ciąg znaków, który korzysta z całej jego bieżącej alokacji i dołączysz do niego jeden znak, nie po prostu ponownie alokuje do swojej bieżącej długości plus jeden, podwaja jego długość. Jest to odmiana strategii „pula częstych małych przydziałów”. Łańcuch chwyta dużą część pamięci, dzięki czemu może skutecznie radzić sobie z powtarzającymi się niewielkimi wzrostami rozmiaru bez powtarzających się małych przesunięć. Wszystkie kontenery STL w rzeczywistości robią takie rzeczy, więc ogólnie nie musisz się zbytnio martwić fragmentacją spowodowaną automatycznym realokowaniem kontenerów STL.
Choć oczywiście nie kontenery STL puli pamięci między sobą, więc jeśli masz zamiar stworzyć wiele małych pojemników (zamiast kilku pojemników, które się często zmieniany) może trzeba martwić się o zapobieganie fragmentacji w taki sam sposób, w jaki będzie dla każdego często tworzonego małego obiektu, STL lub nie.
źródło
Fragmentacja pamięci polega na tym, że pamięć staje się bezużyteczna, mimo że jest teoretycznie dostępna. Istnieją dwa rodzaje fragmentacji: fragmentacja wewnętrzna to pamięć, która jest alokowana, ale nie można jej użyć (np. Gdy pamięć jest alokowana na 8 bajtowe porcje, ale program wielokrotnie wykonuje pojedyncze alokacje, gdy potrzebuje tylko 4 bajtów). fragmentacja zewnętrzna polega na tym, że wolna pamięć zostaje podzielona na wiele małych porcji, tak że nie można spełnić dużych żądań alokacji, chociaż jest wystarczająca ilość wolnej pamięci.
fragmentacja pamięci jest problemem, jeśli twój program zużywa znacznie więcej pamięci systemowej, niż wymagałyby jej faktyczne dane płatne (i wykluczyłeś przecieki pamięci).
Użyj dobrego alokatora pamięci. IIRC te, które stosują strategię „najlepszego dopasowania”, są na ogół znacznie lepsze w unikaniu fragmentacji, jeśli są nieco wolniejsze. Wykazano jednak również, że w przypadku każdej strategii alokacji występują najgorsze przypadki patologiczne. Na szczęście typowe wzorce alokacji większości aplikacji są w rzeczywistości względnie łagodne dla alokatorów. Istnieje wiele dokumentów, jeśli interesują Cię szczegóły:
źródło
Aktualizacja:
Google TCMalloc: Malloc buforowania wątków
Stwierdzono, że jest całkiem dobry w radzeniu sobie z fragmentacją w długim procesie.
Pracuję nad aplikacją serwera, która miała problemy z fragmentacją pamięci w systemie HP-UX 11.23 / 11.31 ia64.
Tak to wyglądało. Był proces, który dokonywał alokacji pamięci i dezalokacji i trwał kilka dni. I chociaż nie było wycieków pamięci, zużycie pamięci przez proces stale rosło.
O moim doświadczeniu. W systemie HP-UX bardzo łatwo jest znaleźć fragmentację pamięci za pomocą gdb HP-UX. Ustawiasz punkt przerwania, a po jego naciśnięciu uruchamiasz to polecenie:
info heap
i widzisz wszystkie alokacje pamięci dla procesu oraz całkowity rozmiar sterty. Następnie kontynuuj program, a jakiś czas później ponownie osiągniesz punkt krytyczny. Znowu to robiszinfo heap
. Jeśli całkowity rozmiar sterty jest większy, ale liczba i rozmiar oddzielnych przydziałów są takie same, prawdopodobnie występują problemy z przydziałem pamięci. W razie potrzeby sprawdź to kilka razy.Mój sposób na poprawę sytuacji był taki. Po przeprowadzeniu analizy za pomocą HP-UX gdb zauważyłem, że problemy z pamięcią były spowodowane faktem, że użyłem
std::vector
do przechowywania niektórych rodzajów informacji z bazy danych.std::vector
wymaga, aby jego dane były przechowywane w jednym bloku. Miałem kilka kontenerów na podstawiestd::vector
. Te pojemniki były regularnie odtwarzane. Często zdarzały się sytuacje, gdy do bazy danych dodawano nowe rekordy, a następnie odtwarzano kontenery. Ponieważ odtworzone pojemniki były większe, nie mieściły się w dostępnych blokach wolnej pamięci, a środowisko wykonawcze poprosiło o nowy większy blok z systemu operacyjnego. W rezultacie, pomimo braku wycieków pamięci, zużycie pamięci procesu wzrosło. Poprawiłem sytuację, kiedy zmieniłem pojemniki. Zamiaststd::vector
zacząłem używaćstd::deque
który ma inny sposób przydzielania pamięci dla danych.Wiem, że jednym ze sposobów uniknięcia fragmentacji pamięci w systemie HP-UX jest użycie programu Small Block Allocator lub MallocNextGen. W systemie RedHat Linux domyślny alokator wydaje się radzić sobie całkiem dobrze z alokacją wielu małych bloków. W systemie Windows istnieje
Low-fragmentation Heap
i rozwiązuje problem dużej liczby małych przydziałów.Rozumiem, że w aplikacji obciążonej STL musisz najpierw zidentyfikować problemy. Dzielniki pamięci (jak w libc) faktycznie radzą sobie z problemem wielu małych alokacji, co jest typowe
std::string
(na przykład w mojej aplikacji serwera jest wiele ciągów STL, ale jak widzę po uruchomieniuinfo heap
, nie powodują żadnych problemów). Mam wrażenie, że musisz unikać częstych dużych alokacji. Niestety zdarzają się sytuacje, w których nie można ich uniknąć i trzeba zmienić kod. Jak mówię w moim przypadku poprawiłem sytuację po przełączeniu nastd::deque
. Jeśli zidentyfikujesz fragmentację pamięci, możliwe, że będziesz mógł mówić o tym bardziej precyzyjnie.źródło
Fragmentacja pamięci jest najbardziej prawdopodobna, gdy przydzielasz i zwalniasz wiele obiektów o różnych rozmiarach. Załóżmy, że masz w pamięci następujący układ:
Teraz, kiedy
obj2
zostanie zwolniony, masz 120 kb nieużywanej pamięci, ale nie możesz przydzielić pełnego bloku 120 kb, ponieważ pamięć jest pofragmentowana.Typowe techniki unikania tego efektu obejmują bufory pierścieniowe i pule obiektów . W kontekście STL takie metody
std::vector::reserve()
mogą pomóc.źródło
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 odpowiedzi na fragmentację pamięci, które udzielam osobom, które zadają mi pytania dotyczące fragmentacji pamięci na stronie softwareverify.com
źródło
Gdy aplikacja korzysta z pamięci dynamicznej, przydziela i zwalnia fragmenty pamięci. Na początku cała pamięć Twojej aplikacji to ciągły blok wolnej pamięci. Jednak gdy przydzielisz i zwolnisz bloki o różnej wielkości, pamięć zaczyna się fragmentować , tzn. Zamiast dużego ciągłego wolnego bloku i pewnej liczby ciągłych przydzielonych bloków, zmienią się przydzielone i wolne bloki. Ponieważ wolne bloki mają ograniczony rozmiar, ich ponowne użycie jest trudne. Np. Możesz mieć 1000 bajtów wolnej pamięci, ale nie możesz przydzielić pamięci na blok 100 bajtów, ponieważ wszystkie wolne bloki mają maksymalnie 50 bajtów długości.
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 granic bajtów 2, 4, 8 itd. (Tzn. Adresy muszą być wielokrotnościami 2, 4, 8 itd.) Oznacza to, że nawet jeśli masz np. strukturę zawierającą 3
char
pola, twoja struktura może mieć rozmiar 12 zamiast 3, ze względu na fakt, że każde pole jest wyrównane do granicy 4 bajtów.Oczywistą odpowiedzią jest to, że otrzymujesz wyjątek braku pamięci.
Najwyraźniej nie ma dobrego przenośnego sposobu na wykrycie fragmentacji pamięci w aplikacjach C ++. Zobacz tę odpowiedź, aby uzyskać więcej informacji.
Jest to trudne w C ++, ponieważ używasz bezpośrednich adresów pamięci we wskaźnikach i nie masz kontroli nad tym, kto odwołuje się do określonego adresu pamięci. Zatem przestawianie przydzielonych bloków pamięci (tak jak robi to moduł śmieciowy Java) nie jest opcją.
Niestandardowy alokator może pomóc, zarządzając alokacją małych obiektów w większej części pamięci i ponownie wykorzystując wolne miejsca w tej części.
źródło
To jest bardzo uproszczona wersja dla manekinów.
Gdy obiekty są tworzone w pamięci, są dodawane na końcu używanej części pamięci.
Jeśli obiekt, który nie znajduje się na końcu użytej części pamięci, zostanie usunięty, co oznacza, że obiekt ten znajdował się pomiędzy 2 innymi obiektami, utworzy „dziurę”.
To się nazywa fragmentacja.
źródło
Gdy chcesz dodać element do stosu, dzieje się tak, że komputer musi wyszukać miejsce, aby zmieścić ten element. Dlatego dynamiczne alokacje, gdy nie są wykonywane w puli pamięci lub w puli alokatora, mogą „spowolnić”. W przypadku ciężkiej aplikacji STL, jeśli wykonujesz wielowątkowość, istnieje alokator Hoard lub wersja Intel TBB .
Teraz, gdy pamięć jest podzielona, mogą wystąpić dwie rzeczy:
źródło
Fragmentacja pamięci występuje, ponieważ wymagane są bloki pamięci o różnych rozmiarach. Rozważ bufor 100 bajtów. Żądasz dwóch znaków, a następnie liczby całkowitej. Teraz uwalniasz dwa znaki, a następnie żądasz nowej liczby całkowitej - ale ta liczba całkowita nie może zmieścić się w przestrzeni dwóch znaków. Ta pamięć nie może być ponownie wykorzystana, ponieważ nie znajduje się w wystarczająco dużym, ciągłym bloku, aby można ją było ponownie przydzielić. Poza tym wywołałeś dużo narzutnika dla twoich znaków.
Zasadniczo pamięć jest dostępna tylko w blokach o określonym rozmiarze w większości systemów. Po podzieleniu tych bloków nie można połączyć ich ponownie, dopóki cały blok nie zostanie uwolniony. Może to prowadzić do użycia całych bloków, gdy w rzeczywistości używana jest tylko niewielka część bloku.
Podstawowym sposobem zmniejszenia fragmentacji sterty jest dokonywanie większych, rzadziej przydzielanych przydziałów. W skrajnym przypadku możesz użyć zarządzanej sterty, która jest w stanie przenosić obiekty przynajmniej w obrębie własnego kodu. To całkowicie eliminuje problem - w każdym razie z perspektywy pamięci. Oczywiście ruchome obiekty i takie mają swój koszt. W rzeczywistości problem występuje tylko wtedy, gdy często przeznaczasz bardzo małe kwoty na stos. Używanie ciągłych kontenerów (wektor, ciąg itp.) I przydzielanie na stos tak dużo, jak to tylko możliwe (co jest dobrym pomysłem na wydajność), jest najlepszym sposobem na jego zmniejszenie. Zwiększa to również spójność pamięci podręcznej, co przyspiesza działanie aplikacji.
Należy pamiętać, że w 32-bitowym systemie stacjonarnym x86 masz całe 2 GB pamięci, która jest podzielona na „strony” 4KB (całkiem pewne, ż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ż współczesne sterty są zbyt duże w przypadku ogromnej większości aplikacji, i istnieje przewaga systemów, które są w stanie to wytrzymać, takich jak sterowane sterty.
źródło
Dobrym (= przerażającym) przykładem problemów związanych z fragmentacją pamięci było opracowanie i wydanie „Elemental: War of Magic” , gry komputerowej firmy Stardock .
Gra została zbudowana dla 32-bitowej pamięci / 2 GB i musiała wiele zoptymalizować w zarządzaniu pamięcią, aby gra działała w obrębie tych 2 GB pamięci. Ponieważ „optymalizacja” prowadzi do ciągłego przydzielania i rozdzielania, z czasem dochodziło do fragmentacji pamięci sterty i powodowało awarię gry za każdym razem .
Na YouTube jest wywiad z „historią wojenną” .
źródło