Трассирующая сборка мусора: управление памятью в программировании

Введение

Форма управления памятью компьютера

В компьютерном программировании, сборка мусора путем трассировки — это форма автоматического управления памятью, которая заключается в определении объектов, подлежащих освобождению ("сбору мусора"), путем отслеживания объектов, до которых можно добраться по цепочке ссылок, начиная с определенных "корневых" объектов, и признании остальных объектов "мусором" с последующим их сбором. Трассировка — наиболее распространенный тип сборки мусора, настолько, что под термином "сборка мусора" часто подразумевается именно метод трассировки, а не другие методы, такие как подсчет ссылок, и для его реализации используется большое количество алгоритмов.

Сильные и слабые ссылки

Сборщик мусора может освободить только те объекты, на которые нет ссылок, указывающих на них напрямую или косвенно из корневого набора. Однако некоторые программы требуют слабых ссылок, которые должны быть доступны до тех пор, пока объект существует, но не должны продлевать его время жизни. В обсуждениях слабых ссылок обычные ссылки иногда называют сильными ссылками. Объект становится кандидатом на сборку мусора, если на него нет сильных (т.е. обычных) ссылок, даже если на него все еще могут быть слабые ссылки. Слабая ссылка – это не просто любой указатель на объект, который сборщик мусора игнорирует. Этот термин обычно зарезервирован для правильно управляемой категории специальных объектов-ссылок, которые безопасны в использовании даже после исчезновения объекта, поскольку они переходят в безопасное состояние (обычно null). Небезопасная ссылка, о которой сборщик мусора не знает, просто останется висячей, продолжая указывать на адрес, где ранее находился объект. Это не слабая ссылка. В некоторых реализациях слабые ссылки подразделяются на подкатегории. Например, виртуальная машина Java предоставляет три типа слабых ссылок: мягкие ссылки, фантомные ссылки и обычные слабые ссылки. Объект, на который есть мягкая ссылка, становится кандидатом на освобождение только в том случае, если сборщик мусора решит, что в программе недостаточно памяти. В отличие от мягкой ссылки или обычной слабой ссылки, фантомная ссылка не предоставляет доступа к объекту, на который она указывает. Вместо этого, фантомная ссылка – это механизм, позволяющий сборщику мусора уведомлять программу о том, что объект стал фантомно досягаемым. Объект является фантомно досягаемым, если он все еще находится в памяти и на него ссылается фантомная ссылка, но его финализатор уже был выполнен. Аналогично, Microsoft .NET предоставляет две подкатегории слабых ссылок: длинные слабые ссылки (отслеживающие воскрешение) и короткие слабые ссылки.

Слабые сборы

Также можно разработать структуры данных, обладающие слабыми возможностями отслеживания. Например, полезны слабые хэш-таблицы. Подобно обычной хэш-таблице, слабая хэш-таблица поддерживает связь между парами объектов, где каждая пара рассматривается как ключ и значение. Однако хэш-таблица фактически не поддерживает сильную ссылку на эти объекты. Происходит особое поведение, когда ключ, значение или оба становятся недостижимыми для сборщика мусора: запись в хэш-таблице автоматически удаляется. Существуют и другие варианты, такие как хэш-таблицы, имеющие только слабые ключи (ссылки на значения являются обычными, сильными ссылками) или только слабые значения (ссылки на ключи являются сильными). Слабые хэш-таблицы важны для поддержания ассоциаций между объектами, позволяя объектам, участвующим в ассоциации, все равно стать недостижимыми, если на них больше нет ссылок в программе (кроме самой хэш-таблицы, поддерживающей ассоциацию). Использование обычной хэш-таблицы для этой цели может привести к "логической утечке памяти": накоплению доступных данных, которые программе не нужны и которые она не будет использовать.

Основной алгоритм

Следовые сборщики мусора получили своё название из-за того, что они прослеживают рабочий набор памяти. Эти сборщики мусора выполняют сборку мусора циклически. Обычно циклы запускаются, когда недостаточно свободной памяти для удовлетворения запроса на выделение памяти менеджером памяти. Однако циклы могут быть инициированы напрямую мутатором или выполняться по расписанию. Изначальный метод предполагает наивную разметку и очистку, при которой весь набор памяти просматривается несколько раз.

