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

12

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.

deadalnix
źródło

Odpowiedzi:

16

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:

Sokół
źródło
5

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 ...

komar
źródło
5

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.

TMN
źródło
Ładny ! Szkoda, że ​​nie mam dostępu do ACM, ten artykuł wygląda naprawdę interesująco.
deadalnix
2

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.

DeadMG
źródło
Nie jest to wystarczające, o ile referencje te mogą być aktualizowane w dowolnym momencie przez dowolny wątek.
deadalnix