Упорядочиваемое и восстанавливаемость. Назначение многопользовательских СУБД

1. Упорядочиваемое и восстанавливаемость

2.

• Назначение протоколов управления
параллельным доступом состоит в подготовке
такого графика выполнения транзакций,
который исключит возможность их влияния на
результаты работы друг друга, что позволит
предотвратить возникновение проблем,
описанных в предыдущем разделе.
• Одно из очевидных решений состоит в
выполнении в каждый момент времени только
одной транзакции — предыдущая транзакция
обязательно должна быть зафиксирована,
прежде чем будет разрешено даже начать
выполнение следующей транзакции.

3.

• Назначение многопользовательских СУБД
состоит в обеспечении максимальной
степени распараллеливания транзакций
пользователей, поэтому те транзакции,
которые не влияют на работу друг друга,
вполне могут выполняться одновременно
(термины "одновременное" и
"параллельное" выполнение транзакций,
которые здесь употребляются как
синонимы, должны рассматриваться в
контексте многозадачной организации
работы).

4.

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

5.

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

6.

• Каждая транзакция состоит из
последовательности операций, включающих
чтение и запись данных в базу, которые
должны завершаться либо фиксацией, либо
откатом полученных результатов.
• График S представляет собой
последовательность операций, входящих в
состав множества из n транзакций Т1, Т2 , ..., Тn
, на которую накладывается ограничение,
требующее, чтобы последовательность
операций каждой из первоначальных
транзакций сохранялась в графике.
• Поэтому для каждой транзакции Ti должен
быть сохранен порядок ее операций в графике
S.

7.

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

8.

• В последовательном графике транзакции выполняются
строго поочередно. Например, если имеются две
транзакции (Т1 и Т2 ), последовательный порядок
выполнения транзакций может предусматривать
применение транзакций Т1( затем Т2 (или Т2 , затем T1).
• Таким образом, при последовательном выполнении
никакое взаимовлияние транзакций невозможно,
поскольку в каждый момент времени выполняется
только одна из транзакций.
• Однако нет гарантии, что результаты применения всех
вариантов последовательного выполнения заданного
набора транзакций всегда будут одинаковы.
• Например, в случае банковских опeраций имеет
значение, на какой именно остаток был начислен
процент (т.е. до или после снятия большой суммы со
счета).

9.

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

10.

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

11.

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

12.

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

13. Порядок выполнения операции чтения записи

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

14.

• Рассмотрим график S1, представленный в столбцах
Варианта А.
• Он устанавливает последовательность операций,
выполняемых параллельно в транзакциях Т7 и Т8
• Поскольку операция записи данных счета balх в
транзакции T8 не конфликтует с последующей
операцией чтения данных счета baly в транзакции Т7
, можно изменить последовательность выполнения
этих операций и получить эквивалентный график S2
, показанный в столбцах Вариантa Б этой же
таблицы.
• Если поменять порядок выполнения и следующих
не конфликтующих между собой операций, то мы
получим эквивалентный последовательный график
S3 , показанный в столбцах Вариант В, для этого
выполним перечисленные ниже действия.

15.

• Изменим последовательность выполнения
операций write (balx) транзакции Т8 и write
(balx) транзакции Т7 .
• Изменим последовательность выполнения
операций read(bal x ) транзакции Т8 и read
(baly) транзакции Т7 .
• Изменим последовательность выполнения
операций read (balx) транзакции Т8 и write
(baly) транзакции Т7 .
График S3 является последовательным, а
поскольку графики S1 и S2 эквивалентны графику
S3, они являются упорядочиваемыми.

16.

Эквивалентные графики:
• вариант А — непоследовательный график
S 1;
• вариант Б— непоследовательный график S2
, эквивалентный графику S1 вариант Б —
последовательный график S3 ,
эквивалентный графикам S1 из S2

17.

18.

19.

20.

• Подобный тип упорядочиваемости принято называть
конфликтной упорядочиваемостъю.
• В конфликтно упорядочиваемом графике порядок
выполнения любых конфликтующих операций
соответствует их размещению в последовательном
графике.
• Согласно правилу записи, подчиняющейся
ограничениям (которое гласит, что транзакция должна
обновлять элемент данных исходя из его прежнего
значения, которое было прочитано транзакцией в
самом начале), для проверки конфликтной
упорядочиваемости можно использовать граф
предшествования (или граф упорядочения).
• Для графика S граф предшествования представляет
собой направленный граф G=(N,E), состоящий из
множества вершин N, множества направленных ребер Е
и формируемый следующим образом.

21.

• Создается вершина, соответствующая каждой
из транзакций.
• Создаются направленные ребра Ti—>Tj, если
транзакция Тj считывает значение элемента,
записанного транзакцией Тi .
• Создаются направленные ребра Ti —> Tj, если
транзакция Тj записывает значение в элемент
данных после того, как он был считан
транзакцией Ti.
• Создаются направленные ребра Ti —> Tj, если
транзакция Tj записывает значение в элемент
данных после того, как он был записан
транзакцией Тi .

22.

• Если в графе предшествования,
соответствующем графику S, существует
ребро Ti—>Tj, то в любом
последовательном графике S1 ,
эквивалентном графику S, транзакция Ti
должна предшествовать транзакции Tj.
• Если граф предшествования содержит
циклы, то соответствующий ему график не
является конфликтно упорядочиваемым.

23. Пример графика, не являющегося конфликтно упорядочиваемым

• Рассмотрим две транзакции, график
выполнения которых представлен в таблице. В
транзакции Т9 100 футов стерлингов
переводятся со счета balx на счет Ьаlу
• Транзакция Т10 увеличивает текущие значения
остатков на каждом из этих счетов на 10%.
Граф предшествования для данного графика,
показанный на рисунке, содержит цикл,
поэтому этот график не является конфликтно
упорядочиваемым.

24. Пример графика выполнения двух параллельных транзакций обновления

25. Граф предшествования для графика, представленного в таблице

26. Упорядочиваемость по просмотру

• Существует и несколько других типов
упорядочиваемости, которые позволяют
сформулировать менее строгое определение
эквивалентности графиков, чем то, что
предусмотрено в случае конфликтной
упорядочиваемости.
• Одно из этих менее строгих определений называют
упорядочиваемостъю по просмотру.
• Два графика, S1 и S2 , состоящие из одних и тех же
операций, входящих в состав п транзакций T1 Т2 , ...,
Тn , являются эквивалентными по просмотру, если
соблюдаются следующие три условия.

27.

• Для каждого элемента данных х: если транзакция Т1
считывает первоначальное значение х в графике S1
эта же транзакция T1 должна считывать то же
первоначальное значение х и в графике S2 .
• Для каждой операции чтения элемента данных х
транзакцией Ti в графике S1 : если считанное
значение элемента х было записано транзакцией Tj
то и в графике S2 транзакция Тj должна считывать
значение элемента х, записанное транзакцией Tj.
• Для каждого элемента данных х: если в графике S1
последняя операция записи значения х была
выполнена транзакцией Ti эта же транзакция
должна выполнять последнюю запись значения
элемента данных х и в графике S2 .

28.

• График является упорядочиваемым по просмотру, если
он эквивалентен по просмотру некоторому
последовательному графику. Каждый конфликтно
упорядочиваемый график в то же время является
упорядочиваемым по просмотру, однако обратное
утверждение неверно.
• Например, график, представленный в таблице, является
упорядочиваемым по просмотру, но не является
конфликтно упорядочиваемым.
• В этом примере для транзакций Т12 и Т13 не
соблюдается правило записи, подчиняющейся
ограничениям, иными словами, в них выполняется так
называемая слепая запись.
• Может быть строго доказано, что любой
упорядочиваемый по просмотру график, который не
является конфликтно упорядочиваемым, содержит одну
или несколько операций слепой записи.

29. Пример упорядочиваемого по просмотру графика, который не является конфликтно упорядочиваемым

30.

• В общем случае проверка того, является ли
график упорядочиваемым по просмотру,
относится к классу NP-иолных задач
(комбинаторных задач с нелинейной
полиномиальной оценкой числа вариантов),
поэтому маловероятно, что когда-то удастся
найти вполне эффективный алгоритм ее
решения [404].
• На практике графики не проверяются в СУБД
на упорядочиваемость. Это было бы
нецелесообразно, поскольку чередование
операций параллельно выполняющихся
транзакций определяется операционной
системой. Вместо этого в СУБД используются
специальные протоколы, позволяющие
создавать упорядочиваемые графики.

31. Восстанавливаемость

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

32.

• Еще раз обратимся к двум транзакциям,
представленным в таблице.
• Но на этот раз предположим, что вместо операции
фиксации commit в конце транзакции Т9 был выполнен
откат всех результатов ее выполнения.
• К тому времени в транзакции Т10 уже было считано
измененное значение счета bal x , записанное
транзакцией Т9 , выполнено его обновление и эти
результаты зафиксированы в базе данных.
• Строго говоря, следовало бы отменить и результаты
выполнения транзакции Т10, поскольку она
использовала значение на счете Ьаlх , изменение
которого должно быть отменено.
• Однако свойство устойчивости транзакций не
позволяет этого сделать. Другими словами, данный
график не обладает свойством восстанавливаемости и
поэтому является недопустимым. На этом основании
сформулировано приведенное ниже понятие
восстанавливаемого графика.

33.

• Восстанавливаемый график. График, в
котором для каждой пары транзакций . Тi и
Tj выполняется следующее правило: если
транзакция Tj считывает элемент данных,
предварительно записанный транзакцией
Тi, то фиксация результатов транзакции Ti.
должна выполняться до фиксации
результатов транзакции Tj.

34.

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

35.

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

36.

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

37.

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

38.

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

39. Пример неверного графика с использованием блокировки

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

40.

• Если до начала выполнения этого графика остаток
на счете bal x был равен 100 фунтам стерлингов, а на
счете bal y — 400 фунтам стерлингов, то в результате
выполнения указанных действий остаток на счете
bal x должен быть равен 220 фунтам стерлингов, а на
счете bal y — 330 фунтам стерлингов, если
транзакция Т9 будет выполнена до транзакции Т10.
• Если транзакция Т10 будет выполнена до транзакции
Ts , то остаток на счете bal x будет составлять 210
фунтов стерлингов, а на счете bal y — 340 фунтов.
• Но выполнение графика S приводит к получению
остатка bal x , равного 220 фунтам стерлингов, a bal y
— 340. (Из этого следует, что график S не является
упорядочиваемым.)

41.

• Для обеспечения упорядочиваемости
следует использовать дополнительный
протокол, определяющий моменты
установки и снятия блокировки для каждой
из транзакций. Самым известным из таких
протоколов является метод двухфазной
блокировки (2PL).

42.

• Двухфазная блокировка. Транзакция
выполняется по протоколу двухфазной
блокировки, если в ней все операции
блокирования предшествуют первой
операции разблокирования.

43.

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

44.

• Как правило, транзакция устанавливает
некоторые блокировки, выполняет
определенную обработку, после чего может
затребовать установку дополни тельных
необходимых ей блокировок. Однако она
не может освободить ни одной из
блокировок, пока не будет достигнута
стадия выполнения, на которой больше не
потребуется установка новых блокировок.
Работа ведется по приведенным ниже
правилам.

45.

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

46.

• Если СУБД поддерживает операции
повышения уровня блокировок, то такое
повышение допускается только в фазе
расширения. Подобные действия могут
потребовать перехода транзакции в
состояние ожидания на то время, пока
другие транзакции отменят установленные
ими разделяемые блокировки данного
элемента. Снижение уровня блокировки
допускается только в фазе сужения.

47. Использование протокола двухфазной блокировки для устранения проблемы потерянного обновления

• Способ устранения проблемы потерянного
обновления с помощью протокола двух- фазной
блокировки показан в таблице.
• Чтобы избежать потери выполненного обновления,
транзакция Т2 должна вначале установить
исключительную блокировку на элементе bаlх.
Затем она может считать из базы данных текущее
значение этого элемента, увеличить его на 100
фунтов стерлингов и записать результат в базу
данных. В момент запуска транзакция Т1 также
потребует установить исключительную блокировку
элемента bal x .

48.

• Но, поскольку на элемент данных Ьаlх к этому
моменту уже установлена исключительная
блокировка в транзакции Т2 , этот запрос со
стороны транзакции Т1 не влечет за собой
немедленного предоставления требуемой
блокировки, поэтому транзакция Т1 переходит
в состояние ожидания (wait) до освобождения
блокировки транзакцией Т2 .
• Однако это произойдет только после фиксации
результатов выполнения транзакции Т2 в базе
данных

49. Пример решения проблемы потерянного обновления

50. Использование протокола двухфазной блокировки для устранения проблемы зависимости от незафиксированных результатов

• Способ устранения проблемы зависимости от
незафиксированных результатов транзакций
продемонстрирован в таблице. Во избежание
возникновения данной проблемы транзакция Т4
должна вначале потребовать предоставления ей
исключительной блокировки на элемент данных bal x .
• Далее она может прочитать из базы данных текущее
значение этого элемента, увеличить его на 100 фунтов
стерлингов, а затем записать новое значение в базу
данных. При выполнении отката этой транзакции
выполненное ею обновление значения элемента bаlx
будет отменено и этому элементу данных будет
возвращено прежнее значение, равное 100 фунтам
стерлингов.

51.

• В момент начала транзакции Т3 она также
потребует предоставления ей исключительной
блокировки элемента bаlх . Но, поскольку на
этот элемент данных уже распространяется
исключительная блокировка, установленная
транзакцией Т4 , запрос транзакции Т3
удовлетворить не удастся и она будет
переведена в состояние ожидания вплоть до
освобождения транзакцией Т4 необходимого
ей элемента данных. Это произойдет только
после отката результатов выполнения
транзакции Т4 и приведения базы данных в
первоначальное состояние.

52. Пример решения проблемы зависимости от незафиксированных результатов

53. Использование протокола двухфазной блокировки для устранения проблемы анализа несогласованности

• Способ устранения проблемы анализа
несогласованности показан в таблице.
• Для устранения этой проблемы в транзакции
Т5 операциям чтения должна предшествовать
установка исключительных блокировок, тогда
как в транзакции Т6 операциям чтения должна
предшествовать установка разделяемых
блокировок.
• Поэтому при запуске на выполнение
транзакция Т5 выдает запрос и получает
исключительную блокировку на элемент bal x .

54.

• В результате при попытке получения
разделяемой блокировки на элемент bal x в
транзакции Т6 выполнение запроса
откладывается и эта транзакция переходит
в состояние ожидания, вплоть до
освобождения требуемого ей элемента
данных, т.е. до фиксации результатов
транзакции Т5 .

55. Пример решения проблемы анализа несогласованности

56.

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

57. Взаимоблокировка

• Туковая ситуация, которая может возникнуть, когда
две (или более) транзакции находятся во взаимном
ожидании освобождения блокировок,
удерживаемых друг другом.
• В таблице показаны две транзакции, Т17 и Т1в,
выполнение которых приводит к
взаимоблокировке, поскольку каждая из них входит
в состояние ожидания освобождения требуемого
ресурса другой транзакцией.
• В момент времени t 2 транзакция Т17 запрашивает
и получает исключительную блокировку на элемент
данных bal x , а в момент времени t s транзакция
Т18 получает исключительную блокировку на
элемент данных bal y .

58.

• Когда в момент времени t6 транзакция Т17 запрашивает
исключительную блокировку на элемент данных Ьа1у ,
она переводится в состояние ожидания, поскольку этот
элемент данных уже заблокирован транзакцией Т18.
• В момент времени t7 транзакция Т19, в свою очередь,
запрашивает исключительную блокировку на элемент
данных Ьа1х и также переходит в состояние ожидания,
поскольку этот элемент оказывается заблокированным
транзакцией Т1Т.
• Ни одна из транзакций не в состоянии продолжить свою
работу, поскольку каждая ожидает завершения работы
другой. Если в системе возникает состояние
взаимоблокировки, вовлеченные в него приложения не
смогут разрешить данную проблему собственными
силами.
• Ответственность за обнаружение взаимоблокировок и
выхода тем или иным образом из этой тупиковой
ситуации должна быть возложена на СУБД.

59. Пример взаимоблокировки двух транзакций

60.

• К сожалению, существует только один
способ устранить состояние
взаимоблокировки: выполнение одной или
нескольких транзакций должно быть
отменено.
• Подобное действие будет сопровождаться
откатом всех изменений, внесенных
отмененными транзакциями. Для
приведенного в таблице примера можно,
допустим, отменить выполнение
транзакции T1S.

61.

• Как только ее откат будет завершен, все
установленные этой транзакцией
блокировки будут освобождены и
транзакция Т17 сможет продолжить свое
выполнение.
• Ситуация взаимоблокировки должна быть
абсолютно прозрачной для конечных
пользователей, поэтому СУБД обязана
автоматически перезапустить все
отмененные ею транзакции.

62.

СУБД обязана автоматически перезапустить
все отмененные ею транзакции. Существуют
три общих метода обработки
взаимоблокировок:
• установка тайм- аутов, предотвращение
взаимоблокировок, обнаружение
взаимоблокировок и возобновление
нормальной работы.
.

63.

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

64.

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

65. Тайм-ауты

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

66.

• В этом случае СУБД действует согласно
предположению, что данная транзакция
могла оказаться в состоянии
взаимоблокировки, даже если это не
соответствует действительности, поэтому
происходит аварийное завершение и
автоматический перезапуск транзакции.
Это — очень простое и удобное решение
задачи устранения взаимоблокировок,
реализованное в некоторых коммерческих
СУБД.

67. Предотвращение взаимоблокировок

• Еще один из возможных подходов к устранению
взаимоблокировок состоит в упорядочении
транзакций на основе использования временных
отметок.
• Были предложены два возможных алгоритма:
Первый алгоритм, получивший название "ожиданиеотмена", требует, чтобы только более старые
транзакции ожидали завершения более новых. В
противном случае транзакция отменяется и
перезапускается с той же временной отметкой.
Однако рано или поздно она станет самой старой из
активных транзакций и уже не будет отменена.

68.

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

69. Обнаружение взаимоблокировок

• Обнаружение взаимоблокировок обычно
выполняется с помощью графа ожидания
(Wait-For Graph — WFG). Этот граф отражает
зависимость транзакций друг от друга.
Транзакция ТА считается зависимой от
транзакции Tj в том случае, если транзакция TJ
заблокировала элемент данных, необходимый
для продолжения работы транзакции IV Граф
ожидания представляет собой направленный
граф G-- (N, Е), который состоит из множества
вершин N, множества направленных ребер Е и
формируется следующим образом.

70.

• Создается вершина, соответствующая каждой
транзакции.
• Создается направленное ребро Ti-^Tj, если
транзакция ТА ожидает освобождения элемента
данных, заблокированного в настоящее время
транзакцией Т-,. Взаимоблокировка имеет место
в том и только в том случае, если граф ожидания
содержит цикл.
На рисунке показан граф ожидания для
транзакций, представленных в таблице.
Как показывает этот рисунок, граф содержит
цикл (Т17-»Т1е-»Т17), поэтому можно сделать
вывод, что в системе существует
взаимоблокировка.

71. Граф ожидания, который показывает наличие взаимоблокировки между двумя транзакциями

72. Частота выполнения операции обнаружения взаимоблокировок

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

73.

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

74. Возобновление нормальной работы после обнаружения взаимоблокировки

• Как указано выше, после обнаружения в СУБД
взаимоблокировок необходимо выполнить аварийное
завершение одной или нескольких транзакций. Для
этого следует решить несколько задач.
1. Выбрать транзакции, отменяемые в результате
взаимоблокировки. При определенных обстоятельствах
выбор аварийно-завершаемых транзакций может
оказаться очевидным. Но в других ситуациях такое
решение требует анализа дополнительных обстоятельств.
В подобных случаях, как правило, следует выбирать
транзакции, отмена которых потребует минимальных
расходов.

75.

При этом необходимо учитывать следующие
соображения:
а) продолжительность выполнения транзакции (может
оказаться более целесообразным аварийное
завершение транзакции, которая была только что
начата, а не транзакции, которая уже выполнялась в
течение некоторого времени);
б) количество элементов данных, обновляемых в
транзакции (может оказаться более целесообразным
аварийное завершение транзакции, в которой были
внесены меньшие изменения в базу данных, а не
транзакции, в кото- рой были внесены значительные
изменения в базу данных);

76.

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

77.

• 2. Определить степень отката транзакции.
После принятия решения об отмене
конкретной транзакции необходимо
определить, до какой степени должен быть
выполнен ее откат. Безусловно, простейшим
решением является отмена всех изменений,
внесенных в транзакции, но оно не всегда
оказывается наиболее эффективным. Иногда
для устранения взаимоблокировки достаточно
выполнить отмену только части изменений,
внесенных в ходе выполнения транзакции.

78.

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

79.

• СПАСИБО ЗА ВНИМАНИЕ!