Протоколы и расписание.
Каждая транзакция состоит из элементарных шагов (блокировка, чтение записи и т.д.).
Расписанием совокупности транзакций называется порядок, в котором выполняются элементарные шаги этих транзакций. Шаги любой транзакции должны появляться в расписании в порядке их вхождения в программу, прогоном которой является эта транзакция.
Расписание считается последовательным, если все шаги каждой транзакции выполняются последовательно; сериализуемым, если результат его реализации всегда эквивалентен результату некоторого последовательного расписания.
Для предотвращения несериализуемости расписания вводят протоколы, которые в наиболее общем смысле представляют собой ограничения на последовательность шагов, которые может выполнить транзакция. Например, протоколом является исключающая тупики стратегия запрашивания блокировок элементов в некотором фиксированном порядке.
Простая модель транзакции.
Изучим простейшую модель транзакции, которая позволяет говорить о сериализуемости. В этой модели транзакция рассматривается как последовательность операторов блокирования и разблокирования. Каждый блокированный элемент впоследствии должен быть разблокирован. Будем считать, что при между шагом LOCK A и UNLOCK A транзакция осуществляет изменение значения .
Поставим
каждой паре шагов LOCK и UNLOCK однозначную
функцию f. Вообще говоря, любой
элемент
может быть заблокирован и разблокирован
достаточно большое число раз. Поэтому
будем рассматривать последовательность
функций
,
где
– начальное значение
до выполнения любых транзакций.
Пример: : LOCK A A B C
: LOCK B …
: LOCK C …
:
UNLOCK B
: LOCK B
:
UNLOCK A
: LOCK A
:
UNLOCK C
:
UNLOCK A
: LOCK A
: LOCK C
:
UNLOCK B
:
UNLOCK C
:
UNLOCK A
Метод, позволяющий определить сериализуемость расписания.
Строится ориентированный граф , который называется графом предшествований, узлы которого соответствуют транзакциям. Определим дуги графа:
Пусть
,
где
действие вида
:
LOCK
(1)
или : UNLOCK (2),
и указывает транзакцию, к которой относится данный шаг.
Для
,
имеющего вид (2) ищем действие
вида:
:
LOCK
.
Если оно существует, то строим дугу из
в
.
Интуитивный смысл этой дуги заключается
в том, что в любом последовательном
расписании, эквивалентном
,
должно предшествовать
.
Если в графе
имеется цикл, то
не сериализуемо.
При отсутствии циклов
находим такой линейный порядок
транзакций, чтобы
предшествовала бы
всякий раз, когда существует дуга
.
Это всегда можно сделать при помощи
процесса так называемой топологической
сортировки, который заключается в
следующем: из ацикличности
следует, что в нем существует некоторый
узел
,
который не имеет входящих дуг. Заносим
в список, удалив его из графа. Процесс
повторяется до тех пор, пока в графе не
останется узлов. Пример:
Чтобы построить дуги,
рассмотрим каждый шаг UNLOCK. Например,
4-й шаг:
:
UNLOCK В. За ним следует 5-й шаг:
:
LOCK B. Строим
.
За шагом 8:
:
UNLOCK С следует шаг 11:
:
LOCK С; между ними нет иных шагов, блокирующих
С. Строим
.
Шаги 6 и 7 дают ещё одну дугу:
.
Т.к. существует цикл в графе, расписание
не сериализуемо.
Расписание сериализуемо, если транзакция выполняет все свои команды блокирования и разблокирования, и после этого выполняется другая транзакция.
Пример: : LOCK A
: UNLOCK A
: LOCK A
: UNLOCK A
: LOCK B
: UNLOCK B
: LOCK B
: UNLOCK B
сериализуемое расписание.
Транзакции, в которых все операции блокирования предшествуют всем операциям разблокирования, называются двухфазными. Первая фаза называется фазой блокировки, а вторая – фазой разблокирования.
Теорема: Любое расписание двухфазных транзакций является сериализуемым.