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


 

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

37507. Особенности Русской философии 72.99 KB
  Учитывая весь тысячелетний опыт русской истории можно говорить об исторической миссии России. Миссия России определяется ее положением среди других народов тем что в ее составе объединилось до трехсот народов больших великих и малочисленных требовавших защиты. Культура России сложилась в условиях этой многонациональности. на новом витке развития России Русская идея стала предметом пристального внимания русских мыслителей.
37508. Философия. Основные понятия и термины 95.72 KB
  ИСТОРИЯ ТЕХНИКИ – наука о развитии технических систем см. С точки зрения естественных наук история техники изучает этапы овладения человеком законами природы что обеспечивает более глубокое и разностороннее использование и применение вещества и энергии природы. С социальной точки зрения история техники изучает общественные движущие силы общественные условия развития техники и роль творцов техники. К наиболее крупным периодам истории техники относятся: история каменного века и ручных орудий техники машин и механизации техники...
37509. Апология Сократа 15.75 KB
  Ксенофонт посвятил Сократу и его учению свои произведения Апология Сократа и Воспоминания о Сократе . Платон же почти все свое учение приписал Сократу так что трудно сказать где кончается Сократ а где начинается Платон Отсутствие прямой информации непосредственно исходящей от Сократа приводит к тому что некоторые историки античной философии в последние десятилетия не раз делали попытки доказать что Сократ всего лишь литературный персонаж. Вопросный метод Сократа Подход Сократа к вопросному методу основан на ведении последовательного...
37510. Патристика и Схоластика 93.75 KB
  К этим принципам относятся: теоцентризм признание в качестве источника всего сущего Бога; креационизм признание того что Бог создал все из ничего; провиденциализм признание того что Бог правит всем; персонализм признание того что человек “персона†сотворен Богом по собственному подобию и наделен совестью; ревеляционизм признание того что самый надежный путь познания наиболее важных для человека истин состоит в постижении смысла Священного писания. И все же на переднем плане осталась проблема человека и его...
37511. Философия. Сборник тестов 425.5 KB
  Предмет и специфика философии. Мировоззрение и философия. Общий обзор исторических типов философии. Античная философия.2 Философия. Средневековья. Философия Возрождения. Философия Нового времени. Немецкая классическая философия. Философия марксизма. Русская философия. Современная западная философия...
37512. Философия. Шпаргалка 363 KB
  Из объемных фигур происходят чувственно воспринимаемые тела которые имеют четыре основы огонь воду землю и воздух; превращение последних приводят к миру живого и человека. Кризис Конечно можно отказаться от атомизма но тогда что делать с парадоксами и апориями элеатов Сюда добавляется еще одна трудность: неясно как подступиться с атомистическими воззрениями к духовному миру человека. Проблема Предлагаемое решение Что удалось объяснить Что не удалось объяснить Что есть единое Материальная субстанция Часть природных явлений...
37514. Философия. Краткий конспект 20.02 KB
  11 Философия Пифагор: Мир не хаос мир подчиняется строгим математическим законам. Средневековая философия. С 5 века по 11 век – европейская философия по 16 – восточная философия. Гуманистическая философия т.
37515. Специфика мифологического мировоззрения 11.53 KB
  Мифологическое мировоззрение характеризуется преимущественно игнорированием причинноследственных методов описания действительности в результате чего картина мира предстает только в ее пространственновременном оформлении например в нереальных сроках жизни людей их перерождении и воскрешении в другом качестве и т. Мифологическое мировоззрение обладает еще одной особенностью – в мифе всегда есть присутствие целостного представления между природной субстанцией и самим человеком. Поэтому мифологическое сознание сначала растворяется в...