Лекция 5

3.2.8. Обновляемые блокировки

Избежать взаимоблоки­ровки, возникающей при повышении уровня, можно за счет использования третьего режима блокиро­вания – с применением так называемых обновляемых блокировок (update locks). Обновляемая блокировка (как и общая) предоставляет транзакции возможность считы­вания элемента X, но не его модификации. При этом только обновляемая блокировка позднее может быть повышена транзакцией до уровня монопольной, раз­решающей запись. Транзакция может также повысить общую блокировку до обновляемой, но как только обновляемая блокировка X установлена, планировщик заданий отвергает запросы на установку любых блокировок того же элемента X.

Для системы с этими тремя режимами блокирования матрица совместимости выглядит так:

S X U

S Да Нет Да

X Нет Нет Нет

U Нет Нет Нет

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

Проблема, указанная в примере 2 п. 3.2.7, разрешима в контексте схемы с обновляемыми блокировками. Здесь транзакции и вначале запрашивают обновляемые блокировки элемента A и только затем - моно­польные. Описания транзакций могут выглядеть следующим образом:

НЕ нашли? Не то? Что вы ищете?

Вероятная последовательность чередования действий такова:

/* Запрет */

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

3.2.9. Инкрементные блокировки

Во многих случаях транзакции выполняют только операции приращения величин хранимых элемен­тов. К подобным примерам относятся:

1)  перевод денежных сумм с одного банковского счета на другой;

2)  резервирование авиабилета с уменьшением количества свободных мест на рейс.

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

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

Инкрементную операцию будем обозначать , а соответствующую ей инкрементную блокировку – . Строго говоря, выражение обозначает атомарно выполняемую последовательность трех действий: чтение, приращение (положительное или отрицательное) и запись. Однако мы не будем обсуждать здесь механизм поддержки атомарности подобного рода. Мы будем считать, что она относится к более низкому уровню, чем атомарность тран­закций, обеспечиваемая инструментами блокирования.

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

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

2.  В корректном расписании допускается одновременная установка инкрементной блокировки элемента X несколькими транзакциями. Ес­ли, однако, какая-либо транзакция удерживает инкрементную блокировку X, другим транзакциям не позволяется устанавливать ни общие, ни монопольные блокировки X.

3.  Действие является конфликтным по отношению к и при , но не конфликтует с .

Требования 1–2 отражены в следующей матрице совместимости (I обозначает инкрементную блокировку):

S X I

S Да Нет Нет

X Нет Нет Нет

I Нет Нет Да

Пример. Рассмотрим две транзакции, каждая из которых вначале считывает элемент A базы данных, а затем выполняет инкрементную операцию над элементом B (можно считать, что к B прибавляется величина, зависящая от A):

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

Если опустить операции установки блокировок, то данное расписание можно описать следующей последовательностью действий:

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

3.2.10. Архитектура планировщика с блокированием

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

3.2.10.1. Двухкомпонентная модель

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

Компо­ненты планировщика заданий выполняют следующие функции.

1.  Компонент I принимает поток сгенерированных транзак­циями заявок на операции. Перед каждой операцией он вставляет подхо­дящую инструкцию блокирования, после чего направляет поток компоненту II. Для выбора типа вставляемых блокировок компоненту I часто приходится анализировать характер затребованных транзакциями действий, просматривая их вперед или взаимодействуя с другими компонентами СУБД (процессором запросов, компилятором SQL и т. п.).

2.  Компонент II получает поток операций над данными и инструкций блокирова­ния и соответствующим образом их выполняет. При получении очередной операции или инструкции он вначале проверяет, находится ли транзакция-источник T в состоянии ожидания захвата блокировки. Если да, то запрашиваемое действие откладывается (добавляется в список действий, подлежащих последующему вы­полнению). Если работа транзакции T не была приостановлена (то есть все запрошенные ею ранее блокировки успешно установлены), осуществляется следующее:

a)  если действие связано с операцией над данными, оно выполняется;

b)  если действие представляет собой инструкцию блокирования, компонент II обращается к таблице блокировок за информацией о том, можно ли удовле­творить запрос на блокирование:

i)  при положительном ответе в таблицу включаются сведения о вновь раз­решенной блокировке;

