Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 67
Текст из файла (страница 67)
Подмножество объектов, в которых нет ссылок друг на друга, известно под названием корневого набора{root set). Объекты корневого набора обычно представляют системные службы,пользователей и т. д.На рис. 4.22 показан граф ссылок. Все белые узлы представляют объекты, накоторые у объектов корневого набора нет прямых или косвенных ссылок. Такиеобъекты могут быть удалены.Недостижимые сущности,образующие замкнутый цикл ссылокКорневой наборДостижимыедля корневогонабора сущностиНедостижимая для корневогонабора сущностьРис.
4 . 2 2 . Пример графа объектов, содержащих ссылки друг на другаВ однопроцессорных системах обнаружение и удаление объектов, на которыенет ссылок, относительно несложно по сравнению с тем, что происходит в распределенных системах (описание сборки мусора в однопроцессорных системахможно найти в [226]). Поскольку объекты в нашем случае разбросаны по множеству машин, распределенная сборка мусора нуждается в сетевой связи. Как выясняется, эта связь оказывает решающее влияние на производительность и масштабируемость решений.
Кроме того, связь (как и машины, как и процессы) подвержена сбоям, которые способны еще более усложнить задачу.В этом пункте мы рассмотрим несколько общеизвестных решений проблемыраспределенной сборки мусора. В большинстве случаев эти решения лишь частично решают проблему. Наш подход подобен подходу, примененному в [356],где описывается целый обзор способов распределенной сборки мусора. Дополнительную информацию можно почерпнуть также из [2].4 .
3 . 2 . Подсчет ссылокМетод проверки (который весьма популярен в однопроцессорных системах) возможности удаления того или иного объекта состоит в том, чтобы просто вестиподсчет ссылок на этот объект. Каждый раз при создании ссылки на объект счетчик ссылок на этот объект увеличивается на единицу. Когда ссылка на объект4.3. Удаление сущностей, на которые нет ссылок259уничтожается, значение счетчика уменьшается. Как только значение счетчика станет равным нулю, объект можно удалять.Простой подсчет ссылокПростой подсчет ссылок в распределенных системах приводит к некоторым проблемам, возникающим отчасти из-за ненадежности связи.
Без потери общностимы можем предположить, что объект хранит свой счетчик ссылок в соответствующем скелетоне, который управляется сервером объекта, отвечающим за этотобъект. Этот случай показан на рис. 4.23.Процесс РСкелетон (поддерживает счетчик ссылок)Объект ОЗаместитель рЗаместитель ручтен в расчетахдваждыРис. 4 .
2 3 . Проблема сохранения правильности счетчика ссылокв условиях ненадежной связиКогда процесс Р создает ссылку на удаленный объект О, он, как показано нарисунке, устанавливает заместитель этого объекта в свое адресное пространство.Для увеличения счетчика ссылок заместитель посылает сообщение (1) скелетонуобъекта и ожидает, что последний вернет подтверждение. Однако если подтверждение затеряется (2), заместитель произведет повторную посылку сообщения (3). Если не предпринимать никаких мер для обнаружения повторных сообщений, скелетон может ошибочно увеличить счетчик еще раз.
На практикеотносительно несложно организовать обнаружение повторных сообщений.Подобные же проблемы могут возникнуть и при уничтожении удаленнойссылки. В этом случае заместитель посылает сообщение, уменьшающее счетчикссылок. Если подтверждение вновь потеряется, повторная посылка сообщенияприведет к повторному, на этот раз ошибочному уменьшению счетчика. Такимобразом, при распределенном подсчете ссылок важно обнаруживать повторныесообщения и в случае обнаружения игнорировать их.Другая проблема, которую необходимо решить, возникает при копированииудаленной ссылки в другой процесс. Если процесс Р1 передает ссылку процессу Р2,объект О, или точнее, его скелетон, может остаться в неведении относительносоздания новой ссылки.
Таким образом, если процесс Р1 решит уничтожитьсвою ссылку, содержимое счетчика ссылок может стать равным нулю и объект Оможет быть удален до того, как Р2 сможет с ним связаться. Эту проблему иллюстрирует рис. 4.24, а.260Глава 4. ИменованиеПроцесс Р1Процесс Р1посылает ссылку удаляет своюпроцессу Р2 ссылку на объект ОПроцесс Р2 сообщает объекту О,что у него есть ссылка на негоПроцесс Р1 сообщаетПроцесс Р1объекту О, что он передаст удаляет свою ссылкуссылку на него процессу Р2на объект ОПроцесс Р1посылаетссылкупроцессу Р2Объект О подтверждает,что ему известноо существовании ссылкина него у процесса Р2Рис. 4.24.
Копирование ссылки в другой процесс и запоздавшее увеличение счетчика (а).Решение (б)Решение состоит в том, чтобы потребовать от Р1 уведомлять скелетон объекта о том, что он собирается передать ссылку процессу Р2. Кроме того, процесс недолжен удалять свою ссылку до тех пор, пока скелетон не подтвердит ему, чтознает о создании ссылки. Это решение продемонстрировано на рис. 4.24, 6. Подтверждение, посылаемое от объекта О процессу Р2, уведомляет F2, что объект Озарегистрировал ссылку, что позволяет Р1 позднее удалить свою ссылку.
До техпор пока процесс Р2 не уверен, что О знает о существовании у него ссылки, Р1 неможет требовать у О уменьшения счетчика ссылок.Заметим, что вдобавок к надежной связи передача ссылки требует теперь трехсообщений. Понятно, что в крупномасштабных распределенных системах это быстро приведет нас к проблемам с производительностью.Улучшенные механизмы подсчета ссылокКак было показано, простой распределенный подсчет ссылок требует соблюдения определенных условий в период между увеличением и уменьшением счетчикассылок.
Эти условия можно не соблюдать, если иметь дело только с уменьшением счетчика. Такое решение реализовано во взвешенном подсчете ссылок {weightedreference counting, при котором каждый объект имеет фиксированный общий вес.При создании объекта этот вес сохраняется в ассоциированном с ним скелетоневместе с его частичным весом, который инициализируется общим весом, как показано на рис.
4.25, а.При создании новой удаленной ссылки половина частичного веса, хранящегося в скелетоне объекта, присваивается новому заместителю, как показано нарис. 4.25, б. Оставшаяся половина хранится в скелетоне. Когда удаленная ссылкадублируется, например, при ее передаче из процесса Р1 в процесс Р2, половиначастичного веса заместителя из Р1 передается заместителю процесса Р2, в который производится копирование, а вторая половина остается в заместителе процесса Р1, как показано на рис. 4.25, в.4.3. Удаление с у щ н о с т е й , на которые нет ссылокСкелетонОбъект ООбщий вес 128 ГЧастичный вес |128|Частичныйвесзаместителя261Частичный весскелетона/сниженПроцесс РX наполовиь128hч"64l ч\М]\LtJ^ЧJЗаместительПроцесс Р2 получаетполовину весазаместителяиз процесса Р1Процесс Р1 передаетссылку процессу Р2Процесс Р2Общий и частичный[128] Jc^ вес скелетонаостался прежним[64]')Й^\iJРис.
4 . 2 5 . Исходное соотношение весов при взвешенном подсчете ссылок (а). Присвоениевеса при создании новой ссылки (б). Присвоение веса при копировании ссылки (в)При уничтожении ссылки скелетону объекта посылается сообщение, уменьшающее счетчик. Затем из общего веса вычитается частичный вес уничтоженнойссылки. Как только общий вес станет равным нулю, объект можно удалять. Отметим, что в этом случае также предполагается, что сообщения не теряются и недублируются.Основная проблема взвешенного подсчета ссылок состоит в том, что количество создаваемых ссылок ограничено.
Как только частичный вес скелетона и удаленных ссылок достигнет нуля, создавать или копировать новые ссылки будетневозможно. Решить проблему можно с помощью косвенных ссылок. Предположим, что процесс Р1 хочет передать ссылку процессу Р2, но частичный вес егозаместителя равен 1, как показано на рис. 4.26. В этом случае Р1 создает в своемадресном пространстве скелетон s' с подходящим общим весом и частичным весом, равным общему.
Это абсолютно аналогично созданию в адресном пространстве объекта скелетона 5. Затем процессу Р2 пересылается заместитель, которомупередается половина частичного веса скелетона s'. Другая половина веса остается у 5' для раздачи другим заместителям.Заметим, что если общий вес скелетона 5' установить в 1, этот подход превратится в подобие передачи указателя из процесса Р1 в процесс Р2. Если, в своюочередь, Р2 захочет передать свою ссылку, он может создать еще один передаваемый указатель.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
