Генералова - БД (стр. 8 )

На диаграмме состояний ожидания видно, что транзакции Т9, Т8, Т2 и Т3 образуют цикл. Именно наличие цикла и является признаком возникновения тупиковой ситуации. Поэтому в момент 3 перечисленные транзакции будут заблокированы.

Разрушение тупика начинается с выбора в цикле транзакций так называемой транзакции-жертвы, то есть транзакции, которой решено пожертвовать, чтобы обеспечить возможность продолжения работы других транзакций.

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

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

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

Для распознавания тупика здесь, так же как и в первом методе, производится построение графа ожидания транзакций и в этом графе ищутся циклы. Традиционной техникой (для которой существует множество разновидностей) нахождения циклов в ориентированном графе является редукция графа.

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

Естественно, такое насильственное устранение тупиковых ситуаций является нарушением принципа изолированности пользователей.

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

Для обеспечения сериализации транзакций синхронизационные захваты объектов, произведенные по инициативе транзакции, можно снимать только при ее завершении. Это требование порождает двухфазный протокол синхронизационных захватов — 2PL(two phase lock) или 2РС (two phase commit). В соответствии с этим протоколом выполнение транзакции разбивается на две фазы:

первая фаза транзакции — накопление захватов;

вторая фаза (фиксация или откат) — освобождение захватов.

В языке SQL введен оператор явной блокировки таблицы, который позволяет точно задать тип блокировки для всей таблицы. Синтаксис операции блокировки имеет вид:

LOCK TABLE имя_таблицы IN {SHARED | EXCLUSIVE} MODE

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

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

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

Различают два типа блокировок:

  Монопольные блокировки (X-блокировки, X-locks - eXclusive locks) - блокировки без взаимного доступа (блокировка записи).

  Разделяемые блокировки (S-блокировки, S-locks - Shared locks) - блокировки с взаимным доступом (блокировка чтения).

Если транзакция A блокирует объект при помощи X-блокировки, то всякий доступ к этому объекту со стороны других транзакций отвергается.

Если транзакция A блокирует объект при помощи S-блокировки, то

  запросы со стороны других транзакций на X-блокировку этого объекта будут отвергнуты,

  запросы со стороны других транзакций на S-блокировку этого объекта будут приняты.

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

	Транзакция B пытается наложить блокировку:
Транзакция A наложила блокировку:	S-блокировку	X-блокировку
S-блокировку	Да	НЕТ (Конфликт R-W)
X-блокировку	НЕТ (Конфликт W-R)	НЕТ (Конфликт W-W)

Таблица 1 Матрица совместимости S - и X-блокировок

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

Доступ к объектам базы данных на чтение и запись должен осуществляться в соответствии со следующим протоколом доступа к данным:

1.  Прежде чем прочитать объект, транзакция должна наложить на этот объект S-блокировку.

2.  Прежде чем обновить объект, транзакция должна наложить на этот объект X-блокировку. Если транзакция уже заблокировала объект S-блокировкой (для чтения), то перед обновлением объекта S-блокировка должна быть заменена X-блокировкой.

3.  Если блокировка объекта транзакцией B отвергается оттого, что объект уже заблокирован транзакцией A, то транзакция B переходит в состояние ожидания. Транзакция B будет находиться в состоянии ожидания до тех пор, пока транзакция A не снимет блокировку объекта.

4.  X-блокировки, наложенные транзакцией A, сохраняются до конца транзакции A.

Решение проблем параллелизма при помощи блокировок

Рассмотрим, как будут себя вести транзакции, вступающие в конфликт при доступе к данным, если они подчиняются протоколу доступа к данным.

Проблема потери результатов обновления

Две транзакции по очереди записывают некоторые данные в одну и ту же строку и фиксируют изменения.

Транзакция A	Время	Транзакция B
S-блокировка - успешна		------
Чтение		------
------		S-блокировка - успешна
------		Чтение
X-блокировка - отвергается		------
Ожидание:		X-блокировка - отвергается
Ожидание:		Ожидание:
Ожидание:		Ожидание:

