Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 70
Текст из файла (страница 70)
4.28, а.Третий шаг состоит из распространения пометок от заместителей к ассоциированным с ними скелетонам. Другими словами, пометки распространяются отпроцесса к процессу. Так, если заместитель был помечен как твердый, ассоциированному с ним скелетону посылается сообщение о том, что он также получаетпометку твердый, если этот скелетон раньше был маркирован иначе.
Сообщениепосылается только тем скелетонам, которые входят в группу. Пометки нетвердый распространять не нужно: исходная разметка уже привела к тому, что всескелетоны группы имеют пометку твердый или нетвердый.Четвертый шаг приводит к глобальному распространению пометок твердыйпредыдущего шага.
Скелетон, скажем, процесса Р может при этом поменять своюпометку с нетвердый на твердый. Эти изменения будут обусловлены тем фактом, что к скелетону получат доступ объекты, содержащиеся в корневом набореудаленного процесса. Соответственно, пометка твердый сначала распространится локально, на заместителей процесса Р, а затем глобально, на смежные процессы. Другими словами, второй и третий шаги будут повторяться до тех пор, покапометки не перестанут распространяться глобально или локально.
Когда ситуация стабилизируется, то есть прекратятся изменения пометок в процессах, входящих в группу, алгоритм перейдет к следующему шагу. В нашем примере результат повторений шагов 2 и 3 приведет к итоговой разметке, показанной нарис. 4.28, в.Пятый и последний шаг состоит из удаления недоступных объектов, включаянедоступные заместители, а также те заместители и скелетоны, которые былипомечены как нетвердые. Важно отметить, что последние недоступны из-за пределов группы или из объектов корневого набора. Другими словами, нетвердыезаместители и скелетоны ссылаются только друг на друга и могут быть удалены.Сборка мусора может в действительности выполняться в виде вторичного эффекта локального распространения. Вместо явного удаления сущностей на последнем шаге скелетоны, помеченные как нетвердые, могут заменяться ссылкойна нуль.
Таким образом, они могут быть обработаны позже, при повторном запуске локальных сборщиков мусора. Кроме того, если объект, ассоциированныйс подобным скелетоном, становится недоступным, он также может быть обработан при повторном проходе. Если заместители, локально ссылающиеся на подоб-270Глава 4. Именованиеный объект, также становятся недоступными, они могут быть помечены какотсутствующие и обработаны точно так же. Поэтому для безопасного использования локальных сборщиков мусора следует обрабатывать заместители, помеченные как отсутствующие, после отправки сообщения об уменьшении счетчика скелетону удаленного процесса, ассоциированному с заместителем.В иерархически организованных процессах в группах необходимо использовать более масштабируемое решение для распределенной сборки мусора.
Основная идея состоит в том, что низкоуровневые группы собирают свой мусор, а анализссылок между группами оставляют на группы более высокого уровня. Поскольку количество объектов в низкоуровневых группах, которые необходимо отслеживать, уменьшается, группы верхнего уровня в основном работают со схожимколичеством объектов, которые просто распределены по большей сети.
Мы опустим детали, которые при необходимости можно найти в [255].4.4. ИтогиИмена используются для ссылок на сущности. По сути, существует три основныхтипа имен. Адрес — имя точки доступа, ассоциированной с сущностью, часто называемый просто адресом сущности. Другой тип имени — идентификатор. Онимеет три свойства: каждая сущность имеет только один идентификатор, идентификатор указывает на единственную сущность и не может быть переназначендругой. И наконец, имена, удобные для восприятия, предназначены для использования людьми и представляют собой строку символов.Имена организованы в пространства имен.
Пространство имен может бытьпредставлено в виде графа именования, в узлах которого расположены именуемые сущности, а метки на ребрах представляет собой имена, под которыми этисущности известны. Узлы, из которых выходит несколько ребер, представляютсобой наборы сущностей и известны также под названием направляющих узлов.Крупномасштабные графы именования часто организуются в виде корневых ациклических направленных графов.Графы именования подходят для структурирования имен, удобных для восприятия.
Доступ к сущности может осуществляться посредством пути. Разрешение имен — это процесс прохода по графу именования в поисках компонентов,входящих в путь, по одному за раз. Крупномасштабный граф именования реализуется путем распределения узлов по нескольким серверам имен. При разрешении пути путем обхода графа именования, если разыскиваемый узел находитсяна следующем сервере имен, то разрешение имен продолжается на нем.Системы именования для имен, удобных для восприятия, невозможно использовать для высокомобильных сущностей.
Локализация мобильных сущностейболее успешно может быть произведена с помощью не зависящих от местоположения идентификаторов. Существует четыре основных подхода к локализациимобильных сущностей.Первый подход состоит в использовании широковещательных или групповыхрассылок. Идентификатор сущности посылается широковещательной посылкой4.4. Итоги271каждому процессу в распределенной системе. Процесс предлагает точку доступав ответ на предоставление ему адреса этой точки доступа. Очевидно, что этотподход имеет ограниченную масштабируемость.Второй подход состоит в пересылке указателей.
Каждый раз при перемещении сущности в другое место она оставляет за собой указатель, информирующийо том, куда она переместилась. Локализация сущности требует обхода цепочкипересылаемых указателей. Чтобы устранить длинную цепочку указателей, важноуменьшить длину цепи после перемещения.Третий подход состоит в создании базы сущности. Каждый раз при перемещении сущности в другое место она уведомляет об этом свою базу.
При локализации сущности первым делом о текущей локализации запрашивается ее база.Четвертый подход состоит в построении иерархического дерева поиска. Сетьразбивается на неперекрывающиеся области (домены). Домены могут группироваться в домены верхнего уровня (неперекрывающиеся) и т. д. Существует одиндомен верхнего уровня, охватывающий всю сеть. Всякий домен на любом уровнеимеет ассоциированный с ним направляющий узел. Если сущность находится вдомене Z), направляющий узел в домене следующего уровня содержит указательна D. Направляющие узлы самого нижнего уровня содержат адреса сущностей.Направляющий узел самого верхнего уровня содержит сведения обо всех сущностях.Сущности, локализация которых больше не нужна, могут быть удалены.
Важная цель использования имен в распределенных системах — создание ссылок насущности так, чтобы сущности, на которые нет ссылок, удалялись автоматически. Такая сборка мусора требует подсчета ссылок или трассировки.В случае подсчета ссылок сущность просто считает количество созданных нанее ссылок. Когда счетчик достигнет нуля, сущность можно удалять. В отличиеот подсчета ссылок можно также поддерживать список ссылок на процессы, ссылающиеся на сущность. Список ссылок более устойчив, чем счетчик ссылок, ноимеет проблемы с масштабированием.В методах трассировки все сущности прямо или косвенно ссылаются на заданный набор корневых сущностей, которые помечаются как доступные.
Недоступные сущности удаляются. Распределенная трассировка трудна, поскольку требуется проверить все сущности в системе. Решения разнообразны, но в основномони основаны на традиционных сборщиках мусора, характерных для однопроцессорных систем.Вопросы и задания1. Приведите пример ситуации, в которой для реального доступа к сущности Еее адрес разрешается в другой адрес.2. Зависит или нет от локализации URL-адрес http://www.acme.org/index.html?Как насчет адреса http.V/www.acme.nl/index.html?3. Приведите несколько примеров правильных идентификаторов.4.
Как найти точку монтирования в большинстве UNIX-систем?272Глава 4. Именование5. Jade — это распределенная файловая система, использующая отдельные пространства имен для каждого пользователя [371]. Другими словами, каждыйпользователь имеет собственное закрытое пространство имен. Могут ли имена из подобных пространств имен при разделении ресурсов совместно использоваться несколькими пользователями?6. Рассмотрим DNS. Для ссылки на узел Л^ в поддомене, реализованном в другой нежели текущий домен зоне, должен быть определен сервер имен для этойзоны. Всегда ли необходимо включать запись о ресурсах для адреса этого сервера или иногда достаточно указать только его доменное имя?7.
Может ли идентификатор содержать информацию о сущности, которую онидентифицирует?8. Опишите эффективную реализацию глобально уникальных идентификаторов.9. Приведите пример того, как должен работать механизм свертывания в URL.10. Объясните разницу между жесткой и мягкой ссылкой в UNIX-системах.11. Высокоуровневые серверы имен в DNS (то есть серверы имен, реализующие узлы пространства имен DNS, близкие к корню) обычно не поддерживают рекурсивного разрешения имен.
Можно ли достичь значительного повышения производительности, если они будут поддерживать рекурсивное разрешение имен?12. Опишите, как можно использовать DNS для реализации ориентированногона наличие базы способа локализации мобильных хостов.13. Существует особая форма локализации сущности, называемая индивидуальной рассылкой (anycasting), в которой служба определяется по IP-адресу [345]. Посылка запроса на адрес индивидуальной рассылки приводит к получению ответа от сервера, который реализует службу, определяемую поадресу индивидуальной рассылки.
Опишите реализацию службы индивидуальной рассылки, основанную на иерархической службе локализации, описанной в пункте 4.2.4.14. Где корень, если считать, что двухзвенный подход, основанный на наличиибазы, является специализацией иерархической службы локализации?15. Предположим, известно, что конкретная мобильная сущность практически никогда не выйдет за пределы домена D, а если это и случится, то быстро вернется обратно. Как можно использовать эту информацию для ускорения операции поиска в иерархической службе локализации?16. Какое максимальное число локализующих записей необходимо обновить виерархической службе локализации глубины k при изменении местонахождения сущности?17. Рассмотрим сущность, перемещающуюся из места А в место В с посещениемнескольких промежуточных мест, в которых эта сущность находится относительно недолго.
По прибытии в В она на время затихает. Изменение адресав иерархической службе локализации может потребовать относительно долгого времени, поэтому в ходе посещения промежуточных мест такого измененияследует избегать. Как можно обнаружить сущность в промежуточном месте?4.4. Итоги27318. Как при передаче удаленной ссылки из процесса Р1 в Р2 при распределенномподсчете ссылок увеличить счетчик Р1 независимо от Р2?19. Поясните, почему взвешенный подсчет ссылок эффективнее простого подсчета ссылок. Считайте связь надежной.20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
