17244

Конфликты между транзакциями

Лекция

Информатика, кибернетика и программирование

Лекция №8 Конфликты между транзакциями Устно. Анализ проблем параллелизма показывает что если не предпринимать специальных мер то при работе в смеси нарушается свойство И изолированность транзакций. Транзакции реально мешают друг другу получать правильные резул

Русский

2013-06-30

77 KB

6 чел.

Лекция №8

Конфликты между транзакциями

Устно. Анализ проблем параллелизма показывает, что если не предпринимать специальных мер, то при работе в смеси нарушается свойство (И) изолированность транзакций. Транзакции реально мешают друг другу получать правильные результаты. Однако не всякие транзакции мешают друг другу. Очевидно, что транзакции не мешают друг другу, если они обращаются к разным данным или выполняются в разное время.

Определение. Транзакции называются конкурирующими, если они пересекаются по времени и обращаются к одним и тем же данным.

В результате конкуренции между транзакциями возникают конфликты доступа к данным. Различают следующие виды конфликтов:

  •  W-W (Запись - Запись). Первая транзакция изменила значение и не закончилась. Вторая транзакция пытается изменить это значение. Результат - потеря обновления.
  •  R-W (Чтение - Запись). Первая транзакция считала значение и не закончилась. Вторая транзакция пытается изменить это значение. Результат - несовместимый анализ данных (неповторяемое считывание).
  •  W-R (Запись - Чтение). Первая транзакция изменила значение и не закончилась. Вторая транзакция пытается считать это значение. Результат - чтение "грязных" данных.

Конфликты типа R-R (Чтение - Чтение) отсутствуют, т.к. данные при чтении не изменяются.

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

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

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

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

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

Определение. График запуска транзакции называется правильным, (сериализуемым), если он эквивалентен какому-либо последовательному графику.

Замечание. При выполнении двух различных последовательных (а, следовательно, правильных) графиков, содержащих один и тот же набор транзакций, могут быть получены различные результаты. Действительно, пусть транзакция A заключается в действии "Сложить X с 1", а транзакция B - "Удвоить X". Тогда последовательный график {A, B} даст результат 2(X+1), а последовательный график {B, A} даст результат 2X+1. Таким образом, может существовать несколько правильных графиков транзакций, приводящих к разным результатам при одном и том же начальном состоянии БД.

Модель конфликтов транзакций. Граф предшествования

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

Для проверки упорядоченности графиков используется граф предшествования (граф упорядоченности).

Определение. Для графика выполнения множества транзакций = {A, B} граф предшествования представляет собой ориентированный граф = (V, E), состоящий из множества вершин V – определяющих выполняемые транзакции и множества ориентированных ребер или дуг E – формируемых следующим образом:

  1.  Создается вершина, соответствующая каждой транзакции.
  2.  Создается дуга  B, если транзакция B считывает значение элемента данных, записанного транзакцией A.
  3.  Создается дуга  B, если транзакция B записывает значение в элемент данных, после того, как он был считан транзакцией A.
  4.  Создается дуга  B, если транзакция B записывает значение в элемент данных, после того, как он был записан транзакцией A.

Если в графе предшествования, соответствующем чередующемуся графику S, существует дуга  B, то в любом последовательном графике S, транзакция A должна предшествовать транзакции B.

Если граф предшествования содержит цикл, то соответствующий ему график является не упорядочиваемым.

Например. Построим граф предшествования для примера графика демонстрирующего проблему потери обновления (см. график выше).

Разрешение конфликтов в смеси транзакций

Т.к. транзакции не мешают друг другу, если они обращаются к разным данным или выполняются в разное время, то имеется два способа разрешить конкуренцию между поступающими в произвольные моменты транзакциями:

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

Первый метод - предоставление разных версий данных - реализуется путем использования данных из журнала транзакций.

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

Журнал транзакций

