15.5. Взаимная блокировка

Как было показано выше, механизм блокировки можно использовать для разрешения трех основных проблем, возникаюших при параллельной обработке кортежей транзакциями. К сожалению, использование блокировок приводит к возникновению другой проблемы - взаимной блокировке транзакций. Выше были приведены два примера подобных ситуаций. На рис. 15.10 показана обобщенная схема возникновения данной проблемы, на которой rl и г2 представляют любые блокируемые объекты, необязательно являющиеся кортежами базы данных (подробности приводятся в разделе 15.8), а выражения типа блокировка... без совместного доступа обозначают любые операции установки блокировки (без совместного доступа), заданные как явно, так и неявно.

Транзакция В

Блокировка г2 без совместного доступа

Блокировка г1 без совместного

доступа

Ожидание

Ожидание

Рис. 15.10. Схема возникновения взаимной блокировки

Взаимная блокировка имеет место в том случае, когда две или более транзакций одновременно находятся в состоянии ожидания, причем для продолжения работы каждая из них ожидает прекращения выполнения другой транзакции. На рис. 15.10 показана взаимная блокировка для двух транзакций, однако, в принципе, возможны ситуации взаимной блокировки с участием трех, четырех и более транзакций. Тем не менее проведенные с системой System R эксперименты показали, что на практике ситуации взаимной блокировки с участием более двух транзакций почти никогда не встречаются [15.4].

Желательно, чтобы при возникновении взаимной блокировки система могла обнаружить ее и найти из нее выход. Для обнаружения ситуации взаимной блокировки следует организовать поиск замкнутых петель в графе ожидания (т.е. в графе, представлявшем транзакции, которые ожидают окончания выполнения других транзакций; см. упр. 15.4). Устранение взаимной блокировки заключается в выборе одной из участвующих 1в ней транзакций (т.е. той, которая входит в состав петли на графе ожидания) в качестве жертвы и ее откате. В результате будут сняты все установленные ею блокировки и выполнение других транзакций можно будет продолжить.

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

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

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

15.6. Упорядочиваемость

в предыдущих разделах были описаны основные положения, необходимые для объяснения ключевого понятия упорядочиваемость (serializability), под которым понимается некий обобщенный критерий правильности выполнения заданного набора транзакций. Согласно этому критерию выполнение заданного множества транзакций считается корректным, если оно является упорядоченным, т.е. если при его выполнении будет получен такой же результат, как и при последовательном выполнении этих же транзакций. Ниже приведено обоснование данного утверждения.

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

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

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

Возвращаясь к приведенным выше примерам из раздела 15.2 (см. рис. 15.1-15.4), можно отметить следующее: проблема в каждом случае заключалась в том, что чередующееся выполнение операций отдельных транзакций не было упорядочено, т.е. не было эквивалентно выполнению либо сначала транзакции А, а затем транзакции В, либо сначала транзакции В, а затем транзакции А. Основной смысл предложенного выше механизма блокировки заключался в принудительно.м обеспечении упорядоченности. На рис. 15.7 и 15.8 чередование выполняющихся операций эквивалентно выполнению сначала транзакции В, а затем транзакции А. На рис. 15.6 и 15.9 показана ситуация взаимной блокировки, для устранения которой следует отменить одну из двух транзакций с последующим ее перезапуском. Если отменить транзакцию А, чередование выполнения операций вновь станет эквивалентным выполнению сначала транзакции В, а затем транзакции А.

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

Необходимо подчеркнуть, что при выполнении двух разных последовательных графиков запуска одного и того же набора транзакций, в принципе, можно получить соверщенно разные результаты. Поэтому и выполнение двух различных чередующихся графиков для этого набора транзакций может привести к различным результатам, которые, тем не менее, будут восприняты, как корректные. Предположим, например, что транзакция А содержит операцию добавить 1 к х , а транзакция В - удвоить значение х (где х - некоторый элемент базы данных). Допустим также, что начальное значение х равно 10. Тогда при последовательном выполнении сначала транзакции А, а затем транзакции В будет получен результат х=22, а при последовательном выполнении сначала транзакции В, а затем транзакции А, будет получен результат х=21. Оба результата являются одинаково верными, а любой график запуска, эквивалентный выполнению либо сначала транзакции А, а затем транзакции В, либо сначала транзакции В, а затем транзакции А, также будет верным (см. упр. 15.3).

Концепция упорядочиваемости впервые была предложена Есвараном (Eswaran) в [15.5] (хотя и под другим названием). В его работе также доказана важная теорема, по-лучивщая название теорема двухфазной блокировки *. Кратко ее можно сформулировать следующим образом.

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

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

1. До выполнения каких-либо операций с некоторым объектом (например, с кортежем базы данных) транзакция должна блокировать этот объект.

2. После первого же снятия блокировки некоторого объекта транзакция теряет право устанавливать какие-либо новые блокировки.

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

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

Двухфазная блокировка не имеет ничего общего с двухфазной фиксацией. Глава 15. Параллельность 577