Czy są jakieś śmietniki, które uwzględniają stronicowanie?

Śmieci muszą odwiedzić wszystkie żywe obiekty, aby znaleźć pamięć, którą można odzyskać. (Posiadanie wielu pokoleń tylko trochę to opóźnia)

Mimo że wszystko jest takie samo, zdecydowanie lepiej jest najpierw odwiedzić obiekt, który jest już przywoływany do pamięci RAM, a następnie przywołać inny blok, a zatem wywołać jakiś obiekt.

Inną możliwością jest to, że gdy OS chce zabrać stronę pamięci RAM z procesu, GC jest najpierw pytana, czy ma stronę, którą można zrezygnować bez konieczności stronicowania. GC można wykonać głównie z ruchomymi obiektami ze strony, więc można wyczyścić tę stronę w terminie wymaganym przez system operacyjny na potrzeby strony.

Jednak nie mogę sobie przypomnieć żadnego śmieciarza zintegrowanego z systemem stronicowania systemu operacyjnego, który steruje kolejnością działania GC.

memory-management paging garbage-collection

— Ian Ringrose
źródło

Niezupełnie stronicowanie, ale gc ruby Enterprise Edition został przepisany w celu zmniejszenia efektu gc na kopiowanie na stronach zapisu poprzez przenoszenie metadanych obiektu na osobne strony.

— user1937198

Nieco powiązane pytanie dotyczące implementacji malloc / free: czy implementacje malloc zwrócą wolną pamięć z powrotem do systemu? , szczególnie ta odpowiedź . Ponadto: Czy free () odwzorowuje pamięć procesu?

— Paul A. Clayton

co zaskakujące, afaik / afaict, prawie cała literatura (?) gc wydaje się nie analizować stronicowania systemu operacyjnego z wyjątkiem abstrakcyjnych. pomysł: system alokacji pamięci, który śledzi wskaźniki między obiektami w strukturze oddzielnej od samych obiektów, może być bardziej przyjazny lokalnie / stronicowaniu, ponieważ tylko same wskaźniki są przemieszczane (podczas gc) w ciasno zagęszczonej przestrzeni zamiast wszystkich obiektów różne rozmiary, które mogą być rozłożone w pamięci (i niektóre rzadko dostępne i stronicowane). mogą występować pewne skromne koszty ogólne, ale może to przynieść ogólne oszczędności w zależności od wdrożenia.

— dniu

Dyski flash muszą korzystać z formy kopiowania pamięci, która uwzględnia uporządkowanie pamięci w bloki, chociaż nie wiem, jak dobrze takie rzeczy są omawiane w literaturze akademickiej. Problemy do rozwiązania są bardzo różne (dyski flash wymagają GC, ponieważ miejsce można odzyskać tylko w bardzo dużych blokach, więc jeśli blok ma kilka aktywnych stron i wiele martwych stron, dane na żywo muszą zostać skopiowane w innym miejscu przed stroną) można poddać recyklingowi), ale zasady konsolidacji danych mogą być pomocne.

— supercat

Wzorzec, którego użyłem w przypadkach, gdy wszystkie dane były małe w stosunku do mojego rozmiaru pamięci, polegał na tym, że każdy element danych składałby się ze stałej wielkości nagłówka, który był przydzielany od przodu do tyłu, oraz danych o zmiennej wielkości, które być alokowanym tyłem do przodu. Tabela zawierała zmapowane logiczne adresy porcji na adresy fizyczne i ilość wolnego miejsca w każdej porcji; po każdym skanie będzie również wskazywać, ile miejsca było martwe. Referencje były przechowywane w pamięci flash, a każda referencja miała postać „Element nr 3 logicznej porcji nr 7”. Cykl GC kopiowałby wszystkie dane na żywo z jednego fragmentu do nowego i ...

— supercat

Odpowiedzi:

O ile pamiętam, kolektory kopii powinny być przyjazne dla stronicowania, ponieważ śledzenie przez kopiowanie ma tendencję do poprawiania lokalizacji odniesień wskaźnika. Ma to pozytywny wpływ na program (mutator), który spowoduje mniej błędów strony podczas podążania za linkami, a także poprawi następny cykl zbierania, ponieważ śledzenie spowoduje również mniej błędów strony. Program śledzenia (które wskaźniki powinny zostać przetworzone w pierwszej kolejności) może mieć wpływ na skuteczność poprawiania lokalizacji danych. Można to poprawić, mierząc statystyki dotyczące liczby dostępu do różnych wskaźników w różnych typach komórek.

