Jakie algorytmy kryją się za GC z niską pauzą?

Niektóre języki, na przykład java, wprowadziły GC z małą pauzą.

Ci GC mogą wykonać większość pracy bez zatrzymywania całego świata. Jest to oczywiście dość trudny problem, ponieważ wymaga analizy pamięci, gdy wątek ją modyfikuje, w wyniku czego powstają dane, które można wykorzystać na początku procesu, a nie już po jego zakończeniu, lub dane, które wyglądają jak garaże, ale ponieważ odniesienie zostało przeniesione do pamięci i nigdy nie pojawiło się tam, gdzie patrzył GC.

Zasadniczo, za czym stoi algorytm (algorytmy)?

Artykuły badawcze lub link do naprawdę technicznego artykułu można uznać za prawidłową odpowiedź, ponieważ ten temat jest naprawdę techniczny.

Zasadniczo, za czym stoi algorytm (algorytmy)?

Jest to w zasadzie algorytm znakowania i przeciągania, który „po prostu” działa jednocześnie w osobnym wątku.

Jeśli chodzi o prace badawcze na ten temat:

• Bardzo równoczesne zbieranie znaków i zamiatanie śmieci bez synchronizacji precyzyjnej

• Jednoczesny kolektor garbabe mark-sweep (zawiera linki do dwóch artykułów, jeden wymieniony poniżej)

• Wdrażanie modułu Garbage Collector w Javie w czasie rzeczywistym

• Przenośny, dyskretny system usuwania śmieci dla systemów wieloprocesorowych (Doligez Leroy, prezentacja Powerpoint)

• Odrzucanie śmieci w locie: ćwiczenie we współpracy (autor: Edsger Wybe Djikstra)

o ile rozumiem, moduł śmieciowy Java G1 wykorzystuje tak zwane regiony sterty, aby uniknąć pauzowania całego świata. Widzę, że chociaż jeden z regionów jest zablokowany przez GC wykonującego czyszczenie, alokacja pamięci odbywa się w innym regionie.

Oto wyjaśnienie Jeremy'ego Mansona :

Zasada jest prosta: kolektor dzieli stertę na regiony o stałej wielkości i śledzi dane na żywo w tych regionach. Utrzymuje zestaw wskaźników - „zapamiętany zestaw” - w regionie i poza nim. Gdy GC zostanie uznane za konieczne, najpierw zbiera regiony z mniej aktywnymi danymi (stąd „najpierw śmieci”). Często może to oznaczać zebranie całego regionu w jednym kroku: jeśli liczba wskaźników w regionie wynosi zero, to nie musi robić zaznaczenia ani zamiatania tego regionu ...

• oto dokument techniczny od inżynierów Sun wyjaśniający ich projekt: Garbage-First Garbage Collection

JVM firmy IBM w czasie rzeczywistym wykorzystuje moduł zbierający śmieci o nazwie Metronome, który dzieli aktywność GC na dyskretne kwanty i przeplata je podczas przetwarzania aplikacji. Zasadniczo zamiast okresowych (i niedeterministycznych) zatrzymań GC w przestoju, aplikacja działa nieco wolniej, podczas gdy GC odbywa się równolegle.

Jest jeszcze jeden GC, który dokonuje dynamicznej defragmentacji i spełnia wymagania w czasie rzeczywistym, ale jedyne źródło, jakie mogę znaleźć, jest tutaj (wymagane członkostwo w ACM).

Interesujący współbieżny śmieciarz w czasie rzeczywistym jest nieograniczony . Wykorzystuje tradycyjne podejście mark-and-sweep, ale jest przeznaczone do stosowania w systemach wieloprocesorowych i obsługuje równoczesną wielowątkowość bez blokady.

Powodem tego jest to, że w Javie tylko GC może zwolnić pamięć, która może zawierać odwołania GC. Oznacza to, że tak długo, jak można bezpiecznie odczytywać obiekty w oddzielnym wątku, wystarczy wstrzymać program, aby obserwował odniesienia na stosie.

Sugerowałbym dla mutacji, aby wdrożyli jakąś formę kopiowania na piśmie, aby poinformować GC o zmianie.