Тема_9 (1122360), страница 6

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

Текст из файла (страница 6)

Базы данных79УправлениМетоды сериализации транзакций (44)Синхронизационные блокировки (39)Предикатные синхронизационные блокировки (9)Достаточно очевидно следующее утверждение:Пусть имеются два простых условия scond1 и scond2Пусть транзакция T1 запрашивает блокировку scond1, атранзакция T2 – scond2 в режимах, которые были бы несовместимы, если бы scond1 и scond2 являлисьне условиями, а объектами базы данных (S-X, X-S, X-X)Эти блокировки совместимы в том и только в том случае,когда прямоугольники, соответствующие scond1 и scond2, непересекаются каждому k-мерному прямоугольнику в n-мерномпространстве возможных значений кортежей Tabсоответствует некоторое подмножество возможных значенийкортежей, иoотсутствие пересечения у двух прямоугольников гарантируетотсутствие конфликтов транзакций03.12.2009С.Д.Кузнецов.

Базы данных80УправлениМетоды сериализации транзакций (45)Синхронизационные блокировки (40)Предикатные синхронизационные блокировки (10)В каких бы режимахне требовала транзакцияT1 блокировки условияа транзакция T2 –блокировки условия(0 < a < 5) & (b = 5),(0 < a <6) & (0 < b <4),эти блокировки всегда будут совместимы03.12.2009С.Д.Кузнецов. Базы данных81УправлениМетоды сериализации транзакций (46)Синхронизационные блокировки (41)Предикатные синхронизационные блокировки (11)При поддержке такой системы блокировок простых условийможно обойтись без гранулированных блокировокВ частности, чтобы гарантированно заблокировать таблицуцеликом, достаточно заблокировать условие &1≤ i ≤n (min(mi) < имя_поляi < max(mi))Чтобы заблокировать базу данных, достаточнозаблокировать условие, являющееся конъюнкцией условийблокировки всех таблиц этой базы данных.Блокировки простых условий описываются таблицами,немногим отличающимися от таблиц традиционныхсинхронизаторов с гранулированными блокировкамиПоэтому введение в СУБД механизма предикатныхблокировок не приводит к значительным усложнениям03.12.2009С.Д.Кузнецов.

Базы данных82УправлениМетоды сериализации транзакций (47)Синхронизационные тупики, их распознавание и разрушение (1)Одним из наиболее чувствительных недостатков методасериализации транзакций на основе синхронизационныхблокировок является возможность возникновение тупиков(deadlocks) между транзакциямиСинхронизационные тупикивозможны при применениилюбого из рассмотренныхвыше вариантов механизмовблокировокНа рисунке показан простойсценарий возникновениясинхронизационного тупика междутранзакциями T1 и T203.12.2009С.Д.Кузнецов. Базы данных83УправлениМетоды сериализации транзакций (48)Синхронизационные тупики, их распознавание и разрушение (2)Транзакции T1 и T2устанавливают монопольныеблокировки объектов o1 и o2соответственнопосле этого T1 требуетсясовместная блокировка объектаo2, а T2 – совместная блокировкаобъекта o1;ни одно из этих требований блокировкине может быть удовлетворено,следовательно,ни одна из транзакций не может продолжаться;поэтому монопольные блокировки объектов никогда не будут сняты, атребования совместных блокировок не будут удовлетвореныПоскольку тупики возможны, и никакого естественного выхода изтупиковой ситуации не существует, то эти ситуации необходимообнаруживать и искусственно устранять03.12.2009С.Д.Кузнецов.

Базы данных84УправлениМетоды сериализации транзакций (49)Синхронизационные тупики, их распознавание и разрушение (3)Обнаружение тупиковых ситуаций (1)Основой обнаружения тупиковыхситуаций является построение или постоянное поддержаниеграфа ожидания транзакцийГраф ожидания транзакций – этоориентированный двудольный граф,в котором существует два типа вершин– вершины, соответствующиетранзакциям будем изображать их прямоугольникамии вершины, соответствующие объектам блокировок будем изображать их окружностямиВ этом графе дуги соединяют только вершины-транзакции свершинами-объектами.03.12.2009С.Д.Кузнецов. Базы данных85УправлениМетоды сериализации транзакций (50)Синхронизационные тупики, их распознавание и разрушение (4)Обнаружение тупиковых ситуаций (2)Дуга из вершины-транзакциик вершине-объекту существуетв том и только в том случае,если для этой транзакцииимеется удовлетвореннаяблокировка данного объектаДуга из вершины-объекта квершине-транзакции существуеттогда и только тогда, когда этатранзакция ожидает удовлетворения запроса блокировкиданного объектаЛегко показать, что в системе существует тупиковаяситуация в том и только в том случае, когда в графеожидания транзакций имеется хотя бы один цикл.03.12.2009С.Д.Кузнецов.