Teraz, jeśli weźmiesz pod uwagę kolekcjoner śledzenia w ogóle, zwykle musisz zachować strukturę, która śledzi wskaźniki, które nie zostały jeszcze wyśledzone. Może być możliwe zorganizowanie tej struktury tak, aby wszystkie oczekujące wskaźniki wskazujące na tej samej stronie były trzymane razem (chociaż może to zająć więcej miejsca, w niektórych przypadkach, w zależności od dostępnych technik utrzymania listy takich wskaźników). Możliwą zasadą jest wtedy, aby zawsze najpierw prześledzić największy zestaw wskaźników oczekujących wskazujących na tę samą stronę, gdy nie ma wskaźnika oczekującego na stronach w pamięci.

Jeśli chodzi o pytanie z trzeciego akapitu, które zostało dodane po tym, jak odpowiedziałem, kolekcja kopii jest znowu odpowiedzią. System operacyjny może zmniejszyć liczbę przydzielonych fizycznych stron w czasie zbierania, ponieważ strony są całkowicie zwolnione. W przypadku kolekcjonowania znaczników i wymiatania wydarzenie uwolnienia całej strony jest prawdopodobnie znacznie rzadsze, a zatem nie jest warte szczególnego machanizmu, który należy wziąć pod uwagę.

Tego rodzaju pomysły są naturalne i prawdopodobnie zostały opisane w niektórych artykułach. Ale nie przypominam sobie tego z ręki. Myślę, że wczesne artykuły na temat Lisp GC zawierają niektóre z tych pomysłów (na przykład: czy najpierw należy zastosować samochód czy CDR?).

Dobrą wiadomością w tej roli kopiowania kolekcji jest również to, że stronicowanie jest przyjazne dla kopiowania kolekcji, ponieważ zwiększa dostępną przestrzeń dyskową. Przypomnijmy, że moduł zbierający kopie wymaga zasadniczo dwa razy więcej miejsca niż używany do faktycznego przechowywania danych. Teraz efekt stronicowania zależy również od przestrzeni adresowej komputera i dostępnej pamięci fizycznej. Na starszym komputerze pamięć fizyczna była znacznie mniejsza niż dostępna przestrzeń adresowa, więc stronicowanie było naprawdę dodatkową przestrzenią, umożliwiając takie zasady, jak kopiowanie GC. Nawet gdy przestrzeń fizyczna jest tak duża jak przestrzeń adresowa, można chcieć ją udostępnić, aby proces korzystający z GC miał mniej przestrzeni adresowej bez stronicowania (patrz stronicowanie). Uwagi te są nieco zastąpione przez zastosowanie kolektorów pokoleniowych. Zasadniczo używają kolekcji kopii dla młodego pokolenia właśnie ze względu na te cechy i dlatego, że młode pokolenie jest przeważnie krótkotrwałe.

Masz wtedy wszystkie interakcje generacyjnej GC z systemem pamięci podręcznej, co zostało omówione w poprzednim pytaniu: Czy generatory śmieci są z natury przyjazne dla pamięci podręcznej?

Aby uzyskać więcej informacji na ten temat, szukałbym w Internecie, na przykład, słów kluczowych wyrzucanie elementów bezużytecznych i lokalizacja .

— Babou
źródło

Mam wątpliwości, czy kolektory kopii są w rzeczywistości bardziej „lokalne” niż śledzenie. kolektory kopii wydają się koncepcyjnie dość podobne pod względem dynamiki dostępu do pamięci (być może prawie nie do odróżnienia) do śledzenia „starej przestrzeni”. myślę, że to wymaga odniesienia. powiedział, że istnieje pewna możliwość mechanizmu kopiowania poprawiającego ciągłość w nowej przestrzeni. nowa przestrzeń zaczyna się doskonale przylegle, ale z czasem ta „lokalizacja” maleje lub pogarsza się.

— dniu

