Содержание к диссертации
Введение
1. Методы и средства бесконфликтного доступа многопоточных приложений к памяти 17
1.1. Гонки по данным и последствия их возникновения 17
1.2. Задача взаимного исключения 23
1.3. Решение задачи взаимного исключения для мультипроцессоров 25
1.4. Решение задачи взаимного исключения для мультикомпьютеров 28
1.4.1. Причинно-следственное отношение частичного порядка и логические часы Лэмпорта 30
1.4.2. Алгоритмы распределенного взаимного исключения на основе разрешений 32
1.4.3. Алгоритмы распределенного взаимного исключения на основе токенов 35
1.5. Неблокирующие методы бесконфликтного доступа к памяти 37
1.6. Транзакционные методы бесконфликтного доступа многопоточных приложений к памяти 40
1.6.1. Основы транзакционной обработки данных 41
1.6.2. Транзакционная память и ее отличие от транзакций баз данных 48
1.6.3. Свойства алгоритмов транзакционной памяти 52
1.6.4. Подходы к реализации транзакционной памяти для мультипроцессоров 55
1.6.5. Распределенная программная транзакционная память
1.7. Принципы организации доступа многопоточных приложений к распределенной памяти кластерных МВС с помощью транзакций 62
1.8. Выводы 64
2. Разработка метода обнаружения rw-конфликтов по данным и протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС 67
2.1. Разработка математической модели системы 67
2.2. Разработка метода обнаружения RW-конфликтов по данным при доступе к распределенной памяти 75
2.3. Разработка протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС 82
2.4. Обоснование корректности протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС 90
2.5. Оценка сложности протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС 98
2.6. Выводы 104
3. Практическая реализация и экспериментальная апробация протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС 105
3.1. Структура и компоненты программного комплекса DSTM P1 107
3.2. Прикладной интерфейс программирования DSTM P1 116
3.3. Подсистема управления памятью и модуль портации на кластерные МВС 122
3.4. Выбор приложений и аналога для экспериментального сравнения 125
3.5. Реализация и экспериментальные исследования приложения “Банк” 128
3.6. Реализация и экспериментальные исследования приложения “Список” 134
3.7. Реализация и экспериментальные исследования приложения “Дерево” 141
3.8. Выводы 148
Заключение 149
Список использованных источников
- Решение задачи взаимного исключения для мультикомпьютеров
- Принципы организации доступа многопоточных приложений к распределенной памяти кластерных МВС с помощью транзакций
- Разработка протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС
- Выбор приложений и аналога для экспериментального сравнения
Решение задачи взаимного исключения для мультикомпьютеров
Наличие гонок в многопоточной программе может привести к недетерминированному и, возможно, некорректному поведению программы с вероятными ошибками времени выполнения.
Будем определять корректность как свойство программы, которое характеризует безошибочность ее работы: будем считать, что алгоритм такой про граммы не содержит ошибок; при выполнении корректной программы отсутствуют ошибки времени выполнения (такие как “деление на ноль”) и ошибки, связанные с доступом к памяти (например, выход за границы массива); само выполнение корректной программы завершается за конечное число шагов (отсутствуют бесконечные циклы).
Детерминированность — свойство программы, которое характеризует воспроизводимость результатов ее работы: результат работы недетерминированной программы может отличаться от запуска к запуску при одних и тех же входных данных. Детерминированная программа в некоторых случаях может быть некорректной, а недетерминированная — корректной и удовлетворяющей требованиям разработчика. В своей работе [17] Emrath и Padua охарактеризовали четыре уровня недетерминизма параллельных программ:
1) внутренний детерминизм (англ. internally determinate) — в программе, обладающей данным свойством, для каждого потока последовательность инструкций и значение их операндов всегда детерминированны, т.е. отсутствуют условия гонок, а результат работы программы при запуске с одними и теми же данными всегда одинаков. Пример внутренне детерминированной программы представлен на рис. 1.1, а. В данной программе отсутствует зависимость между итерациями цикла, выполняемыми разными OpenMP-потоками — отсутствуют условия гонок, а результат программы детерминирован и не меняется от запуска к запуску;
2) внешний детерминизм (англ. externally determinate) — программа называется внешне детерминированной, если результат ее работы детерминирован, но она не обладает свойством внутреннего детерминизма. В такой программе могут существовать гонки, однако результат ее работы при запуске с одними и теми же данными всегда одинаков. Наиболее типичный пример внешне детерминированной программы — программа, в которой над общими данными производятся коммутативные и ассоциа-18 тивные операции (рис. 1.1, б);
3) ассоциативный недетерминизм (англ. associatively non-determinate) — в ассоциативно недетерминированной программе существуют гонки между ассоциативными операциями, выполняемыми конкурирующими потоками над операндами с плавающей точкой. В силу конечности разрядной сетки для представления операндов с плавающей точкой результат программы может быть недетерминирован, т.е. такая программа является внешне недетерминированной только из-за возможных ошибок округления (пример на рис. 1.1, в);
4) полный недетерминизм (англ. completely non-determinate) — программа, которую нельзя отнести ни к одному из первых трех уровней недетерминизма, является полностью недетерминированной. Результат работы таких программ недетерминирован, и диапазон значений результирующих переменных зависит не от самих операций, выполняемых потоками над общими данными, а от времени их выполнения (рис. 1.1, г).
Различают условия гонок двух видов [9]:
1) общие гонки (англ. general races) — являются причиной недетерминированного выполнения разработанной ожидаемо детерминированной программы, что может, но не обязательно, приводить к ошибкам времени выполнения, т.е. некорректному поведению программы;
2) гонки по данным (англ. data races) — возникают в результате нарушения условия неделимости (атомарности) выполнения критических секций (КС) — участков кода, в которых происходит доступ к разделяемым данным, и зачастую являются причиной некорректного выполнения разработанной ожидаемо недетерминированной программы.
Условия гонок, о которых говорится в классификации Emrath и Padua, относятся к типу общих гонок. Однако можно расширить данную классификацию, разделив класс полностью недетерминированных программ на два под-19
Как можно увидеть, изначально корректная последовательно выполняе мая программа при параллельном выполнении ее частей может стать некорректной из-за наличия гонок, которые являются причиной конфликтов по данным. Гонки возникают при параллельном доступе к данным нескольких потоков одновременно и на чтение, и на запись. В такой ситуации возможно чтение любым потоком программы значений переменных, не согласованных со значениями других используемых (как правило, ранее считанных) переменных. Можно сказать, что в случае наличия гонок по данным потоки программы могут получить доступ к памяти с несогласованным состоянием или к несогласованному слепку/снапшоту (англ. snapshot) [18] памяти. Чтение такого состояния памяти называют несогласованным чтением (англ. inconsistent read). К примеру, поток программы может вычислять арифметическое выражение вида 1/(y-x) в предположении, что всегда выполняется y = x. Тогда при наличии ситуации гонок возможно несогласованное чтение, при котором y будет равен x, что приведет к ошибке времени выполнения, т.е. некорректному выполнению (см. пример на рис. 1.2).
Принципы организации доступа многопоточных приложений к распределенной памяти кластерных МВС с помощью транзакций
Задача взаимного исключения в классическом виде впервые была сформулирована и решена (приведено решение математика Деккера) в работе голландского математика Дейкстры [11]. Формальная постановка задачи выглядит следующим образом [21].
Предположим, что в ВС есть N 2 процессов, выполняющих некоторую последовательность программных инструкций в бесконечном цикле. Выполняемые инструкции разделяются на четыре непрерывных блока кода: код, не требующий синхронизации, КС, вход в КС, выход из КС. Каждый процесс начинает свое выполнение с блока кода, не требующего синхронизации. В некоторый момент времени процессу может потребоваться выполнить инструкции из блока критической секции. Перед этим ему необходимо войти в КС, выполнив инструкции блока входа в КС, тем самым обеспечив себе эксклюзивное право выполнения инструкций КС. По завершении КС процесс выполняет инструкции выхода из нее, тем самым оповещая другие процессы о возможности получения доступа к КС. После выхода из КС процесс продолжает выполнять код, не требующий синхронизации. Задача взаимного исключения состоит в разработке кода для блоков входа в КС и выхода из КС таким образом, чтобы были удовлетворены следующие два основных требования:
1) взаимное исключение (англ. mutual exclusion) — свойство безопасности, которое гарантирует, что никакие два процесса не могут одновременно находиться внутри КС;
2) отсутствие мертвой блокировки (англ. deadlock-freedom) — свойство живости, подразумевающее, что если один процесс пытается войти в КС, то некоторый процесс, не обязательно тот же самый, рано или поздно войдет в свою КС.
Условие отсутствия мертвой блокировки предоставляет гарантию прогресса всей системы в целом, однако оно допускает ситуацию “голодания” отдельных процессов, которые периодически и безуспешно пытаются войти в КС. Более строгое условие гарантии прогресса — условие отсутствия “голодания” процессов — если один процесс пытается войти в КС, то этот процесс рано или поздно обязательно войдет в свою КС. Кроме перечисленных условий решение задачи взаимного исключения может гарантировать определенную справедливость порядка выполнения КС процессами. Примером справедливого условия может служить условие “первый зашел-первым обслужен” или FIFO (англ. first-in-first-out) — ни один процесс не может войти в КС до процесса, уже ожидающего своей очереди на вход в КС.
Изначально проблема взаимного исключения ставилась [11] для систем с общей памятью, в которых есть возможность применения атомарных на аппаратном уровне операций чтения/записи. В настоящее время существует большое количество методов и средств решения данной задачи как для мультипроцессорных, так и для мультикомпьютерных систем.
Методы бесконфликтного доступа к памяти, которые решают задачу взаимного исключения, основаны на понятии блокировки или исключающего пра-24
ва. Попытка захвата блокировки осуществляется при входе в КС, а освобождение — при выходе из КС. При неуспешной попытке захвата процесс останавливается и помещается операционной системой в очередь ожидания блокировки. Обладание таким исключающим правом означает для процесса возможность исполнения КС. Популярность данного подхода обосновывается относительной простотой использования средств синхронизации на основе блокировок при программировании и наличием достаточно эффективных реализаций блокировок.
Ранние решения задачи взаимного исключения для систем с общей памятью были алгоритмическими (необходима была лишь поддержка неделимости операций чтения/записи регистров памяти) и использовали схему активного ожидания. При данной схеме процесс постоянно считывает значение одной или нескольких переменных-флагов. Значение такой переменной или набора переменных говорит о возможности доступа к разделяемому ресурсу, т.е. о возможности выполнения КС. Алгоритм Деккера — первый корректный алгоритм (фактически изложенный в работе Дейкстры [11]), решающий задачу взаимного исключения и использующий активное ожидание. Алгоритм Декке-ра разработан для двух процессов и основан на строгом чередовании: выполнение КС разрешается только одному из двух процессов в зависимости от того, чья сейчас очередь. Реализуется алгоритм с помощью трех общих переменных-флагов, две из которых указывают на намерение одного из двух процессов войти в КС, а третья показывает, чья сейчас очередь. Очень похожий на решение Деккера, но более изящный алгоритм был предложен Петерсо-ном [22]. Оба оригинальных алгоритма (Деккера и Петерсона) разрабатывались для двух процессов. Решение для большего и заранее неопределенно го количества процессов было впервые предложено Лэмпортом (Lamport). В его алгоритме, который называется алгоритмом булочной [23], по аналогии с различными системами обслуживания, процесс является клиентом. Каждый клиент обслуживается (процессу предоставляется доступ к КС) на основании полученного им ранее “талончика”, т.е. некоторого уникального числового идентификатора. Однако в силу особенностей традиционной аппаратной архитектуры ВС (невозможности атомарно выполнять несколько операций чтения/записи подряд) несколько процессов могут получить талончики с одинаковыми номерами. Для разрешения данного конфликта используется приоритет процесса, его номер: чем меньше номер процесса, тем выше его приоритет. Недостатком описанных алгоритмов является использование активного ожидания, что влечет за собой бесполезное использование процессорных ресурсов и пропускной способности шины памяти.
Избежать недостатков программных решений задачи взаимного исключения, позволяет аппаратная поддержка со стороны вычислительной системы. В первую очередь, это использование запрета/разрешения прерываний и специальные атомарные операции. При использовании запрета/разрешения прерываний процесс при входе в КС специальной инструкцией запрещает прерывания, а при выходе из КС — вновь разрешает прерывания. Взаимное исключение достигается за счет того, что в КС никто не сможет прервать процесс, соответственно диспетчер операционной системы не может назначить на выполнение другой конкурентный процесс. У данного метода несколько недостатков; основной — его можно использовать только на однопроцессорной системе.
Разработка протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС
В настоящее время актуальными являются исследования возможностей и преимуществ применения механизмов транзакционной памяти для масштабируемых вычислительных систем с распределенной памятью, в первую очередь для кластерных МВС. В силу своих особенностей ТП может оказаться более эффективным и масштабируемым по сравнению с традиционными решениями на основе алгоритмов распределенного взаимного исключения (см. параграф 1.4) подходом к синхронизации в таких системах, что уже подтверждает ряд имеющиеся исследований [85–87]. При этом основной интерес для исследований представляют оптимистичные подходы к реализации механизмов ТП.
Как следует из рассмотрения особенностей алгоритмов ТП и их программных реализаций в предыдущих параграфах, одним из самых важных вопросов помимо выбора стратегии обнаружения и разрешения конфликтов (см. параграф 1.6.2) является реализация метода обнаружения конфликтов. При использовании отложенной стратегии обновления данных существует необходимость в обнаружении только RW-конфликтов, т.к. для записи используется промежуточный буфер (WR-конфликты невозможны), а сама память изменяется только в момент фиксации транзакции. Возникающие при этом “отложенные” WW-конфликты зачастую разрешаются на основе правила “первая фиксация побеждает” (англ. first committer wins, FCW): в момент фиксации транзакция проверяет свои перезаписываемые данные на наличие обновлений, сделанных конкурентными транзакциями, и, при обнаружении таких обновлений, откатывается. Для оптимистичных механизмов (см. параграф 1.6.1) основной процедурой методов обнаружения конфликтов является валидация (проверка) множества считанных значений Rset. Но момент времени, определяющий как и когда данную процедуру использовать, зависит от ре ализуемого для отслеживания конкурентных обновлений разделяемых данных подхода. Описанные в предыдущем параграфе подходы, которые применяются в алгоритмах для мультипроцессорных систем, нельзя напрямую использовать для мультикомпьютерной или распределенной транзакционной памяти, РТП (англ. distributed software transactional memory, DSTM). Подход на основе версионных блокировок с локальными версиями требует для выполнения критерия бесконфликтности либо инкрементальной валидации (после каждого чтения значения из памяти), что затратно для мультипроцессорных алгоритмов ТП, а для РТП и вовсе неприемлем (из-за больших накладных сетевых расходов), либо использования видимых для других транзакций чтений, что также затратно и практически не применяется [79].
Подход на основе глобальных синхронизируемых часов также ограничен в применении для РТП в силу описанных в параграфе 1.4 возможных проблем. В работе [86] был предложен метод обнаружения RW-конфликтов с использованием версий для данных и валидации множества Rset путем отслеживания причинно-следственного порядка между операцией чтения транзакции и операциями записи остальных транзакций системы. Для этого авторы предложили специального вида логические часы, реализованные в виде целочисленного счетчика:
Сам метод обнаружения конфликтов, названный методом продвижения транзакции (англ. transaction forwarding), заключается в следующем: - при старте транзакция Tt, выполняемая на узле Nk, считывает текущее значение часов Q и сохраняет его в переменной wv; - транзакция Tt продвигает свое стартовое время wv до значения wv wv, т.е. делает присваивание wv = wv только в случае успешной вали-дации Rset: для всех объектов в Rset их текущая версия сравнивается с wv и если версия какого-либо объекта превышает wv, то валидация заканчивается неуспешно, а транзакция откатывается; - для чтения удаленного объекта транзакция Tt посылает сообщение-запрос на узел расположения объекта Nm; при получении ответного сообщения q к посланному ранее сообщению-запросу с текущей версией объекта транзакции необходимо продвинуть свое стартовое время wv до значения tq в случае, если wv tq (см. выражение (1.6) для логических часов); если же wv tq, то объект может быть считан безопасно; - при чтении локального объекта, расположенного на узле выполнения транзакции, его версия проверяется и, если она больше, чем wv, то транзакция откатывается; - в момент фиксации транзакция наращивает часы Q (см. выражение (1.5)) и назначает новую версию для всех перезаписываемых объектов, равную значению только что увеличенных часов С к.
На базе предложенного метода авторами разработан алгоритм TFA, который по производительности превосходит все существующие конкурентные решения [86] и, как заявлено авторами, соответствуют критерию бесконфликтности транзакций. Однако это не совсем так. Представим ситуацию, иллюстра ция к которой изображена на рис. 1.5. В системе из четырех узлов: (N1, N2, N3, N4) выполняются две транзакции T1 и T2. При этом транзакция T2 перезаписывает между R1(z) и R1(v) считанный ранее T1 объект y, но в мо мент чтения R1(v) продвижения транзакции и, следовательно, валидация Rset не происходит в силу того, что wv1 == C4. Чтение R1(v) получается несогласованным.
Кроме этого, недостатками предложенного подхода являются его ориентированность на распределенные протоколы когерентности кэша (такие, как Ballistic [88] или Relay [89]), которые плохо масштабируются, и предоставление всего одной перезаписываемой копии объекта транзакциями системы. В работе [87] авторами был предложен подход и ряд принципов для эффективной реализации программно-организуемой транзакционной памяти на основе модели PGAS и односторонних коммуникаций. Предложенный подход был реализован в системе Cluster-STM, хорошо масштабируемой на кластерной системе с сотнями вычислительных узлов. Основной недостаток Cluster-STM — отсутствие поддержки динамического параллелизма на уровне потоков, ограничение “один процессор, одна транзакция” — был устранен в системе GTM [90], также построенной на основе модели PGAS и SPMD-подхода, но вместе с этим предоставляющей поддержку динамического параллелизма на уровне потоков и удаленного вызова процедур. Недостатком обоих систем является предоставление только лишь гарантии сериализуемости; вопрос возможного возникновения гонок и, как следствие некорректное выполнение программы, не рассматривается.
Выбор приложений и аналога для экспериментального сравнения
Для обоснования корректности любого распределенного алгоритма необходимо проверить, что конфигурации, порождаемые данным алгоритмом, соответствует определенному свойству или ряду свойств. Такие свойства принято относить [73] к двум классам: классу свойств безопасности и классу свойств живости. Как было показано в параграфе 1.6.3, существуют различные варианты формулировок свойств безопасности и живости для алгоритмов транзакционной памяти. Также было показано, что алгоритмы реализаций ТП, предназначенных для выполнения в неуправляемой среде, должны обеспечивать выполнение строгих в плане чтения согласованного состояния памяти свойств безопасности. Некоторые предложенные формулировки свойств безопасности (они же критерии согласованности) обеспечивают выполнение данных условий: для транзакций памяти это критерий бесконфликтности.
Покажем, что разработанный протокол бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС удовлетворяет свойству бесконфликтности. Для этого необходимо показать, что для любого выполнения протокола в каждой конфигурации этого выполнения справедливо следующее: - выполняется свойство сериализуемости для всех зафиксированных транзакций; - каждая конфигурация является результатом наблюдения транзакциями согласованного состояния памяти.
Будем говорить, что история Н(Е), заданная для некоторого выполнения Е семейства транзакций Т определяет отношение частичного порядка на последовательности событий Ё, которое задается согласно определениям 2.4 и 2.5. Например, история 1-lser(E) = BiB2R\(tslx)W\(ts2x)R2(tslx)C\W2(ts2x)A2 представляет порядок на некоторой последовательности событий выполнения Е семейства транзакций Т = {ТьГг}, где R\,R2 и W\, W2 — соответственно события чтения и записи транзакциями Ті, Гг значений ячейки х с соответствующими версиями (ts\, ts2).
На истории Л(Е) определим ориентированный граф сериализации транзакций (англ. direct serialization graph) или DSG( K) следующим образом[76].
Определение 2.7. DSG(H) - такой ориентированный граф, узлы которого соответствуют зафиксированным транзакциям выполнения Е, а направленные ребра соответствуют наличию определенного согласно определению 2.6 вида зависимости: в графе существует направленное от узла, которому соответствует транзакция Tt, к узлу, которому соответствует транзакция wr ww rw
Tj, ребро истинной/выходной/антизависимости или — /— /— , если Tt wr / ww / rw Tj соответственно. Зафиксированная транзакция — такая транзакция Тъ для которой в последовательности событий Ё существует событие фиксации Ск. История HiE) удовлетворяет свойству сериализуемости в том случае, если граф DSG(K) не содержит ориентированных циклов [64].
Утверждение 2.2. Для любого выполнения Е, которое является следствием исполнения системы переходов, порожденной протоколом, его история fi{E) удовлетворяет свойству сериализуемости.
Доказательство. Для доказательства данного утверждения достаточно показать, что для любого выполнения Е граф DSG( K), построенный на истории Н(Е), не имеет ориентированных циклов.
Для начала определим понятие точка сериализуемости Р транзакции 7V Будем считать, что данная точка расположена в момент времени между последним событием фазы захвата блокировок и первым событием валидации множестваRsetk в алгоритме фиксации, представленном нарис. 2.12, т.е. точка сериализуемости расположена строго перед выполнением строки 17 алгоритма 2.12 и после цикла захвата блокировок (строки 7-16). Покажем, что для любых двух транзакций Т( и Tj, которым соответствуют узлы графа DSG( K) и между которыми существует ребро зависимости любого типа согласно определению 2.7 направленное от Tt к Tj, их точки сериализуемости Pt и Pj всегда расположены в реальном времени таким образом, что момент времени точки Pi расположен раньше, чем момент времени точки Pj.
Предположим наличие истинной зависимости между транзакциями Т( wr Tj, т.е. в графе DSG(K) существует ребро — между узлами, которым соответствуют транзакции Tt и Tj. Наличие зависимости Tt wr Tj означает, что существует событие записи Є[ транзакции Tt в некоторую ячейку х є G и событие чтения ej транзакцией Tj ячейки х так, что et ш ej (см. определение 2.6).
Следовательно, т.к. событие Є[ происходит уже после прохождения ТІ точки сериализуемости Pt (см. строки 21-27 алгоритма 2.12), а событие ej происхо дит до момента выполнения макрооперации фиксации tryCj транзакции Tj, то точка сериализуемости Pt расположена во времени раньше, чем точка Pj.
Предположим наличие выходной зависимости между транзакциями Т( ww Tj, т.е. в графе DSG(K) существует ребро — между узлами, которым соответствуют транзакции Tt и Tj. Наличие зависимости Tt ww Tj означает, что существует событие записи Є[ транзакции Tt в некоторую ячейку х є G и событие записи ej транзакцией Tj в ту же ячейку х так, что et ww ej. Можно увидеть, что успешное событие записи ej (строки 21-27 алгоритма 2.12) может произойти только после захвата блокировки, перезаписи ячейки х (события е() и освобождения блокировки (в строках 24-27 алгоритма 2.12) транзакцией Tt. В случае, когда блокировка ячейки х еще захвачена транзакцией Т, а Tj попытается ее захватить (строка 9 алгоритма 2.12), то попытка захвата не удастся и Tj откатится. Следовательно, т.к. событие Є[ происходит уже после прохождения ТІ точки сериализуемости Pt, а успешный захват блокировки ячейки х и последующее прохождение точки Pj транзакцией Tj происходят только после события et и освобождения блокировки транзакцией Tt, то точка сериализуемости Р[ расположена во времени раньше, чем точка Pj.
Предположим наличие антизависимости между транзакциями Tt rw Tj, т.е. в графе DSG(K) существует ребро — между узлами, которым соответствуют транзакции Tt и Tj. Наличие зависимости Tt rw Tj означает, что существует событие чтения et транзакцией Т( некоторой ячейки х є G и последующее событие записи ej транзакцией Tj в ту же ячейку х так, что et rw ej. Как можно увидеть, валидация множества Rset производится сразу же после точки сериализуемости транзакции Tt (строка 17 алгоритма 2.12). Поэтому в случае захвата блокировки прочитанной ранее Т( ячейки х другой транзакцией Tj до выполнения валидации транзакцией Т( захват блокировки другой транзакцией будет обнаружен (строки 6-9 алгоритма 2.11) и Tt откатится. Следовательно, транзакция Tj захватила блокировку, связанную с ячейкой х, уже после начала процедуры валидации и прохождения транзакцией Т( точки сери-ализуемости Р(. Таким образом, в силу того, что захват блокировки, связанной с ячейкой х, транзакцией Tj присходит перед точкой сериализуемости Pj, то точка сериализуемости Pt расположена во времени раньше, чем точка Pj.
Отсюда не сложно показать, что граф DSG( K), построенный на любой истории Н(Е), не имеет ориентированных циклов. Если предположить, что такой цикл существует, то должна существовать циклическая зависимость между транзакциями вида Тц Та ... Тш Тц, где соответствует любому типу зависимости из определения 2.6. Но тогда точка сериализуемо сти PiN должна предшествовать точке сериализуемости Рц, что невозможно, т.к. транзакция Тш транзитивно зависит от Тц
