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


 

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

54432. Бачу пейзаж неозорого моря 122.5 KB
  Діти посміхаються. Що за вивіска така Музей Діти читають. Паличка торкається до стрічки і вона опускається падає і діти заходять в картинну галерею. Портретдіти декламують вірші Якщо бачиш на картині В безкозирці моряка Чи принцесу в кринолині Чи сусідського Вітька Як зображено людину А не вазу чи букет Всім відомо цю картину Називаємо портрет.
54433. Комплексная система заданий по развитию творческих способностей учащихся по теме «Морфология» 145 KB
  Я уверена, что вы хорошо усвоили изученную тему. Но если хотите проверить свои знания, творческие способности, умение использовать их в нестандартных ситуациях, предлагаю вам выполнить задания разных видов и выразить своё отношение к ним.
54434. ВЕСІЛЛЯ МОРКОВИНКИ 74.5 KB
  Діти співають пісню Вже настала осінь Дід Панас: Дорогі гості Сьогодні в наш край завітала ОСІНЬ ЗОЛОТАВКА встелила килимами землю навкруги.Жовтий лист під ноги пада Осінь Осінь Золотисту стелить постіль Осінь Осінь 2. Сидить осінь на горбрчку вишиває лісові сорочку Наче золоті пташенята Злітають у дерев листки.
54435. Пояснювальна записка до інтегрованого уроку (англійська, німецька мови, інформатика) 115 KB
  Тема: Die Brücke vom Herzen zum Herzen The Bridge from Hert to Hert Міст від серця до серця Мета уроку: 1 практична: розвивати навички монологічного та діалогічного мовлення; стимулювати інтерес учнів до теми уроку активізуючи використання вивченого лексичного матеріалу з теми; повторити правила утворення ступенів порівняння прикметників тренувати їх вживання; розвивати навички читання пошуку потрібної інформації в тексті; повторити географічні назви країн та...
54436. Мотивація навчальної діяльності учнів 58.5 KB
  Мотивація навчальної діяльності учнів Найважливіший сенс учительської праці навчити учнів так щоб вони не розгубилися в бурхливому вирії сучасного життя. Треба зацікавити учнів не лише конкретним предметом а й процесом отримання знань. За словами французького письменника вчитись треба тільки весело; щоб переварити знання треба поглинати їх з апетитом Саме тому однією з моїх методичних тем є проблема Мотивація навчальної діяльності учнів Будь яка діяльність людинив тому числі і навчання підкоряється загальній схемі: 1. Навіщо...
54437. Мотивація - один і з структурних елементів інтерактивного навчання 68.5 KB
  Використовую різноманітні прийоми мотивації: Мотивація навчальної діяльності шляхом бесіди Шляхом створення проблемної ситуації Шляхом використання технології мозкова атака Шляхом опрацювання тексту періодичних видань За технологією незакінчене речення Шляхом виготовлення саморобних наочних посібників Шляхом використання творчих завдань Шляхом використання художньої та науковопопулярної літератури Шляхом створення ситуацій успіху На основі діяльнісного підходу до навчання За допомогою екстраполяції прогнозування...
54438. Die Ukraine − unsere Heimat 49.5 KB
  Die Ukrine − unsere Heimt Мета. Мовна зарядка Welche Tg ist heute Der wievielte ist heute Sind lle Schen in Ordnung Ist die Tfel suber 3. Де ви живете Ви живете в Києві Ми живемо на вулиці Шевченка 12 Konjugiert die folgenden Verben im Präsens sprechen wohnen leben. Die Hupstdt der Ukrine heißt Kyjiw.
54439. Лексикологія. Багатозначність слів, вживання їх у прямому та переносному значеннях, синоніми і антоніми 44.5 KB
  Сухомлинський Мова жива сходинка людського духу Панас Мирний Мова коштовній скарб народу І. Франко Мова життя духовного основа М. Рильский Мова генофонд культури О.Завжди йдуть у парі мова й думка.
54440. Голос рідної природи серцем слухати навчись 84.5 KB
  Полтави Голос рідної природи серцем слухати навчись Мова – найбільший скарб який є у кожного народу. Навчальний процес в початковій школі ми намагаємося організувати так щоб перші кроки до науки маленькі школярі робили на уроках мислення серед природи гортаючи сторінку за сторінкою Книгу рідної землі. Дитина від своєї природи писав Сухомлинський допитливий дослідник відкривач світу. Один із перших кроків наближення дітей до природи розуміння її – це спостереження що проводиться безпосередньо в довкіллі.