Наивный маркер и прочесывание

В наивном методе маркировки и прочистки каждый объект в памяти имеет флаг (обычно один бит), зарезервированный исключительно для использования сборщиком мусора. Этот флаг всегда сбрасывается, за исключением цикла сборки. Первый этап – это этап маркировки, который выполняет обход дерева всего "набора корней" и помечает каждый объект, на который указывает корень, как "в использовании". Все объекты, на которые указывают эти объекты, и так далее, также помечаются, таким образом, каждый объект, достижимый из набора корней, будет помечен. На втором этапе, этапе прочистки, вся память просматривается от начала до конца, анализируя все свободные или используемые блоки; те, которые не помечены как "в использовании", недоступны ни из одного корня, и их память освобождается. Для объектов, которые были помечены как используемые, флаг "в использовании" сбрасывается, подготавливая к следующему циклу. Этот метод имеет несколько недостатков, наиболее существенным из которых является необходимость полной остановки системы во время сборки; любые изменения рабочего набора недопустимы. Это может приводить к периодическим (и, как правило, непредсказуемым) "зависаниям" программ, что делает невозможным использование в некоторых приложениях реального времени и критичных ко времени. Кроме того, необходимо просматривать всю рабочую память, причем большую ее часть дважды, что потенциально может вызывать проблемы в системах с постраничной организацией памяти.

Движение против недвижения

После того, как недостижимый набор был определен, сборщик мусора может просто освободить недостижимые объекты и оставить все остальное без изменений, либо скопировать некоторые или все достижимые объекты в новую область памяти, обновляя все ссылки на эти объекты по мере необходимости. Они называются сборщиками мусора с "неперемещением" и "перемещением" (или, альтернативно, "некомпактифицирующими" и "компактифицирующими") соответственно. На первый взгляд, алгоритм перемещения может показаться неэффективным по сравнению с алгоритмом без перемещения, поскольку кажется, что на каждый цикл требуется гораздо больше работы. Однако алгоритм перемещения приводит к нескольким преимуществам в производительности как во время самого цикла сбора мусора, так и во время выполнения программы: не требуется дополнительной работы для освобождения пространства, занятого удаленными объектами; вся область памяти, из которой были перемещены достижимые объекты, может считаться свободным пространством. В отличие от этого, сборщик мусора без перемещения должен просматривать каждый недостижимый объект и отмечать, что память, которую он занимал, доступна. Аналогично, новые объекты могут выделяться очень быстро. Поскольку сборщик мусора с перемещением обычно предоставляет большие смежные области памяти, новые объекты могут выделяться простым инкрементированием указателя "свободной памяти". Стратегия без перемещения со временем может привести к сильно фрагментированной куче, требующей дорогостоящего обращения к "спискам свободных блоков" небольших доступных областей памяти для выделения новых объектов. Если используется подходящий порядок обхода (например, cdr first для списков cons), объекты могут быть перемещены очень близко к объектам, на которые они ссылаются в памяти, что увеличивает вероятность их расположения в одной строке кэша или странице виртуальной памяти. Это может значительно ускорить доступ к этим объектам через эти ссылки. Одним из недостатков сборщика мусора с перемещением является то, что он позволяет доступ только через ссылки, управляемые средой сбора мусора, и не позволяет выполнять арифметику указателей. Это связано с тем, что любые указатели на объекты станут недействительными, если сборщик мусора переместит эти объекты (они превратятся в висячие указатели). Для обеспечения совместимости с нативным кодом сборщик мусора должен скопировать содержимое объекта в область памяти, находящуюся за пределами области, управляемой сборщиком мусора. Альтернативный подход — зафиксировать объект в памяти, предотвратив его перемещение сборщиком мусора и разрешив прямое совместное использование памяти с нативными указателями (и, возможно, разрешив арифметику указателей).

