|
а) результирующий граф содержит циклы — транзакция ti откатывается; Ь) полученный граф ацикличен — действие добавляется к списку запланированных. Что означает, что в графе появился цикл? Полученное расписание больше не будет сериализуемым. Это утверждение становится очевидным, если заметить, что дуга из ti в tj фиксирует порядок следования транзакций в эквивалентном последовательном расписании. Результат нашего расписания должен быть таким же, как и последовательное выполнения сначала всех действий транзакции ti, а затем tj. Поскольку транзакция не может следовать раньше самой себя, граф с циклами не будет иметь соответствующего последовательного расписания. Теперь мы можем перейти к более общему многоверсионному случаю и будем рассматривать многоверсионный граф конфликтов MVSG. Покажем, что ограничения, которые мы накладывали на граф сериализации в моноверсионним случае, недостаточны. Рассмотрим следующий пример: S = Vrf[xl]yvl[yl]r2[yl]r3[xl]w2[z2]r3[z2]w2[x2] Граф (рис. 46), составленный по правилам алгоритма SGT, будет содержать дуги (tl, t2), (tl, t3), (t2, t3). T3 Рисунок 4 Граф сериализации для плана S, составленный по правилам SGT. Этот граф ацикличен. Однако для б1 не существует эквивалентного моноверсионного последовательного расписания. Действительно, поскольку t3 читает версию х, записанную tl (r3[xlj), то t2, которая тоже пишет элемент х (w2[x2J), должна следовать в моноверсионном последовательном расписании либо после t3, либо перед tl. Но первый вариант невозможен изза шага r3[z2], а второй — из-за г2[у1]. Таким образом, многоверсионный 69 |
* 1. Если это первая операция транзакции ti, поступившая планировщику, то создается новый узел в графе сериализации. 2. В граф добавляются дуги вида (tj, ti) для каждой запланированной ранее операции qj(x) (i _ j), конфликтующей с pi(x). Возможны два варианта: а) результирующий граф содержит циклы — транзакция ti откатывается; Ь) полученный граф ацикличен — действие добавляется к списку запланированных. Что означает, что в графе появился цикл? Полученное расписание больше не будет сериализуемым. Это утверждение становится очевидным, если заметить, что дуга из ti в tj фиксирует порядок следования транзакций в эквивалентном последовательном расписании. Результат нашего расписания должен быть таким же, как и последовательное выполнения сначала всех действий транзакции ti, а затем tj. Поскольку транзакция fie может следовать раньше самой себя, граф с циклами не будет иметь соответствующего последовательного расписания. Теперь мы можем перейти к более общему многоверсионному случаю и будем рассматривать многоверсионный граф конфликтов MVSG. Покажем, что ограничения, которые мы накладывали на граф сериализации в моноверсионним случае, недостаточны. Рассмотрим следующий пример: S = wl[xl]wl[yl]r2[yl]r3[xl]w2[z2]r3[z2]w2[x2] Граф (рис. 26), составленный по правилам алгоритма SGT, будет содержать дуги (tl, t2), (tl, t3), (t2, t3). «I Рис.26 Граф сериализации для плана S, составленный по правилам SCT 139 Этот граф ацикличен. Однако для S не существует эквивалентного моноверсионного последовательного расписания. Действительно, поскольку t3 читает версию х, записанную ll (r3[xl]), то (2, которая тоже пишет элемент х (w2fx2J), должна следовать в моноверсионном последовательном расписании либо после t3, либо перед t l . Но первый вариант невозможен изза шага r3[z2], а второй — из-за г2[у1]. Таким образом, многоверсионный планировщик должен также специальным способом проверять согласованность шагов, создающих новые версии. Для этого в граф добавляются дополнительные дуги, которые фиксируют «позиции записи» в соответствующем последовательном расписании. Опишем общую схему работы предлагаемого MVSG-планировщика. Когда очередной шаг pi(x) поступает планировщику, он предпринимает следующие действия. 1. Если это первое действие транзакции ti, поступившее планировщику, то соответствующий узел добавляется к графу конфликтов. 2. Если это шаг ri(x), то выбирается подходящая версия xj, и в граф добавляется дуга (tj, ti) (поскольку, согласно нашим обозначениям, версию xj записала транзакция tj). Для всех других к, таких что wk(xk) является шагом tk, в граф добавляется либо дуга (tk, tj), либо дуга (ti, Ik). В этом и состоит выбор «позиции записи». 3. Если это шаг wi(xi), то для каждой транзакции tk, которая прочитала, скажем, версию xj, нужно добавить либо дугу (ti, tj), либо дугу (tk, ti). То есть ti должна следовать либо до tj, либо после tk в соответствующем последовательном расписании. 4. Если граф остается ацикличным, то изменения в графе фиксируются, а действие добавляется к списку запланированных. Иначе транзакция откатывается. Следует обратить внимание на выборе подходящей версии для чтения. Версия xj не является подходящей в двух случаях: во-первых, если существует путь из ti в tj (tj следует после ti по порядку сериализации); во |