Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 69
Текст из файла (страница 69)
Пометка заместителя серым цветом означает, что его локальный сборщик мусора указывает на необходимость проверки ссылок данного удаленного объекта ассоциированным с ним локальным сборщиком мусора.Когда заместитель помечается серым, ассоциированному с заместителем скелетону посылается сообщение, маркирующее серым и его. Объект, к которомуотносится скелетон, помечается серым вслед за своим скелетоном. Далее, рекурсивно, все заместители в этом объекте помечаются серым. В этот момент скелетон и ассоциированный с ним объект помечаются черным, и соответствующеесообщение посылается всем ассоциированным с ним заместителям. Отметим, чтохотя в этом подходе скелетону известны связанные с ним заместители, это не означает, что они достижимы из скелетона. Логически рассуждая, пара (заместитель, скелетон) — это исключительно однонаправленная связь от заместителяк скелетону.Когда заместитель получает сообщение о том, что ассоциированный с нимскелетон стал черным, он тоже помечается черным.
Другими словами, локальный сборщик мусора теперь знает, что удаленный объект, на который идет ссылка через заместитель, признан доступным.Когда все локальные сборщики мусора заканчивают фазу пометки, каждыйиз них по отдельности собирает все белые объекты, считая их мусором. Фаза пометки завершается, когда все объекты, скелетоны и заместители приобретут либо белый, либо черный цвет.
Удаление белых объектов означает также удалениеассоциированных с ними скелетонов, а также заместителей этих объектов.266Глава 4. ИменованиеОсновной недостаток алгоритма «помечай и подметай» состоит в том, что онтребует, чтобы граф доступности в течение обоих фаз оставался неизменным.Иначе говоря, выполнение программы, для которой изначально был создан процесс, должно быть временно приостановлено и система должна переключитьсяна сборку мусора.
Для распределенных систем это означает, что все процессыдолжны быть синхронизированы. Каждый из них должен переключиться на сборку мусора, после чего все они смогут продолжить свою работу.Такой сценарий, называемый также синхронизацией «все замри!», обычнонедоступен для распределенных сборщиков мусора. Усовершенствование можетзаключаться в использовании инкрементных сборщиков мусора, которые позволяют программе работать, перемежая ее выполнение со сборкой мусора.
К сожалению,подобные сборщики мусора в распределенных системах плохо масштабируются.Поскольку они работают параллельно с программой, которая изменяет граф доступности, объекты часто должны помечаться серым, а это приведет к распространению серых пометок по удаленным процессам. Результатом будет большойтрафик сообщений, способный снизить общую производительность системы.Трассировка в группахРассматривая проблемы масштабируемости, присущие многим трассировочнымсистемам сборки мусора, разработчики придумали способ, в ходе которого процессы (содержащие объекты) в больших распределенных системах собираютсяв группы [255]. Сборка мусора производится внутри групп путем сочетания методов «помечай и подметай» и подсчета ссылок. Сосредоточимся на базовом алгоритме сборки мусора в группе процессов.Группа — это просто набор процессов. Единственная причина работы с группами — масштабируемость.
Базовая идея состоит в том, чтобы сначала собратьвесь мусор в группе, включая цепочки ссылок, полностью находящиеся внутригруппы. На следующем шаге выполняется переход к группе большего размера,содержащей несколько подгрупп, каждая из которых была очищена сборщикоммусора.Чтобы понять трассировку в группе, предположим, что удаленные ссылкивновь реализованы в виде пар (заместитель, скелетон). Для каждого объектасуществует лишь один скелетон, находящийся в адресном пространстве объекта,и множество заместителей, способных связываться со скелетоном. Скелетонподдерживает счетчик ссылок, описанный в пункте 4.3.2, который подсчитываетчисло ассоциированных с этим скелетоном заместителей. Процесс может иметьмаксимум один заместитель на каждый распределенный объект.Как только будет сформирована группа процессов, вступает в работу базовыйалгоритм сборки мусора, состоящий из пяти шагов.1.
Первичная маркировка, помечаются только скелетоны.2. Распространение маркировки внутри процессов со скелетонов на заместителей.3. Распространение маркировки между процессами с заместителей на скелетоны.4. Стабилизация путем многократного повторения двух предыдущих шагов.5.
Удаление мусора.4.3. Удаление сущностей, на которые нет ссылок267До начала каждого из этих шагов важно понять, что означает маркировкасущности. Алгоритм относится в основном к маркировке заместителей и скелетонов. Важно отметить, что ни заместители, ни скелетоны не относятся к корневому набору.Скелетоны могут помечаться как нетвердые или твердые^ а заместители —как отсутствующие, нетвердые или твердые. Если скелетон помечен как твердый, значит, он достижим либо из заместителя процесса, не входящего в группу,либо из корневого объекта, входящего в группу, то есть объекта, содержащегосяв корневом наборе и входящего в группу процесса.
Скелетон, помеченный какнетвердый, доступен только из заместителя внутри группы. Скелетон может бытьпомечен только как нетвердый или твердый.Заместитель, помеченный как твердый, достижим из объектов корневого набора. Если заместитель помечен как нетвердый, он достижим из скелетона, такжепомеченного как нетвердый. Такие скелетоны потенциально могут расположиться цепочкой, к которой не будет доступа у объектов корневого набора.
Заместитель, помеченный как отсутствующий, недоступен ни из скелетонов, ни из объектов корневого набора. Только заместители, помеченные как отсутствующие,могут изменить маркировку на твердые. Как мы увидим, заместители, помеченные как нетвердые, сохраняют эту маркировку и далее.Первый шаг состоит в пометке одних скелетонов. Скелетон помечается кактвердый или нетвердый в зависимости от того, доступен ли он для заместителей,не входящих в группу. Эта доступность может быть легко проверена по счетчикуссылок скелетона.
Значение этого счетчика показывает, сколько заместителей других процессов на него ссылаются. Некоторые из этих процессов входят в группу,другие не входят. Если среди них имеются заместители процессов, не входящихв группу, скелетон помечается как твердый. Просто пересчитав, сколько заместителей, ассоциированных со скелетоном, входят в группу, и вычтя это число из значения счетчика ссылок, мы можем решить, имеются ли у скелетона ассоциированные с ним заместители вне группы.
Это приводит нас к следующему алгоритму.1. Для каждого заместителя внутри группы уменьшается счетчик ссылок соответствующего скелетона на единицу, в том случае, если скелетон также находится внутри группы.2. Скелетон внутри группы помечается как нетвердый, если его счетчик ссылоксброшен в ноль. В противном случае он доступен из-за границ группы и помечается как твердый.Первый шаг иллюстрирует рис.
4.28, а, на котором все скелетоны, кроме одного, являются нетвердыми. Только один скелетон, который является твердым,доступен заместителю из-за границ группы.Второй шаг включает в себя переключение каждого из процессов на свойсборщик мусора. Эти локальные сборщики работают независимо от глобальногосборщика мусора. Единственное, что от них требуется в ходе работы, — это распространить маркировку со скелетонов на заместителей.
Конкретнее, мы полагаем, что внутри одного процесса заместители достижимы из скелетона (отметим,что заместитель и скелетон принадлежат разным объектам). В результате ло-268Глава 4. Именованиекального распространения пометок заместители будут помечены как минимумтак же, как и скелетон. Более того, если заместитель будет доступен объекту корневого набора, он будет помечен как твердый.Внешний процессГруппа процессово Нетвердый• Твердый4d^тн1тшм и"Ш;:.-Рис. 4 . 2 8 . Исходная маркировка скелетона (а). Ситуация после локального распространениямаркировки в каждом процессе (б).
Итоговая маркировка (в)4.3. Удаление сущностей, на которые нет ссылок269Локальное распространение внутри процесса Р может происходить следующим образом. Изначально все заместители помечаются как отсутствующие. Локальный сборщик мусора начинает трассировку с набора, в который входят скелетоны, которые ранее были помечены как твердые, а также объекты корневогонабора.
Твердые пометки распространяются на все объекты (то есть на локальные объекты и заместители), доступные из этого набора. Второй проход осуществляется, начиная со скелетонов, помеченных как нетвердые. Если заместители,доступные из этого набора, помечены как отсутствующие, их маркировка меняется на нетвердые. Если достижимые заместители уже помечены как твердые, заними сохраняется эта маркировка. Таким образом, после локального распространения каждый заместитель процесса получает одну из трех маркировок — отсутствующий, нетвердый или твердый. Рисунок 4.28, б отражает момент послелокального распространения маркировок в группе, изображенной на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
