BC/NW 2009; №1 (14):4.2

УПРАВЛЕНИЕ ДОСТУПА К ОБЪЕКТАМ ИЗМЕНЧИВЫХ ДАННЫХ В ПИРИНГОВЫХ СИСТЕМАХ

Обейдат А. А., Губарев В. В.

(Новосибирск, Новосибирский Государственный Технический Университет, Россия)

Пиринговые системы (П2П или P2P), первоначально использовались для совместного доступа через Интернет к файлам типа «только для чтения». Поэтому они не требовали механизмов защиты от конкуренции доступа и обновления совместно используемых данных. Однако последние приложения П2П систем сталкиваются с ситуациями, когда возникает необходимость исключить одновременный доступ к этим ресурсам разных пользователей (проблема взаимного исключения - ВИ). Поэтому необходимость построения алгоритмов взаимного исключения (ВИ) одновременного доступа разных пользователей к одному и тому же ресурсу. В [1-3] представлено несколько вариантов решения проблемы ВИ. Но эти решения обладают рядом недостатков таких, например, как единая точка отказа системы, упорядоченность, высокая загрузка сети служебным трафиком. В данной статье предложен новый алгоритм ВИ, работающий по принципу дерева. Назовем такое алгоритм условно ДВИ. Отвечать требованиям эффективности и масштабируемости. Идея алгоритма ДВИ – построить дерево, образованное объединением узлов, расположенных на всем протяжении от запросного узла до корневого узла, когда промежуточные узлы на пути являются подкорневыми, и запросные узлы - листьями дерева. Ниже описаны операции алгортима - 1. Узел C_i, желающий войти в критическую секцию(CS) для доступа к ресурсу R, посылает сообщение ЗАПРОС корневому узлу (B), который связан с ресурсом R. 2. Каждый узел, находится на пути от узла C_i до B, добавляет запись об узле C_i в очередь ждущих запросов и источник сообщения в список дочерних элементов, а затем пересылает запрос к следующему промежуточному узлу. 3. Узел B, получая запрос от узла C_i, определяет, что доступен ли ресурс R или нет. Если ресурс R доступен, корень B блокирует его для узла C_i, но если R не доступен то, B добавляет C_i в очередь ждущих запросов. 4. Когда узел C_i получает ответ от корневого узла B, он входит в CS и начинает использовать ресурс R. В то же время, когда какой-нибудь узел запрашивает доступ к ресурсу он получает ответ «нет» от корня и понимает, что ресурс R используется другим узлом и следовательно ждет. 5. По окончании своей работы в CS узел C_i отправляет В сообщение ОСВОБОЖДЕНИЕ, тем самым показывая, что закончил использование CS (т.е. ресурс R). Тогда корень отправляет сообщение ОТВЕТ «да» на следующий запрос в очереди. 6. Шаги 1-5 повторяются по мере того, как узлы хотят получить доступ к совместно используемому ресурсу R. Проведено сравнение ДВИ и существующих алгоритмов оцениваются путем имитации. Как показаны на рис.1. Несмотря на то, что графики линейны относительно числа узлов, в ДВИ - алгоритме загрузка сети служебным трафиком в среднем примерно в 3 раза меньше, чем в наилучшем варианте из отработанных алгоритмов [3]. Алгоритм может быть легко сконфигурирован для работы на любой П2П системе. Поэтому представляет по настоящему обобщенное решение рассматриваемой взоимное исключения.

Литература

1. Shiding Lin, Qiao Lian, Ming Chen, and Zheng Zhang, A practical distributed mutual exclusion protocol in dynamic peer-to-peer systems // In 3rd International Workshop on Peer-to-Peer Systems (IPTPS'04), 2004.С.1-10.

2. Moosa Muhammad, Adeep S. Cheema, Indranil Gupta: Efficient mutual exclusion in peer-to-peer systems // 6th IEEE/ACM International Workshop on Grid Computing (GRID), 2005. С. 296-299.

3. V. V. Gubarev, A. A.Obeidat, Developing End-To-End Mutual Exclusion Protocol in Peer-to-Peer Systems // The Third International Forum on Strategic Technologies (IFOST), 2008. С. 282-286.