Once the unreachable set has been determined, the garbage collector may simply release the unreachable objects and leave everything else as it is, or it may copy some or all of the reachable objects into a new area of memory, updating all references to those objects as needed. These are called "non moving" and "moving" (or, alternatively, "non compacting" and "compacting") garbage collectors, respectively. At first, a moving algorithm may seem inefficient compared to a non moving one, since much more work would appear to be required on each cycle. But the moving algorithm leads to several performance advantages, both during the garbage collection cycle itself and during program execution:
No additional work is required to reclaim the space freed by dead objects; the entire region of memory from which reachable objects were moved can be considered free space. In contrast, a non moving GC must visit each unreachable object and record that the memory it occupied is available. Similarly, new objects can be allocated very quickly. Since large contiguous regions of memory are usually made available by a moving GC, new objects can be allocated by simply incrementing a 'free memory' pointer. A non moving strategy may, after some time, lead to a heavily fragmented heap, requiring expensive consultation of "free lists" of small available blocks of memory in order to allocate new objects. If an appropriate traversal order is used (such as cdr first for list conses), objects can be moved very close to the objects they refer to in memory, increasing the chance that they will be located in the same cache line or virtual memory page. This can significantly speed up access to these objects through these references. One disadvantage of a moving garbage collector is that it only allows access through references that are managed by the garbage collected environment, and does not allow pointer arithmetic. This is because any pointers to objects will be invalidated if the garbage collector moves those objects (they become dangling pointers). For interoperability with native code, the garbage collector must copy the object contents to a location outside of the garbage collected region of memory. An alternative approach is to pin the object in memory, preventing the garbage collector from moving it and allowing the memory to be directly shared with native pointers (and possibly allowing pointer arithmetic).

Копирование против отметки и прочесывания против отметки и не прочесывания

Коллекторы различаются не только тем, являются ли они перемещающими или неподвижными, но и тем, как они обрабатывают объекты белого, серого и черного цветов в течение цикла сбора. Наиболее простой подход — полупространственный сборщик, появившийся в 1969 году. В этом перемещающемся сборщике память разделена на области одинакового размера: «из пространства» и «в пространство». Изначально объекты выделяются в «пространстве в», пока оно не заполнится, и запускается цикл сбора. В начале цикла «пространство в» становится «пространством из», и наоборот. Объекты, доступные из корневого множества, копируются из «пространства из» в «пространство в». Эти объекты сканируются поочередно, и все объекты, на которые они указывают, копируются в «пространство в», пока все доступные объекты не будут скопированы в «пространство в». После возобновления выполнения программы новые объекты снова выделяются в «пространстве в», пока оно снова не заполнится, и процесс повторяется. Этот подход очень прост, но поскольку для выделения объектов используется только одно полупространство, использование памяти вдвое выше по сравнению с другими алгоритмами. Этот метод также известен как «остановка и копирование». Алгоритм Чейни является улучшением полупространственного сборщика. Сборщик мусора хранит один или два бита с каждым объектом, чтобы указать, является ли он белым или черным. Серый набор хранится в виде отдельного списка или с использованием другого бита. При обходе дерева ссылок во время цикла сбора (фаза «маркировки») эти биты манипулируются сборщиком. Затем окончательная «подметающая» фаза освобождает белые объекты. Стратегия «маркировка и подметание» имеет то преимущество, что как только набор на удаление определен, можно использовать стратегию сбора с перемещением или без перемещения. Этот выбор стратегии можно сделать во время выполнения, по мере наличия памяти. Она имеет недостаток «раздувания» объектов на небольшую величину, то есть каждый объект имеет небольшую скрытую стоимость памяти из-за списка/дополнительного бита. Это можно несколько смягчить, если сборщик также обрабатывает выделение памяти, поскольку тогда он потенциально может использовать неиспользуемые биты в структурах данных выделения. Или эту «скрытую память» можно устранить, используя помеченный указатель, обменивая стоимость памяти на время процессора. Однако «маркировка и подметание» — единственная стратегия, которая легко взаимодействует с внешними распределителями памяти. Сборщик мусора «маркировка и не подметание», как и «маркировка и подметание», хранит бит с каждым объектом, чтобы указать, является ли он белым или черным; серый набор хранится в виде отдельного списка или с использованием другого бита. Здесь есть два ключевых различия. Во-первых, значения черного и белого отличаются от значений в сборщике «маркировка и подметание». В сборщике «маркировка и не подметание» все доступные объекты всегда черные. Объект помечается черным в момент выделения и остается черным, даже если он станет недоступным. Белый объект — это неиспользуемая память, и его можно выделить. Во-вторых, интерпретация бита черного/белого может измениться. Изначально бит черного/белого может иметь значение (0=белый, 1=черный). Если операция выделения памяти не сможет найти доступную (белую) память, это означает, что все объекты помечены как используемые (черные). Затем смысл бита черного/белого инвертируется (например, 0=черный, 1=белый). Все становится белым. Это временно нарушает инвариантность, согласно которой доступные объекты черные, но сразу же следует полная фаза маркировки, чтобы снова пометить их черными. После этого вся недоступная память становится белой. Фаза «подметания» не требуется. Стратегия «маркировка и не подметание» требует взаимодействия между распределителем и сборщиком, но невероятно эффективна с точки зрения использования памяти, поскольку требует только одного бита на выделенный указатель (который в любом случае требуется большинству алгоритмов выделения). Однако этот плюс несколько смягчается, поскольку большую часть времени большие части памяти ошибочно помечаются черным (используются), что затрудняет возврат ресурсов в систему (для использования другими распределителями, потоками или процессами) в условиях нехватки памяти. Таким образом, стратегия «маркировка и не подметание» может рассматриваться как компромисс между преимуществами и недостатками стратегий «маркировка и подметание» и «остановка и копирование».

