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

15.2. Berenson Н. et al. А Critique of ANSI SQL Isolation Levels Proc. 1995 ACM SIGMOD Int. Conf. on Management of Data. - San Jose, Calif, May, 1995.

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

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

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

Изменения, выполненные одной транзакцией, не могут быть восприняты другими фанзакциями [за исключением фанзакций на уровне READ UNCOMMITTED] до тех пор, пока ее выполнение не будет зафиксировано. Что в данном контексте означает слово восприняты! Может ли фанзакция обновить часть неаккуратно считываемых данных без их восприятия ?

Замечание. Все эти замечания взяты из работы [4.19].

15.3. Bernstein Р.А., Goodman N. Timestamp-Based Algorithms for Concurrency Control in Distributed Database Systems Proc. 6th Intem. Conf on Very Large Data Bases. - Montreal, Canada, October, 1980.

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

Иначе говоря, конфликты могут происходить только между операциями обновления и для их устранения используется механизм блокировки. Однако для устранения конфликтов, безусловно, могут использоваться и другие методы, например временные отметки [15.3].

закции В, то система ведет себя так, как будто выполнение транзакции А полностью завершилось еще до начала выполнения транзакции В (как это имеет место в последовательном графике запуска). Таким образом, для транзакции А будут недоступны любые обновления, выполняемые транзакцией В. Кроме того, она не сможет обновить объект, уже считанный транзакцией В. Подобная схема управления может быть организована следующим образом. Для каждого запроса к базе данных система сравнивает временндю отметку транзакции этого запроса с временной отметкой транзакции, выполнившей последнее считывание или обновление запрашиваемого кортежа. В случае конфликта транзакция запроса может быть перезапущена с новой временной меткой (так же, как и в случае с оптимистическими методами [15.14]).

Как следует из заголовка этой работы, данная методика была изначально создана в контексте распределенной системы (где использование блокировки сопряжено с возникновением нежелательных накладных расходов из-за отправки сообщений для проверки и установки блокировок). Однако такая методика почти наверняка не годится для нераспределенных систем. Кроме того, существует достаточно скептическое отношение к практичности ее использования даже для распределенных систем. Одной очевидной проблемой является то, что каждый кортеж должен содержать временню метку последней транзакции, которая считывала данные этого кортежа (а также временню метку последней транзакции, которая обновляла данные этого кортежа). В таком случае подразумевается, что каждая операция чтения становится операцией записи! Действительно, в [14.12] утверждается, что такая схема на самом деле является частным случаем схем оптимистического метода управления параллельностью [15.14], для которых, в свою очередь, характерны собственные проблемы. 15.4. Blasgen M.W., Gray J.N., Mitoma М., Price Т.О. The Convoy Phenomenon ACM Operating Systems Review. - April, 1979. - 13, № 2.

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

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

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

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

15.5. Eswaran К.Р., Gray J.N., Lorie R.A., Traiger LL. The Notions of Consistency and Predicate Locics in a Data Base System CACM. - November, 1976. - 19, № П.

В этой работе впервые предложено строгое теоретическое описание основ управления параллельностью.

15.6. Franaszeic Р., Robinson J.T. Limitations on Concurrency in Transaction Processing ACM TODS. - March, 1985. - 10, № L

Cm. комментарий к [15.14].

15.7. Franaszek P., Robinson J.T., Thomasian A. Concurrency Control for High Contention Environments Ibid. - 1992. - 17, № 2.

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

15.8. Gray J.N. Experience with the System R Lock Manager. IBM San Jose Research Laboratory internal memo, 1980.

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

Использование блокировок связано с накладными расходами в размере 10% при работе с интерактивными транзакциями и в размере 1% при работе с пакетными транзакциями.

Желательно поддерживать разные уровни детализация блокировок.

Приветствуется автоматическая эскалация уровня блокировок.

Ситуации взаимной блокировки очень редко возникают на практике и никогда не включают более двух транзакций. Почти все ситуации взаимной блокировки (97%) можно устранить с помощью U-блокировок, что и предусмотрено в