17244

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

Лекция

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

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

Русский

2013-06-30

77 KB

7 чел.

Лекция №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


 

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

36472. Древняя Греция 36.5 KB
  ранняя Греция возникают общества разделенные на классы Архаическим периодом в истории Греции обычно называют VIII VI вв. По мнению некоторых исследователей это время наиболее интенсивного развития античного общества. Действительно в течение трех столетий были сделаны многие важнейшие открытия определившие характер технической основы античного общества развились те социальноэкономические и политические явления которые придали античному обществу определенную специфику по сравнению с другими рабовладельческими обществами:...
36473. Древний Египет 29 KB
  групп перед властью Моноотраслевая экономика всегда ведет к жесткой политической системе с одним центром силы Главное достижение появление профессиональной армии Межгосударственная дипломатия появление письменных договоров мир на вечные времена Единое централизованное государство главное в политике Духовная жизнь Агрокультурный календарь Развитие государства и налоговой базы обеспечение финансовой системы государства а затем и бюрократической появление письменности Наука эмпирическая путем наблюдения теоретическая...
36474. Древне-китайская цивилизация 28 KB
  иерархии Прядение и ткачество Более крупные поселения Оседлое мотыжное земледелие Специализация районов Внедрение оружий из металла Рыболовство и скотоводство Массовое производство керамики гончарный круг Жреческая культура Особенность существовала в рамках неолита экономика отдельных поселений так и не стала централизованной на отдельной отрасли зачатки полиотраслевой экономики Рубеж перехода образование протогосударства появление города Шан Шелк Тутовое дерево Строительство дамб Развитие экономических...
36475. Неолитическая цивилизация 51.5 KB
  лесов быстро исчерпались Саванны нет земледелия переселение в субтропики Неолитическая катастрофа выжило 1000 чел Начало новой ц.
36476. Древняя Персия 27 KB
  За помощь в осуществлении контроля над обществом им предоставлялась наибольшая политическая самостоятельность Частный интерес работает на общественный Внешняя политика Восточное побережье Эгейского моря Греция колонии господство над торговлей в средиземном море Внешняя политика обусловлена экономической структурой: цель экономически важные регионы.
36477. Древние Шумеры 30.5 KB
  долина рек Тигр и Ефрат Неблагоприятные условия сухой климат мало полезных ископаемых Тростник и рыба самые доступные ресурсы Население сосредоточено в предморье и не углублялось во влажные равнины Увеличение численности населения перенаселение Технологии Сельскохозяйственные культуры ячмень эммера Одомашнен ряд животных быки овцы козы свиньи и ослы Примитивные технологии обработки меди Колесо Первые постройки из сырого глиняного кирпича Шумеры пытаются вести с х на новых землях строят системы очищения почвы....
36478. Понятия «цивилизация». Подходы к толкованию термина. Цивилизационная теория 93.5 KB
  Понятия цивилизация впервые употребил Виктор Мирабо в 1757 году в значении общего уровня культурного развития. Среди деятелей просвещения цивилизация ассоциировалась с концепцией прогресса стала идеалом интеллектуального и социального развития человечества. Отсюда ясно что цивилизация носила отрицательный оттенок.
36479. Структура цивилизация, ее основные элементы 73 KB
  технологический способ производства: орудия труда источники энергии предметы труда природные ресурсы технологии организация производства в плане технологий экономический способ производства структура воспроизводства обмен распределение экономическое управление социальнополитические отношения: социальные отношения национальные отношения политические отношения государственные отношения правовые духовный мир: наука культура образование мораль идеология или религия Все элементы цивилизационной...
36480. Динамика развития цивилизации, этапы ее развития на историческом примере 46.5 KB
  В истории человечества выделяют следующие глобальные цивилизации: неолитическую раннеклассовую античную средневековую индустриальную и наконец постиндустриальную цивилизации. Условия формирования античной цивилизации. Безусловно их наследие оказало определенное влияние на становление античной цивилизации тем не менее античный период в истории человечества дал рождение совершенно новым экономическим политическим и духовным институтам.