    Глава 14 

    Параллелизм 

    14.1. Введение 

    Как разъяснялось во введении к главе 13, восстановление данных и 
параллельное выполнение операций следует рассматривать совместно, поскольку 
обе эти темы являются частями более общей темы, связанной с обработкой 
транзакций. Однако в этой главе основное внимание уделяется именно 
параллелизму. Термин параллелизм означает возможность одновременной обработки 
в СУБД многих транзакций с доступом к одним и тем же данным, причем в одно и 
то же время. Как известно, в такой системе для корректной обработки 
параллельных транзакций без возникновения конфликтных ситуаций необходимо 
использовать некоторый метод управления параллелизмом. Ниже в этой главе 
приведены примеры конфликтных ситуаций, возможных при отсутствии 
соответствующего управления. 
    В общем данная глава имеет следующую структуру. Вначале рассматриваются 
некоторые проблемы, которые могут возникнуть при отсутствии должного 
управления параллелизмом. Затем вводится стандартный метод разрешения таких 
проблем, т.е. метод блокировки. 
    Замечание. Блокировка не является единственным возможным подходом в 
решении проблемы управления параллелизмом, но она, несомненно, чаще других 
встречается на практике. Некоторые другие подходы описаны в комментариях, 
приведенных в списке литературы. 
    Далее описывается, как можно использовать блокировку для решения проблем, 
о которых идет речь в начале главы. Однако с внедрением метода блокировки 
возникают другие проблемы; среди них наиболее известна проблема тупиковых 
ситуаций, которая и описывается ниже в этой главе. Затем описывается концепция 
способности к упорядочению, которая определяется как формальный критерий 
правильности выполнения некоторого набора параллельных транзакций. Потом 
продолжается рассмотрение некоторых важных уточнений основной идеи 
блокирования, а именно уровней изоляции и преднамеренной блокировки. Далее 
описывается, как используются перечисленные выше понятия в стандарте языка 
SQL. И наконец, приводится резюме и несколько заключительных замечаний. 
    Здесь также уместно привести общие замечания. 
    1.  Во-первых, идеи параллелизма, как и идеи восстановления данных, в 
некоторой степени не зависят от того, является ли СУБД реляционной или 
какой-либо другой. Однако большая часть теоретической работы в этой области, 
как и в области восстановления данных, выполнялась именно в некотором 
специализированном реляционном контексте. 
    2.  Во-вторых, параллелизм, как и восстановление данных, является весьма 
обширной темой, а потому в этой главе будут описаны только некоторые наиболее 
важные идеи. Кроме того, в упражнениях и ответах на них, а также в списке 
литературы в конце главы содержится обсуждение некоторых последних достижений 
в этой области знаний. 

    368	Часть IV, Защита данных 

    14.2. Три проблемы параллелизма 

    Прежде всего следует уточнить, что каждый метод управления параллелизмом 
предназначен для решения некоторой конкретной задачи. Тем не менее, при 
обработке правильно составленных транзакций возникают ситуации, которые могут 
привести к получению неправильного результата из-за взаимных помех среди 
некоторых транзакций. (Обратите внимание, что вносящая помеху транзакция сама 
по себе может быть правильной. Неправильный конечный результат возникает по 
причине бесконтрольного чередования операций из двух правильных транзакций. 
Более подробно смысл понятия "правильная транзакция" обсуждается далее в этой 
книге.) Основные проблемы, возникающие при параллельной обработке транзакций 
(далее они рассматриваются более подробно) следующие: 
    •	проблема потери результатов обновления; 
    •	проблема незафиксированной зависимости', 
    •	проблема несовместимого анализа. 
    Проблема потери результатов обновления 
    Рассмотрим ситуацию, показанную на рис. 14.1, в такой интерпретации: 