Not only do collectors differ in whether they are moving or non moving, they can also be categorized by how they treat the white, grey and black object sets during a collection cycle. The most straightforward approach is the semi space collector, which dates to 1969. In this moving collector, memory is partitioned into an equally sized "from space" and "to space". Initially, objects are allocated in "to space" until it becomes full and a collection cycle is triggered. At the start of the cycle, the "to space" becomes the "from space", and vice versa. The objects reachable from the root set are copied from the "from space" to the "to space". These objects are scanned in turn, and all objects that they point to are copied into "to space", until all reachable objects have been copied into "to space". Once the program continues execution, new objects are once again allocated in the "to space" until it is once again full and the process is repeated. This approach is very simple, but since only one semi space is used for allocating objects, the memory usage is twice as high compared to other algorithms. The technique is also known as stop and copy. Cheney's algorithm is an improvement on the semi space collector. A mark and sweep garbage collector keeps a bit or two with each object to record if it is white or black. The grey set is kept as a separate list or using another bit. As the reference tree is traversed during a collection cycle (the "mark" phase), these bits are manipulated by the collector. A final "sweep" of the memory areas then frees white objects. The mark and sweep strategy has the advantage that, once the condemned set is determined, either a moving or non moving collection strategy can be pursued. This choice of strategy can be made at runtime, as available memory permits. It has the disadvantage of "bloating" objects by a small amount, as in, every object has a small hidden memory cost because of the list/extra bit. This can be somewhat mitigated if the collector also handles allocation, since then it could potentially use unused bits in the allocation data structures. Or, this "hidden memory" can be eliminated by using a Tagged pointer, trading the memory cost for CPU time. However, the mark and sweep is the only strategy that readily cooperates with external allocators in the first place. A mark and don't sweep garbage collector, like the mark and sweep, keeps a bit with each object to record if it is white or black; the grey set is kept as a separate list or using another bit. There are two key differences here. First, black and white mean different things than they do in the mark and sweep collector. In a "mark and don't sweep" collector, all reachable objects are always black. An object is marked black at the time it is allocated, and it will stay black even if it becomes unreachable. A white object is unused memory and may be allocated. Second, the interpretation of the black/white bit can change. Initially, the black/white bit may have the sense of (0=white, 1=black). If an allocation operation ever fails to find any available (white) memory, that means all objects are marked used (black). The sense of the black/white bit is then inverted (for example, 0=black, 1=white). Everything becomes white. This momentarily breaks the invariant that reachable objects are black, but a full marking phase follows immediately, to mark them black again. Once this is done, all unreachable memory is white. No "sweep" phase is necessary. The mark and don't sweep strategy requires cooperation between the allocator and collector, but is incredibly space efficient since it only requires one bit per allocated pointer (which most allocation algorithms require anyway). However, this upside is somewhat mitigated, since most of the time large portions of memory are wrongfully marked black (used), making it hard to give resources back to the system (for use by other allocators, threads, or processes) in times of low memory usage. The mark and don't sweep strategy can therefore be seen as a compromise between the upsides and downsides of the mark and sweep and the stop and copy strategies.

