Инструменты пользователя

Инструменты сайта


examination:rsubd:question18

Вопрос №18. Проблема управления параллельностью

Управление параллельностью

Как было указано ранее, управление параллельным доступом в большинстве распределенных систем строится на использовании механизма блокировки, т.е. точно так, как и в большинстве нераспределенных систем. Однако в распределенных системах запросы на проверку, установку и отмену блокировки становятся сообщениями (если считать, что рассматриваемый объект расположен на удаленном узле), а сообщения создают дополнительные издержки. Рассмотрим, например, транзакцию t обновления объекта, для которого существуют дубликаты на n удаленных узлах. Если каждый узел отвечает за блокировку объектов, которые на нем хранятся (как предполагается в соответствии с принципом локальной независимости), то непосредственная реализация будет требовать по крайней мере 5n таких сообщений:

  • n запросов на блокировку;
  • n разрешений на блокировку;
  • n сообщений об обновлении;
  • n подтверждений;
  • n запросов на снятие блокировки.

Безусловно, можно разумно воспользоваться комбинированными сообщениями. Например, можно объединить сообщение запроса на блокировку и сообщение об обновлении, а также сообщение о разрешении блокировки и сообщение о подтверждении. Но даже в этом случае общее время обновления может быть на порядок больше, чем в централизованной системе.

Для решения проблемы обычно выбирается стратегия первичной копии. Для данного объекта А все операции блокировки будет обрабатывать узел, содержащий его первичную копию (напомним, что первичные копии различных объектов будут в общем случае размещаться на разных узлах). При использовании этой стратегии набор всех копий объекта с точки зрения блокировки можно рассматривать как единый объект, а общее количество сообщений будет сокращено с 5n до 2n+3 (один запрос блокировки, одно разрешение блокировки, n обновлений, n подтверждений и один запрос на снятие блокировки). Но обратите внимание на то, что это решение влечет за собой серьезную потерю независимости – транзакция может теперь не завершиться, если первичная копия окажется недоступной, даже если в транзакции выполнялось лишь чтение и локальная копия была доступна. Таким образом, у стратегии первичной копии есть нежелательный побочный эффект – снижение уровня производительности и доступности как для выборки, так и для обновления.)

Другая проблема, касающаяся блокировок в распределенных системах, состоит в том, что блокировка может привести к состоянию глобальной взаимоблокировки, охватывающей два или больше узлов. Обратимся, например, к рис. 5, где показана описанная ниже последовательность событий.

  • Агент транзакции Т2 на узле X ожидает, пока агент транзакции Т1 на узле X освободит блокировку.
  • Агент транзакции T1 на узле X ожидает, пока агент транзакции Т1 на узле Y завершит транзакцию.
  • Агент транзакции Т1 на узле Y ожидает, пока агент транзакции Т2 на узле У освободит блокировку.
  • Агент транзакции Т2 на узле Y ожидает, пока агент транзакции Т2 на узле X завершит транзакцию. Налицо явная взаимоблокировка.

В состоянии глобальной взаимоблокировки, подобном только что рассмотренному, никакой узел не может обнаружить ситуацию взаимоблокировки, используя лишь собственную внутреннюю информацию. Иными словами, в локальном графе ожиданий нет никаких циклов, и подобный цикл возникает только при объединении локальных графов в общий глобальный граф. Итак, для обнаружения состояния глобальной блокировки требуются дополнительные коммуникационные расходы, поскольку необходимо, чтобы отдельные локальные графы рассматривались вместе.


Рис. 5. Пример состояния глобальной взаимоблокировки

examination/rsubd/question18.txt · Последние изменения: 2014/01/15 08:21 (внешнее изменение)