транзакция А извлекает некоторый кортеж/? в момент времени tl\ транзакция В 
извлекает некоторый кортеж р в момент времени ?2; транзакция А обновляет 
некоторый кортеж р (на основе значений, полученных в момент времени //) в 
момент времени t3; транзакция В обновляет тот же кортеж р (на основе значений, 
полученных в момент времени /2, которые имеют те же значения, что и в момент 
времени //) в момент времени t4. Однако результат операции обновления, 
выполненной транзакцией А, будет утерян, поскольку в момент времени t4 она не 
будет учтена и потому будет "отменена" операцией обновления, выполненной 
транзакцией В. 

    Транзакция Л	Время	Транзакция В 
    Извлечение кортежа р	I tl	
    -	t2 I	Извлечение кортежа	Р 
    Обновление кортежа р	t3	
    -	\	
    -	t4	Обновление кортежа	Р 
    -	±	— 

    Рис. 14.1. Потеря в момент времени t4 результатов обновления, выполненного 
транзакцией А 

    Проблема незафиксированной зависимости 

    Проблема незафиксированной зависимости появляется, если с помощью 
некоторой транзакции осуществляется извлечение (или, что еще хуже, обновление) 
некоторого кортежа, который в данный момент обновляется другой транзакцией, но 
это обновление еще не закончено. Таким образом, если обновление не завершено, 
существует некоторая вероятность того, что оно не будет завершено никогда. 
(Более того, в подобном случае может быть выполнен возврат к предыдущему 
состоянию кортежа с отменой выполнения транзакции.) В таком случае в первой 
транзакции будут принимать участие данные, которых больше не существует (в том 
смысле, что они "никогда" не существовали). Эта ситуация показана на рис. 14.2 
и 14.3. 
    В первом примере (см. рис. 14.2) транзакция А в момент времени t2 
встречается с невыполненным обновлением (оно также называется невыполненным 
изменением). Затем это обновление отменяется в момент времени (3. Таким 
образом, транзакция А вы

    Глава 14. Параллелизм 369 

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

    Транзакция Л	Время	Транзакция В 
    -	I	
    -	tl	Обновление кортежа	Р 
    -	I	
    Извлечение кортежа р	t2	— 
    -	t3	Отмена выполнения транзакции 
    —	4	— 

    Рис. 14.2. Транзакция А становится зависимой от невыполненного изменения в 
момент времени t2 

    Транзакция А	Время                Транзакция В 
    —	tl             Обновление кортежа р 
    I Обновление кортежа р         t2	— 
    —	t3           Отмена выполнения транзакции 
    —	J, 

    Рис. 14.3. Транзакция А обновляет невыполненное изменение в момент времени 
т.2, и результаты этого обновления утрачиваются в момент времени t3 

    Второй пример, приведенный на рис. 14.3, иллюстрирует более "ужасный" 
случай. Не только транзакция А становится зависимой от изменения, не 
выполненного в момент времени 12, но также в момент времени t3 фактически 
утрачивается результат обновления, поскольку отмена выполнения транзакции В в 
момент времени t3 приводит к восстановлению кортежа р к исходному значению в 
момент времени tl. Это еще один вариант проблемы потери результатов обновления. 

    Проблема несовместимого анализа 

    На рис. 14.4 показаны транзакции А и В, которые выполняются для кортежей 
со счетами (СЧЕТ). При этом транзакция А суммирует балансы, транзакция В 
производит перевод суммы 10 со счета 3 на счет 1. Полученный в итоге 
транзакции А результат 110, очевидно, неверен, и если он будет записан в базе 
данных, то в ней может возникнуть проблема несовместимости. В таком случае 
говорят, что транзакция А встретилась с несовместимым состоянием и на его 
основе был выполнен несовместимый анализ. Обратите внимание на следующее 
различие между этим примером и предыдущим: здесь не идет речь о зависимости 
транзакции А от транзакции В, так как транзакция В выполнила все обновления до 
того, как транзакция А извлекла СЧЕТ 3. 

    14.3. Блокировка 

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

    370 Часть IV. Защита данных 

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

    СЧЕТ 1	СЧЕТ 2СЧЕТ 3 ______________40___________________50___________________30______________ 
    _________Транзакция А___________Время____________Транзакция В________ _	.  
                  _ 
    I 
    Извлечение кортежа СЧЕТ 1 :        tl	— sum =40                I           
        — 
    I 
    Извлечение кортежа СЧЕТ 2 :        t2	— sum =90                I           
        
    —	t3         Извлечение кортежа СЧЕТ 3 : 
    —	t4        Обновление кортежа СЧЕТ 3 : I                  30 -» 20 
    —	I 
    —	t5        Извлечение кортежа СЧЕТ 1 : 
    I 
    —	t6         Обновление кортежа СЧЕТ 1 : 
    I	40 -» 50 I 
    —	t7           Завершение выполнения 
    —	|                 транзакции 
    I 
    Извлечение кортежа СЧЕТ 3 :        t8 sum = 110 (а не 120)	J, 

    Рис. 14.4. Транзакция А выполнила несовместимый анализ 


    Ниже функционирование блокировки описано более подробно. 
    1.  Прежде всего, предположим, что в системе поддерживается два типа 
блокировок: блокировка без взаимного доступа (монопольная блокировка), 
называемая Х-блокировкой (X locks — exclusive locks), и блокировка с взаимным 
доступом, называемая S-блокировкой (S locks — Shared locks). 
    Замечание. Х- и S-блокировки иногда называют блокировками записи и чтения 
соответственно. Здесь предполагается, что Х- и S-блокировки единственно 
возможные, хотя ниже в этой главе приводятся примеры блокировок других типов. 
Кроме того, допустим, что в данном случае кортежи являются единственным типом 
"блокируемого объекта", хотя опять же ниже описаны примеры других типов таких объектов. 
    2.  Если транзакция А блокирует кортеж р без возможности взаимного доступа 
(Х-блокировка), то запрос другой транзакции В с блокировкой этого кортежа р 
будет отменен. 
    3.  Если транзакция А блокирует кортеж р с возможностью взаимного доступа 
(S-блокировка), то " запрос со стороны некоторой транзакции В на Х-блокировку 
кортежа будет отвергнут; • запрос со стороны некоторой транзакции В на 
S-блокировку кортежа р будет принят (т.е. транзакция В также будет блокировать 
кортеж р с  помощью S-блокировки). 

    Глава 14. Параллелизм 371 

    Эти правила можно наглядно представить в виде матрицы совместимости, 
показанной на рис. 14.5, и интерпретировать ее следующим образом. Рассмотрим 
некоторый кортеж р и предположим, что транзакция А блокирует кортеж р 
различными типами блокировки (это обозначено соответствующими символами S и X, 
а отсутствие блокировки — прочерком). Предположим также, что некоторая 
транзакция В запрашивает блокировку кортежа р, что обозначено в первом слева 
столбце матрицы на рис. 14.5 (для полноты картины в таблице также приведен 
случай "отсутствия блокировки"). В других ячейках матрицы символ N обозначает 
конфликтную ситуацию (запрос со стороны транзакции В не может быть 
удовлетворен, и сама эта транзакция переходит в состояние ожидания), a Y — 
полную совместимость (запрос со стороны транзакции В удовлетворен). Очевидно, 
что эта матрица является симметричной. 

    II   х.|    s			
    X	N	N	Y 
    s	N	Y	Y 
    -	Y	Y	Y 

    Рис. 14.5. Матрица совместимости для Х- и S-блокировки 

    Теперь следует ввести протокол доступа к данным, который на основе 
введения только что описанных Х- и S-блокировки позволяет избежать 
возникновения проблем параллелизма (описанных выше в этой главе). 
    1.  Транзакция, предназначенная для извлечения кортежа, прежде всего 
должна наложить S-блокировку на этот кортеж. 
    2.  Транзакция, предназначенная для обновления кортежа, прежде всего 
должна наложить Х-блокировку на этот кортеж. Иначе говоря, если, например, для 
последовательности действий типа извлечение/обновление для кортежа уже задана 
S-блокировка, то ее необходимо заменить Х-блокировкой. 
    Замечание. Блокировки в транзакциях обычно задаются неявным образом: 
например, запрос на "извлечение кортежа" является неявным запросом с 
S-блокировкой, а запрос на "обновление кортежа"— неявным запросом с 
Х-блокировкой соответствующего кортежа. При этом под термином "обновление" 
(как и ранее) подразумеваются помимо самих операций обновления также операции 
вставки и удаления. При строгом описании протокола возможны небольшие отличия, 
связанные с операциями вставки и удаления, однако здесь они будут опущены. 
    3.  Если запрашиваемая блокировка со стороны транзакции В отвергается 
из-за конфликта с некоторой другой блокировкой со стороны транзакции А, то 
транзакция В переходит в состояние ожидания. Причем транзакция В будет 
находиться в состоянии ожидания до тех пор, пока не будет снята блокировка, 
заданная транзакцией А. 
    Замечание. В системе обязательно должны быть предусмотрены способы 
устранения бесконечно долгого состояния ожидания транзакции В (это состояние 
обычно называется зависанием). Самым простым способом может служить 
организация обработки запросов на блокировку в очередности "первым поступил — 
первым обработан". 
    4.  Х-блокировки сохраняются вплоть до конца выполнения транзакции (до 
операции "завершение выполнения" или "отмена выполнения"). S-блокировки также 
обычно сохраняются вплоть до этого момента, однако при работе с ними следует 
учесть замечания, которые излагаются несколько ниже в этой главе. 

    14.4. Решение проблем параллелизма 

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

    372 Часть IV. Защита данных 

    Проблема потери результатов обновления 
    
    На рис. 14.6 приведена измененная версия процесса, показанного на рис. 
14.1, с учетом применения протокола блокировки для чередующихся операций. 
Операция обновления для транзакции А в момент времени t3 не будет выполнена, 
поскольку она является неявным запросом с заданием Х-блокировки для кортежа р, 
а этот запрос вступает в конфликт с S-блокировкой, уже заданной транзакцией В. 
Таким образом, транзакция А переходит в состояние ожидания. По аналогичным 
причинам транзакция В переходит в состояние ожидания в момент времени (4. Хотя 
в таком случае результаты любых обновлений не будут утрачены, решение этой 
проблемы с помощью блокировки возможно только при решении другой проблемы. Эта 
новая проблема называется тупиком, она рассматривается ниже в этой главе. 

    Транзакция А	Время	Транзакция В 
    _	.	_ 
    I 
    Извлечение кортежа р	tl	~ 
    (задание S-блокировки для р)	I	— 
    —	t2	Извлечение кортежа р 
    —	I	(задание S-блокировки для р) 
    I 
    Обновление кортежа р	t3	— 
    (задание Х-блокировки для р)	I	— 
    Ожидание	I	— 
    Ожидание	t4	Обновление кортежа р 
    Ожидание	|	(задание Х-блокировки для р) 
    Ожидание	|	Ожидание 
    Ожидание	|	Ожидание 
    Ожидание	J,	Ожидание 

    Рис. 14.6. Хотя обновления не утрачиваются, но в момент времени 14 
возникает тупиковая ситуация 

    Проблема незафиксированной зависимости 

    На рис. 14.7 и 14.8 приведены в измененном виде примеры, показанные ранее 
на рис. 14.2 и 14.3 соответственно. Они демонстрируют чередующееся выполнение 
операций согласно описанному выше протоколу блокировки. Операция для 
транзакции А в момент времени /2 (извлечение на рис. 14.7 и обновление на рис. 
14.8) не будет выполнена. Дело в том, что она является неявным запросом с 
заданием блокировки для кортежа р, а этот запрос вступает в конфликт с 
Х-блокировкой, уже заданной транзакцией В. Таким образом, транзакция А 
переходит в состояние ожидания до тех пор, пока не будет прекращено выполнение 
транзакции В (до операции окончания или отмены выполнения транзакции В). Тогда 
заданная транзакцией В блокировка будет снята и транзакция А может быть 
выполнена. Причем транзакция А будет иметь дело с некоторым фиксированным 
значением (либо существовавшим до выполнения транзакции В при отмене ее 
выполнения, либо полученным после выполнения транзакции В). В любом случае 
транзакция А больше не зависит о т незафиксированного обновления. 

    Проблема несовместимого анализа 

    На рис. 14.9 приведена измененная версия рис. 14.4 с перечислением 
чередующихся транзакций согласно протоколу блокировки из раздела 14.3. 
Операция обновления для транзакции В в момент времени t6 не будет выполнена. 
Дело в том, что она является неявным запросом с заданием Х-блокировки для 
кортежа СЧЕТ 1, а этот запрос вступает в конфликт с S-блокировкой, уже 
заданной транзакцией А. Таким образом, 

    Глава 14. Параллелизм 373 

транзакция В переходит в состояние ожидания. Точно так же операция 
извлечения для транзакции А в момент времени /7 не будет выполнена. Дело в 
том, что она является неявным запросом с заданием S-блокировки для кортежа 
СЧЕТ 3, а этот запрос вступает в конфликт с Х-блокировкой, уже заданной 
транзакцией В. Таким образом, транзакция А переходит в состояние ожидания. 
Следовательно, блокировка хотя и помогает решить одну проблему (а именно 
проблему несовместимого анализа), но приводит к необходимости решения другой 
проблемы (а именно проблемы возникновения тупиковой ситуации, которая 
обсуждается в ниже). 

    ________Транзакция А__________Время_____________Транзакция В__________ 
    _	.                    _ 
    I 
    —	tl            Обновление кортежа р 
    —	I          (задание Х-Олокировки для р) 
    I 
    Извлечение кортежа р         t2	— (задание S-блокировки для р)       |     
               — Ожидание               |                    — Ожидание        
      t3       Окончание или отмена выполнения Ожидание               |        
  (снятие Х-блокировки для р) Итог: извлечение кортежа р        t4 (задание 
S-блокировки для р)        | ____________4-__________________________ 

    Рис. 14.7. Транзакция А предохраняется от выполнения операций с 
незафиксированным изменением в момент времени t2 

    Транзакция А	Время               Транзакция В 
    —	tl            Обновление кортежа р 
    —	I          (задание Х-блокировки для р) 
    Обновление кортежа р	t2                     — 
    {задание Х-блокировки для р)	I                    — 
    Ожидание	|                    — 
    Ожидание	t3            Окончание или отмена 
    Ожидание	|                  выполнения 
    Ожидание	|           (снятие Х-блокировки для р) 
    Итог: обновление кортежа р	t4 
    (задание Х-блокировки для р)	I 
    4. 

    Рис. 14.8. Транзакция А предохраняется от выполнения операций с 
незафиксированным изменением в момент времени (2 

    14.5. Тупиковая ситуация 

    Как было показано выше, блокировку можно использовать для разрешения трех 
основных проблем, возникающих при параллельной обработке кортежей. К 
сожалению, использование блокировок приводит к возникновению другой проблемы — 
тупиковой ситуации. Два примера таких ситуаций были приведены выше. На рис. 
14.10 показан обобщенный пример этой проблемы, в котором р! и р2 представляют 
любые блокируемые объекты, необязательно кортежи базы данных (подробнее об 
этом ниже в данной главе), а выражения типа "блокировка ... без взаимного 
доступа" представляют любые операции с наложением блокировки (без взаимного 
доступа), заданные как явно, так и неявно. 

    374 Часть IV. Защита данных 

    СЧЕТ 1                СЧЕТ 2                  СЧЕТ 3 40                    
50                     30 Транзакция А            Время             Транзакция 
В \ \ Извлечение кортежа СЧЕТ 1 :        tl                   — (задание 
S-блокировки для         |                   — кортежа СЧЕТ 1)              |  
                   — sum =40               |                   — Извлечение 
кортежа СЧЕТ 2 :        t2                    — (задание S-блокировки для      
   |                   — кортежа СЧЕТ 2)              |                     — 
sum =90               |                   -—                 t3        
Извлечение кортежа СЧЕТ 3 : —                  |          (задание 
S-блокировки для -                   |               кортежа СЧЕТ 3) _         
          1                     _ —                  t4         Обновление 
кортежа СЧЕТ 3 : —                   |           (задание Х-блокировки для -   
               |              кортежа СЧЕТ 3) 1                   30 -> 20 — 
t5         Извлечение кортежа СЧЕТ 1 : —                  |          (задание 
S-блокировки для -                   |               кортежа СЧЕТ 1) _         
          1                     _ —                   t6         Обновление 
кортежа СЧЕТ 1 : —                   |           (задание Х-блокировки для —   
                |               кортежа СЧЕТ 1) —                   |          
        Ожидание Извлечение кортежа СЧЕТ 3 :        t7                 
Ожидание (задание S-блокировки для         |                 Ожидание кортежа 
СЧЕТ 3)              |                  Ожидание Ожидание                1     
             Ожидание Ожидание                J,                 Ожидание 

    Рис. 14.9. Проблема несовместимого анализа разрешается, но в момент 
времени 17 возникает тупиковая ситуация 

    Транзакция А            Время             Транзакция В \ 1 Блокировка р! 
без взаимного       tl                  — доступа                |             
      -—                 t2        Блокировка р2 без взаимного -               
   |                 доступа Блокировка р2 без взаимного       t3              
    — доступа                |                   — Ожидание               |    
               -Ожидание               t4        Блокировка р1 без взаимного 
Ожидание               |                 доступа Ожидание               |      
           Ожидание Ожидание               -                Ожидание 

    Рис. 14.10. Пример тупиковой ситуации 


    375	Часть IV. Защита данных 


    Тупиковая ситуация возникает тогда, когда две или более транзакции 
одновременно находятся в состоянии ожидания, причем для продолжения работы 
каждая из транзакций ожидает прекращения выполнения другой транзакции. На рис. 
14.10 показана тупиковая ситуация, включающая две транзакции, однако в 
принципе возможны тупиковые ситуации с участием трех, четырех и более 
транзакций. Однако эксперименты с системой System R показали, что на практике 
никогда не встречаются тупиковые ситуации с участием более чем двух транзакций [14.4]. 
    Желательно, чтобы при возникновении тупиковой ситуации система могла 
обнаружить ее и найти из нее выход. Для обнаружения тупиковой ситуации следует 
обнаружить цикл в диаграмме состояний ожидания, т.е. в перечне "транзакций, 
которые ожидают окончания выполнения других транзакций". Поиск выхода из 
тупиковой ситуации состоит в выборе одной из заблокированных транзакций в 
качестве жертвы и отмене ее выполнения. Таким образом, с нее снимается 
блокировка, а выполнение другой транзакции может быть возобновлено. 
    Замечание. На практике не все системы в состоянии обнаружить тупиковую 
ситуацию. Например, в некоторых из них используется хронометраж выполнения 
транзакций, и сообщение о возникновении тупиковой ситуации поступает, если 
транзакция не выполняется за некоторое предписанное заранее время. 
    Обратите внимание, что транзакция-жертва признается "некорректной" и 
отменяется "не из-за собственной некорректности". В некоторых системах 
предусмотрен автоматический перезапуск транзакции с самого начала при условии, 
что обстоятельства, которые привели к тупиковой ситуации, не повторятся вновь. 
А в других системах в программу, связанную с данной транзакцией, просто 
посылается сообщение о "вызвавшей тупиковую ситуацию транзакции-жертве" для 
обработки этой ситуации в самой программе. С точки зрения программирования 
приложений предпочтительнее первый из этих подходов. Но несмотря на это, 
всегда рекомендуется решать данную проблему с точки зрения пользователя. 

    14.6. Способность к упорядочению 

    В предыдущих разделах были описаны некоторые основы, необходимые для 
объяснения ключевого понятия "способность к упорядочению", которое является 
общепринятым критерием правильности управления параллельной обработкой 
кортежей. Точнее говоря, чередующееся выполнение заданного множества 
транзакций будет верным, если оно упорядочено, т.е. при его выполнении будет 
получен такой же результат, как и при последовательном выполнении тех же 
транзакций. Обосновать это утверждение помогут следующие замечания. 
    1. Отдельные транзакции считаются верными, если при их выполнении база 
данных переходит из одного непротиворечивого состояния в другое 
непротиворечивое состояние в смысле, изложенном в главе 13. 
    2.  Следовательно, выполнение транзакций одна за другой в любом 
последовательном порядке также является верным. При этом под выражением "любой 
последовательный порядок" подразумевается, что используются независимые друг 
от друга транзакции. 
    3. Чередующееся выполнение транзакций, следовательно, является верным, 
если оно эквивалентно некоторому последовательному выполнению, т.е. если оно 
подлежит упорядочению. 
    Возвращаясь к приведенным выше примерам (рис. 14.1-14.4), можно отметить: 
данная проблема в каждом случае заключалась в том, что чередующееся выполнение 
транзакций не было упорядочено, т.е. не было эквивалентно выполнению либо 
сначала транзакции А, а затем транзакции В, либо сначала транзакции В, а затем 
транзакции А. Основное значение предложенной выше схемы блокировки заключается в 

    376	Часть IV. Защита данных 

принудительном упорядочении. На рис. 14.7 и 14.8 чередующееся выполнение 
эквивалентно выполнению сначала транзакции В, а затем транзакции А. На рис. 
14.6 и 14.9 показана тупиковая ситуация, в которой можно было бы отменить и, 
возможно, повторно запустить одну из двух транзакций. Если транзакция А 
отменяется, чередующееся выполнение вновь становится эквивалентным выполнению 
сначала транзакции В, а затем транзакции А. 
    Терминология. Для заданного набора транзакций любой порядок их выполнения 
(чередующийся или какой-либо другой) называется графиком запуска. Выполнение 
транзакций по одной без их чередования называется последовательным графиком 
запуска, а непоследовательное выполнение транзакций — чередующимся графиком 
запуска или непоследовательным графиком запуска. Два графика называются 
эквивалентными, если при их выполнении будет получен одинаковый результат, 
независимо от исходного состояния базы данных. Таким образом, график запуска 
является верным (т.е. допускающим возможность упорядочения), если он 
эквивалентен некоторому последовательному графику запуска. 
    Стоит подчеркнуть, что при выполнении двух различных последовательных 
графиков запуска, содержащих одинаковый набор транзакций, можно получить 
совершенно различные результаты. Поэтому выполнение двух различных 
чередующихся графиков запуска с одинаковыми транзакциями может также привести 
к различным результатам, которые могут быть восприняты как верные. Например, 
предположим, что транзакция А означает действие "сложить 1 с х", а транзакция 
В — "удвоить х" (где х — это некоторый объект базы данных). Предположим также, 
что начальное значение х равно 10. Тогда при последовательном выполнении 
сначала транзакции А, а затем транзакции В будет получен результат х=22, а при 
последовательном выполнении сначала транзакции В, а затем транзакции А —х=2\. 
Оба результата одинаково верные, а любой график запуска, эквивалентный 
выполнению либо сначала транзакции А, а затем транзакции В, либо сначала 
транзакции 5, а затем транзакции А, также является верным (это еще будет 
обсуждаться в упражнениях к да нной главе). 
    Концепция способности к упорядочению была впервые предложена (хотя и под 
другим названием) Есвараном (Eswaran) в [14.5]. В этой работе также доказана 
важная теорема двухфазной блокировки', которая кратко может быть 
сформулирована следующим образом: 
    Если все транзакции подчиняются "протоколу двухфазной блокировки", то для 
всех возможных чередующихся графиков запуска существует возможность упорядочения. 
    При этом протокол двухфазной блокировки, в свою очередь, формулируется 
следующим образом. 
    1.  Перед выполнением каких-либо операций с некоторым объектом (например, 
с кортежем базы данных) транзакция должна заблокировать этот кортеж. 
    2.  После снятия блокировки транзакция не должна накладывать никаких 
других блокировок. 
    Таким образом, транзакция, которая подчиняется этому протоколу, 
характеризуется двумя фазами: фазой наложения блокировки и фазой снятия блокировки. 
    Замечание. На практике вторая фаза часто сводится к единственной операции 
окончания выполнения (или отмены выполнения) в конце транзакции. 
Действительно, описанный выше в этой главе протокол блокировки можно 
рассматривать как строгую формулировку двухфазного протокола. 
    Понятие способности к упорядочению существенно облегчает понимание этой 
довольно запутанной области знаний. В дополнение к сказанному следует добавить 
несколько комментариев. Пусть Е является чередующимся графиком запуска, вклю

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

    Глава 14. Параллелизм	377 

чающим некоторый набор транзакций 77, Т2, ... Тп. Если Е является 
графиком, допускающим возможность упорядочения, то существует некоторый 
последовательный график запуска S, содержащий такой набор транзакций Т], 72, 
... Тп, что график Е эквивалентен графику 5. В таком случае S называется 
упорядочением Е. Как уже было показано ранее, S необязательно является 
уникальным, т.е. некоторый график запуска Е может иметь несколько упорядочений. 
    Пусть ТУ и ТУ— некоторые транзакции множества транзакций 77, 72, ... Тп. 
Не теряя общности изложения, предположим, что в упорядочении S транзакция ТУ 
предшествует Ту. Следовательно, для чередующегося графика запуска Е это 
значит, что транзакция ТУ выполняется перед транзакцией ТУ. Иначе говоря, 
неформальная, но очень полезная характеристика упорядочения может быть 
выражена следующим образом. Если А и В являются любыми двумя транзакциями 
некоторого графика запуска, допускающего возможность упорядочения, то либо А 
логически предшествует В, либо В логически предшествует А, т.е. либо В 
использует результаты выполнения транзакции А, либо А использует результаты 
выполнения транзакции В. (Если транзакция А приводит к обновлению кортежей р, 
q, ... г и транзакция В использует эти кортежи в качестве входных данных, то 
используются либо все обновленные с помощью А кортежи, либо полностью не 
обновленные кортежи до выполнения транзакции А, но никак не их смесь.) 
Наоборот, график запуска является н еверным и не подлежит упо рядочению, если 
результат выполнения транзакций не соответствует либо сначала выполнению 
транзакции А, а затем транзакции В, либо сначала выполнению транзакции В, а 
затем транзакции А. 
    В заключение стоит подчеркнуть, что если некоторая транзакция А не 
является двухфазной (т.е. не удовлетворяет протоколу двухфазной блокировки), 
то всегда можно построить некоторую другую транзакцию В, которая при 
чередующемся выполнении вместе с транзакцией А может привести к графику 
запуска, не подлежащему упорядочению и неверному. В настоящее время с целью 
понижения требований к ресурсам и, следовательно, повышения производительности 
и пропускной способности в реальных системах обычно предусмотрено 
использование не двухфазных транзакций, а транзакций с "ранним снятием 
блокировки" (еще до выполнения операции прекращения транзакции) и наложением 
нескольких блокировок. Однако следует понимать, что использование таких 
транзакций сопряжено с большим риском. Действительно, при использовании 
недвухфазной транзакции А предполагается, что в данной системе не существует 
никакой другой чередующейся с ней транзакции В (в противном случае в системе 
возможно получение ошибочных результатов). 

    14.7. Уровни изоляции 

    Термин уровень изоляции, грубо говоря, используется для описания степени 
вмешательства параллельных транзакций в работу некоторой заданной транзакции. 
Но при обеспечении возможности упорядочения не допускается никакого 
вмешательства, иначе говоря, уровень изоляции должен быть максимальным. 
Однако, как уже отмечалось в конце предыдущего раздела, в реальных системах по 
различным причинам обычно допускаются транзакции, которые работают на уровне 
изоляции ниже максимального. 
    Замечание. Уровень изоляции обычно рассматривается как некоторое свойство 
транзакции. В действительности нет никаких причин, по которым данная 
транзакция не могла бы работать в одно и то же время на различных уровнях 
изоляции в разных частях базы данных. Однако здесь для простоты уровень 
изоляции будет рассматриваться всего лишь как некоторое свойство транзакции. 
    Уровней изоляции может быть несколько, например в [14.4] их задано пять, в 
[14.9], как и в стандарте языка SQL, — четыре, а в системе DB2 фирмы IBM 
поддерживается два уровня. Вообще говоря, чем выше уровень изоляции, тем 

    378	Часть IV. Защита данных 

меньше степень вмешательства (и параллелизма), а чем ниже уровень изоляции, тем 
больше степень вмешательства (и параллелизма). В качестве примера рассмотрим 
два уровня, поддерживаемых системой DB2, которые называются уровнями 
стабильности курсора и повторяемого считывания. Уровень повторяемого 
считывания (ПС) является максимальным уровнем; причем если все транзакции 
действуют на этом уровне, то графики запуска обладают возможностью 
упорядочения (при изложении материала выше в этой главе по умолчанию 
полагалось, что все транзакции выполняются именно на этом уровне изоляции). 
Уровню стабильности курсора (СК) для транзакции 77 присущи несколько другие особенности: 
    •	транзакция адресуется к некоторому кортежу/?,1 
    •	таким образом задается блокировка для кортежар, 
    •	после этого снимается адресуемость к кортежу р без его обновления, 
    •	уровень Х-блокировки не достигается, 
    •   в результате блокировка снимается без необходимости ожидания окончания 
выполнения транзакции. 
    Обратите внимание, что теперь некоторая другая транзакция 72 может 
привести к обновлению кортежа/? и внесению в него изменений. Если транзакция 
Т] вновь обратится к кортежу/?, эти изменения будут обнаружены, что может 
привести к несовместимому состоянию базы данных. На уровне ПС, наоборот, все 
блокировки кортежа (а не только Х-блокировки) сохраняются до окончания 
выполнения транзакции и упомянутой выше проблемы не возникает. 
    Замечание. Описанная проблема не единственная, которая может возникнуть на 
уровне СК, просто ее легче всего объяснить. Однако она, к сожалению, приводит 
к выводу, что уровень ПС необходим только в сравнительно маловероятных 
случаях, когда данная транзакция дважды выполняется для одного и того же 
кортежа. Однако существуют аргументы в защиту повсеместного использования 
уровня ПС по сравнению с уровнем СК. Дело в том, что выполнение транзакции на 
уровне СК не является двухфазным, а потому (как разъяснялось выше) в этом 
случае возможность упорядочения не гарантируется. В качестве контраргумента 
следует указать тот факт, что на уровне СК достигается более широкий 
параллелизм, чем на уровне ПС (такая ситуация возможна, но вовсе не обязательна). 
    В заключение следует отметить, что предшествующая характеристика уровня ПС 
как уровня максимальной изоляции относится к уровню ПС, воплощенному в системе 
DB2. К сожалению, в стандарте языка SQL тот же термин "повторяемость 
считывания" используется для описания уровня изоляции, который находится ниже 
максимального уровня. Подробнее это описано ниже в данной главе. 

    14.8. Преднамеренная блокировка 

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

    ' Название "уровень стабильности курсора" происходит от того, что 
обращение к кортежу осуществляется с помощью установки курсора для заданного 
кортежа (это обсуждалось в предыдущих главах книги). Следует уточнить, что в 
системе DB2 блокировка 77, наложенная на кортеж р, является блокировкой 
"обновления" (U-блокировка), а не блокировкой с возможностью взаимного доступа 
(S-блокировка). U-блокировки совместимы с S-блокировками, но не с другими 
U-блокировками и, конечно, не с другими X-блокировками. Далее эти уточнения не 
будут приниматься во внимание. 

    Глава 14. Параллелизм	379 

чем крупнее степень дробления, тем меньше блокировок можно задать и 
требуется протестировать, а значит, будут меньшие накладные расходы (т.е. 
требуется меньшее количество необходимых действий). Например, если транзакция 
накладывает Х-блокировку на целое отношение, то нет необходимости задавать 
Х-блокировку для отдельных кортежей внутри этого отношения, что в результате 
приводит к уменьшению общего числа блокировок. С другой стороны, никакая 
другая параллельная транзакция не в состоянии наложить никаких других 
блокировок на это отношение или кортежи этого отношения. 
    Предположим, что транзакция Т задает Jf-блокировку для некоторого 
отношения R. В ответ на запрос транзакции Т система должна сообщить о наличии 
других блокировок, наложенных другими транзакциями на любой кортеж отношения 
R. И если такая блокировка наложена, то запрос транзакции Т не будет выполнен 
в данный момент времени. Как система может обнаружить конфликт такого рода? 
Очевидно, было бы крайне нежелательно проверять, блокируется ли каждый кортеж 
отношения R какой-либо другой транзакцией, а также задана ли какая-нибудь 
блокировка для какого-либо кортежа отношения R. Вместо этого можно ввести еще 
один протокол, а именно протокол преднамеренной блокировки, в соответствии с 
которым, прежде чем накладывать блокировку на кортеж (вероятно, преднамеренную 
блокировку, о которой подробнее рассказывается ниже), следует наложить ее на 
все отношения, в которых этот кортеж находится. Тогда обнаружить конфликтную 
ситуацию, рассмотренную выше, значительно проще за счет обнаружения блокировки 
науро вне отношений. 
    Как уже упоминалось, Х- и S-блокировки можно задавать как для отдельных 
кортежей, так и для целых отношений. В соответствии с [14.8, 14.9] можно 
ввести три типа преднамеренных блокировок, которые имеют смысл для целых 
отношений, но не для отдельных кортежей: преднамеренная блокировка с 
возможностью взаимного доступа (Intent Shared lock — IS), преднамеренная 
блокировка без взаимного доступа (Intent exclusive lock — IX), а также 
преднамеренная блокировка одновременно как с возможностью взаимного доступа, 
так и без него (Shared Intent exclusive lock — SIX). Ниже приводятся 
неформальные определения различных видов блокировок (здесь предполагается, что 
транзакция Т накладывает блокировку рассматриваемого типа на отношение R), 
причем для полноты картины также приводятся определения S- и Х-блокировки. 
    •  IS 
    Транзакция Т накладывает S-блокировки на отдельные кортежи отношения R для 
того, чтобы гарантировать стабильность этих кортежей при их обработке. 
    •  IX 
    В дополнение к действиям, описанным в приведенной выше формулировке, 
транзакция Т может осуществить обновление отдельных кортежей отношения R, а 
потому на эти кортежи накладываются Х-блокировки. И   S 
    Транзакцией Г допускаются параллельные считывания для отношения R, но не 
обновления. Сама по себе транзакция Г не может обновлять любые кортежи 
отношения R. 
    •   SIX 
    В определении этой блокировки комбинируются определения S- и 
1Х-блокировки, т.е. транзакцией Г допускаются параллельные считывания для 
отношения R, но не обновления. В дополнение к этому транзакция Т может 
осуществить обновление отдельных кортежей отношения R, а потому на эти кортежи 
накладываются Х-блокировки. 
    •  X 
    Транзакцией Т вовсе не допускаются параллельные запросы к отношению R. 
Сама по себе транзакция Глибо может, либо не может обновлять любые кортежи 
отношения R. 

    380	Часть IV. Защита данных 

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

    		X	SIX	IX	S	IS	
    X		N	N	N	N	N	Y 
    SIX	N	N	N	N	Y	Y 
    IX	N	N	Y	N	Y	Y 
    S		N	N	N	Y	Y	Y 
    IS	N	Y	Y	Y	Y	Y 
    -		Y	Y	Y	Y	Y	Y 

    Рис. 14.11. Матрица совместимости, расширенная преднамеренными блокировками 

    Теперь можно представить более точную формулировку протокола 
преднамеренной блокировки. 
    1.  Прежде чем транзакция наложит S-блокировку на данный кортеж, она 
должна наложить IS-блокировку или другую более сильную блокировку на 
отношение, в котором содержится данный кортеж. 
    2.  Прежде чем транзакция наложит Х-блокировку на данный кортеж, она 
должна наложить IX-блокировку или другую более сильную блокировку на 
отношение, в котором содержится данный кортеж. 
    (Однако следует отметить, что это еще далеко не полное определение, 
которое приведено в комментариях к [14.8].) 
    Упомянутое понятие относительной силы блокировок можно объяснить с помощью 
диаграммы приоритета, представленной на рис. 14.12. Блокировка типа L2 
называется более сильной (т.е. находится выше на диаграмме приоритета) по 
отношению к блокировке L1 тогда и только тогда, когда для любой конфликтной 
ситуации (N) в столбце блокировки L1 в некоторой строке матрицы совместимости 
существует также конфликт в столбце блокировки L2 в той же строке (см. рис. 
14.11). Обратите внимание, что запрос на задание блокировки, который 
отвергается для некоторого типа блокировки, также будет отвергнут и для более 
сильного типа блокировки (таким образом подразумевается, что всегда можно 
использовать типы блокировки, более сильные по сравнению с той, которая строго 
необходима в некотором заданном случае.) 

    X 
    I 
    SIX 
    
    
    I	S             I	X 
    I 
    IS 

    Рис. 14.12. Диаграмма приоритета различных типов блокировок 

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

    Глава 14. Параллелизм 381 

вместо этого, вероятно, потребуется задать IX-блокировку. Однако в системе 
также может быть предусмотрено явное задание блокировок с помощью разного рода 
утверждений LOCK, для того чтобы в случае необходимости позволить транзакциям 
наложить S-, Х- и SIX-блокировки на заданном уровне отношений. Например, такое 
заданное явным образом утверждение LOCK поддерживается системой DB2 (хотя это 
и не является стандартом языка SQL). 
    Наконец, необходимо сделать замечание об эскалации блокировок, которая 
реализована во многих системах и представляет собой попытку балансирования 
между вступающими в конфликт требованиями высокого параллелизма и низкими 
накладными расходами на управление блокировками. Основная идея заключается в 
том, что, когда система достигает некоторого заранее заданного порога, она 
автоматически заменяет множество мелких блокировок одной крупной блокировкой. 
Например, набор отдельных S-блокировок на уровне кортежа, составляющий 
IS-блокировку на уровне отношения, можно преобразовать в S-блокировку на 
уровне отношения. На практике это решение часто оказывается весьма полезным. 

    14.9. Поддержка блокировок в SQL 

    В стандарте языка SQL не предусмотрена поддержка явным образом возможности 
блокировки (фактически, блокировка в нем вообще не упоминается). Однако она 
необходима, чтобы гарантировать отсутствие конфликтных ситуаций при 
параллельном выполнении нескольких транзакций. Точнее, требуется, чтобы 
обновления, выполняемые данной транзакцией 77, не были доступны для любой 
другой транзакции 72 до тех и только до тех пор, пока не будет завершено 
выполнение транзакции 77. Завершение выполнения транзакции открывает доступ ко 
всем обновлениям, выполненным данной транзакцией. А отмена выполнения 
транзакции приведет к тому, что все обновления будут отменены. 
    Замечание, Сказанное выше относится к случаям, когда все транзакции 
выполняются на уровне изоляции READ COMMITTED (завершенное считывание), 
REPEATABLE READ (повторяемое считывание) и SERIALIZABLE (способность к 
упорядочению). Особые рассуждения относятся к транзакциям, выполняемым на 
уровне изоляции READ UNCOMMITTED (незавершенное считывание) и предназначенным 
для выполнения "неаккуратных считываний" (об этом речь идет ниже), но только в 
режиме считывания READ ONLY (подробнее это описано в главе 13). 

    Уровни изоляции 

    В главе 13 уже упоминалось утверждение SET TRANSACTION из языка SQL, 
которое используется для указания некоторых характеристик запускаемой на 
выполнение транзакции. Одной из таких характеристик является уровень изоляции, 
который включает уровень завершенного считывания (READ COMMITTED), 
повторяемого считывания (REPEATABLE READ) и способности к упорядочению 
(SERIALIZABLE). По умолчанию устанавливается SERIALIZABLE, хотя, если задан 
один из трех перечисленных уровней, всегда можно использовать более высокий 
уровень, где выражение "более высокий" подразумевает следующий приоритет 
уровней: SERIALIZABLE > REPEATABLE READ > READ COMMITTED > READ UNCOMMITTED. 
    Если все транзакции выполняются на уровне способности к упорядочению 
(принятом по умолчанию), то чередующееся выполнение любого множества 
параллельных транзакций может быть упорядочено. Однако, если любая транзакция 
выполняется на более низком уровне изоляции, то существует множество различных 
способов нарушения способности к упорядочению. В данном стандарте указано три 
особых случая нарушения способности к упорядочению, а именно: 
    •  Неаккуратное считывание. Допустим, что транзакция 77 выполняет 
обновление с некоторой строкой, затем транзакция 72 извлекает эту строку, 
после чего вы

    382	Часть IV. Защита данных 

полнение транзакции 77 отменяется. В результате транзакция 72 обнаружит, 
что данной строки больше не существует в том смысле, что она никогда не 
существовала (поскольку транзакция 77 действительно не была выполнена). 
    •   Неповторяемое считывание. Допустим, транзакция 77 извлекает некоторую 
строку, транзакция Т2 затем обновляет эту строку, после чего транзакция 77 
вновь извлекает "ту" строку. В результате транзакция 77 извлечет из "одной и 
той же" строки два совершенно разных значения. 
    •   Фиктивные элементы. Допустим, что транзакция 77 извлекает множество 
всех строк, которые удовлетворяют некоторому условию (например, строки всех 
поставщиков из Парижа). Допустим, что транзакция 72 вставляет новую строку, 
которая удовлетворяет тому же условию. Если транзакция 77 вновь повторит ту же 
операцию извлечения, что и раньше, то ею будет обнаружена ранее 
отсутствовавшая строка — "фиктивная строка". 
    Различные уровни изоляции определяются на основе приведенных выше случаев 
нарушения способности к упорядочению, и эти определения схематически 
представлены на рис. 14.13. 
    Уровень изоляции	Неаккуратное считывание	Неповторяемое 
считывание	Фиктивные элементы 

    READ UNCOMMITTED	Y	Y	Y 
    READ COMMITTED	N	Y	Y 
    REPEATABLE READ	N	N	Y 
    SERIALIZABLE	N	N	N 

    Рис. 14.13. Уровни изоляции языка SQL 

    Здесь может возникнуть очевидный вопрос: каким образом система может 
предотвратить появление "фиктивных элементов"? Для этого в ней должна быть 
предусмотрена блокировка пути доступа к этим данным. Если в приведенном выше 
примере с поставщиками из Парижа путем доступа к данным служит индекс по 
городам поставщиков, то в системе должен быть заблокирован индекс Парижа. 
Благодаря такой блокировке не будет возникать фиктивных элементов, поскольку 
для их создания потребуется обратиться к пути доступа (т.е. в приведенном 
примере к конкретному значению индекса). Более подробно этот вопрос 
рассматривается в [13.11, 14.4]. 
    Как уже упоминалось выше в этой главе, в системе, поддерживающей помимо 
уровня SERIALIZABLE (который, по сути, является единственным безопасным 
уровнем) также и другие уровни, могут быть предусмотрены некоторые инструменты 
для явного управления параллелизмом. Обычно такие инструменты имеют вид 
задаваемых явным образом выражений LOCK и применяются пользователями для 
обеспечения безопасности, если такая безопасность не обеспечивается самой 
системой. Однако в стандарте языка SQL не предусмотрен такой способ явного 
управления блокировками. 
    В заключение следует повторить, что формулировки уровня REPEATABLE READ в 
стандарте языка SQL и в системе DB2 являются совершенно разными. На самом деле 
уровню REPEATABLE READ в системе DB2 соответствует уровень SERIALIZABLE в 
стандарте SQL. 

    14.10. Резюме 

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

    Глава 14. Параллелизм 383 

    Наиболее распространенной методикой разрешения таких проблем является 
задани блокировок. Существует два основных типа блокировок: с возможностью 
взаимной доступа (S-блокировка) и без возможности взаимного доступа 
(Х-блокировка). Есл] транзакция накладывает S-блокировку на некоторый объект, 
то другие транзакции так же могут накладывать на этот объект S-блокировку, но 
только не Х-блокировку. Есш транзакция накладывает Х-блокировку на некоторый 
объект, то никакая другая тран закция не может накладывать на этот объект 
никакой другой блокировки. Затем бы; введен протокол использования этих 
блокировок для устранения проблемы утраты результатов обновления и других 
возникающих проблем. Для этого S-блокировка накладывается на все извлекаемые 
объекты, Х-блокировка — на все обновляемые объекты, к все блокировки 
сохраняются до окончания выполнения транзакции. С помощью этого протокола 
можно добиться упорядочения выполнения транзакций. 
    Описанный протокол является более строгой (и более общей) формой протокола 
двухфазной блокировки. Можно показать с помощью теоремы двухфазной блокировки, 
что если все транзакции подчиняются этому протоколу, то все графики запуска 
допускают упорядочение. Из такого графика запуска следует, что если А и В 
являются двумя транзакциями данного графика, то либо транзакция А использует 
результаты выполнения транзакции В, либо транзакция В использует результаты 
выполнения транзакции А. К сожалению, применение протокола двухфазной 
блокировки может привести к возникновению тупиковых ситуаций. Для их 
разрешения следует выбрать одну из конфликтующих транзакций в качестве 
транзакции-жертвы для отмены ее выполнения. 
    Вообще нельзя гарантировать безопасность выполнения любого набора 
транзакций, который не полностью упорядочен. Однако в некоторых системах для 
повышения производительности и пропускной способности предусмотрено 
чередующееся выполнение нескольких транзакций на некотором уровне изоляции, 
что на самом деле является не совсем безопасным способом. В этой главе был 
описан один такой "небезопасный уровень", т.е. уровень стабильности курсора (с 
точки зрения терминологии, принятой в системе DB2, хотя в стандарте языка SQL 
есть аналогичный уровень READ COMMITTED). 
    Затем вкратце было рассмотрено понятие степени дробления блокировок и 
связанная с ним идея преднамеренной блокировки. Обычно перед наложением 
некоторой транзакцией блокировки определенного типа на некоторый объект, 
например на кортеж базы данных, прежде всего следует задать соответствующую 
преднамеренную блокировку, по крайней мере на "родительскую" часть этого 
объекта (т.е. в случае кортежа— на отношение, в котором этот кортеж 
содержится). На практике такие преднамеренные блокировки обычно задаются точно 
так же, как S- и Х-блокировки кортежей, т.е. неявным образом. Однако в 
разрабатываемой системе все же рекомендуется (в случае необходимости) 
предусмотреть утверждения типа LOCK для явного задания блокировок более 
сильных, чем заданные неявно. 
    Наконец, в этой главе было кратко описано управление параллелизмом на 
языке SQL. В стандарте языка SQL возможности явной блокировки не предусмотрены 
вовсе, однако в нем поддерживаются различные уровни изоляции — SERIALIZABLE, 
REPEATABLE READ, READ COMMITTED, READ UNCOMMITTED, которые в СУБД воплощаются 
с помощью скрытого от пользователя блокирования. 

    Упражнения 

    14.1. Дайте определение понятия способность к упорядочению. 
    14.2. Опишите протокол и теорему двухфазной блокировки. 
    14.3. Пусть даны транзакции 77, 72 и ТЗ, которые выполняют следующие операции: 
    Т1:  сложить 1 с А, 

    384	Часть IV. Защита данных 

    Т2: удвоить А, 
    ТЗ: вывести А на экран, а затем задать для А значение 1 
    (где А — это некоторый объект базы данных). 
    а) Допустим, что транзакции Т], Т2 и ТЗ выполняются параллельно. 