Устно. Реализация принципа “все или ничего” по отношению к транзакциям в различных СУБД реализовано по-разному, но все они, как правило, основаны на применении журнала транзакций.

Журнал транзакций — это структура данных транзакционной системы, в которой хранятся записи об операциях над данными. Работа с ним состоит из трёх шагов:

  1.  Записать намерение произвести некоторые операции
  2.  Выполнить задание
  3.  Записать, что всё сделано без ошибок

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

  •  Если повреждена запись, то сбой произошёл во время проставления отметки в журнале. Значит, ничего важного не потерялось, игнорируем эту ошибку.
  •  Если все записи помечены как успешно выполненные, то сбой произошёл между транзакциями, здесь также нет потерь.
  •  Если в журнале есть незавершённая транзакция, то сбой произошёл во время записи на диск. В этом случае восстанавливается старая версия данных из сегмента отката.

Основы журнализации

Устно. Оператор CREATE DATABASE используется для создания базы данных. Опция этой команды LOG ON используется для определения журнала транзакций создаваемой базы данных.

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

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

  •  Время начала каждой транзакции.
  •  Изменения внутри каждой транзакции и информацию для их отката (для этого используются снимки страниц данных до, и после транзакции).
  •  Информация о распределении памяти для страниц БД (выделении и изъятии экстента).
  •  Информация о завершении или откате каждой транзакции.

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

Блокировки

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

Различают два типа блокировок:

  •  Монопольные блокировки (X-блокировки, X-locks - eXclusive locks) - блокировки без взаимного доступа (блокировка записи).
  •  Разделяемые блокировки (S-блокировки, S-locks - Shared locks) - блокировки с взаимным доступом (блокировка чтения).

Если транзакция A блокирует объект при помощи X-блокировки, то всякий доступ к этому объекту со стороны других транзакций отвергается.

Если транзакция A блокирует объект при помощи S-блокировки, то

  •  запросы со стороны других транзакций на X-блокировку этого объекта будут отвергнуты,
  •  запросы со стороны других транзакций на S-блокировку этого объекта будут приняты.

Правила взаимного доступа к заблокированным объектам можно представить в виде таблицы совместимости блокировок. Если транзакция A определила блокировку на некоторый объект, а транзакция B после этого пытается наложить еще одну блокировку на этот же объект, то успешность блокирования транзакцией B объекта описывается таблицей 1:

Таблица 1. Матрица совместимости S- и X-блокировок 

 

Транзакция B пытается наложить блокировку:

Транзакция A наложила блокировку:

S-блокировку

X-блокировку

S-блокировку

Да

НЕТ
(Конфликт
R-W)

X-блокировку

НЕТ
(Конфликт
W-R)

НЕТ
(Конфликт
W-W)

Три случая, когда транзакция B не может блокировать объект, соответствуют трем видам конфликтов между транзакциями.

Доступ к объектам базы данных на чтение и запись должен осуществляться в соответствии со следующим протоколом доступа к данным:

  1.  Прежде чем прочитать объект, транзакция должна наложить на этот объект S-блокировку.
  2.  Прежде чем обновить объект, транзакция должна наложить на этот объект X-блокировку. Если транзакция уже заблокировала объект S-блокировкой (для чтения), то перед обновлением объекта S-блокировка должна быть заменена X-блокировкой.
  3.  Если блокировка объекта транзакцией B отвергается оттого, что объект уже заблокирован транзакцией A, то транзакция B переходит в состояние ожидания. Транзакция B будет находиться в состоянии ожидания до тех пор, пока транзакция A не снимет блокировку объекта.
  4.  X-блокировки, наложенные транзакцией A, сохраняются до конца транзакции A.


A

B: p = p0

A: p1  p

Конфликт R - W

A: p1  p

B: p2  p

Конфликт W - W


 

А также другие работы, которые могут Вас заинтересовать

