Главная » SQL, Базы данных » ВЗАИМОБЛОКИРОВКА

0

Выше было описано, как может использоваться блокировка (а точнее, строгий протокол двухфазной блокировки) для решения трех основных проблем  управления параллельным выполнением. Но, к сожалению, было также показано, что блокировка может сама стать причиной возникновения проблем, из которых основной является проблема взаимоблокировки. В предыдущем разделе были приведены два примера взаимоблокировки. На рис. 16.10 показан немного более общий вариант этой проблемы; на данном рисунке через rl и г2 обозначены любые блокируемые ресурсы, а не только кортежи базы данных (см. раздел 16.9), а с помощью операторов "LOCK . . . EXCLUSIVE" обозначаются  любые операторы, для выполнения которых требуется выдача запросов на блокировки X, явных или неявных.

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

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

чтобы получить возможность продолжить свою работу2. На рис. 16.10 показана взаимоблокировка, в которой участвуют две транзакции, но возможны также такие ситуации (по крайней мере, в принципе), когда во взаимоблокировке участвуют три, четыре или большее количество транзакций. Однако эксперименты,  проведенные в системе System R, показывают, что на практике взаимоблокировки, в которых участвуют больше двух транзакций, почти никогда не возникают [16.9].

Рис. 16.9. Проблема анализа несовместимости исключается, но в момент времени t7

возникает взаимо блокировка

Если произошла взаимоблокировка, желательно, чтобы система обнаружила ее и разорвала. Для обнаружения взаимоблокировки необходимо определить  наличие цикла в графе ожидания (Wait-For Graph). Так называется граф, который, неформально выражаясь, показывает "кто кого ожидает" (см. упр. 16.4). Чтобы разорвать взаимоблокировку, необходимо выбрать одну из транзакций, участвующих во взаимоблокировке (т.е. одну из транзакций, которые входят в состав цикла в графе ожидания), в качестве "жертвы" и

2  Иногда в литературе для обозначения взаимоблокировки применяется также довольно  красочный термин "смертельные объятья" (deadly embrace).

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

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

Рис. 16.10. Пример взаимоблокировки

Кстати, следует отметить, что неудачное завершение работы транзакции, выбранной в качестве жертвы, и последующий ее откат происходят не по вине самой этой транзакции. В некоторых системах осуществляется автоматический перезапуск такой транзакции с самого начала на основании предположения о том, что условия, которыми прежде было вызвано возникновение взаимоблокировки, вероятно, больше не повторятся. В других системах просто предусмотрена  передача в ответ приложению кода исключения "deadlock victim" (жертва взаимоблокировки); выбор способа дальнейших действий для правильного выхода из этой ситуации предоставляется самому приложению. Разумеется, что с точки зрения прикладного программиста первый из этих двух подходов является более предпочтительным. А если даже сам программист иногда захочет принять участие в устранении указанной проблемы, он имеет для этого все  возможности,  но по очевидным причинам всегда желательно скрывать ее существование от конечного пользоштеля.

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

Некоторые подходы к устранению взаимоблокировок основаны на том, что существует возможность  модифицировать  протокол  блокировки  различными  способами,  с  тем чтобы полностью избежать взаимоблокировок, а не ожидать их возникновения, после чего их устранять (как это делается в большинстве систем). Один из подобных подходов кратко рассматривается в данном разделе. Этот подход реализован в двух версиях, называемых "ожидание-отмена" и  "отмена-ожидание", и был впервые предложен для использования в распределенных системах [16.19], но может также применяться в централизованных системах. Краткое описание рассматриваемого подхода к  предотвращению взаимоблокировок приведено ниже.

■      Каждая транзакция обозначается отметкой времени ее начала (которая должна быть уникальной).

■      Если транзакция А запрашивает блокировку на кортеже, который уже заблокиро ван транзакцией в, то выполняются описанные ниже действия в зависимости от применяемого варианта.

■     "Ожидание-отмена" (Wait-Die). Если выполнение транзакции А началось рань ше, чем в, А переходит в состояние ожидания; в противном случае происходит ее отмена. Это означает, что осуществляется откат и перезапуск транзакции А.

■     "Отмена—ожидание" (Wound-Wait). Если выполнение транзакции А началось позже, чем в, она переходит в состояние ожидания; в противном случае, она отменяет В. Это означает, что происходит откат и перезапуск транзакции В.

■      Если транзакция должна быть перезапущена, ей после запуска присваивается ее первоначальная отметка времени.

Следует отметить, что первый компонент названия используемой версии (ожидание или отмена) в любом случае указывает, что произойдет, если выполнение транзакции А началось раньше, чем В. Вполне очевидно, что в версии "ожидание-отмена" множество всех ожидающих транзакций состоит из транзакций, начавшихся раньше и ожидающих завершения работы тех  транзакций,  которые были начаты позже, а в версии "отменаожидание" множество всех ожидающих транзакций состоит из транзакций, начавшихся позже и ожидающих завершения работы тех транзакций, которые были начаты раньше. Вполне очевидно, что при использовании любой из этих версий  взаимоблокировка не может вообще возникнуть. Кроме того, можно легко убедиться в том, что в конечном итоге гарантировано успешное завершение работы каждой транзакции. Это означает, что возникновение активного тупика невозможно (ни одна из транзакций не должна ожидать до бесконечности), к тому же ни одна транзакция не должна перезапускаться снова и снова бесконечное количество раз. Основным недостатком этого подхода (при использовании любой из версий) является то, что в нем приходится выполнять слишком много откатов.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии