Материал: Базы данных и их безопасность. Плотников Д.Г

БД на счет а1, после чего блокировка а1 отменяется. Затем Т15 устанавливает блокировку а1 для записи, считывает его текущее значение, изменяет и записывает новое значение, после чего отменяет блокировку а1. Наконец, Т16 устанавливает блокировку счета а1 для чтения и считывает его текущее значение. В этот момент происходит отказ в работе Т14, в результате которого происходит ее откат. Однако, поскольку Т15 зависит от результатов Т14, для нее также необходимо выполнить откат. Аналогично - для Т16.

181

Подобная ситуация, в которой отмена единственной транзакции приводит к целой серии откатов зависящих от нее транзакций, называется каскадным откатом.

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

Одним из возможных вариантов является дополнение обычного двухфазного протокола блокировки требованием откладывать выполнение отмены всех установленных блокировок до конца транзакции – как в предыдущих примерах. В подобном случае продемонстрированная в последнем примере проблема никогда не возникнет, поскольку Т15 не сможет установить требуемую ей блокировку для записи, пока Т14 не завершит свою работу тем или иным образом. Этот вариант протокола называется строгим 2PL. Может быть доказано, что при использовании строгого протокола двухфазной блокировки транзакции могут быть расположены в том порядке, в котором они завершают свою работу.

Другой вариант протокола 2PL, называемый ограниченным 2PL, предусматривает откладывание до конца транзакции освобождение только блокировок для записи. В большинстве СУБД реализуется один из этих двух вариантов протокола 2PL.

Взаимная блокировка

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

Кроме того, транзакции могут входить в состояние

бесконечного ожидания (самоблокировки), не имея

182

возможности установить требуемую им новую блокировку, хотя СУБД не будет фиксировать состояние взаимной блокировки. Эта ситуация возможна в случаях, когда алгоритм перевода транзакций в состояние ожидания недоработан и не принимает во внимание время, на протяжении которого транзакция уже находится в состоянии ожидания. Для исключения самоблокировок может использоваться система приоритетов, в которой приоритет транзакции тем выше, чем дольше она находится в состоянии ожидания. Альтернативным вариантом является использование для ожидающих транзакций очередей, построенной по схеме FIFO.

Взаимная блокировка – это тупиковая ситуация, которая может возникнуть, когда две (или более) транзакции находятся во взаимном ожидании освобождения блокировок, удерживаемых каждой из них (табл. 6.13).

Таблица 6.13 Пример взаимной блокировки двух транзакций

Взаимная блокировка возникает, поскольку каждая из двух транзакций входит в состояние ожидания освобождения

183

требуемого ресурса другой транзакцией. В момент времени t2 транзакция Т17 запрашивает и осуществляет блокировку для записи элемента данных balх, а момент времени t3 транзакция Т18 выполняет блокировку для записи элемента данных baly. Ни одна из транзакций не в состоянии продолжать работу, поскольку каждая ожидает завершения работы другой. Если в системе возникает состояние взаимной блокировки, вовлеченные в него приложения не смогут разрешить данную проблему собственными силами. Ответственность за обнаружение взаимных блокировок и выхода тем или иным образом из этой тупиковой ситуации должна быть возложена на СУБД.

К сожалению, существует только один способ нарушить состояние взаимной блокировки – выполнение одной или более транзакций должно быть отменено. Подобное действие будет сопровождаться откатом всех изменении, внесенных отмененными транзакциями.

Существует два общих метода обработки взаимных блокировок: предупреждение этих ситуаций и выявление взаимных блокировок с последующим их устранением.

При использовании метода предупреждения взаимных блокировок СУБД заранее определяет ситуации, в которых транзакция сможет вызвать появление и устранение взаимных блокировок. При использовании второго метода, СУБД допускает появление подобных ситуаций в системе, однако затем распознает их появление и организует выход из сложившейся тупиковой ситуации. Второй метод проще первого, поэтому он чаще употребим.

Выявление взаимных блокировок

Выявление взаимных блокировок обычно производится с помощью конструкции, называемой графом ожидания. Этот граф отражает зависимость транзакций друг от друга. Транзакция Ti зависит от Tj в том случае, если транз. Tj заблокировала элемент данных, необходимый для продолжения работы тр. Ti. Граф ожидания строится следующим образом.

184

Для каждой выполняющейся транзакции создается отдельная вершина.

Отдельное направленное ребро Ti->Tj

___создается для каждого случая, когда транзакция Ti ожидает освобождения элемента данных, заблокированного транзакцией

Tj.

Взаимная блокировка имеет место в том и только в том случае, если граф ожидания содержит петлю.

Граф ожидания для последнего примера представлен на рис. 6.2.

Рис. 6.2. Граф ожидания

На рис. 6.2 показан граф ожиданий для транзакций предыдущего примера. Этот граф содержит петлю (Т17-> Т18-> Т17), поэтому можно сделать заключение, что в системе имеет место ситуация взаимной блокировки.

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

185