Презентация «Упорядочиваемое и восстанавливаемость. Назначение многопользовательских СУБД»
Смотреть слайды в полном размере 
Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 79 слайдов и доступен в формате ppt. Размер файла: 763.91 KB
Pic.1
Упорядочиваемое и восстанавливаемость
Pic.2
Назначение протоколов управления параллельным доступом состоит в подготовке такого графика выполнения транзакций, который исключит возможность их влияния на результаты работы друг друга, что позволит …
Pic.3
Назначение многопользовательских СУБД состоит в обеспечении максимальной степени распараллеливания транзакций пользователей, поэтому те транзакции, которые не влияют на работу друг друга, вполне …
Pic.4
Например, транзакции, обращающиеся к разным частям базы данных, не окажут влияния на работу друг друга и, следовательно, могут выполняться параллельно. Например, транзакции, обращающиеся к разным …
Pic.5
График. Последовательность запуска операций нескольких параллельно выполняемых транзакций, сохраняющая очередность выполнения операций в каждой отдельной транзакции.
Pic.6
Каждая транзакция состоит из последовательности операций, включающих чтение и запись данных в базу, которые должны завершаться либо фиксацией, либо откатом полученных результатов. Каждая транзакция …
Pic.7
Последовательный график. График, в котором операции каждой из транзакций выполняются строго последовательно и не могут чередоваться с операциями, выполняемыми в других транзакциях. Последовательный …
Pic.8
В последовательном графике транзакции выполняются строго поочередно. Например, если имеются две транзакции (Т1 и Т2 ), последовательный порядок выполнения транзакций может предусматривать применение …
Pic.9
Непоследовательный график. График, в котором чередуются операции из некоторого набора одновременно выполняемых транзакций. Непоследовательный график. График, в котором чередуются операции из …
Pic.10
Причиной проблем, описанных в примерах, является неправильная организация параллельного выполнения транзакций, что приводит к переходу базы данных в несогласованное состояние (в первых двух примерах) …
Pic.11
Не имеет значения, какой именно последовательный график будет выбран, поскольку при последовательном выполнении транзакций база данных никогда не переходит в несогласованное состояние. Не имеет …
Pic.12
Суть упорядочивания состоит в поиске таких непоследовательных графиков, которые позволят транзакциям выполняться параллельно, но без влияния друг на друга, и поэтому переводят базу данных в …
Pic.13
Порядок выполнения операции чтения записи Если две транзакции только считывают некоторый элемент данных, они не будут конфликтовать между собой и последовательность их выполнения не имеет значения. …
Pic.14
Рассмотрим график S1, представленный в столбцах Варианта А. Рассмотрим график S1, представленный в столбцах Варианта А. Он устанавливает последовательность операций, выполняемых параллельно в …
Pic.15
Изменим последовательность выполнения операций write (balx) транзакции Т8 и write (balx) транзакции Т7 . Изменим последовательность выполнения операций write (balx) транзакции Т8 и write (balx) …
Pic.16
Эквивалентные графики: Эквивалентные графики: вариант А — непоследовательный график S1; вариант Б— непоследовательный график S2 , эквивалентный графику S1 вариант Б — последовательный график S3 , …
Pic.17
Pic.18
Pic.19
Pic.20
Подобный тип упорядочиваемости принято называть конфликтной упорядочиваемостъю. Подобный тип упорядочиваемости принято называть конфликтной упорядочиваемостъю. В конфликтно упорядочиваемом графике …
Pic.21
Создается вершина, соответствующая каждой из транзакций. Создается вершина, соответствующая каждой из транзакций. Создаются направленные ребра Ti—>Tj, если транзакция Тj считывает значение …
Pic.22
Если в графе предшествования, соответствующем графику S, существует ребро Ti—>Tj, то в любом последовательном графике S1 , эквивалентном графику S, транзакция Ti должна предшествовать транзакции …
Pic.23
Пример графика, не являющегося конфликтно упорядочиваемым Рассмотрим две транзакции, график выполнения которых представлен в таблице. В транзакции Т9 100 футов стерлингов переводятся со счета balx на …
Pic.24
Пример графика выполнения двух параллельных транзакций обновления
Pic.25
Граф предшествования для графика, представленного в таблице
Pic.26
Упорядочиваемость по просмотру Существует и несколько других типов упорядочиваемости, которые позволяют сформулировать менее строгое определение эквивалентности графиков, чем то, что предусмотрено в …
Pic.27
Для каждого элемента данных х: если транзакция Т1 считывает первоначальное значение х в графике S1 эта же транзакция T1 должна считывать то же первоначальное значение х и в графике S2 . Для каждого …
Pic.28
График является упорядочиваемым по просмотру, если он эквивалентен по просмотру некоторому последовательному графику. Каждый конфликтно упорядочиваемый график в то же время является упорядочиваемым …
Pic.29
Пример упорядочиваемого по просмотру графика, который не является конфликтно упорядочиваемым
Pic.30
В общем случае проверка того, является ли график упорядочиваемым по просмотру, относится к классу NP-иолных задач (комбинаторных задач с нелинейной полиномиальной оценкой числа вариантов), поэтому …
Pic.31
Восстанавливаемость Упорядочиваемыми называются такие графики, которые позволяют сохранить согласованность базы данных при условии, что ни одна из транзакций этого графика не будет отменена. …
Pic.32
Еще раз обратимся к двум транзакциям, представленным в таблице. Еще раз обратимся к двум транзакциям, представленным в таблице. Но на этот раз предположим, что вместо операции фиксации commit в конце …
Pic.33
Восстанавливаемый график. График, в котором для каждой пары транзакций . Тi и Tj выполняется следующее правило: если транзакция Tj считывает элемент данных, предварительно записанный транзакцией Тi, …
Pic.34
Исключительная блокировка. Если в транзакции установлена исключительная блокировка элемента данных, то в ней могут выполняться и чтение, и обновление этого элемента Исключительная блокировка. Если в …
Pic.35
Поскольку разделяемые блокировки не могут служить причиной конфликта, допускается устанавливать разделяемые блокировки для чтения одного и того же элемента одновременно со стороны сразу нескольких …
Pic.36
Любая транзакция, которой необходимо получить доступ к элементу данных, должна вначале выполнить блокировку этого элемента. Для этого может быть затребована разделяемая блокировка, обеспечивающая …
Pic.37
Если элемент данных в настоящий момент уже заблокирован, СУБД проанализирует, является ли тип полученного запроса совместимым с типом уже существующей блокировки. Если запрашивается разделяемая …
Pic.38
Транзакция продолжает удерживать блокировку элемента данных до тех пор, пока явным образом не освободит ее — либо в ходе своего выполнения, либо по окончании (успешном или неуспешном). Только после …
Pic.39
Пример неверного графика с использованием блокировки
Pic.40
Если до начала выполнения этого графика остаток на счете bal x был равен 100 фунтам стерлингов, а на счете bal y — 400 фунтам стерлингов, то в результате выполнения указанных действий остаток на …
Pic.41
Для обеспечения упорядочиваемости следует использовать дополнительный протокол, определяющий моменты установки и снятия блокировки для каждой из транзакций. Самым известным из таких протоколов …
Pic.42
Двухфазная блокировка. Транзакция выполняется по протоколу двухфазной блокировки, если в ней все операции блокирования предшествуют первой операции разблокирования. Двухфазная блокировка. Транзакция …
Pic.43
В соответствии с основным правилом этого протокола каждая транзакция может быть разделена на две фазы: фазу расширения, в которой устанавливаются все необходимые блокировки и не освобождается ни одна …
Pic.44
Как правило, транзакция устанавливает некоторые блокировки, выполняет определенную обработку, после чего может затребовать установку дополни тельных необходимых ей блокировок. Однако она не может …
Pic.45
Прежде чем начать работу с элементом данных, транзакция должна установить для него блокировку. Блокировка может устанавливаться для чтения или записи, в зависимости от типа требуемого доступа. Прежде …
Pic.46
Если СУБД поддерживает операции повышения уровня блокировок, то такое повышение допускается только в фазе расширения. Подобные действия могут потребовать перехода транзакции в состояние ожидания на …
Pic.47
Использование протокола двухфазной блокировки для устранения проблемы потерянного обновления Способ устранения проблемы потерянного обновления с помощью протокола двух- фазной блокировки показан в …
Pic.48
Но, поскольку на элемент данных Ьаlх к этому моменту уже установлена исключительная блокировка в транзакции Т2 , этот запрос со стороны транзакции Т1 не влечет за собой немедленного предоставления …
Pic.49
Пример решения проблемы потерянного обновления
Pic.50
Использование протокола двухфазной блокировки для устранения проблемы зависимости от незафиксированных результатов Способ устранения проблемы зависимости от незафиксированных результатов транзакций …
Pic.51
В момент начала транзакции Т3 она также потребует предоставления ей исключительной блокировки элемента bаlх . Но, поскольку на этот элемент данных уже распространяется исключительная блокировка, …
Pic.52
Пример решения проблемы зависимости от незафиксированных результатов
Pic.53
Использование протокола двухфазной блокировки для устранения проблемы анализа несогласованности Способ устранения проблемы анализа несогласованности показан в таблице. Для устранения этой проблемы в …
Pic.54
В результате при попытке получения разделяемой блокировки на элемент bal x в транзакции Т6 выполнение запроса откладывается и эта транзакция переходит в состояние ожидания, вплоть до освобождения …
Pic.55
Пример решения проблемы анализа несогласованности
Pic.56
Можно доказать, что если во всех транзакциях графика соблюдается протокол двухфазной блокировки, этот график будет являться конфликтно упорядочиваемым. Можно доказать, что если во всех транзакциях …
Pic.57
Взаимоблокировка Туковая ситуация, которая может возникнуть, когда две (или более) транзакции находятся во взаимном ожидании освобождения блокировок, удерживаемых друг другом. В таблице показаны две …
Pic.58
Когда в момент времени t6 транзакция Т17 запрашивает исключительную блокировку на элемент данных Ьа1у , она переводится в состояние ожидания, поскольку этот элемент данных уже заблокирован …
Pic.59
Пример взаимоблокировки двух транзакций
Pic.60
К сожалению, существует только один способ устранить состояние взаимоблокировки: выполнение одной или нескольких транзакций должно быть отменено. К сожалению, существует только один способ устранить …
Pic.61
Как только ее откат будет завершен, все установленные этой транзакцией блокировки будут освобождены и транзакция Т17 сможет продолжить свое выполнение. Как только ее откат будет завершен, все …
Pic.62
СУБД обязана автоматически перезапустить все отмененные ею транзакции. Существуют три общих метода обработки взаимоблокировок: СУБД обязана автоматически перезапустить все отмененные ею транзакции. …
Pic.63
При использовании тайм-аутов транзакция, потребовавшая установить какую-либо блокировку, ожидает в течение периода времени, который не превышает некоторого установленного значения. При использовании …
Pic.64
Поскольку метод предотвращения взаимоблокировок сложнее по сравнению с применением тайм-аутов или контроля за появлением взаимоблокировок и их устранения, как правило, метод предотвращения …
Pic.65
Тайм-ауты Один из наиболее простых методов устранения взаимоблокировок состоит в использовании тайм-аутов. При таком подходе транзакция, которая запрашивает блокировку, может ожидать ее получения …
Pic.66
В этом случае СУБД действует согласно предположению, что данная транзакция могла оказаться в состоянии взаимоблокировки, даже если это не соответствует действительности, поэтому происходит аварийное …
Pic.67
Предотвращение взаимоблокировок Еще один из возможных подходов к устранению взаимоблокировок состоит в упорядочении транзакций на основе использования временных отметок. Были предложены два возможных …
Pic.68
Второй алгоритм, "отмена-ожидание", использует диаметрально противоположный подход: только более новые транзакции могут ожидать завершения более старой транзакции. Если более старая …
Pic.69
Обнаружение взаимоблокировок Обнаружение взаимоблокировок обычно выполняется с помощью графа ожидания (Wait-For Graph — WFG). Этот граф отражает зависимость транзакций друг от друга. Транзакция ТА …
Pic.70
• Создается вершина, соответствующая каждой транзакции. • Создается вершина, соответствующая каждой транзакции. • Создается направленное ребро Ti-^Tj, если транзакция ТА ожидает освобождения элемента …
Pic.71
Граф ожидания, который показывает наличие взаимоблокировки между двумя транзакциями
Pic.72
Частота выполнения операции обнаружения взаимоблокировок Поскольку наличие цикла в графе ожидания является необходимым и достаточным условием существования в системе взаимоблокировки, алгоритм …
Pic.73
Если выбранный промежуток окажется слишком продолжительным, наличие взаимоблокировки может оставаться незамеченным в течение длительного времени. Еще один вариант предусматривает применение …
Pic.74
Возобновление нормальной работы после обнаружения взаимоблокировки Как указано выше, после обнаружения в СУБД взаимоблокировок необходимо выполнить аварийное завершение одной или нескольких …
Pic.75
При этом необходимо учитывать следующие соображения: При этом необходимо учитывать следующие соображения: а) продолжительность выполнения транзакции (может оказаться более целесообразным аварийное …
Pic.76
в) количество элементов данных, которые все еще подлежат обновлению в транзакции (может оказаться более целесообразным решение отменить транзакцию, в которой еще предстоит внести в базу данных …
Pic.77
2. Определить степень отката транзакции. После принятия решения об отмене конкретной транзакции необходимо определить, до какой степени должен быть выполнен ее откат. Безусловно, простейшим решением …
Pic.78
3. Предотвратить возникновение ситуации истощения ресурсов. Истощение ресурсов возникает, если для отмены всегда выбирается одна и та же транзакция, поэтому ее так и не удается выполнить. Истощение …
Pic.79
СПАСИБО ЗА ВНИМАНИЕ! СПАСИБО ЗА ВНИМАНИЕ!
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!