Поколенческая ГК (эфемерная ГК)

Эмпирически было замечено, что во многих программах наиболее недавно созданные объекты также являются теми, которые с наибольшей вероятностью быстро становятся недостижимыми (известное как "младенческая смертность" или генерационная гипотеза). Поколенческий сборщик мусора (GC, также известный как эфемерный GC) разделяет объекты на поколения и, в большинстве циклов, помещает только объекты подмножества поколений в начальный "белый" (осужденный) набор. Кроме того, среда выполнения отслеживает пересечение ссылок между поколениями, наблюдая за созданием и перезаписью ссылок. Когда сборщик мусора запускается, он может использовать эти данные, чтобы доказать недостижимость некоторых объектов в начальном "белом" наборе, не просматривая всё дерево ссылок. Если генерационная гипотеза верна, это приводит к значительно более быстрым циклам сбора, при этом большая часть недостижимых объектов освобождается. Для реализации этой концепции многие поколенческие сборщики мусора используют отдельные области памяти для объектов разного возраста. Когда область заполняется, объекты в ней просматриваются, используя ссылки из старших поколений в качестве корней. Обычно это приводит к тому, что большинство объектов в поколении собираются (согласно гипотезе), освобождая область для выделения новых объектов. Если в ходе сбора освобождается мало объектов (например, гипотеза не подтверждается, потому что программа вычислила большой набор новых объектов, которые необходимо сохранить), некоторые или все выжившие объекты, на которые ссылаются из старших областей памяти, перемещаются в следующую область более высокого уровня, после чего вся область может быть перезаписана новыми объектами. Эта техника позволяет выполнять очень быструю инкрементную сборку мусора, поскольку обычно достаточно собирать мусор только в одной области за раз. Классический поколенческий сборщик мусора Унгара имеет два поколения. Он разделяет молодое поколение, называемое "новым пространством", на большую область "Эдем", где создаются новые объекты, и два меньших "пространства выживших": "прошлое пространство выживших" и "будущее пространство выживших". Объекты в старшем поколении, которые могут ссылаться на объекты в новом пространстве, хранятся в "запоминающем наборе". При каждой сборке объекты в новом пространстве просматриваются от корней в запоминающем наборе и копируются в будущее пространство выживших. Если будущее пространство выживших заполняется, объекты, которые не помещаются, перемещаются в старое пространство – этот процесс называется "удержанием" (tenuring). В конце сборки некоторые объекты находятся в будущем пространстве выживших, а "Эдем" и прошлое пространство выживших пусты. Затем будущее и прошлое пространства выживших меняются местами, и программа продолжает работу, выделяя объекты в "Эдеме". В оригинальной системе Унгара "Эдем" в 5 раз больше, чем каждое пространство выживших. Сборка мусора по поколениям – это эвристический подход, и некоторые недостижимые объекты могут не освобождаться при каждом цикле. Поэтому иногда может потребоваться полная маркировка и подметание или копирование мусора для освобождения всего доступного пространства. Фактически, среды выполнения для современных языков программирования (таких как Java и .NET Framework) обычно используют гибрид различных стратегий, описанных выше; например, большинство циклов сбора могут просматривать только несколько поколений, в то время как периодически выполняется маркировка и подметание, а ещё реже – полное копирование для борьбы с фрагментацией. Термины "минорный цикл" и "мажорный цикл" иногда используются для описания различных уровней агрессивности сборщика мусора.