13314. Дослідження характеристик регулюючих органів 1.41 MB
  Лабораторна робота №6 Тема: Дослідження характеристик регулюючих органів Мета: Навчитись вибирати регулюючі органи в залежності від вимог до системи управління 1.Вступ Автоматизація виробничих процесів створює певні технікоекономічні переваги у всіх галу
13315. Використання локальних регуляторів для управління моніторингу, контролю і аварійної сигналізації система при управлінні охолоджувальною технікою 1.9 MB
  Лабораторна робота № 8 Тема: Використання локальних регуляторів для управління моніторингу контролю і аварійної сигналізації система при управлінні охолоджувальною технікою. Мета: Навчитись працювати з локальними регуляторами для управління моніторингу контролю ...
13316. Визначення коефіцієнта лінійного розширення тіл методом Менделєєва 444 KB
  Лабораторна робота № 1 Визначення коефіцієнта лінійного розширення тіл методом Менделєєва. Мета роботи: аВивчення теплового розширення твердих тіл. бВизначення коефіцієнта лінійного розширення різних матеріалів методом Менделєєва. Прилади та матеріали: прил...
13317. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ПОВЕРХНЕВОГО НАТЯГУ РІДИНИ МЕТОДОМ ВІДРИВУ КРАПЛІ 285 KB
  Лабораторна робота № 2 ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ПОВЕРХНЕВОГО НАТЯГУ РІДИНИ МЕТОДОМ ВІДРИВУ КРАПЛІ. Мета роботи: а вивчення властивостей рідкого стану речовини; б експериментальне визначення коефіцієнта поверхневого натягу рідини та дослідження його залежності від
13318. ВИЗНАЧЕННЯ ТЕМПЕРАТУРНОГО КОЕФІЦЇЄНТА ОБЄМНОГО РОЗШИРЕННЯ РІДИН 341.5 KB
  Лабораторна робота №З ВИЗНАЧЕННЯ ТЕМПЕРАТУРНОГО КОЕФІЦЇЄНТА ОБЄМНОГО РОЗШИРЕННЯ РІДИН Мета роботи: а визначення теплового розширення речовин; 2 дослідне визначення коефіцієнта обємного розширення. Прилади і матеріали: прилад Дюлонга і Пті; нагрівам; лаборат
13319. ВИЗНАЧЕНИМ КОЕФІЦІЄНТА ТЕПЛОПРОВІДНОСТІ МЕТАЛІВ КАЛОРИМЕТРИЧНИМ МЕТОДОМ 242 KB
  Лабораторна робота №4 ВИЗНАЧЕНИМ КОЕФІЦІЄНТА ТЕПЛОПРОВІДНОСТІ МЕТАЛІВ КАЛОРИМЕТРИЧНИМ МЕТОДОМ Мета роботи: а вивчення явища тепло переносу; б експериментальне визначення коефіцієнта теплопровідності. Прилади та матеріали: калориметрична установка ваги з ...
13320. ВИЗНАЧЕННЯ ПИТОМОЇ ТЕПЛОТИ ПАРОУТВОРЕННЯ РІДИНИ 236 KB
  Лабораторна робота № 5 ВИЗНАЧЕННЯ ПИТОМОЇ ТЕПЛОТИ ПАРОУТВОРЕННЯ РІДИНИ Мета роботи: а вивчення процесів пароутворення; б експериментальне визначення питомої теплоти пароутворення води при температурі кипіння. Прилади та матеріали: калориметр з мішалкою ки
13321. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ПОВЕРХНЕВОГО НАТЯГУ РІДИНИ МЕТОДОМ ВІДРИВУ КІЛЬЦЯ 168.5 KB
  Лабораторна робота № 6 ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ПОВЕРХНЕВОГО НАТЯГУ РІДИНИ МЕТОДОМ ВІДРИВУ КІЛЬЦЯ. Мета роботи: а вивчення властивостей рідкого стану речовини; б визначення коефіцієнта поверхневого натягу рідини від типу речовини; в визначення залежності коефі