Алгоритм проверки сериализуемости расписания.

Алгоритм построения последовательности транзакций начинается с создания узла в графе для каждой транзакции.

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

Если FIRST() является предком FIRST(), то: если блокирует FIRST() перед тем как это делает , строим ; в противном случае .

Пример: {продолжение}

 

 

 

ЗАЩИТА ОТ ОТКАЗОВ.

До сих пор предполагалось, что любая транзакция используется без сбоев. На практике различные обстоятельства могут препятствовать её завершению:

1) Отказ системы.

В этом случае все активные транзакции не способны завершить свою работу; возможно даже аннулирование результатов уже завершенных транзакций (они читали значения, записанные транзакциями, которые еще не завершились). В этом случае необходимо найти множество транзакций, которые следует аннулировать, чтобы возвратить систему в непротиворечивое состояние; и удостовериться, что такое состояние существует (меры 1-5).

2) Исполнение транзакции может быть принудительно прекращено до её завершения. Так, если система обнаружила тупик, то транзакция, которая явилась его причиной, может быть аннулирована.

Ошибка в транзакции (деление на 0) также может быть причиной для аннулирования транзакции (мера 4).

Меры для восстановления БД.

1. Копии БД для восстановления.

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

2. Журнал.

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

Записи журнала содержат:

1) уникальный идентификатор транзакции, вызывающей изменения;

2) старое значение элемента;

3) новое значение элемента;

4) моменты времени, характеризующие главные этапы хода выполнения транзакции: начало, конец, точка фиксации транзакции.

3. Имея дело с транзакциями, для которых нужно производить рестарт или аннулирование, удобно оперировать понятиями зафиксированных и незафиксированных транзакций.

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

1) Транзакция не может осуществить запись в БД до своей фиксации.

2) Транзакция не будет зафиксирована до тех пор, пока она не запишет все произведённые ею изменения элементов в журнал.

Первая фаза представляет собой запись данных в журнал; вторая – запись тех же самых даных в БД.

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

В случае отказа системы имеется возможность просмотреть журнал и провести рестарт всех зафиксированных транзакций, у которых не было возможности записать свои значения в БД. Если отказ системы сопровождается разрушением данных в БД, то нужно сделать рестарт всех транзакций, зафиксированных с тех пор, как была сделана последняя копия для восстановления.

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

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

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