ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 1575
Скачиваний: 23
171
существовать
несколько
правильных
графиков
запусков
транзакций
,
приводящих
к
разным
результатам
при
одном
и
том
же
начальном
состоянии
базы
данных
.
Задача
обеспечения
изолированной
работы
пользователей
не
сводиться
просто
к
нахождению
правильных
(
сериальных
)
графиков
запуска
транзакций
.
Такая
задача
решается
,
например
,
очевидным
способом
–
просто
организацией
очереди
транзакций
.
Проблема
состоит
в
оптимизации
графика
запуска
транзакций
с
точки
зрения
эффективности
доступа
пользователей
к
данным
,
например
,
с
точки
зрения
суммарного
времени
,
затрачиваемого
на
выполнение
транзакций
,
или
минимизации
времени
ожидания
транзакций
,
очевидно
,
при
обеспечении
изолированности
транзакций
.
Следует
,
однако
,
заметить
,
что
нахождение
строго
оптимального
по
выбранному
критерию
графика
запуска
транзакций
оказывается
в
реальных
условиях
недостижимым
из
-
за
того
,
что
,
как
правило
,
заранее
неизвестно
–
какие
транзакции
будут
поступать
,
время
поступления
и
длительность
поступающих
транзакций
и
т
.
д
.
Поэтому
на
практике
используются
решения
,
позволяющие
лишь
в
той
или
иной
степени
приближаться
к
оптимальному
решению
.
14.3.
Методы
сериализации
транзакций
Существуют
два
базовых
подхода
к
сериализации
транзакций
:
•
подход
,
основанный
на
синхронизационных
захватах
или
блокировках
объектов
базы
данных
,
и
•
подход
,
основанный
на
использовании
временных
меток
.
Суть
обоих
подходов
состоит
в
обнаружении
конфликтов
транзакций
и
их
устранении
.
Ниже
эти
подходы
рассматриваются
более
подробно
.
Предварительно
следует
заметить
,
что
для
каждого
из
этих
подходов
имеется
две
разновидности
–
пессимистическая
и
оптимистическая
.
Пессимистические
методов
ориентированны
на
ситуацию
,
когда
конфликты
возникают
часто
.
При
использовании
этих
методов
,
конфликты
распознаются
и
разрешаются
немедленно
при
их
возникновении
.
Оптимистические
методы
,
напротив
,
используются
в
случаях
,
когда
конфликты
транзакций
достаточно
редкие
.
Эти
методы
основываются
на
том
,
что
результаты
всех
операций
модификации
базы
данных
сохраняются
в
рабочей
памяти
транзакций
.
Реальная
модификация
базы
данных
производится
только
на
стадии
фиксации
транзакций
.
И
только
в
этот
момент
проверяется
,
не
возникают
ли
конфликты
с
другими
транзакциями
.
172
Ниже
мы
ограничимся
рассмотрением
более
распространенных
пессимистических
разновидностей
методов
сериализации
транзакций
.
Пессимистические
методы
сравнительно
просто
трансформируются
в
свои
оптимистические
варианты
.
14.4.
Сериализация
транзакций
с
использованием
синхронизационных
захватов
(
блокировок
)
Наиболее
распространенным
в
централизованных
СУБД
(
включая
системы
,
основанные
на
архитектуре
«
клиент
-
сервер
»)
является
подход
,
основанный
на
соблюдении
двухфазового
протокола
синхронизационных
захватов
(
блокировок
)
объектов
базы
данных
(two-phase blocking protocol).
Суть
протокола
двухфазной
блокировки
состоит
в
следующем
.
1.
Перед
выполнением
каких
-
либо
операций
с
некоторым
объектом
базы
данных
транзакция
должна
заблокировать
этот
объект
.
2.
После
снятия
блокировки
транзакция
не
должна
накладывать
никаких
других
блокировок
.
Блокировки
,
рассматриваемые
в
этом
протоколе
,
не
различаются
по
типам
и
считаются
монопольными
.
Есвараном
(Esvaran)
была
доказана
важная
теорема
двухфазной
блокировки
,
которая
кратко
может
быть
сформулирована
следующим
образом
:
Если
все
транзакции
в
смеси
подчиняются
«
протоколу
двухфазной
блокировки
»,
то
для
всех
чередующихся
графиков
запуска
транзакция
существует
возможность
их
упорядочения
(
сериализации
).
Протокол
называется
двухфазным
,
потому
что
он
характеризуется
двумя
фазами
:
•
Фаза
1 –
нарастание
блокировок
.
Во
время
этой
фазы
накладываются
блокировки
,
и
производится
работа
с
заблокированными
объектами
.
•
Фаза
2 –
снятие
блокировок
.
Во
время
этой
фазы
блокировки
только
снимаются
.
Работа
с
ранее
заблокированными
данными
может
быть
возобновлена
.
Работа
транзакции
,
подчиняющейся
двухфазному
протоколу
блокировок
,
может
выглядеть
приблизительно
,
как
на
рис
. 14.1.
173
Блокирование
объекта
А
Блокирование
объекта
B
Работа
с
объектом
А
Работа
с
объектом
B
Работа
с
объектом
B
Освобождение
объекта
А
Освобождение
объекта
B
Начало
транзакции
Конец
транзакции
1
фаза
(
нарастание
блокировок
)
2
фаза
(
снятие
блокировок
)
Рис
. 14.1
Работа
транзакции
по
протоколу
двухфазной
блокировки
На
следующем
рисунке
показан
альтернативный
пример
транзакции
,
которая
не
подчиняется
протоколу
двухфазной
блокировки
.
Блокирование
объекта
А
Блокирование
объекта
B
Работа
с
объектом
А
Работа
с
объектом
B
Освобождение
объекта
А
Освобождение
объекта
B
Начало
транзакции
Конец
транзакции
Рис
. 14.2.
Транзакция
,
не
подчиняющаяся
протоколу
двухфазной
блокировки
.
На
практике
,
как
правило
,
вторая
фаза
(
рис
. 14.1)
сводится
к
одной
операции
завершения
транзакции
(
или
отката
транзакции
)
с
одновременным
снятием
всех
блокировок
.
Если
некоторая
транзакция
А
не
подчиняется
протоколу
двухфазной
блокировки
(
и
,
следовательно
,
состоит
не
менее
чем
из
двух
операций
блокирования
и
разблокирования
),
то
всегда
возможно
построение
другой
транзакции
В
,
которая
при
чередующемся
выполнении
вместе
с
А
приводит
к
графику
,
не
подлежащему
упорядочению
,
т
.
е
.
к
неверному
.
В
современных
СУБД
используются
модификации
двухфазного
протокола
,
когда
накладываемые
на
объекты
базы
данных
блокировки
имеют
различные
типы
.
Различают
два
типа
блокировок
:
•
Монопольные
блокировки
(
X
-
блокировки
,
X
-locks – eXclusive locks) –
блокировки
без
взаимного
доступа
(
блокировка
записи
)
•
Разделяемые
блокировки
(
S
-
блокировки
,
S
-locks – Shared locks) –
блокировки
с
взаимным
доступом
(
блокировка
чтения
).
174
Если
транзакция
А
блокирует
объект
при
помощи
X
-
блокировки
,
то
любой
доступ
к
этому
объекту
со
стороны
других
транзакций
отвергается
.
Если
транзакция
А
блокирует
объект
при
помощи
S
-
блокировки
,
то
•
запросы
со
стороны
других
транзакций
на
X
-
блокировку
этого
объекта
будут
отвергнуты
,
•
запросы
со
стороны
других
транзакций
на
S
-
блокировку
этого
объекта
будут
приняты
.
Правила
взаимного
доступа
к
заблокированным
объектам
можно
представить
в
виде
матрицы
совместимости
блокировок
.
Если
транзакция
А
наложила
блокировку
на
некоторый
объект
,
а
транзакция
В
после
этого
пытается
наложить
блокировку
на
этот
же
объект
,
то
успешность
блокирования
транзакцией
В
объекта
описывается
следующей
таблицей
:
Транзакция
В
пытается
наложить
блокировку
:
Транзакция
А
заблокировала
объект
:
S
-
блокировку
X
-
блокировку
S
-
блокировкой
Разрешено
Запрещено
из
-
за
конфликта
R-W
X
-
блокировкой
Запрещено
из
-
за
конфликта
W-R
Запрещено
из
-
за
конфликта
W-W
Матрица
совместимости
S
-
и
X
-
блокировок
.
Три
случая
,
когда
транзакции
В
не
разрешается
блокировать
объект
,
соответствует
приведенным
выше
трем
видам
конфликтов
между
транзакциями
.
Доступ
к
объектам
базы
данных
на
чтение
и
запись
должен
осуществляться
в
соответствии
со
следующим
протоколом
доступа
к
данным
.
1.
Прежде
чем
получить
доступ
к
объекту
для
его
чтения
,
транзакция
должна
наложить
на
этот
объект
S
-
блокировку
.
2.
Прежде
чем
получить
доступ
к
объекту
для
его
обновления
,
транзакция
должна
наложить
на
этот
объект
X
-
блокировку
.
Если
транзакция
уже
заблокировала
этот
объект
S
-
блокировкой
(
для
чтения
),
то
перед
обновлением
объекта
S
-
блокировка
должна
быть
заменена
X
-
блокировкой
.
3.
Если
блокировка
объекта
транзакцией
В
отвергается
из
-
за
того
,
что
объект
уже
заблокирован
транзакцией
А
,
то
транзакция
В
переходит
в
состояние
ожидания
.
Транзакция
В
будет
находится
в
состоянии
ожидания
до
тех
пор
,
пока
транзакция
А
не
снимет
блокировку
объекта
.
4.
X
-
блокировки
,
наложенные
транзакцией
А
,
сохраняются
до
конца
транзакции
А
и
не
могут
быть
отменены
никакой
другой
транзакцией
.
175
14.5.
Решение
проблем
параллелизма
при
помощи
блокировок
Рассмотрим
,
как
будут
себя
вести
транзакции
,
вступающие
в
конфликт
при
доступе
к
данным
,
если
они
подчиняются
приведенному
выше
протоколу
доступа
к
данным
.
Проблема
потери
результатов
обновления
Две
транзакции
по
очереди
записывают
некоторые
данные
в
одну
и
ту
же
строку
и
фиксируют
изменения
.
Транзакция
А
Время
Транзакция
В
↓
t
1
---
Блокирует
кортеж
P
S
-
блокировкой
↓
Чтение
значения
Р
0
из
кортежа
P
t
2
---
↓
---
t
3
↓
Блокирует
кортеж
P
S
-
блокировкой
(
разрешена
)
---
t
4
Чтение
значения
Р
0
из
кортежа
P
↓
t
5
---
Попытка
X
-
блокировки
кортежа
Р
для
его
обновления
отвергается
↓
t
6
Ожидание
снятия
блокировки
с
кортежа
Р
↓
Попытка
X
-
блокировки
кортежа
Р
для
его
обновления
отвергается
Ожидание
…
t
5
↓
Ожидание
снятия
блокировки
с
кортежа
Р
Ожидание
…
t
6
Ожидание
…
↓
Ожидание
…
Ожидание
…
Как
видно
из
приведенной
схемы
,
обе
транзакции
успешно
накладывают
S
-
блокировки
и
получают
доступ
для
чтения
значения
объекта
Р
.
Для
того
,
чтобы
осуществить
обновление
объекта
Р
,
транзакция
А
пытается
наложить
на
него
X
-
блокировку
.
Эта
блокировка
отвергается
,
т
.
к
.
объект
Р
уже
заблокирован
S
-
блокировкой
,
осуществленной
транзакцией
В
.
Транзакция
А
переходит
в
состояние
ожидания
до
тех
пор
,
пока
транзакция
В
не
освободит
объект
.
Транзакция
В
,
в
свою
очередь
,
также
пытается
для
обновления
значения
объекта
Р
наложить
на
него
X
-
блокировку
.
Эта
блокировка
также
отвергается
,
так
как
объект
Р
уже
заблокирован
S
-
блокировкой
транзакции
А
.
Транзакция
В