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

В статье описывается несколько ситуаций, в которых можно использовать метод депонирования. Одним из примеров коммерческого продукта, в котором поддерживается данный метод, является информационная система IMS Fast Path фирмы IBM. Следует отметить, что этот метод может рассматриваться как особый случай оптимистического управления параллельностью [15.14] (обратите внимание, однако, что именно специфичность, т.е. применение специальных операторов обновления, и является важнейшим условием).

15.16.Papadimitriou С. The Theory of Database Concurrency Control. - Rockville, Md.: Computer Science Press, 1986.

Учебное пособие, в котором особое внимание уделяется формальной теории. IS.n.Salem К., Garcia-Molina G., Shands J. Altruistic Locking ACM TODS. - March, 1994. - 19, № 1.

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

Ответы к некоторым упражнениям

15.3.

а) Существует шесть возможных корректных результатов, соответствующих шести возможным последовательным графикам запуска.

Исходно : А = О

Т1-Т2-ТЗ : А = 1

Т1-ТЗ-Т2 : А = 2

Т2-Т1-ТЗ : А = 1

Т2-ТЗ-Т1 ТЗ-Т1-Т2 ТЗ-Т2-Т1

А = 2 А = 4 А = 3

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

б) Сушествует 90 возможных графиков запуска, отличных один от другого, которые можно представить в приведенном ниже символическом виде. (Здесь Ri, Rj, Rk обозначают операции извлечения R1, R2, R3, причем необязательно в той же последовательности. Аналогично Up, Uq, Ur обозначают операции обновления U1, U2, из, необязательно в той же последовательности.)

Ri-Rj-Rk-Up-Uq-Ur :3*2*1*3*2*1=36 вариантов

Ri-Rj-Up-Rk-Uq-Ur :3*2*2*1*2*1=24 вариантов

Ri-Rj-Up-Uq-Rk-Ur :3*2*2*1*1*1=12 вариантов

Ri-Up-Rj-Rk-Uq-Ur :3*1*2*1*2*1=12 вариантов

Ri-Up-Rj-Uq-Rk-Ur :3*1*2*1*1*1= 6 вариантов

Всего =90 вариантов

в) Да. Например, график запуска R1-R2-R3-U3-U2-U1 приводит к тому же результату (единица) для заданного начального значения (нуль), что и два из шести возможных последовательных графиков запуска. (Упражнение. Проверьте это утверждение.) Однако следует понимать, что корректность полученного результата является всего лишь счастливой случайностью и следствием того, что исходное значение было равно О, а не какому-то другому числу. В качестве примера обратной ситуации рассмотрите случай, когда исходное значение равно 10. Будет ли показанный выше график запуска давать один из действительно корректных результатов? (Какими в этом случае будут действительно корректные результаты?) Если нет, то график запуска R1-R2-R3-U3-U2-U1 не допускает упорядочения.

г) Да. Например, график запуска R1-R3-U1-U3-R2-U2 является упорядоченным (он эквивалентен последовательном) графику запуска Т1-Т2-ТЗ), но не может быть получен, если выполнение транзакций Т1, Т2 и ТЗ подчиняется двухфазному протоколу блокировки. В этом случае для выполнения операции R3 потребуется установить S-блокировку для элемента А с согласия транзакции ТЗ. Тогда операция U1 в транзакции Т1 не будет выполняться до тех пор, пока не будет снята блокировка, а это не произойдет до завершения выполнения транзакции ТЗ (действительно, при достижении операции U3 транзакции ТЗ и Tl попадут в ситуацию взаимной блокировки).

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

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

PRODUCIBLE < SERIALIZABLE < CORRECT < ALL

15.4. В момент tn ни одна из транзакций не выполнит никакой полезной работы! Дело в том, что имеет место ситуация взаимной блокировки, включающая транзакции Т2, ТЗ, Т9 и Т8. Кроме того, транзакция Т4 находится в состоянии ожидания (ожидает) завершения выполнения транзакции Т9, транзакция Т12 ожидает завершения выполнения транзакции Т4, а транзакции Т10 и ТИ ожидают завершения выполнения транзакции Т12. Эту ситуацию можно представить с помощью приведенного на рис. 15.14 графа ожидания, узлы которого представляют собой транзакции, а направленные от узла Ti к узлу Tj ребра указывают на то, что транзакция Ti находится в состоянии ожидания завершения выполнения транзакции Tj. Возле стрелок размещены названия объектов базы данных с указанием в скобках уровня блокировки, в котором они находятся в состоянии ожидания.

15.5. Для задач, приведенных на рис. 15.1-15.3, уровень изоляции стабильности курсора обладает тем же эффектом, что и уровень повторяемости считывания (обратите внимание, однако, что для СУБД DB2 это утверждение не применимо к уровню стабильности курсора из-за того, что в этой СУБД вместо S-блокировок используются U-блокировки [4.20]). Что касается проблемы несогласованной обработки данных (см. рис. 15.4), то уровень изоляции стабильности курсора не позволяет разрешить эту проблему. Дело в том, что транзакция А должна выполняться на уровне повторяемости считывания для того, чтобы сохранить все свои блокировки до завершения выполнения транзакции, иначе будет получен неверный результат. (Конечно, если система поддерживает такой режим, то в качестве альтернативного варианта можно было бы с помощью транзакции А полностью заблокировать всю переменную-отношение счетов, установив некоторую явно заданную блокировку. Это решение можно было бы использовать как для уровня стабильности курсора, так и для уровня повторяемости чтения.)

15.6. См. раздел 15.8. Обратите внимание на то, что формальные определения даются с помощью матрицы совместимости типов блокировок (см. рис. 15.11).

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

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

Зависимость от незафиксированных результатов. Это всего лишь иное название проблемы некорректного чтения.

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