Алгоритм разблокировки транзакций в РБД

1. Цель работы: Ознакомиться с алгоритмом разблокировки конфликтующих транзакций в РБД.

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

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

Для описания взаимоблокировок транзакций используется граф, в котором вершины соответствуют транзакциям, а ребра – блокировкам. Причем, если вершины Т1 и Т2 соединены ребром, направленным от Тр1 к Тр2, это означает, что транзакция Тр1 блокирует выполнение транзакции Тр2. Граф можно описать множеством ребер, указав для каждого из них начальную и конечную вершины, например, ребро от Тр1 к Тр2 обозначается (Тр1,Тр2).

Рассмотрим следующий пример. Пусть во взаимоблокировках участвуют транзакции Тр1, Тр2, Тр3, Тр4, Тр5 и граф описывается множеством ребер (Тр1,Тр2), (Тр2,Тр3), (Тр3,Тр4), (Тр4,Тр1), (Тр4,Тр5), (Тр5,Тр2). Для транзакций заданы значения С1=20, С2=10, С3=15, С4=20, С5=5 - величины непроизводительных потерь при откате транзакции. Из рассмотрения графа следует, что все транзакции заблокированы. Следовательно, нужно выбрать транзакцию для отката. Согласно критерию для отката выбирается транзакция Тр5. При этом из графа удаляется соответствующая вершина и связанные с ней ребра. В оставшемся графе снова все транзакции заблокированы. Согласно критерию следующей для отката выбирается транзакция Тр2. После удаления из графа Тр2 и связанных с ней ребер транзакция Тр3 оказывается незаблокированной и оставшиеся транзакции успешно выполняются в следующем порядке: Тр3, Тр4, Тр1. После этого могут быть выполнены транзакции Тр5, Тр2. При этом суммарное количество непроизводительных потерь равно С5+С2=15.

Отметим, что алгоритм последовательного отката транзакций не всегда обеспечивает в итоге минимальное количество непроизводительных потерь. В частности, при откате на первом шаге транзакции Тр2 остальные транзакции могут быть успешно выполнены, например, в следующем порядке: Тр3, Тр4, Тр1, Тр5. Выполнив после них транзакцию Тр2, мы получим количество непроизводительных потерь, равное С2=10.

Для программирования описанного алгоритма в общем случае требуется ввести следующие переменные и массивы:

Блокировки (1:КолБлок, 1:2) – в i-й строке этого массива записаны номера соответственно блокирующей и блокируемой транзакции;

Потери (1:КолТранз) - i-й элемент массива равен количеству непроизводительных потерь при откате i-й транзакции.

Во внешнем цикле программы выполняются итерации, каждая из которых включает следующие действия:

- выбрать транзакцию, для которой нужно выполнить откат;

- для выбранной транзакции удалить все связанные с ней блокировки;

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

- для успешно завершенных транзакций удалить все связанные с ними блокировки;

- если не все транзакции успешно завершены, то перейти к следующей итерации.

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

3.1. Для выбранного варианта задания нарисовать граф, отображающий взаимоблокировки транзакций.

3.2. Определить последовательность откатываемых транзакций и порядок успешного завершения транзакций.

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

3.4. Составить и отладить программу, которая по введенному описанию транзакций определяет последовательность откатываемых транзакций, последовательность успешного завершения транзакций и соответствующую величину непроизводительных потерь, связанных с откатом транзакций.

3.5. Протестировать разработанную программу на примерах, выполненных вручную.

4.4 Граф, отображающий взаимоблокировки транзакций.

4.5 Последовательность откатываемых транзакций

4.7 Сравнение величин непроизводительных потерь для пошагового и оптимального решения об откате транзакций

5.1. Чем обусловлена необходимость блокировок транзакций?

5.2. Как строится граф взаимоблокировок транзакций?

5.3. В чем заключается алгоритм последовательного отката транзакций?

5.4. Что является критерием оптимизации в задаче устранения взаимоблокировок транзакций?

5.5. Всегда ли алгоритм последовательного отката транзакций обеспечивает получение оптимального решения?

Протокол двухфазной фиксации транзакций в РБД

1. Цель работы: Ознакомиться с протоколом двухфазной фиксации транзакций (ПДФТ) в РБД и с особенностями его моделирования.

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

При выполнении ПДФТ осуществляются следующие действия.

- Сервер – координатор распределенной транзакции определяет состав серверов – исполнителей транзакции, формирует для них частные задания (локальные транзакции) и рассылает их исполнителям.

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

- Сервер – координатор принимает от исполнителей сообщения о возможности выполнения локальных транзакций и если все они положительны, посылает исполнителям команду зафиксировать результаты локальных транзакций в таблицах РБД. Если хотя бы один исполнитель прислал сообщение о невозможности выполнения локальной транзакции, то координатор посылает исполнителям команду откатить все локальные транзакции.

Описанный протокол на практике может приводить к неприятным последствиям. Например, сервер – исполнитель по каким-либо причинам не может послать координатору сообщение. В этом случае выполнение распределенной транзакции затягивается на неопределенное время. Чтобы избежать таких ситуаций, координатор ограничивает время ожидание ответов от исполнителей некоторой величиной ТС и протокол дополняется следующим требованием. Если через время ТС не получен ответ хотя бы от одного исполнителя, то его ответ считается отрицательным и координатор посылает исполнителям команду на откат распределенной транзакции.

Для программы моделирования ПДФТ должны быть определены следующие входные данные.

КолИсп – число серверов – исполнителей распределенной транзакции;

Fi(x) (i = 1: КолИсп) –ИФРВ для случайной величины времени выполнения локальной транзакции без фиксации ее результатов;

ТС – допустимое время ожидания координатором сообщений от исполнителей.

В процессе моделирования формируются оценки для следующих величин:

Тi (i=1: КолИсп) - среднее время выполнения локальной транзакции i-м исполнителем,

ТРТ – среднее время выполнения распределенной транзакции.

3.1. Для выбранного варианта задания составить и отладить программу моделирования процесса выполнения распределенной транзакции во времени.

3.2. Протестировать разработанную программу на примерах, выполненных вручную.

3.3. Оценить среднее время выполнения распределенной транзакции при разных значениях ТС.

4.6 Оценки среднего времени выполнения распределенной транзакции.

4.7 Графики зависимостей среднего времени выполнения распределенной транзакции от величины ТС.

5.1. Чем обусловлена необходимость использования протокола двухфазной фиксации транзакций?

5.2. В чем заключается протокол двухфазной фиксации транзакций?

5.3. Что может быть причиной «зависания» протокола двухфазной фиксации транзакций?

5.4. Как устраняется «зависание» протокола двухфазной фиксации транзакций?

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: