Атрибуты транзакции

Определим для транзакции T следующие атрибуты:

a(T) – время прихода;

s(T) – время начала работы;

– число порожденных отложенных транзакций в момент времени t;

P_t(T) – приоритет транзакции в момент времени t.

Некоторые атрибуты могут меняться во время выполнения транзакции. Они помечены индексом t, что означает значение атрибута в момент времени t.

Методы назначения приоритетов, описанные в следующих пунктах, используют следующие оценки:

X_t(T) – оставшееся время выполнения;

С_t(T) – время завершения (C_t(T)=t+X_t(T));

S_t(T) – запас свободного времени (S_t(T)=d(T)–C_t(T));

– число непосредственных транзакций, порожденных T после времени t;

– число отложенных транзакций, порожденных T после времени t;

– среднее время выполнения непосредственной транзакции, порожденной транзакцией T;

– среднее время выполнения отложенной транзакции, порожденной транзакцией T;

– оставшееся среднее время выполнения транзакции, T учитывая все ее подтранзакции на момент времени t:

; (4.9.6)

– оставшийся средний запас свободного времени на момент времени t, учитывая все ее подтранзакции:

. (4.9.7)

Заметим, что наименьшее значение P_t(T) равносильно наибольшему приоритету. Во всех описанных ниже методах директивный срок подтранзакции назначается равным директивному сроку породившей ее транзакции, т.е. d(T^sub)=d(T).

4.9.15 Приоритет «непосредственной» транзакции

Рассмотрим некоторые из политик назначения приоритетов непосредственным подтранзакциям.

· PD метод:

Согласно этой политике непосредственной подтранзакции назначается приоритет, равный директивному сроку отцовской транзакции. Более того, приоритет отцовской транзакции не меняется после порождения подтранзакции. Т.е., если – i-я непосредственная транзакция, порожденная транзакцией T в момент времени t, то .

· DIV метод:

Рассмотрим транзакцию T, которая в момент времени t порождает непосредственную транзакцию , тогда:

(4.9.8)

Пусть транзакция заканчивается в момент времени w>t, тогда приоритет отцовской транзакции будет следующим:

. (4.9.9)

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

· SL метод:

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

Пусть, например, транзакция T стартует в момент времени t₀, а момент времени t является потенциальным для порождения i-й непосредственной транзакции . Первоначальный на момент времени t₀ приоритет транзакции T вычисляется как:

.

Если в момент времени t транзакция была порождена, то:

(4.9.10)

.

Если в момент времени t подтранзакция не была порождена, то:

. (4.9.11)

4.9.16 Приоритет «отложенной» транзакции

Рассмотрим те же политики назначения приоритетов, что и для случая «непосредственной» транзакции.

Назначение приоритета для случая порождения «отложенной» транзакции очень похоже, как и в случае порождения «непосредственной» транзакции. В случае использования DIV и SL методов приоритет отцовской транзакции будет изменяться, когда порождается отложенная транзакция, а в случае использования PD метода нет.

Рассмотрим транзакцию T, которая порождает i-ю отложенную транзакцию в момент времени t. Тогда приоритет породившей транзакции будет следующим:

· PD метод:

P_t(T)=d(T)

· DIV метод:

P_t(T)=P_t(T)–X_t( ). (4.9.12)

· SL метод:

. (4.9.13)

Предположим, что транзакция T породила m отложенных транзакций до своего завершения. Пусть – j-ая отложенная транзакция, j£m, начинает свою работу в момент времени w (после того, как породившая транзакция закончила свою работу). Тогда приоритет транзакции будет следующим:

· PD метод:

. (4.9.14)

· DIV метод:

. (4.9.15)

Т.е. запас свободного времени отцовской транзакции делится поровну между всеми отложенными транзакциями. Эта величина плюс оценка времени выполнения подтранзакции определяет приоритет подтранзакции.

· SL метод:

. (4.9.16)

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

Заключение

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

В системах реального времени транзакции имеют ассоциированные директивные сроки, а используемые критерии производительности отличаются от тех, что используются в классических СУБД. Поэтому протоколы управления транзакциями, используемые в классических СУБД, показывают далеко не лучшую производительность в системах реального времени.

За последние несколько лет был предложен ряд специализированных протоколов управления транзакциями для систем реального времени, которые учитывают специфику таких систем. Интересно, что в отличие от случая классических СУБД, в системах реального времени «оптимистические» протоколы показывают лучшие результаты по сравнению с «пессимистическими».

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

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

Конкретные системы реального времени зачастую имеют очень жесткие требования к производительности алгоритмов управления транзакциями, и обобщенные подходы им плохо подходят. С другой стороны, такие системы часто имеют ряд уникальных особенностей, которые позволяют придумать специализированный протокол управления транзакциями для этой конкретной системы, который будет показывать лучшие результаты. Обычно это достигается при помощи оптимизации производительности для класса наиболее важных транзакций за счет ухудшения ее для прочих транзакций.

В данной теме затронута только часть проблем, связанных с поддержкой целостности данных в СУБД, но многое осталось за ее рамками. В частности, известны попытки использовать другие критерии корректности, отличные от сериализуемости [79], другие наборы свойств транзакций (вместо ACID). Также в системах реального времени большое внимание уделяется формальным методам, используемых для моделирования, спецификации ограничений, проверки корректности [79].