Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 68
Текст из файла (страница 68)
Наиболее серьезная проблема передачи указателей состоит в том.262Глава 4. Именованиечто длинные цепочки существенно снижают производительность. Кроме того,цепочки весьма уязвимы при сбоях.У процесса Р1исчерпан вес,и он создает скелетон s'У объекта исчерпанчастичный весПроцесс Р1Процесс Р2Процесс Р2 \ О б ] Общий весссылается\^-^ частичный весна объект^'через процесс Р1Рис. 4.26. Создание косвенной ссылки в случае исчерпания частичного весаАльтернативой косвенным ссылкам может быть подсчет поколений ссылок{generation reference counting). Вновь предположим, что каждая удаленная ссылкапредставляет из себя пару (заместитель, скелетон), причем скелетон принадлежит тому же адресному пространству, что и объект. Каждый заместитель хранитсчетчик копий и номер поколения. При создании новой ссылки вида (заместитель, скелетон) номер поколения соответствующего заместителя устанавливается в ноль. Поскольку пока еще не было сделано копий заместителя, его счетчиккопий также равен нулю.Копирование удаленной ссылки (заместитель, скелетон) в другой процесспроизводится обычным образом — пересылкой ему копии заместителя.
В этомслучае счетчик копий в исходном заместителе увеличивается на единицу, а счетчик копий в скопированном заместителе выставляется в ноль. Однако посколькуэтот заместитель был скопирован, он принадлежит к следующему поколению,и по этой причине его номер поколения на единицу больше, чем у исходного заместителя, что и демонстрирует рис. 4.27.Процесс Р2Процесс Р1 передаетссылку процессу Р2Счетчик копийНомер поколенияРис. 4 .
2 7 . Создание и копирование удаленных ссылокпри подсчете поколений ссылокСкелетон поддерживает таблицу С, в которой G[i] обозначает число созданных копий для поколения i. Если заместитель р удаляется, сообщение об удале-4.3. Удаление сущностей, на которые нет ссылок263НИИ посылается скелетону, содержащему номер поколения заместителя, скажем й,и число копий, порожденных от заместителя р, скажем п.
Скелетон приводит Gв соответствие с действительностью, сначала уменьшая на единицу G[k] и показывая, таким образом, что удалена ссылка ^-го поколения. Затем он увеличиваетG[^+l] на п, чтобы показать, что удаленная ссылка создала п потомков или, другими словами, что она была скопирована в п ссылок следующего поколения (отметим, что скелетон должен сначала создать элемент G[^+l], если ранее он ничего не знал о поколении й+1). В том случае, если все элементы G[i\ равны нулю,на объект больше нет ссылок и его можно удалить.Подсчет поколений ссылок также требует надежных коммуникаций, но способен обеспечивать копирование ссылок, не обращаясь при создании копий к скелетону.4.3.3.
Организация списка ссылокДругой подход к управлению ссылками состоит в том, чтобы заставить скелетонотслеживать заместители, которые содержат ссылки на него. Другими словами,вместо подсчета ссылок скелетон должен поддерживать полный список всех заместителей, которые на него указывают. Подобный список ссылок {reference list)имеет следующие важные свойства.
Добавление заместителя в список ссылок недолжно давать никакого результата, если этот заместитель в списке уже присутствует. Точно так же попытка удаления заместителя, отсутствующего в списке, недолжна ни к чему вести. Добавление и удаление заместителей являются такимобразом идемпотентными (idempotent) операциями.Идемпотентные операции характеризуются тем, что их многократное повторение не влияет на конечный результат. В частности, при создании новой ссылки на объект создавший ссылку процесс может многократно отправлять сообщения скелетону объекта, требуя добавить ссылку в список ссылок. Он прекращаетпосылать сообщения после получения подтверждения о доставке.
Соответственно, об удалении ссылки можно уведомлять посылкой (возможно, многократной)скелетону сообщения с требованием исключить ссылку из списка ссылок. Понятно, что операции увеличения и уменьшения счетчика не являются идемпотентными операциями.Таким образом, список ссылок не требует от связи надежности, а также не нуждается в механизмах обнаружения и отбрасывания повторных сообщений (однако необходимо, чтобы добавление ссылок в список и удаление их из спискаподтверждались). Это серьезное преимущество по сравнению с механизмами подсчета ссылок.Списки ссылок, используемые в системе RMI языка Java, основаны на методе, описанном в [60]. Согласно этому методу, когда процесс Р создает удаленнуюссылку на объект, он посылает свой идентификатор скелетону объекта, которыйдобавляет Р в список ссылок.
Когда приходит подтверждение, процесс создаетзаместитель объекта в своем адресном пространстве.Передача ссылки другому процессу, то есть посылка копии заместителя, обрабатывается сходным образом. Когда процесс Р1 посылает копию своего замес-264Глава 4.
Именованиетителя объекта О процессу Р2, процесс Р2 сначала требует у скелетона объектадобавить Р2 в список ссылок. Когда это сделано, процесс Р2 встраивает заместитель в свое адресное пространство.Проблемы могут возникнуть в том случае, если процесс Р1 удалит свой заместитель до того, как Р2 подаст запрос на вставку в список ссылок. В этом случае если запрос на удаление, который Р1 посылает скелетону объекта, будетобработан раньше запроса на вставку от Р2, список ссылок может оказаться пустым, то есть скелетон может прийти к неправильному выводу о возможностиудаления объекта.
Эта ситуация полностью аналогична ситуации из вариантас подсчетом ссылок, показанного на рис. 4.24, а, и может быть решена таким жеспособом.Другим важным достоинством списка ссылок является простота сохраненияего непротиворечивости при сбоях процессов. Скелетон объекта регулярно проверяет, все ли имеющиеся в списке процессы в порядке. Это делается посредством посылки сообщения ping с запросом, живы ли они еще и сохраняют ли ссылкуна объект. Процесс должен немедленно ответить на это сообщение.
Если ответне получен, возможно, даже после нескольких попыток, скелетон удаляет процесс из списка.Основной недостаток списка ссылок состоит в том, что он плохо масштабируется, особенно если скелетон должен отслеживать много ссылок. Один из способовсохранить управляемость состоит в том, чтобы указать скелетону на необходимость регистрировать ссылки на ограниченный срок. Если заместитель до истечения этого срока не подтверждает скелетону свою регистрацию, ссылка простоудаляется из списка. Этот подход называется также арендой {lease).
Мы вернемся к аренде в главе 6.4.3.4. Идентификация сущностей,на которые нет ссылокКак уже было продемонстрировано с помощью рис. 4.22, набор сущностей в распределенных системах может содержать сущности со ссылками только друг надруга, то есть недоступные из корневого набора. Такие сущности должны удаляться.
К сожалению, методы сборки мусора, описанные ранее, не в состояниивыявить подобные сущности.Нам необходим метод, который позволит отследить все сущности в распределенной системе. В основном он состоит в проверке доступности сущностей изкорневого набора с последующим удалением всех недоступных. Подобные методы носят общее название трассировочной сборки мусора {tracing-based garbagecollection). В противоположность распределенным ссылкам, которые мы рассматривали ранее, трассировочной сборке мусора присущи проблемы масштабируемости, поскольку необходимо отслеживать все сущности распределенной системы.Примитивная трассировка в распределенных системахЧтобы разобраться в распределенной трассировочной сборке мусора, полезно обсудить трассировку в однопроцессорных системах. Наиболее простой подход4.3. Удаление сущностей, на которые нет ссылок265к однопроцессорной трассировке представлен сборщиками типа «помечай и подметай».
Эти сборщики работают в два приема.В ходе фазы пометки сущности отслеживаются по существующим цепочкамссылок, исходящим из сущностей корневого набора. Каждая сущность, котораяможет быть достигнута оттуда, помечается, например, путем записи сущностив отдельную таблицу. Фаза подметания состоит из тщательной проверки памятидля локализации «ничейных» сущностей.
Эти сущности считаются мусором, который должен быть удален.Другой вариант работы сборщиков «помечай и подметай» — трехцветная пометка сущностей, Изнача.71ьно каждая сущность, которую следует проверить, окрашена в белый цвет. К концу фазы пометки все сущности, доступные из корня,помечаются черным, а недоступные остаются белыми. Серый цвет используетсядля индикации хода фазы пометки. Сущность помечается серым, если она доступна, но ссылки, которые содержит эта сущность, еще нуждаются в проверке.Когда все сущности, на которые ссылается данная сущность, окрашиваются серым, сама она становится черной.Распределенный вариант схемы «помечай и подметай» был реализована в системе Emerald, описанной в [220].
В Emerald каждый процесс запускает локальный сборщик мусора, причем все сборщики работают параллельно. Сборщикиокрашивают заместители, скелетоны и сами объекты. Изначально все они помечаются белым цветом. Когда объект, расположенный в адресном пространствепроцесса Р, доступен из корневого набора, объект помечается серым. При этомвсе заместители, содержащиеся в этом объекте, также помечаются серым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
