179
Собственно несовместимый анализ
Длинная транзакция выполняет некоторый анализ по всей таблице, например, подсчитывает общую сумму денег на счетах клиентов банка для главного бухгалтера. Пусть на всех счетах находятся одинаковые суммы, например, по 100 руб. Короткая транзакция в этот момент выполняет перевод 50 руб. с одного счета на другой так, что общая сумма по всем счетам не меняется.
|
Транзакция А |
Время |
Транзакция В |
|
|
|
|
|
|
|
Блокирует счет Р1 S-блокировкой |
↓ |
--- |
|
|
t1 |
|
||
|
|
↓ |
--- |
|
|
Чтение счета Р1=100 и суммирование. |
t 2 |
|
|
|
SUM=100 |
↓ |
|
|
|
--- |
t 3 |
Блокирует счет Р3 X-блокировкой |
|
|
|
↓ |
(разрешено) |
|
|
--- |
t 4 |
Снятие денег со счета Р3. |
|
|
|
↓ |
(на счете Р3 вместо 100 уже 50) |
|
|
--- |
t 5 |
Попытка X-блокировки счета Р1 |
|
|
--- |
↓ |
для его обновления отвергается |
|
|
t 6 |
Ожидание |
|
|
|
--- |
↓ |
Ожидание… |
|
|
t 7 |
|
||
|
Чтение счета Р2=100 и суммирование. |
↓ |
Ожидание… |
|
|
t 8 |
|
||
|
SUM=200 |
↓ |
|
|
|
Попытка S-блокировки счета Р1 |
t 9 |
Ожидание… |
|
|
для его чтения отвергается |
↓ |
|
|
|
Ожидание… |
t 10 |
Ожидание… |
|
|
Ожидание … |
↓ |
Ожидание … |
|
|
Результат. |
|
|
|
|
Обе транзакции ожидают друг друга |
и не могут продолжаться. Опять |
||
возникла ситуация тупика. |
|
|
|
|
Выводы.
Таким образом, использование протокола доступа к данным с использованием блокировок в рассмотренных выше ситуациях конфликтов транзакций, позволило получить следующие результаты.
•Проблема потери результатов обновления – возник тупик.
•Проблема незафиксированной зависимости (чтение «грязных» данных) –
проблема разрешилась.
180
•Неповторяемое считывание – проблема разрешилась.
•Появление фиктивных элементов – проблема не разрешилась.
•Проблема несовместимого анализа – возник тупик.
Видно, что использование блокировок позволило часть из приведенных проблем решить. Однако возникла новая проблема – тупики.
Общий вид тупика.
Транзакция А |
Время |
Транзакция В |
|
|
|
Успешная блокировка объекта Р1 |
↓ |
--- |
t1 |
||
--- |
↓ |
Успешная блокировка объекта Р2 |
t 2 |
||
|
↓ |
--- |
Попытка блокировки объекта Р2 |
t 3 |
|
отвергается из-за блокировки, |
↓| |
|
наложенной транзакцией B |
↓ |
|
Ожидание… |
t 4 |
Попытка блокировки объекта Р1 |
|
↓ |
отвергается из-за блокировки, |
Ожидание… |
↓ |
наложенной транзакцией A |
t 5 |
Ожидание… |
|
|
↓ |
|
Ожидание … |
↓ |
Ожидание … |
Как видно, ситуация тупика может возникать при наличии не менее двух транзакций, каждая из которых выполняет не менее двух операций. На самом деле в тупике может участвовать и большее число транзакций, ожидающих друг друга.
Так как нормального выхода их тупиковой ситуации с помощью механизма блокировок нет, то такую ситуацию необходимо распознавать и устранять. Методом разрешения тупиковой ситуации является откат одной из транзакций, выбираемой в качестве транзакции-жертвы, так чтобы другие транзакции продолжили свою работу. После разрешения тупика, транзакцию, выбранную в качестве жертвы необходимо повторить заново.
Можно представить два принципиальных подхода к обнаружению тупиковой ситуации и выбору транзакции-жертвы.
1.СУБД не следит за возникновением тупиков. Транзакции сами принимают решения, быть ли им жертвой.
2.За возникновением тупиковой ситуации следит сама СУБД, она же принимает решение, какой транзакцией пожертвовать.
Первый подход характерен для так называемых персональных СУБД
(Clipper, FoxPro и т.п.). Этот метод является более простым и не требует дополнительных ресурсов системы. Для транзакций задается время ожидания (или число попыток), в течение которого транзакция пытается установить
181
нужную блокировку. Если за указанное время (или после указанного числа попыток) блокировка не установилась, то транзакция откатывается (или генерируется ошибочная ситуация). За простоту использования этого метода приходиться расплачиваться тем, что транзакции-жертвы выбираются, вообще говоря, случайным образом. В результате – из-за одной простой транзакции может откатиться более дорогая транзакция, на выполнение которой уже потрачено много времени и ресурсов системы.
Второй способ характерен для промышленных СУБД (Oracle, DB2, MS SQL Server и т.п.). В этом случае система сама следит за возникновением ситуации тупика, путем построения (или постоянного поддержания) так называемого графа ожидания транзакций.
Граф ожидания транзакций – это ориентированный граф, в котором существует два типа вершин – вершины, соответствующие транзакциям, и вершины, соответствующие объектам блокировки. В этом графе существует дуга, ведущая из вершины-транзакции к вершине-объекту,
если даже для этой транзакции существует удовлетворительная блокировка объекта. В графе существует дуга из вершины-объекта к вершине-транзакции, если транзакция ожидает удовлетворения захвата объекта.
Нетрудно показать, что в системе существует ситуация тупика, если в графе ожидания транзакций имеется хотя бы один цикл.
Для распознавания тупика системой производиться построение графа ожидания транзакций и в этом графе ищутся циклы. Одним из методов нахождения циклов в ориентированном графе является редукция графа. Для этого из графа, прежде всего, удаляются все дуги, исходящие из вершинтранзакций, в которые входят дуги из вершин-объектов. Это как бы соответствует той ситуации, что транзакции, не ожидающие удовлетворения захватов, успешно завершились и сняли свои блокировки. Далее, для тех вершин-объектов, для которых не осталось входящих дух, но существуют исходящие, ориентация исходящих дуг изменяется на противоположную. Это моделирует удовлетворение захватов. После этого повторяют первый шаг и так до тех пор, пока на первом шаге не прекратиться удаление дуг. Если после этого в графе остаются не удаленные дуги, то они обязательно образуют цикл.
Разрушение тупика начинается с выбора транзакции-жертвы, которая откатывается для обеспечения возможности продолжения работы других транзакций. Критерий выбора транзакции-жертвы обычно основан на учете стоимости транзакции, определяемой на основе многофакторной оценки, в которую с разными весами входят время выполнения транзакции, число накопленных транзакцией блокировок, приоритет транзакции и другие факторы.