Базы данных86УправлениМетоды сериализации транзакций (51)Синхронизационные тупики, их распознавание и разрушение (5)Обнаружение тупиковых ситуаций (3)Для распознавания тупиковых ситуацийпериодически производится построение графаожидания транзакцийи в этом графе ищутся циклыТрадиционной техникойкак уже отмечалось, иногда граф ожиданияподдерживается постоянно,для которой существует множество разновидностейнахождения циклов в ориентированном графеявляется редукция графа03.12.2009С.Д.Кузнецов. Базы данных87УправлениМетоды сериализации транзакций (52)Синхронизационные тупики, их распознавание и разрушение (6)Обнаружение тупиковых ситуаций (4)В целях упрощения примера предполагается, что все блокировки являютсямонопольными,Прежде всего, из графа ожидания удаляютсявсе дуги, исходящие из вершин-транзакций,в которые не входят дуги из вершин-объектовтранзакции, ожидающие удовлетворенияблокировок, но не удерживающиезаблокированные объекты, не могут бытьпричиной тупикаДля тех вершин-объектов, для которых не осталосьвходящих дуг, но существуют исходящие, ориентацияодной из исходящих дугЭто основывается на том разумномпредположении, что транзакции, не ожидающиеудовлетворения запроса блокировок, могутуспешно завершиться и освободить блокировкиКроме того, удаляются дуги, входящие в вершинытранзакции, из которых не исходят, ведущие к вершинам-объектамт.е.

для каждой вершины-объекта имеется не более одной входящей дугивыбираемой произвольным образомизменяется на противоположную это моделируетудовлетворение запроса блокировки03.12.2009С.Д.Кузнецов. Базы данных88УправлениМетоды сериализации транзакций (53)Синхронизационные тупики, их распознавание и разрушение (7)Обнаружение тупиковых ситуаций (5)После этого снова повторяются описанные действияи так до тех пор, пока не прекратится удаление дугЕсли в графе остались дуги, то они обязательнообразуют цикл03.12.2009С.Д.Кузнецов. Базы данных89УправлениМетоды сериализации транзакций (54)Синхронизационные тупики, их распознавание и разрушение (8)Разрушение тупиков (1)Предположим теперь, что нам удалось найтицикл в графе ожидания транзакцийЧто делать теперь?Нужно каким-то образом обеспечитьвозможность продолжения работы хотя бы длячасти транзакций, попавших в тупикРазрушение тупика начинается с выбора в циклетранзакций так называемой транзакции-жертвы,т.е.

транзакции, которой решено пожертвовать, чтобыобеспечить возможность продолжения работы другихтранзакций03.12.2009С.Д.Кузнецов. Базы данных90УправлениМетоды сериализации транзакций (55)Синхронизационные тупики, их распознавание и разрушение (9)Разрушение тупиков (2)Выбрать «жертву» не так уж легко, поскольку для этого могутиспользоваться различные, зачастую противоречивые критерииС одной стороны, было бы разумно жертвовать наиболее«богатой» транзакцией, т.е.

той транзакцией, которая удерживаетнаиболее число блокировок объектовВ этом случае после принудительно завершения такой транзакцииосвободилось бы наибольшее число объектов, что с большойвероятностью привело бы к исчезновению тупиковой ситуацииНо, с другой стороны, «богатая» транзакция, скорее всего,выполнялась дольше других транзакцийНа ее выполнение уже затрачено большое количество системныхресурсов и, вероятно, она скоро завершится самостоятельноПоэтому этот выбор может оказаться в системном отношении несамым удачным03.12.2009С.Д.Кузнецов. Базы данных91УправлениМетоды сериализации транзакций (56)Синхронизационные тупики, их распознавание и разрушение (10)Разрушение тупиков (3)Можно пожертвовать самой «молодой» транзакцией, котораясуществует в системе в течение наименьшего времениТакую транзакцию менее всего жалко, поскольку она еще не успелаизрасходовать много системных ресурсовНо, с другой стороны, такая транзакция не могла и накопить многоблокировок, и поэтому ее насильственное завершение вряд липоможет устранить тупиковую ситуациюТак стоит ли ею жертвовать?Можно выбрать транзакцию-жертву случайным образом из всехтранзакций, попавших в тупикВозможно, что в среднем этот подход привел бы к хорошимрезультатамНо, к сожалению, в нем не учитывается возможная приоритетностьтранзакцийБыло бы не слишком хорошо, например, жертвовать транзакцией,запущенной от имени руководителя организации03.12.2009С.Д.Кузнецов.

Базы данных92УправлениМетоды сериализации транзакций (57)Синхронизационные тупики, их распознавание и разрушение (11)Разрушение тупиков (4)Поэтому обычно при выборе транзакции-жертвыиспользуется многофакторная оценка ее стоимости, вкоторую с разными весами входят время выполнения, числонакопленных блокировок, приоритет и т.д. В качестве «жертвы» выбирает транзакция, для которой этаоценка выдает наиболее подходящий результатПосле выбора транзакции-жертвы выполняется откат этойтранзакции, который может носить полный или частичный(до некоторой точки сохранения) характерПри этом, естественно, освобождаются блокировки, и можетбыть продолжено выполнение других транзакций03.12.2009С.Д.Кузнецов.

Характеристики

Список файлов лекций