Введение в системы БД (542480), страница 146
Текст из файла (страница 146)
Обратите внимание, что транзакция-жертва признается "неудачной" и ее откат выполняется не по ее собственной виве. В одних системах предусмотрен автоматический перезапуск этой транзакции в предположении, что обстоятельства, которые привели к возникновению взаимной блокировки, вновь не повторятся. В других системах в программу, связанную с остановленной транзакцией, просто посылается сообщение об имевшей место ситуации взаимной блокировки, после чего вся остальная обработка ошибки возлагается на саму эту программу. С точки зрения прикладного программиста, первый из подходов, безусловно, предпочтительнее.
Тем не менее решать данную проблему всегда рекомендуется, учитывая точку зрения пользователя. 15.б. Упорядочиваемость В предыдущих разделах были описаны основные положения, необходимые для объяснения ключевого понятия упорядочиваемость (зег1а!1заЬ11пу), под которым понимается некий обобщенный критерий правильности выполнения заданного набора транзакций.
Согласно этому критерию выполнение заданного множества транзакций считается корректным, если оно является упорядоченным, т.е. если при его выполнении будет получен такой же результат, как н при последовательном выполнении этих же транзакций. Ниже приведено обоснование данного утверждения. 1. Отдельные транзакции считаются корректными, если при их выполнении база данных переходит из одного непротиворечивого состояния в другое непротиворечивое состояние. 2. Значит, последовательное выполнение транзакций в некотором произвольном порядке также является корректным.
Порядок выполнения транзакций может быть произвольным, поскольку отдельные транзакции независимы одна от другой. 3. Чередующееся выполнение операций отдельных транзакций также можно считать корректным, если полученные результаты будут эквивалентны тем, которые были бы достигнуты при последовательном выполнении этих же транзакций; в таком случае данная последовательность операций считаетсяупорядоченвой.
Возвращаясь к приведенным выше примерам из раздела 15.2 (см. рис. 15.1 — 15.4), можно отметить следующее: проблема в каждом случае заключалась в том, что чередующееся выполнение операций отдельных транзакций не было упорядочено, т.е. не было эквивалентно выполнению либо сначала транзакции А, а затем транзакции В, либо сначала транзакции В, а затем транзакции А, Основной смысл предложенного выше механизма блокировки заключался в прииудитегьнаи обеспечении упорядоченности. На рис. 15.7 и 15.8 чередование выполняющихся операций эквивалентно выполнению сначала транзакции В, а затем транзакции А.
На рис. 15.6 и 15.9 показана ситуация взаимной блокировки, для устранения которой следует отменить одну из двух транзакций с последующим ее перезапуском. Если отменить транзакцию А, чередование выполнения операций вновь станет эквивалентным выполнению сначала транзакции В, а затем транзакции А. 576 Часть 1К Управление транзакциячи Терминология. Для заданного набора транзакций любой порядок выполнения их операций (чередующийся или какой-либо иной) называется графиком запуска.
Выполнение транзакций по одной без чередования их операций называется последовательным графиком, а любой другой порядок выполнения — чередующимся или непоследовательным графиком. Два графика называются эквивалентными, если при их выполнении будет получен один результат, независимо от исходного состояния базы данных. Таким образом, график запуска является корректным (т.е. упорядоченным), если он эквивалентен некоторому последовательному графику запуска.
Необходимо подчеркнуть, что при выполнении двух разных последовательных графиков запуска одного и того же набора транзакций, в принципе, можно получить совершенно разные результаты. Поэтому и выполнение двух различных чередующихся графиков для этого набора транзакций может привести к различным результатам, которые, тем не менее, будут восприняты, как корректные. Предположим, например, что транзакция А содержит операцию "добавить 1 к х'*, а транзакция  — "удвоить значение х" (где х— некоторый элемент базы данных).
Допустим также, что начальное значение х равно 10, Тогда при последовательном выполнении сначала транзакции А„а затем транзакции В будет получен результат х=22, а при последовательном выполнении сначала транзакции В, а затем транзакции А, будет получен результат х=21, Оба результата являются одинаково верными, а любой график запуска, эквивалентный выполнению либо сначала транзакции А, а затем транзакции В, либо сначала транзакции В, а затем транзакции А, также будет верным (см. упр. 15.3). Концепция упорядочиваемости впервые была предложена Есвараном (Езхчагап) в (15.5) (хотя и под другим названием).
В его работе также доказана важная теорема, получившая название теорема двухфазной блокировки4. Кратко ее можно сформулировать следующим образом. Если выполнение всех транзакций подчиняется протоколу двухфазной блокировки, то всв возиажныв чвредуюи)неся графики запуска этих транзакций будут упарядочвнны.ми.
При этом требования, выдвигаемые протоколом двухфазной блокировки, заключаются в следующем. 1. До выполнения каких-либо операций с некоторым объектом (например, с кортежем базы данных) транзакция должна блокировать этот объект. 2.
После перво~о же снятия блокировки некоторого объекта транзакция теряет право устанавливать какие-либо новые блокировки. В соответствии с требованиями этого протокола выполнение любой транзакции должно включать две послеловательные фазы: фазу установки блокировок (фазу роста) и фазу снятия блокировок (фазу сжатия).
Замечание. На практике вторая фаза часто сводится к единственной операции фиксации (или отката) в конце транзакции. Поэтому протокол блокировки, описанный выше, в разделе 15.3, можно рассматривать как строго соответствующий определению двухфазного протокола. В Двухфазная блокировка не имеет ничего общего с двухфазнай фиксацией 577 Глава 15. Параллельность Понятие упорядочиваемости существенно облегчает понимание этой довольно запуганной области знаний. В дополнение к уже сказанному следует добавить еще несколько комментариев. Пусть 1 является чередующимся графиком, включающим некоторый набор транзакций Т1, Т2, ..., Тп. Если 1 является упорядоченным графиком, то существует некоторый последовательный график Я, включающий тот же набор транзакций Т1, Т2, ..., Тл, ~акой, что график 1 будет эквивалентен графику Я.
В этом случае график Я называется упорядочением графика В. Как уже было показано ранее, график Я необязательно является уникальным, т.е, некоторый чередующийся график 1 может иметь несколько упорядочений. Пусть Т1 и Т) — некоторые транзакции из множества транзакций Т1, Т2, ..., Тп. Не ~еряя общности рассуждений, предположим, что в упорядочении Я транзакция Т1 предшествует транзакции Т). Следовательно, чередующийся график запуска 1 должен иметь такой эффект, как если бы транзакция Т1 выполнялась перед транзакцией Т). Иначе говоря, неформальная, но очень полезная характеристика упорядочиваемости может быть выражена следующим образом.
Если й и В являются двумя произвольными транзакциями некоторого упорядоченного графика запуска, то либо транзакция А логически предшествует транзакции В, либо транзакция В логически предшествует транзакции А. Иначе говоря, либо транзакция В имеет доступ к результатам выполнения транзакции А, либо транзакция А имеет доступ к результатам выполнения транзакции В.
(Если в транзакции й выполняется обновление кортежей р, г), ..., г и транзакция В используе~ эти кортежи в качестве входных данных, то либо все доступные ей кортежи будут обновлены транзакцией А, либо все доступные ей кортежи будут находиться в том состоянии, в котором они были до выполнения транзакции А, т.е. транзакция В никогда не сможет иметь доступ к "смеси" кортежей в разных состояниях.) И наоборот, если результат выполнения транзакций не соответствует тем результатам, которые были бы получены при последовательном выполнении транзакции й, а затем транзакции В, либо при последовательном выполнении транзакции В, а затем транзакции А, то данный график является неупорядоченным и, следовательно, неверным.
В заключение стоит подчеркнуть, что если выполнение некоторой транзакции й не является двухфазным (т.е. не удовлетворяет требованиям протокола двухфазной блокировки), то всегда можно построить другую транзакцию В, которая при чередующемся выполнении с транзакцией й приведет к графику запуска, который не будет упорядоченным, и потому будет неверным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