ii)  в противном случае в таблицу помещается запись, свидетельствующая о том, что запрос пока не удовлетворен; выполнение транзакции Т приостанавливается до тех пор, пока не возникнут условия, подходящие для разрешения запроса.

3.  Если транзакция Т выполняет фиксацию или прерывание, компонент I снимает все установленные ею блоки­ровки. Если были транзакции, ожидавшие снятия этих блокировок, компонент I сообщает об этом компоненту II.

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

3.2.10.2. Таблица блокировок

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

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

1.  Обобщенный признак блокирования – сообщает о наличии блокировок элемента A. Для схемы общих/монопольных/обновляемых блокировок правило формирова­ния обобщенного признака блокирования таково:

a)  S означает наличие только общих блокировок;

b)  U – существует одна обновляемая и, возможно, одна или несколько общих блокировок;

c)  X – элемент блокирован монопольно и других блокировок нет.

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

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

3.  Список содержит ссылки на описания всех транзакций, которые либо установили блокировки элемента A, либо ожидают предоставления такой возможности. Элементы списка могут со­держать следующие фрагменты полезной информации:

a)  идентификатор транзакции, установившей или ожи­дающей блокировку;

b)  обозначение режима блокирования;

c)  бит, удостоверяющий, что транзакция владеет блокировкой или пребывает в состоянии ожидания.

3.2.10.3. Обработка запросов на блокирование и разблокирование

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

Если элемент захвачен в режиме обновляемого блокирования (признак = U), запросы на новые блокировки отвергаются (за исключением случая, ко­гда блокировкой U владеет та же транзакция T, и другие блокировки элемента A совмес­тимы с той, которая запрашивается транзакцией T). В результате запрета в список, со­ответствующий записи таблицы блокировок, включается элемент о запросе со стороны транзакции T блокировки элемента A и содержащий в поле Ожидание значение "да". Те же действия выполняются и в случае, когда обобщенный признак блокирования равен (то есть элемент A монопольно блокирован какой-либо транзакцией).

Если значением признака является S (общая блоки­ровка), планировщик имеет право удовлетворить очередной запрос на общую или обновляе­мую блокировку элемента A. В подобном случае элемент списка, соответствующий транзакции T, будет содержать в поле Ожидание значение "нет", а в ячейке Режим – признак U или S, соответствующий запрашиваемому режиму блокирования элемента A.

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

Теперь предположим, что транзакция T требует снять блокировку элемента A базы данных. Тогда в записи таблицы блокировок (для А) элемент списка, соответствующий транзакции T, удаляется. Если режим снимаемой блокировки не совпада­ет с обобщенным признаком блокирования, причин для изменения признака нет. В противном случае планировщику заданий, возможно, придется просмотреть весь список в поисках нового значения признака. Например, если снимается блокировка уровня U (а элемент может быть блокирован в режи­ме U только единожды), то при снятии блокировки новым значением обобщенного признака блокирования может быть только S (если в состоянии ожидания есть запросы на общие блокировки). Если обобщенный признак блокирования содержит X, то больше блокировок нет. Когда признак равен S, необходимо определить, существуют ли другие общие блокировки. Если никаких других блоки­ровок в данный момент нет, соответствующая запись таблицы блокировок удаляется.

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

1.  "Первым пришел – первым обслужен" – удовлетворить запрос, поступивший пер­вым. Такая стратегия позволяет избежать ситуации "гибели" транзакции ввиду неограниченно долгого пребывания в состоянии ожидания.

2.  "Отдать приоритет общей блокировке" – первым делом удовлетворить все за­явки на общие блокировки, затем разрешить один запрос на блокирование в режиме обновления (если подобные запросы существуют); одно требование монопольного блокирования принять только в том случае, если запросов на блокирование в иных режимах не поступало. В таком случае есть риск "бесконечного" ожидания транзакции, запрос которой связан с обновляемой или монопольной блокировкой.

3.  "Отдать приоритет повышению уровня блокирования": если существует транзак­ция, владеющая блокировкой U, которая должна быть преобразована в блоки­ровку X, предоставить эту возможность в первую очередь; в противном случае действовать в соответствии с любой другой стратегией.