Znalazłeś większość odpowiedzi. Więc nie wątpcie. Jest w podstawowych źródłach na ten temat. Lokalność wynika z faktu, że pamięć jest zwarta, oraz z kopiowania, które zastępuje blisko siebie komórki danych, które są logicznie bliskie zgodnie ze strukturą wskaźnika (które mogą ewoluować wraz z ponownym przypisaniem wskaźnika).

— babou

wciąż jestem sceptyczny / wątpliwy. wydaje się intuicyjnie, że stara przestrzeń będzie miała słabą lokalizację i / lub ciągłość po zainicjowaniu cyklu kopiowania / gc. lokalizacja jest powiązana z odczytami (ze starej przestrzeni) i zapisami (do nowej przestrzeni). aby to przeanalizować, należy zbadać zachowanie gestalt / emergent. być może wiele z tego można tylko skutecznie / dokładnie / realistycznie zbadać empirycznie i nie wiele teoretycznie.

— dniu

Mówię, że tak jest w literaturze, jak wiele innych rzeczy. Ale nie mam czasu na szukanie i myślę, że moja odpowiedź jest długa i pełna informacji., Możesz google: lokalizacja kopiowania pamięci i istnieje odniesienie do poprzedniego pytania. Przepraszam, że jestem zwięzły, mam pociąg do złapania.

— babou

Przepraszam ... pomyl to pytanie z innym ... który ma więcej.

— babou

Emery Berger, Matthew Hertz i Yi Feng pracowali nad tym.

Wyrzucanie elementów bezużytecznych oferuje wiele zalet inżynierii oprogramowania, ale źle współdziała z menedżerami pamięci wirtualnej. Istniejące kolektory śmieci wymagają znacznie więcej stron niż zestaw roboczy aplikacji i stron dotykowych, bez względu na to, które z nich są w pamięci, szczególnie podczas pełnego wyrzucania elementów bezużytecznych. Wynikowe stronicowanie może spowodować spadek przepustowości i skrócenie czasów pauzy do sekund lub nawet minut.

Przedstawiam śmietnik, który unika stronicowania. Ten kolektor zakładek współpracuje z menedżerem pamięci wirtualnej, aby kierować jego decyzjami dotyczącymi eksmisji.

To jest wideo z rozmowy Emery'ego na ten temat, a on napisał papierową wersję Śmieci bez stronicowania

Z niektórych powodów wydaje się, że nie będzie o wiele późniejszej pracy nad tym ani użycia w „świecie rzeczywistym”. Na końcu artykułu napisano: „Opracowujemy równoległy wariant algorytmu zbierania zakładek” , ale nie mogę go wyśledzić.

CRAMM: Obsługa pamięci wirtualnej dla aplikacji Garbage-Collected sprawdza zmianę systemu operacyjnego, aby GC tworzyło mniej stronicowania.

Wykorzystanie rezydencji strony do zrównoważenia kompromisów w śledzeniu usuwania śmieci

Wprowadzamy rozszerzenie głównie kolekcji kopiowania, które korzysta z rezydencji stron w celu ustalenia, kiedy przenieść obiekty. Nasz kolektor promuje strony o wysokiej rezydencji na miejscu, unikając niepotrzebnej pracy i marnowanej przestrzeni. Przewiduje rezydencję każdej strony, ale gdy jego przewidywania okażą się niedokładne, nasz kolektor odzyskuje niezajętą przestrzeń, wykorzystując ją do zaspokojenia żądań alokacji. Korzystanie z rezydencji pozwala naszemu kolektorowi dynamicznie równoważyć kompromisy związane z kopiowaniem i nie kopiowaniem kolekcji. Nasza technika wymaga mniej miejsca niż zwykły moduł kopiujący i obsługuje przypinanie obiektów bez poświęcania możliwości przemieszczania obiektów. W przeciwieństwie do innych hybryd nasz kolektor nie zależy od konfiguracji specyficznej dla aplikacji i może szybko reagować na zmieniające się zachowanie aplikacji. Nasze pomiary pokazują, że nasza hybryda działa dobrze w różnych warunkach; woli kopiować kolekcję, gdy jest wystarczająco dużo miejsca na sterty, ale wraca do kolekcji bez kopiowania, gdy przestrzeń staje się ograniczona.

— Ian Ringrose
źródło