Обе транзакции успешно накладывают S-блокировки и читают объект. Транзакция A пытается наложить X - блокировку для обновления объекта. Блокировка отвергается, т. к. объект уже S-заблокирован транзакцией B. Транзакция A переходит в состояние ожидания до тех пор, пока транзакция B не освободит объект. Транзакция B, в свою очередь, пытается наложить X-блокировку для обновления объекта. Блокировка отвергается, т. к. объект уже S-заблокирован транзакцией A. Транзакция B переходит в состояние ожидания до тех пор, пока транзакция A не освободит объект.

Результат. Обе транзакции ожидают друг друга и не могут продолжаться. Возникла ситуация тупика.

Проблема незафиксированной зависимости (чтение "грязных" данных, неаккуратное считывание)

Транзакция B изменяет данные в строке. После этого транзакция A читает измененные данные и работает с ними. Транзакция B откатывается и восстанавливает старые данные.

Транзакция A	Время	Транзакция B
---		S-блокировка - успешна
---		Чтение
------		X-блокировка - успешна
------		Запись
S-блокировка - отвергается		------
Ожидание:		Откат транзакции (Блокировка снимается)
S-блокировка - успешна		------
Чтение		------
Работа с прочитанными данными		------
---		------
Фиксация транзакции		---
Все правильно

Результат. Транзакция A притормозилась до окончания (отката) транзакции B. После этого транзакция A продолжила работу в обычном режиме и работала с правильными данными. Конфликт разрешен за счет некоторого увеличения времени работы транзакции A (потрачено время на ожидание снятия блокировки транзакцией B).

Проблема несовместимого анализа

Неповторяемое считывание

Транзакция A дважды читает одну и ту же строку. Между этими чтениями вклинивается транзакция B, которая изменяет значения в строке.

Транзакция A	Время	Транзакция B
S-блокировка - успешна		---
Чтение		---
------		X-блокировка - отвергается
------		Ожидание:
Повторное чтение		Ожидание:
Фиксация транзакции (Блокировка снимается)		Ожидание:
------		X-блокировка - успешна
------		Запись
------		Фиксация транзакции (Блокировка снимается)
Все правильно

Результат. Транзакция B притормозилась до окончания транзакции A. В результате транзакция A дважды читает одни и те же данные правильно. После окончания транзакции A, транзакция B продолжила работу в обычном режиме.

Фиктивные элементы (фантомы)

Транзакция A дважды выполняет выборку строк с одним и тем же условием. Между выборками вклинивается транзакция B, которая добавляет новую строку, удовлетворяющую условию отбора.

Транзакция A	Время	Транзакция B
S-блокировка строк, удовлетворяющих условию. (Заблокировано n строк)		---
Выборка строк, удовлетворяющих условию. (Отобрано n строк)		---
------		Вставка новой строки, удовлетворяющей условию.
---		Фиксация транзакции
S-блокировка строк, удовлетворяющих условию. (Заблокировано n+1 строка)		---
Выборка строк, удовлетворяющих условию. (Отобрано n+1 строк)		---
Фиксация транзакции		---
Появились строки, которых раньше не было

Результат. Блокировка на уровне строк не решила проблему появления фиктивных элементов.

Собственно несовместимый анализ

Длинная транзакция выполняет некоторый анализ по всей таблице, например, подсчитывает общую сумму денег на счетах клиентов банка для главного бухгалтера. Пусть на всех счетах находятся одинаковые суммы, например, по $100. Короткая транзакция в этот момент выполняет перевод $50 с одного счета на другой так, что общая сумма по всем счетам не меняется.

Транзакция A	Время	Транзакция B
S-блокировка счета - успешна		---
Чтение счета и суммирование.		---
------		X-блокировка счета - успешна
------		Снятие денег со счета.
---		X-блокировка счета - отвергается
---		Ожидание:
S-блокировка счета - успешна		Ожидание:
Чтение счета и суммирование.		Ожидание:
S-блокировка счета - отвергается		Ожидание:
Ожидание:		Ожидание:
Ожидание:		Ожидание:

Результат. Обе транзакции ожидают друг друга и не могут продолжаться. Возникла ситуация тупика.