Материал: Базы данных и их безопасность. Плотников Д.Г

6.4. Предупреждение взаимных блокировок

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

Первый, получивший название «ожидание-отмена», требует, чтобы более старые транзакции ожидали завершения более новых. В противном случае транзакция отменяется и перезапускается с той же самой временной отметкой. Однако рано или поздно она станет самой старой из активных транзакций и уже не будет отменена.

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

Использование временных отметок

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

Методы использования временных отметок совершенно отличаются от методов с использованием блокировок. Эти методы не предусматривают какого-либо ожидания –

186

вовлеченные в конфликт транзакции просто отменяются, после чего запускаются заново.

Временная отметка – уникальный идентификатор, создаваемый СУБД с целью обозначения относительного момента времени запуска транзакции.

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

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

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

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

Вариант 1. Транзакция Т выдает команду «чтение (х)»

187

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

Если (Т) <запись (х) – то более старая транзакция опоздала и уже не может

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

В противном случае (Т)> запись (х) – операция чтения может быть выполнена.

Вариант 2. Транзакция Т выдает команду «запись (х)»

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

Если (Т) <чтение (х) – то более новая транзакция уже использовала текущее

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

В этом случае следует выполнить откат транзакции Т и перезапустить ее с использованием новой временной отметки.

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

Если (Т) <запись (х)

Это означает, что транзакция Т пытается поместить в элемент данных (х) устаревшее значение.

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

188

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

запись (х) = (Т)

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

Однако базовый протокол упорядочивания по временным отметкам не обеспечивает восстанавливаемости графиков.

Правило записи Томаса

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

правило записи Томаса.

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

Если (Т) <чтение (х) - то В этом случае транзакция Т откатывается и

перезапускается с использованием новой временной отметки.

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

Если (Т) <запись (х)

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

189

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

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

запись (х) = (Т)

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

В табл. 6.14 представлен пример базового протокола упорядочивания по временным отметкам.

Таблица 6.14 Пример базового протокола упорядочивания по

временным отметкам

190