Перечислите все возможные результаты выполнения этих транзакций, если 
начальное значение А равно нулю. 
    б) Допустим, что транзакции 77, 72 и ТЗ имеют показанную ниже внутреннюю структуру. 
    Т1		Т2		ТЗ 
    R1:	Извлечь значение А в tl	R2:	Извлечь значение А в t2	R3:	Извлечь 
значение А в		t3 
    tl := tl + 1		t2 := tZ * 2		Вывести на 13	экран значение 
    U1:	Обновить А значением tl	U2:	Обновить Л значением t2	U3:	Обновить А	значением	1 
    Сколько возможных графиков запуска существует, если эти транзакции 
выполняются без каких-либо блокировок? 
    в) Существуют ли какие-либо чередующиеся графики запуска, которые для 
начального значения А (нуль) приводят к получению "корректного" результата, но 
не допускают упорядочения? 
    г) Существуют ли какие-либо графики запуска, которые действительно 
допускают упорядочение, но не могут быть реализованы, если все три транзакции 
подчиняются протоколу двухфазной блокировки? 
    14.4. Ниже приведена последовательность выполнения различных событий в 
графике запуска с транзакциями 77, 72, ..., 772 и объектами базы данных А, 
В,..., Н. 

    Время tO	........ 
    Извлечь А 
    Время tl         (Tl)	Извлечь А 
    Время t2          (T2)	Извлечь В 
    -	(Т1)	Извлечь С 
    -	(Т4)	Извлечь D 
    -	(15)	Извлечь А 
    -	(Т2)	Извлечь Е 
    -	(Т2)	Обновить ? 
    -	(ТЗ)	Извлечь F 
    -	(Т2)	Извлечь F 
    -	(Т5)	Обновить А 
    -	(Т1)	Завершить выполнение транзакции 
    -	(Т6)	Извлечь А 
    -	(Т5)	Отменить выполнение транзакции 
    -	(Те)	Извлечь С 
    -	(Т6)	Обновить С 
    -	(Т7)	Извлечь G 
    -	(Т8)	Извлечь Я 
    -	(Т9)	Извлечь G 
    -	(Т9)	Обновить G 
    -	<Т8)	Извлечь Е 

    Глава 14. Параллелизм 385 
    13 Введение в системы баз данных 


    (Т7) 
    (Т9) 
    (ТЗ) 
    (ПО) 
    (Т9) 
    (Т6) 
    (Till 
    (Т12) 
    (Т12) 
    (Т21 
    (Til) 
    (Т12) 
    Завершить выполнение транзакции 
    Извлечь н 
    Извлечь G 
    Извлечь А 
    Обновить Н 
    Завершить выполнение транзакции 
    Извлечь С 
    Извлечь D 
    Извлечь С 
    Обновить F 
    Обновить С 
    Извлечь А 
    —	(Т10)       Обновить А 
    —	(Т12)       Обновить D 
    —	(Т4)        Извлечь G 
    Время	tn           ........ 

    Предположим, что извлечение G означает (в случае успеха этой операции) 
наложение S-блокировки на объект G, а обновление G (в случае успеха этой 
операции) — задание Х-блокировки для объекта G. Допустим, что все блокировки 
сохраняются до конца выполнения транзакции. Возникнут ли тупиковые ситуации в 
момент времени tnl 
    14.5. Еще раз рассмотрим проблемы параллелизма, показанные на рис. 
14.1-14.4. Что произойдет в каждом из этих случаев, если все транзакции 
выполняются на уровне изоляции повторяемого чтения, а не на уровне 
стабильности курсора? 
    14.6. Дайте формальные и неформальные определения пяти типам блокировок: 
X, S, IX, IS, SIX. (Замечание. Формальные определения даются с помощью матриц совместимости.) 
    14.7. Сформулируйте понятие относительной силы блокировок и нарисуйте 
соответствующую диаграмму их приоритета. 
    14.8. Сформулируйте протокол преднамеренной блокировки, а также объясните 
основную цель этого протокола? 
    14.9. В стандарте языка SQL определяется три проблемы параллелизма: 
неаккуратное считывание, неповторяемое считывание и фиктивные элементы. Как 
они связаны с тремя проблемами параллелизма, описанными в начале этой главы 
(потери результатов обновления, незафиксированной зависимости, несовместимого анализа)? 

    Список литературы 

    Здесь следует также упомянуть работы [13.1, 13.9] и особенно [13.11] из 
главы 13. 
    14.1. Bayer R., Heller M., Reiser A. Parallelism and Recovery in Database 
Systems // ACM TODS. — 1980. — 5, № 2. 
    В работе описывается методика управления параллелизмом, называемая 
многовариантной блокировкой, а также многовариантным считыванием, которое 
используется в нескольких программных продуктах. Преимущество этой методики 
заключается в том, что операции считывания выполняются без вынужденного 
ожидания, т.е. любое количество операций считывания и одна операция записи 
могут выполняться с одним и тем же объектом одновременно. 

    386	Часть IV. Защита данных 

    Это преимущество особенно важно для распределенных систем (подробнее это 
еще будет обсуждаться далее в настоящей книге), где для обновлений может 
потребоваться значительное время, а потому выполнение запросов только для 
чтения может чрезмерно затянуться. Основную идею этой методики можно 
сформулировать следующим образом. 
    1.   Если транзакция 72 пытается выполнить операцию считывания объекта, 
для которого в данный момент выполняется обновление с помощью транзакции 77, 
то транзакции 72 предоставляется доступ к предварительному варианту этого 
объекта. Такой вариант обычно хранится в каком-то особом месте системы, как 
правило в файле регистрации, и предназначен для восстановления последнего 
состояния системы. 
    2.   Если транзакция 72 пытается выполнить операцию обновления объекта, 
для которого в данный момент выполняется считывание с помощью транзакции 77, 
то транзакции 72 предоставляется доступ к этому объекту, тогда как транзакции 
77 предоставляется доступ к некоторому варианту этого объекта (который в 
действительности является предварительным вариантом). 
    Конечно, в этой методике предусмотрены соответствующие элементы управления 
для того, чтобы каждая транзакция всегда имела дело с непротиворечивым 
состоянием базы данных. 
    14.2. Bernstein P.A., Goodman N. Timestamp-Based Algorithms for 
Concurrency Control in Distributed Database Systems // Proc. 6th Intern. Conf. 
on Very Large Data Bases. — Montreal, Canada, 1980. 
    В работе рассматриваются некоторые методики управления параллелизмом, в 
основу которых положена не блокировка, а следующая идея: если транзакция А 
начинает выполнение некоторых операций раньше транзакции В, то система 
предполагает, что выполнение транзакции А полностью завершилось перед началом 
выполнения транзакции В (как это организовано в последовательном графике 
запуска). Таким образом, для транзакции А становятся недоступными никакие 
обновления, выполняемые транзакцией В, а также она не сможет выполнить 
обновления с объектами, которые считываются транзакцией В. Для некоторого 
запроса базы данных такое управление может быть организовано следующим 
образом. Система сравнивает временные метки транзакции запроса и транзакции, 
выполнившей последнее извлечение или обновление запрашиваемого кортежа. В 
случае конфликта транзакция запроса может быть запущена опять с новой 
временной меткой (так же как и в случае с оптимистическими методами [14.11]). 
    Как следует из заголовка этой работы, данная методика была изначально 
создана в контексте распределенной системы (где использование блокировки 
сопряжено с возникновением нежелательных накладных расходов из-за посылки 
сообщений с проверкой и установкой блокировок). Однако такая методика почти 
наверняка не годится для нераспределенных систем. Кроме того, существует 
достаточно скептическое отношение к практичности использования этой методики 
даже для распределенных систем. Одной очевидной проблемой является то, что 
каждый кортеж должен содержать временную метку последней транзакции, которая 
извлекала данные из этого кортежа (а также временную метку последней 
транзакции, которая обновляла данные этого кортежа). В таком случае 
подразумевается, что каждая операция чтения становится операцией записи! 
Действительно, Грей (Gray) в [13.11] заявляет, что такая схема на самом деле 
является частным случаем схем оптимистического метода управления параллелизмом 
[14.11], для которых, в свою очередь, характерны собственные проблемы. 
    14.3. Blasgen M.W., Gray J.N., Mitoma M., Price T.G. The Convoy Phenomenon 
// ACM Operating Systems Review. — 1979. — 13, № 2. 

    Глава 14. Параллелизм	387 

    Проблема образования процессий встречается при использовании блокиро вок в 
ситуациях с интенсивным обменом данными. Например, такая блоки ровка нужна для 
выполнения операций записи в файл регистрации в система; с приоритетным планированием. 
    Замечание. Понятие "планирования" здесь относится к проблеме распределения 
машинных циклов для выполнения транзакций, а не для чередующихс; операций, 
принадлежащих различным транзакциям, как это уже обсуждалось ранее в этой главе. 
    Эта проблема может быть описана следующим образом. Пусть транзакция 7 
задает блокировку при интенсивном обмене данными и приоритет этой блокировки 
подавляется системным планированием, т.е. транзакция переходит в состояние 
ожидания, например из-за того, что время ее выполнения было просрочено. В 
таком случае образуется процессия транзакций, ожидающих своего выполнения 
из-за блокировки интенсивного обмена данными. Когда транзакция Г выходит из 
состояния ожидания, блокировка снимается. Однако именно из-за того, что 
блокировка накладывается на интенсивный обмен данными, транзакция Т сама, 
вероятно, вновь присоединится к процессии, прежде чем следующая транзакция 
окончит свою работу с данным источником. Поэтому такая транзакция не сможет 
продолжить выполнение своих операций и перейдет в состояние ожидания. 
    Суть проблемы заключается в том, что в большинстве случаев (но не во всех) 
планирование является частью базовой операционной системы, а не СУБД, а потому 
оно спроектировано для других параметров производительности. По наблюдениям 
авторов этой работы, однажды образованная процессия является стабильной. Таким 
образом, система находится в состоянии "переполнения блокировками", а 
большинство машинных циклов посвящается обработке переключений, а не 
выполнению какой-то полезной работы. В качестве возможного решения этой 
проблемы, за исключением замены способа планирования, можно предложить задание 
блокировок в произвольном порядке, а не на основе схемы "первым поступил — 
первым обработан". 
    14.4. Date C.J. Concurrency // С. J. Date. An Introduction to Database 
Systems: Volume II. — Reading. Mass.: Addison-Wesley, 1983. 
    Некоторые части данной главы основаны на этом раннем вводном курсе. 
    14.5. Eswaran К.P., Gray J.N., Lorie R.A., Traiger I.L. The Notions of 
Consistency and Predicate Locks in a Data Base System // CACM. — 1976. — 19, № 11. 
    Здесь впервые предложено строгое теоретическое описание основ управления параллелизмом. 
    14.6. Franaszek P., Robinson J.T. Limitations on Concurrency in 
Transaction Processing //ACM TODS. — 1985.— 10, № 1. 
    Смотрите комментарий к [14.11], 
    14.7. Franaszek P.,  Robinson J.T.,  Thomasian A.  Concurrency Control  
for High Contention Environments // Ibid. — 1992. — 17, № 2. 
    В статье делается заявление, что, вероятно, в будущем по разным причинам 
системы обработки транзакций будут обладать гораздо большей степенью 
параллелизма, чем современные системы. Поэтому в таких системах будут гораздо 
чаще возникать конфликтные ситуации на уровне данных. Затем авторы 
представляют "несколько концепций управления параллелизмом [без блокировок] и 
методики планирования транзакций, которые применимы к средам с большим 
количеством конфликтных ситуаций". Преимущества такого подхода подтверждается 
экспериментами с различными имитационными моделями. 

    388	Часть IV. Защита данных 

    14.8. Gray J.N., Lorie R.A., Putzolu G.R. Granularity of Locks in a Large 
Shared Data Base // Proc. 1st Intern. Conf. on Very Large Data Bases. — 
Framingham, Mass., 1975. 
    В статье впервые описана концепция преднамеренной блокировки. Как 
объясняется в этой главе, понятие "степень дробления блокировок" относится к 
размеру блокируемых объектов. Поскольку разные транзакции, очевидно, имеют 
разные характеристики и требования, желательно, чтобы в системе существовал 
целый набор различных степеней дробления (что в принципе реализовано во многих 
системах). В этой статье представлена методика воплощения нескольких степеней 
дробления блокировок на основе преднамеренной блокировки. 
    Поскольку в данной главе было дано весьма упрощенное описание протокола 
преднамеренной блокировки, ниже он будет описан несколько подробнее. 
Во-первых, стоит отметить, что блокируемыми объектами могут быть не только 
отношения и кортежи, как предполагалось прежде. Во-вторых, типы блокируемых 
объектов могут в общем случае не обладать строгой иерархической структурой. 
Присутствие индексов или других структур доступа будет лишь означать, что их 
следует рассматривать как направленную ациклическую диаграмму. Например, база 
данных поставщиков и товаров может содержать как (хранимое) отношение товаров 
Р, так и индекс, например ХР, основанный на атрибуте #Р этого отношения. Для 
получения кортежей отношения Р следует запустить всю базу данных целиком, а 
затем либо перейти непосредственно к этому отношению и выполнить 
последовательный поиск, либо использовать индекс ХР для перехода к искомым 
кортежам отношения Р. Таким образом, кортежи отношения Р имеют два 
"родительских" объекта на этой диаграм ме — Р и ХР, для которых "родительским" 
объектом является база данных. 
    Теперь формулировку этого протокола можно представить в обобщенной форме. 
    • При задании Х-блокировки для данного объекта неявным образом задается 
Х-блокировка для всех дочерних объектов этого объекта. 
    " При задании S- или SIX-блокировки для данного объекта неявным образом 
задается S-блокировка для всех дочерних объектов этого объекта. 
    • Прежде чем транзакция наложит S- или IS-блокировку на заданный объект, 
она должна задать IS-блокировку (или более сильную) по крайней мере для одного 
родительского объекта этого объекта. 
    • Прежде чем транзакция наложит S-, IX- или SIX-блокировку на заданный 
объект, она должна задать IX-блокировку (или более сильную) для всех 
родительских объектов этого объекта. 
    • Прежде чем для данной транзакции будет отменена блокировка для данного 
объекта, должны быть отменены все блокировки для дочерних объектов данного объекта. 
    При практическом воплощении этот протокол не сопровождается большими 
накладными расходами, как это могло показаться, поскольку в некоторый момент 
времени транзакция уже обладает почти всеми необходимыми блокировками. 
Например, IX-блокировка, вероятно, будет задана сразу для всей базы данных во 
время инициализации программы. Эта блокировка будет удерживаться для всех 
транзакций, выполняемых на протяжении всей работы программы. 
    14.9. Gray J.N., Lorie R.A., Putzolu G.R., Traiger I.L. Granularity of 
Locks and Degrees of Consistency in a Shared Data Base // Proc. IFIP TC-2 
Working Conf. on Modeling in Data Base Management Systems (ed. G. M. Nijssen). 
— Amsterdam, Netherlands: North-Holland; New York, N.Y.: Elsevier Science, 1976. 

    Глава 14. Параллелизм	389 

    В статье впервые введено понятие уровня изоляции (под названием "сте непротиворечивости"). 
    14.10. Harder Т., Rothermel К. Concurrency Control Issues in Nested 
Transactions / VLDB Journal. — 1993. — 2, № 1. 
    Как уже объяснялось в главе 13, несколькими различными авторами ( 
предложена идея вложенных транзакций. В этой статье предлагается с ветствующий 
набор протоколов блокировки для таких транзакций. 
    14.11.Kung Н.Т., Robinson J.T. On Optimistic Methods for Concurrency Contr 
ACM TODS. — 1981. — 6, № 2. 
    Схемы блокировки рассматриваются как пессимистические в случае, к< 
делается предположение (худшее из возможных) о том, что все данные, н< ходимые 
для заданной транзакции, могут также потребоваться для параллел выполняемой 
транзакции, а поэтому их следует заблокировать. В оптимис ческих схемах, 
наоборот, делается противоположное допущение о том, что кие конфликтные 
ситуации маловероятны. Поэтому в таких схемах допускае беспрепятственное 
выполнение транзакций. И только после полного завер! ния всех операций 
проводится проверка наличия конфликтных ситуаций. Е< такие конфликты имели 
место, то вызвавшие их транзакции запускаются сно Никакие обновления не 
записываются в базу данных до успешного завершеь выполнения всех операций, 
поэтому при повторном запуске транзакций не г требуется отменять никаких 
операций обновления. 
    В [14.6] впоследствии было показано, что при некоторых разумных предп 
ложениях, оптимистические методы демонстрируют некоторые присущие i 
преимущества по сравнению с традиционными методами блокировки для н которого 
уровня параллелизма (т.е. некоторого числа одновременно выпо. няемых 
транзакций), который они могут поддерживать. Предполагается, 41 
оптимистические методы могут быть полезны для работы в системах с бол] шим 
количеством параллельных процессоров. (В [13.11], наоборот, yreef ждается, что 
оптимистические методы в общем случае на самом деле хуж методов блокировки в 
некоторых "горячих" ситуациях, т.е. ситуациях, когд объект данных обновляется 
очень часто и несколькими различными транзак циями. Более подробную информацию 
о методах, эффективных при работе i горячих ситуациях, можно получить в [14.12].) 
    14.12. O'NeilP.E. The Escrow Transactional Method // Ibid.— 1986. — 11, №4. 
    Рассмотрим следующий весьма простой пример. Предположим, что база данных 
содержит объект данных ТС, представляющий "имеющуюся на руках наличность", и 
допустим, что почти каждая транзакция в системе обновляет данные в объекте ГС 
с некоторым уменьшением их значения (соответствующим некоторому текущему 
платежу). Объект ТС представляет собой пример горячей ситуации, т.е. объект 
базы данных, который используется большинством транзакций системы. Образно 
говоря, при традиционной блокировке горячая ситуация может очень быстро 
привести к затору, а потому было бы весьма пагубно использовать традиционную 
блокировку в таком случае. Если начальное значение ТС равно 10 миллионам 
долларов, а каждая отдельная транзакция приводит к ее уменьшению (в среднем) 
на 10 долларов, то в целом может быть выполнено около миллиона таких 
транзакций. Причем для этого потребовалось бы выполнить в произвольном порядке 
около .миллиона операций вычитания. В таком случае, действительно, вовсе нет 
необходимости в использ овании традиционной блокировки для ГС. Вместо этого 
достаточно убедиться в том, что текущее значение довольно велико для успешного 
выполнения данной операции вычитания, а затем выполнить обновление значения. 
(Если выполнение такой транзакции не будет успешно завершено, то последнюю 
операцию вычитания следует отменить.) 

    390	Часть IV. Защита данных 

    Метод трехстороннего соглашения применяется в ситуациях, подобных 
описанной выше, т.е. когда обновления имеют не произвольную форму, а некоторую 
особую. В такой системе должен быть задан особый вид утверждения обновления 
(например, "уменьшить на х тогда и только тогда, когда текущее значение больше 
чем х"). Тогда обновление можно выполнить, уменьшая на х некоторый третий 
объект, таким образом после выполнения транзакции полученное значение можно 
извлечь из третьего объекта (возвращая уменьшенное значение, если транзакция 
успешно завершается, или исходное значение, если выполнение транзакции было отменено). 
    В статье описывается несколько случаев, в которых можно использовать метод 
трехстороннего соглашения. Одним из примеров коммерческого продукта, в котором 
поддерживается эта методика, является информационная система IMS Fast Path 
фирмы IBM. Следует отметить, что эта методика может рассматриваться как особый 
случай оптимистического управления параллелизмом [14.11] (обратите внимание, 
однако, что именно эта "особенность", т.е. применение специальных утверждений 
обновления, является чрезвычайно критическим условием). 
    14.13. Papadimitriou С. The Theory of Database Concurrency Control.— 
Rockville, Md.: Computer Science Press, 1986. 
    Учебное пособие, в котором особое внимание уделяется формальной теории. 
    Ответы к некоторым упражнениям 
    14.3. а) Существует три корректных результата, соответствующих шести 
возможным последовательным графикам запуска: 
    А	=	О 
    А	=	1 
    А	=	2 
    А	=	1 
    А	=	2 
    А	=	4 
    А	=	3 
    Начальное значение 
    Т1-Т2-ТЗ 
    Т1-ТЗ-Т2 
    Т2-Т1-ТЗ 
    Т2-ТЗ-Т1 
    ТЗ-Т1-Т2 
    ТЗ-Т2-Т1 
    Конечно, не все шесть полученных результатов отличаются. Фактически, в 
данном примере так получилось потому, что благодаря смыслу транзакции ТЗ 
возможные правильные результаты независимы от начального состояния базы данных. 
    б) Существует 90 возможных различных графиков запуска, которые можно 
представить в приведенном ниже символическом виде. (Здесь Ri, Rj, Rk 
обозначают операции извлечения Rl, R2, R3, причем не обязательно в той же 
последовательности. Аналогично, Up, Uq, Ur обозначают операции обновления UJ, 
U2, U3, также не обязательно в той же последовательности.) 
    Ri-Rj-Rk-Up-Uq-Ur : 3*2*1*3*2*1 =	36 вариантов 
    Ri-Rj-lp-Rk-Uq-Ur : 3*2*2*1*2*1 =	24 вариантов 
    Ri-Rj-Lp-Uj-Rk-Ur : 3*2*2*1*1*1 =	12 вариантов 
    Ri-Up-Rj-Rk-Uq-Ur =3*1*2*1*2*1 =	12 вариантов 
    Ri-lp-Rj-Uq-Rk-Ur =3*1*2*1*1*1=	6 вариантов 
    Всего =	90 вариантов 
    в) Да. Например, график запуска RJ-R2-R3-U3-U2-U] приводит к тому же 
результату (единица) для заданного начального значения (нуль), как и два из 
шести возможных последовательных графиков запуска. (Упражнение. 

    Глава 14. Параллелизм 391 

Проверьте это утверждение.) Однако следует понимать, что "корректность" 
полученного результата является всего лишь счастливой случайностью и 
следствием того, что исходное значение было равно 0, а не какому-то другому 
значению. В качестве примера обратной ситуации рассмотрите случай, в котором 
исходное значение равно 10. Будет ли показанный выше график запуска приводить 
к одному из действительно корректных результатов? (Какие в этом случае будут 
действительно корректные результаты?) Если нет, то график запуска 
R1-R2-R3-U3-U2-U1 не допускает упорядочения. 
    г) Да. Например, график запуска R1-R3-U1-U3-R2-U2 допускает упорядочение 
(он эквивалентен последовательному графику запуска Т1-Т2-ТЗ), но не может быть 
получен, если Т], 72 и ТЗ подчиняются двухфазному протоколу блокировки. В 
таком случае для выполнения операции R3 потребуется с согласия транзакции ТЗ 
задать S-блокировку для А. Тогда операция UI в транзакции 77 не будет 
выполняться до тех пор, пока не будет снята блокировка, а это не произойдет до 
завершения выполнения транзакции ТЗ (действительно, при достижении операции Ш 
транзакции ТЗ и 77 попадут в тупиковую ситуацию). 
    Это упражнение прекрасно иллюстрирует следующий очень важный момент. Пусть 
для данного набора транзакций и начального состояния базы данных задано 
множество всех возможных графиков запуска (ВСЕ), содержащих эти транзакции, 
множество всех графиков запуска (ПРАВИЛЬНЫЕ), которые гарантированно приводят 
к корректному финальному состоянию или, по крайней мере, могут привести к нему 
для некоторого начального состояния, множество всех способных к упорядочению 
графиков запуска (ДОПУСКАЮЩИЕ УПОРЯДОЧЕНИЕ), а также множество всех графиков 
запуска (РЕЗУЛЬТАТИВНЫЕ), которые приводят к корректному результату согласно 
двухфазному протоколу блокировки. Тогда вообще будет верно следующее 
утверждение (здесь знак "<" обозначает "подмножество"): 
    РЕЗУЛЬТАТИВНЫЕ < ДОПУСКАКШИЕ УПОРЯДОЧЕНИЕ < ПРАВИЛЬНЫЕ < ВСЕ 
    14.4. В момент времени tn ни одна из транзакций вовсе не выполнит никакой 
полезной работы! Дело в том, что будет существовать одна тупиковая ситуация, 
включающая транзакции 72, ТЗ, Т9 и Т8. Кроме того, транзакция Т4 находится в 
состоянии ожидания (ожидает) завершения выполнения транзакции 79, транзакция 
Т12 ожидает завершения выполнения транзакции Т4, а транзакции Т10 и Т11 
ожидают завершения выполнения транзакции Т12. Эту ситуацию можно представить с 
помощью приведенной на рис. 14.14 диаграммы состояний ожидания, в которой узлы 
представляют собой транзакции, а стрелка от узла 77 к узлу Tj указывает на то, 
что транзакция 77 находится в состоянии ожидания завершения выполнения 
транзакции Tj. Возле стрелок размещены названия объектов базы данных с 
указанием в скобках уровня блокировки, на котором они находятся в состоянии ожидания. 

    ТЮ 
    А  ( X  ) 
    С  ( X ) 

    Рис. 14.14, Диаграмма состояний ожидания для упр. 14.4 


    392 Часть IV. Защита данных 

    14.5. Для задач, приведенных на рис. 14.1-14.3, уровень изоляции 