It has been empirically observed that in many programs, the most recently created objects are also those most likely to become unreachable quickly (known as infant mortality or the generational hypothesis). A generational GC (also known as ephemeral GC) divides objects into generations and, on most cycles, will place only the objects of a subset of generations into the initial white (condemned) set. Furthermore, the runtime system maintains knowledge of when references cross generations by observing the creation and overwriting of references. When the garbage collector runs, it may be able to use this knowledge to prove that some objects in the initial white set are unreachable without having to traverse the entire reference tree. If the generational hypothesis holds, this results in much faster collection cycles while still reclaiming most unreachable objects. In order to implement this concept, many generational garbage collectors use separate memory regions for different ages of objects. When a region becomes full, the objects in it are traced, using the references from the older generation(s) as roots. This usually results in most objects in the generation being collected (by the hypothesis), leaving it to be used to allocate new objects. When a collection doesn't collect many objects (the hypothesis doesn't hold, for example because the program has computed a large collection of new objects it does want to retain), some or all of the surviving objects that are referenced from older memory regions are promoted to the next highest region, and the entire region can then be overwritten with fresh objects. This technique permits very fast incremental garbage collection, since the garbage collection of only one region at a time is all that is typically required. Ungar's classic generation scavenger has two generations. It divides the youngest generation, called "new space", into a large "eden" in which new objects are created and two smaller "survivor spaces", past survivor space and future survivor space. The objects in the older generation that may reference objects in new space are kept in a "remembered set". On each scavenge, the objects in new space are traced from the roots in the remembered set and copied to future survivor space. If future survivor space fills up, the objects that do not fit are promoted to old space, a process called "tenuring". At the end of the scavenge, some objects reside in future survivor space, and eden and past survivor space are empty. Then future survivor space and past survivor space are exchanged and the program continues, allocating objects in eden. In Ungar's original system, eden is 5 times larger than each survivor space. Generational garbage collection is a heuristic approach, and some unreachable objects may not be reclaimed on each cycle. It may therefore occasionally be necessary to perform a full mark and sweep or copying garbage collection to reclaim all available space. In fact, runtime systems for modern programming languages (such as Java and the NET Framework) usually use some hybrid of the various strategies that have been described thus far; for example, most collection cycles might look only at a few generations, while occasionally a mark and sweep is performed, and even more rarely a full copying is performed to combat fragmentation. The terms "minor cycle" and "major cycle" are sometimes used to describe these different levels of collector aggression.

Остановить мир против инкрементального против одновременного

Простые сборщики мусора с остановкой мира полностью приостанавливают выполнение программы для запуска цикла сбора, тем самым гарантируя, что новые объекты не будут выделены и объекты не станут внезапно недоступными во время работы сборщика. Это имеет недостаток в том, что программа не может выполнять полезную работу во время цикла сбора (иногда называемую "неудобной паузой"). Поэтому сборка мусора с остановкой мира в основном подходит для неинтерактивных программ. Её преимущество заключается в простоте реализации и более высокой скорости по сравнению с инкрементной сборкой мусора. Инкрементные и конкурентные сборщики мусора разработаны для уменьшения этого прерывания, чередуя свою работу с активностью основной программы. Инкрементные сборщики мусора выполняют цикл сбора мусора в дискретных фазах, разрешая выполнение программы между каждой фазой (и иногда во время некоторых фаз). Конкурентные сборщики мусора вообще не останавливают выполнение программы, за исключением, возможно, кратковременной приостановки при сканировании стека выполнения программы. Однако суммарное время инкрементных фаз больше, чем время одного прохода пакетной сборки мусора, поэтому эти сборщики мусора могут обеспечивать меньшую общую пропускную способность. Эти методы требуют тщательной разработки, чтобы гарантировать, что основная программа не мешает сборщику мусора и наоборот; например, когда программе необходимо выделить новый объект, среда выполнения может либо приостановить её до завершения цикла сбора, либо каким-то образом уведомить сборщик мусора о существовании нового, доступного объекта.

Точные и консервативные указатели и внутренние указатели

