Материал: Л-6 - Сеансы, транзакции и блокировки

Граф состояний ожидания транзакций

Направленный граф, в вершинах которого расположены имена транзакции.

Если транзакция А1 ждет окончания транзакции А2, то из вершины А1 в вершину А2 идет стрелка. Стрелки могут быть помечены именами заблокированных объектов и типом блокировки.

Признак тупика – наличие в графе цикла транзакций.

Пример графа состояний ожидания транзакций

Разрушение тупика

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

время выполнения,

число накопленных захватов,

приоритет.

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

Двухфазная блокировка

Для заданного набора транзакций любой порядок их выполнения называется графиком запуска:

последовательный график – выполнение транзакций по одной без их чередования;

чередующийся график – непоследовательное выполнение транзакций.

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

Теорема двухфазной блокировки

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

Протокол двухфазной блокировки 2PL (two phase lock)

или 2РС (two phase commit):

перед выполнением каких-либо операций с некоторым объектом транзакция должна заблокировать этот объект;

после снятия блокировки транзакция не должна накладывать никаких других блокировок.