Итак, при использовании протокола доступа к данным с использованием блокировок возникают проблемы - тупики:
- Проблема потери результатов обновления - возник тупик.
- Проблема несовместимого анализа - возник тупик.
Общий вид тупика (dead locks) следующий:
| Транзакция A | Время | Транзакция B |
Блокировка объекта  - успешна
| 
| --- |
| --- | 
| Блокировка объекта  -успешна
|
| Блокировка объекта - конфликтует с блокировкой, наложенной транзакцией B
| 
| --- |
| Ожидание… | 
| Блокировка объекта - конфликтует с блокировкой, наложенной транзакцией A
|
| Ожидание… | 
| Ожидание… |
| Ожидание… | Ожидание… |
Т.к. нормального выхода из тупиковой ситуации нет, то такую ситуацию необходимо распознавать и устранять. Методом разрешения тупиковой ситуации является откат одной из транзакций (транзакции-жертвы) так, чтобы другие транзакции продолжили свою работу. После разрешения тупика, транзакцию, выбранную в качестве жертвы можно повторить заново.
Выделяют два принципиальных подхода к обнаружению тупиковой ситуации и выбору транзакции-жертвы:
3. СУБД не следит за возникновением тупиков. Транзакции сами принимают решение, быть ли им жертвой.
4. За возникновением тупиковой ситуации следит сама СУБД, она же принимает решение, какой транзакцией пожертвовать.
Первый подход характерен для так называемых настольных СУБД (Access, FoxPro и т.п.). Этот метод является более простым и не требует дополнительных ресурсов системы. Для транзакций задается время ожидания (или число попыток), в течение которого транзакция пытается установить нужную блокировку. Если за указанное время (или после указанного числа попыток) блокировка не завершается успешно, то транзакция откатывается (или генерируется ошибочная ситуация). За простоту этого метода приходится платить тем, что транзакции-жертвы выбираются, вообще говоря, случайным образом. В результате из-за одной простой транзакции может откатиться очень дорогая транзакция, на выполнение которой уже потрачено много времени и ресурсов системы.
Второй способ характерен для промышленных СУБД (ORACLE, MS SQL Server и т.п.). В этом случае система сама следит за возникновением ситуации тупика, путем построения (или постоянного поддержания) графа ожидания транзакций.
Основой обнаружения тупиковых ситуаций является построение (или постоянное поддержание) графа ожидания транзакций.
Граф ожидания транзакций - это ориентированный двудольный граф, в котором существует два типа вершин - вершины, соответствующие транзакциям, и вершины, соответствующие объектам захвата. В этом графе существует дуга, ведущая из вершины-транзакции к вершине-объекту, если для этой транзакции существует удовлетворенный захват объекта. В графе существует дуга из вершины-объекта к вершине-транзакции, если транзакция ожидает удовлетворения захвата объекта.
Например:
где P1, P2, P3 – параллельные транзакции, R – элемент обработки.
Одну из транзакций, попавших в цикл, необходимо откатить, причем, система сама может выбрать эту транзакцию в соответствии с некоторыми стоимостными соображениями (например, самую короткую, или с минимальным приоритетом и т.п.).
Граф ожидания представляет собой ориентированный граф G¢ = (V¢, E¢), состоящий из множества вершин V¢ – определяющих выполняемые транзакций и множества ориентированных ребер или дуг E¢ – формируемых следующим образом:
7. Создается вершина, соответствующая каждой транзакции.
8. Создается дуга A → B, если транзакция A ожидает освобождение элемента данных, заблокированного в настоящее время транзакцией B.
Взаимоблокировка имеет место, если граф ожидания содержит цикл.