Некоторые сборщики мусора могут правильно идентифицировать все указатели (ссылки) в объекте; они называются точными (также корректными или аккуратными) сборщиками, в отличие от консервативных или частично консервативных сборщиков. Консервативные сборщики мусора предполагают, что любой шаблон битов в памяти может быть указателем, если при интерпретации как указатель он указывает на выделенный объект. Консервативные сборщики мусора могут выдавать ложные срабатывания, когда неиспользуемая память не освобождается из-за неправильной идентификации указателей. Это не всегда является проблемой на практике, если программа не обрабатывает большой объем данных, которые легко могут быть ошибочно приняты за указатели. Ложные срабатывания, как правило, менее проблематичны в 64-битных системах, чем в 32-битных, поскольку диапазон допустимых адресов памяти обычно составляет лишь небольшую часть диапазона 64-битных значений. Таким образом, произвольный 64-битный шаблон вряд ли будет похож на допустимый указатель. Ложные отрицания также могут возникать, если указатели "скрыты", например, при использовании связного списка, реализованного с помощью XOR. Практичность точного сборщика мусора обычно зависит от свойств типобезопасности используемого языка программирования. Примером, для которого требуется консервативный сборщик мусора, является язык C, который позволяет приводить указатели с типом (не void) к указателям без типа (void) и наоборот. Связанная проблема касается внутренних указателей, то есть указателей на поля внутри объекта. Если семантика языка допускает внутренние указатели, то может существовать множество различных адресов, которые могут ссылаться на части одного и того же объекта, что усложняет определение, является ли объект мусором. Примером этого является язык C++, в котором множественное наследование может приводить к тому, что указатели на базовые объекты будут иметь разные адреса. В сильно оптимизированной программе соответствующий указатель на сам объект мог быть перезаписан в регистре, поэтому такие внутренние указатели необходимо сканировать.

Детерминизм

Отслеживание сборки мусора не является детерминированным по времени завершения объектов. Объект, ставший кандидатом на сборку мусора, обычно в конечном итоге будет очищен, но нет никакой гарантии, когда (или даже произойдет ли это). Это представляет проблему для корректности программы, когда объекты связаны с ресурсами, отличными от памяти, освобождение которых является внешне наблюдаемым поведением программы, например, закрытие сетевого подключения, освобождение устройства или закрытие файла. Техника сборки мусора, обеспечивающая детерминизм в этом отношении, – это подсчет ссылок. Сборка мусора может оказывать недетерминированное влияние на время выполнения, потенциально вызывая паузы в выполнении программы, не связанные с обрабатываемым алгоритмом. При отслеживающей сборке мусора запрос на выделение нового объекта иногда может выполняться быстро, а в других случаях запускать длительный цикл сборки мусора. При подсчете ссылок, хотя выделение объектов обычно происходит быстро, уменьшение счетчика ссылок является недетерминированным, поскольку счетчик ссылки может достичь нуля, что вызовет рекурсивное уменьшение счетчиков ссылок других объектов, на которые ссылается данный объект.

Сбор мусора в реальном времени

Хотя сборка мусора обычно недетерминирована, её можно использовать в системах жёсткого реального времени. Коллектор мусора в реальном времени должен гарантировать, что даже в худшем случае он будет выделять определённое количество вычислительных ресурсов для мутаторных потоков. Ограничения, налагаемые на коллектор мусора в реальном времени, обычно основаны на объёме выполненной работы или на времени. Временное ограничение может выглядеть так: в каждом временном окне длительностью T мутаторные потоки должны иметь возможность выполняться не менее Tm времени. Для анализа, основанного на объёме работы, обычно используется MMU (минимальная загрузка мутаторов) как ограничение реального времени для алгоритма сборки мусора. Одной из первых реализаций сборки мусора в реальном времени для JVM стал алгоритм Metronome, коммерческая реализация которого доступна в составе IBM WebSphere Real Time. Другой алгоритм сборки мусора в реальном времени – Staccato, доступный в JVM J9 от IBM, который также обеспечивает масштабируемость для больших многопроцессорных архитектур, предоставляя различные преимущества по сравнению с Metronome и другими алгоритмами, которые, напротив, требуют специализированного аппаратного обеспечения. Одна из основных задач сборки мусора в реальном времени на современных многоядерных архитектурах – разработка неблокирующей параллельной сборки мусора, которая не позволит параллельным потокам блокировать друг друга и создавать непредсказуемые задержки. Исследование алгоритмов, обеспечивающих неблокирующую параллельную сборку мусора в реальном времени, представлено в статье Pizlo и др. в Microsoft Research.