стабильности курсора обладает тем же эффектом, что и уровень повторяемого 
считывания (обратите внимание, однако, что для системы DB2 это утверждение не 
применимо к уровню стабильности курсора из-за того, что в системе DB2 вместо 
S-блокировок используются U-блокировки). Что касается проблемы несовместимого 
анализа (см. рис. 14.4), то уровень изоляции стабильности курсора не позволяет 
разрешить эту проблему. Дело в том, что транзакция А должна выполняться на 
уровне повторяемости считывания для того, чтобы сохранить все блокировки до 
завершения выполнения транзакции, иначе будет получен неверный результат. 
(Конечно, если система поддерживает такой режим, то в качестве альтернативного 
варианта можно было бы с помощью транзакции А полностью заблокировать все 
отношение счетов с помощью некоторой явно заданной блокировки. Это решение 
можно было бы использовать для уровней изоляции стабильности курсора и 
повторяемости считывания .) 
    14.9. В этой главе были рассмотрены три проблемы параллелизма, а именно: 
проблемы потери результатов обновления, незафиксированной зависимости и 
несовместимого анализа. 
    • Потеря результатов обновления. Согласно стандарту языка SQL требуется, 
чтобы (при любых обстоятельствах) никогда не возникала проблема потери 
результатов обновления. 
    • Незафиксированная зависимость. Это всего лишь иное название проблемы 
неаккуратного считывания. 
    • Несовместимый анализ. Этим термином обозначаются как проблема 
неповторяемого считывания, так и проблема фиктивных элементов. 

    Глава 14. Параллелизм	393 

