Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

10 Возможно здесь другое слово согласованном непротиворечивом Было- cceptbleКаждый ли Ведь есть объектыз

Работа добавлена на сайт samzan.ru: 2015-07-10


- 10-

Возможно, здесь другое слово (согласованном, непротиворечивом) Было: acceptableКаждый ли? Ведь есть объекты-значенияЕсть ли необходимость в графе зависимостей? Может, достаточно обойтись списком зависимостей?Возможно, номер изменитсяСтоит ли оставлять это предложение?А что с объектами-значениями?Не слишком ли жадно до ресурсов?

Транзакции

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

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

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

В зависимости от организации протокола совместного выполнения транзакций он является пессимистическим или оптимистическим.

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

Протокол согласованного управления ООСУБД обеспечивает:

  •  Управление совместно выполняющимися продолжительными транзакциями
  •  Усиливает корректность критерия другого, чем сериализуемость
  •  Учитывает объектную ориентированность данных
  •  Допускает обобщение операций (не только чтение и запись)

Определения и запись

Определение 1. Пусть значение объекта O определяется набором его частей-значений, обозначаемых iv1, iv2, …, ivn. Это могут быть, например, атрибуты агрегата, элементы списка и др. Обозначим операции (методы) op1, op2, …, opn. Каждая операция opi имеет множество (возможно пустое) параметров p1, p2, …, pr.

Каждая операция opi может состоять из более элементарных операций, представленнных списком opi1,…,opis. Каждая из этих операций является локальной или глобальной. Локальная операция работает только с собственными данными объекта O, иначе операция является глобальной. Глобальная операция состоит в посылке сообщения другому объекту и получения от него результата.

Говорят, что операция opi на объекте O порождает операцию opj, на объекте O', если opj была вызвана глобальным шагом opi, пославшей сообщение к объекту O'. Это отношение порождения одной операции другой (отец-сын), может быть представлено отношением предок-потомок через транзитивное замыкание.

Определение 2. Область действия операции opi на объекте O, (Scope(opi(O)) ) состоит из следующих объектов:

  1.  Все экземпляры переменных объекта O.
  2.  Все параметры p1, p2, …, pr, связанные с операцией opi на O.
  3.  Все системные объекты
  4.  Если O -- класс, то область действия операции opi на объекте O включает в себя непосредственных наследников O (тоже классов) и классы, являющиеся доменами для iv1, iv2, …, ivn. Дополнительно, все объекты которые являются экземплярами класса O, также попадают в область действия opi объекта O.

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

Все воздействия любой операции (на объекте) попадают под одну из четырех категорий: запрос, создание, модификация, удаление.

Иерархия наследования и отношение класс-экземпляр_класса приводят к каскадному эффекту. Поэтому для каждой операции opi на объекте O определяется множество запросов (query set: QS(opi(O)) ), множество созданий (create set: CS(opi(O)) ), множество модификаций (modify set: MS(opi(O)) ) и множество удалений (delete set: DS(opi(O)) ).

Определение 3. Множество запросов QS(opi(O)) определяется рекурсивно как QS(opi(O)) = LocalQS(opi(O)) GlobalQS(opi(O)), где

  1.  LocalQS =
  •  , если нет собственных ivj из O "запрошенных" операцией opi.
  •  {O}, иначе.
  1.  GlobalQS =

{Ogq | opi , посылает сообщение к Os для выполнения метода opj, где Os Scope(opi(O)), и OgqQS(opj(Os))}.

Аналогично определяются можества создания модификации и удаления операции opi на объекте O.

Определение 4. Пусть можество замен (update set) определяется как US(opi(O)) = (CS(opi(O)) MS(opi(O)) DS(opi(O))).

Определение 5. Говорят, что имеется конфликт двух операций opi на объекте O и opj на объекте O', если выполняется хотя бы одно из следующих условий:

  1.  US(opi(O)) US(opj(O'))  
  2.  QS(opi(O)) US(opj(O'))  
  3.  US(opi(O)) QS(opj(O'))  

Пользовательские транзакции можно рассматривать как методы или операции специального объекта базы данных: DBIO (Database User-Interface Object) -- пользовательского представления базы данных. Таким образом, транзакции выглядят как любой другой метод в системе.

Пусть для каждого объекта O в базе данных OpTypes(O) -- множество типов методов или операций, разрешенных для выполнения на объекте O.

Пусть OpTypes(O) = { OpType1(O), OpType2(O), …, OpTypep(O)) }

OpTypes(O) предоставляет механизм классификации операций op1, op2, …, opn на объекте O. Каждой операции opi поставлен в соответствие тип OpTypejOpTypes(O).

Определение 6.

Пусть CG0 -- спецификация k-уровневой группировки для множества OpTypes(O). CG0 определяется так:

  •  CG0(1) состоит только из одного множества -- OpTypes.
  •  CG0(k) состоит из множеств с одним элементом (singleton sets) , по одному на каждый тип операции в множестве OpTypes.
  •  Каждое CG0(i) уточняет CG0(i-1), т.е. для любого множества cgsCG0(i), найдется множество cgs'CG0(i-1) такое, что cgs cgs'.

Определение 7. Уровень Level(opi(O),opj(O))=l, где CG0(l) содержит opi(O) и opj(O) в одном множестве и для каждого m > l, opi(O) и opj(O) не содержатся в одном множестве CG0(m).

Определение 8. Для каждой операции opi(O) спецификация точки разрыва k-го уровня B(opi(O),k) определяется так:

  •  B(opi(O),1) состоит только из одного множества -- { opi1(O), opi2(O), …, opik(O)}
  •  B(opi(O),k) состоит из множеств с одним элементом, по одному для каждого шага операции opi на объекте O.
  •  Каждое B(opi(O),j) представляет собой уточнение B(opi(O),j-1).
  •  Если bl = B(opi(O),j), opijbl, opinbl, и существует opim такая, что на операции opi(O) подоперация opij предшествует opim, которая, в свою очередь, предшествует opin, тогда opimbl. (Т.е. если два шага операции находятся в одном классе эквивалентностей, то любая промежуточная операция находится в одном с ними классе эквивалентностей.)

Для увеличения производительности СУБД, некоторые операции могут взаимодействовать друг с другом в базе данных. Некоторые из этих операций могут выполняться на одном объекте. Совместное выполнение многих операций (псевдопараллельность) может приводить к произвольному чередованию операций (или их шагов). Порядок чередования называется объектно-ориентированным расписанием. Так как "пользовательские транзакции" являются только операциями на DBIO, ОО-расписание можно определить на DBIO как пару (S,<расп), где S – множество всех шагов (как локальных, так и глобальных), а <распчастичный порядок на множестве шагов в S. Глобальные шаги в S -- это результат обращения операций к другим объектам, и шаги основанные на результате этих обращений также  включаются в расписание.

Пусть T – пользовательская транзакция вида T = {tOP1(DBIO), tOP2(DBIO), …, tOPn(DBIO)}.

Некоторые из вызываемых ей операций могут вызываться другой аналогичной операций на DBIO, т.е. на DBIO могут выполняться несколько независимых копий одной и той же операции. Пусть T’={t’(O’) | t’(O’) порождена операцией t(DBIO)T}.

Определение 9. Расписание Sch для T на DBIO является корректным объектно-ориентированным расписанием, если:

  1.  Sch состоит только из шагов операций T’, и для каждый из них выполняется только один раз в Sch.
  2.  <t’(O’)   <Sch , для каждой операции t’(O’)T’. Другими словами, в расписании сохраняется отношение порядка выполнения шагов операций для всех транзакций.
  3.  Если t’(O)T’, t”(O)T’,
    Level(t’(O),t”(O)) =
    l,
    t’(O) = { t’
    1(O), t’2(O), …, t’m(O) },
    t”(O) = { t”
    1(O), t”2(O), …, t”n(O) },
    t’
    p(O), t’r(O) bl’, blB(t’(O), l),
    t”
    q(O) bl”, blB(t”(O), l),
    t’
    p(O) <t’(O)  t’r(O), t’p(O) <Sch t”q(O),
    тогда t’r(O) <Sch t”q(O).


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

Определение 10. Расписание Sch1 эквивалентно Sch2, если

  1.  Оба определены через одно и то же множество операций (например, T).
  2.  Если t’(O’), t”(O”) T,
    t’
    p(O’) -- шаг t’(O’),
    t”
    q(O’) -- шаг t”(O”),
    t’
    p(O’) <Sch1 t”q(O”), t’p(O’) конфликтует с t”q(O”),
    тогда t’p(O’) <Sch2 t”q(O”)

Другими словами, если результат t” получается на основе результата t’, то в любых двух эквивалентных расписаниях операция t’ предшествует операции t”, порядок конфликтующих операций в эквивалентных расписаниях сохраняется. Если конфликта нет, то любой порядок следования операций является допустимым. Если при этом получаются разные результаты, то каждый из них, тем не менее, является правильным. Этот парадокс можно проиллюстрировать на следующем примере:

Положим, имеются две операции: увеличить сумму на счете вдвое и увеличить сумму на счете на 10%. Очевидно, что результат будет разным в зависимости от порядка следования операций. Но, поскольку операции независимы, в любом случае он считается правильным.

Обзор протокола

Если объекты, которые доступны различным транзакциям, заранее известны, задача механизма согласованного управления относительно проста. Априорная информация облегчает статичное определение конфликтующих операций; следовательно, стратегия управления чередованием операций может быть сформулирована. Однако, позднее связывание (late binding), характерная черта объектно-ориентированных систем, приводит к трудности предварительного определения объектов доступа. При отсутствии такого знания, одним из выходов является блокировка некоторых транзакций до тех пор, пока вид объектов доступа не станет известен. Однако, для продолжительных (long-duration) транзакций, такая блокировка может привести к слишком большому времени ожидания.

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

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

Спецификация точки проверки

Идея точки проверки используется для минимизации глубины отката в случае обрыва транзакций. Эти точки могут быть описаны пользователем. Точки проверки связаны с операциями на объектах и могут быть описаны как шаг операции. Нет необходимости иметь спецификацию точки проверки для каждого объекта в системе. Однако пользователь может описать точки проверки в некоторых операциях на некоторых объектах, так, что каждоя точка представляет логическую единицу работы. Идея установки точек проверки предоставляет базе данных возможность определять, находится ли она в стабильном состоянии. Точка проверки служит как механизмом синхронизации, так и заботой о связности базы данных. Любая пользовательская транзакция может иметь зависимость от результатов других транзакций. Таким образом, точка проверки в транзакции имеет значение только если все другие активные операции также согласны с тем, что состояние базы данных в этой точке является непротиворечивым состоянием (consistent state). При этом точка проверки действует как точка встречи, в которой все активные транзакции системы фиксируют (commit) свою (частично сделанную) до этой точки работу.

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

Описание протокола

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

Каждый объект в системе хранит следующую информацию:

  •  Таблица чередований в точках разрыва (Breakpoint/Interleaving Table)
  •  Таблица конфликтов
  •  Списки зависимости и Граф зависимости

Таблица чередований в точках разрыва (статичная информация)

Эта информация получается из точек разрыва и группировки спецификаций для объекта и имеет форму, показанную в таблице:

Запрошенная

Операция

Выполняющиеся операции

op1

op2

opj

opn

op1

op2

opi

EBI(i,j)

opn

Ячейка (i,j), т.е. EBI(i,j) – множество точек разрыва opj(O) на которых opi(O) может чередоваться с ней. Статичная информация предоставляемая Таблицей чередований в точках разрыва комбинируется с информацией времени выполнения (run-time) на этапе выполнения операций, т.е. тем шагом каждой операции, который в данный момент выполняется.

Таблица конфликтов (Conflict Table)

Таблица конфликтов устроена точно также, как и таблица чередований в точках разрыва. Ячейка в ней обозначается ECon(i,j) и принимает одно из трех значений:

  •  Да, если opi(O) конфликтует с opj(O).
  •  Нет, если opi(O) не конфликтует с opj(O).
  •  Неизвестно (unknown), если заранее не известно, конфликтует ли opi(O) с opj(O).

Неизвестно является следствием наличия позднего связывания, характерной черты объектно-ориентированных систем. Проверка наличия конфликта производится в соответствии с определением 5.

Списки зависимости и граф зависимости

Список зависимости состоит из нуля или более элементов зависимости. Каждый элемент зависимости имеет вид <Ti,Tj> где Ti и Tj – пользовательские транзакции, так что Ti следует за Tj и конфликтует с ним.

Есть три вида списков зависимости:

  •  Локальный список зависимости
    Каждый объект
    O содержит локальный список зависимости, обозначаемый DSL(O). Этот список состоит из элементов зависимости, локально порожденных на объекте O. В начале, этот список пуст и элементы зависимости добавляются, когда пользовательская транзакция (прямо или косвенно) обращается к локальной информации конфликтующего элемента.
  •  Список унаследованных зависимостей
    Каждый объект
    O также содержит список унаследованных зависимостей, обозначаемый DSI(O). Этот список также вначале пуст. Когда операция op(O) обращается к O как к результату сообщения от opi(Oi) из вызываемого объекта., вызываемый объект также посылает свое множество зависимостей DS(Oi), которое добавляется к DSI(O). Список унаследованных зависимостей можно рассматривать как форму прямого размножения зависимостей от вызывающей операции (объекта) к вызываемой операции (объекту).
  •  Список приобретенных зависимостей.
    Список приобретенных зависимостей, обозначаемый
    DSR(O) наращивается, когда операция opr(Or), вызванная как результат глобального шага операции op(O) на O, закончила выполнение. Вместе с результататами вызванной операции, вызванный объект также посылает свое множество зависимостей DS(Or). Список приобретенных зависимостей можно рассматривать как форму обратного распространения зависимостей от вызванного объекта к вызывавшему объекту.

Множество зависимостей для O определяется как

DS(O) = DSL(O) DSI(O) DSR(O).

Граф зависимостей DG(O) каждого объекта O -- это графическое представление множества зависимостей DS(O). Узлы этого графа состоят из пользовательских транзакций. Для каждого элемента зависимости <Ti,Tj>, в графе существует ребро TiTj в DG.

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

Состояние пользовательских транзакций на объектах.

Каждый объект O в системе хранит состояние каждой пользовательской транзакции в системе. Состояние пользовательской транзакции (т.е. операции на DBIO) может принимать одно из следующих значений:

  •  Никогда не активировалась (Never Activated)
    Любая пользовательская транзакция, которая не воздействоваа на
    O прямо или косвенно, находится в этом состоянии на O. Это эквивалентно тому, что не имеется никакой информации о пользовательской транзакции в O.
  •  Завершена (Completed)
    Пользовательская транзакция находится в состоянии Завершена на O, если операция вызванная ей на O закончила выполнение всех своих шагов.
  •  Находится в точке проверки (Chekpoint)
    Пользовательская транзакция не произвела никаких действий с тех пор, как оказалась в точке проверки.
  •  Задержана для точки проверки (BlockedForCheckPoint)
    Пользовательская транзакция ожидает выполнения условий, которые будут удовлетворять переводу ее в Точку проверки.
  •  Выполняется (Executing)
    Пользовательская транзакция выполняется на O, если операция op(O), вызванная этой транзакцией выполняется.

Пример изменения состояния транзакции при ее выполнении:

Действия

Новое состояние транзакции на O

Никогда не активировалась

Объект O получил запрос на выполнение op(O) впервые для транзакции Tr(op(O)) и op(O) начинает выполняться

Выполняется

Операция транзакции достигла описанной для нее точки проверки,  все остальные активные операции на O "никогда не активировались" в точке проверки

Находится в точке проверки

Операция транзакции достигла описанной для нее точки проверки, но активные операции не находятся в своих точках проверки

Блокирована для точки проверки

Tr(op(O)) закончила все свои шаги

Завершена

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

Определение 1. Пусть объект O состоит из экземпляров переменных

Протокол согласованного управления

  1.  Операция запрошена (requested)
  2.  Операция вызывает другую операцию
  3.  Вызванная операция возвращается
  4.  Операция завершена
  5.  Точка разрыва (breakpoint) достигнута
  6.  Точка проверки (checkpoint) достигнута
  7.  В точке проверки получено сообщение

  1.  Обработка запроса для получения операции

Пусть на объекте O в данный момент выполняется операция {opj1, opj2, …, opjn}.

Пусть CurPoint(opj(O)) обозначает текущий шаг операции opj.

Запрос на операцию op на O получен (через сообщение) от opi(Oi) (вызывающей операции). Сообщение также содержит информацию зависимости (в виде множества зависимостей) из вызывающего объекта. Запрос для операции op(O) обрабатывается следующим образом:

Шаг1

Проверяется: содержит ли DS(O)DS(Oi) цикл с Tr(opi(Oi)).

Если да, то Abort_Processing

Иначе, следующий шаг.

Шаг2

Используется таблица конфликтов

  1.  k 1kn, если ECоп(op(O), opjk(O)) = Нет, то расписать op(O) на выполнение. Списки зависимостей не меняются. Состояние Tr(op(O)) становится «Выполняется». Если условие (1) не выполнено, то
  2.  k 1kn условие (1) или CurPoint(opjk(O))EBI(op(O), opjk(O)), тогда
    k 1kn : ECоп(op(O), opjk(O))  Нет; добавить <Tr(op(O)), Tr(opjk(O))> в DSL(O). Если DG(O) теперь содержит цикл с Tr(op(O)), то Abort_Processing
    иначе расписать op(O) для выполнения и изменить состояние Tr(op(O)) в «Выполняется». Если (2) не выполняется, то (3), иначе выход.
  3.  k 1kn : условие (2) или ECоп(op(O), opjk(O)) = Неизвестно, то
    k 1kn : ECоп(op(O), opjk(O)) = Да; добавить <Tr(op(O)), Tr(opjk(O))> в DSL(O). Если теперь DG(O) содержит цикл с Tr(op(O)), то Abort_Processingб иначе расписать op(O) для выполнения и изменить состояние Tr(op(O)) на «Выполняется». Это выполнение будет проверяться позже, когда вид объектов доступа будет известен, и множества зависимостей разрастутся, вернувшись с результатом операций. Если (3) не выполняется, то (4), иначе выход.
  4.  Блокировать выполнение op(O) до тех пор, пока каждая операция opjk(O), для которой ECоп(op(O), opjk(O)) = Да достигнет шага такого, что CurPoint(opjk(O))EBI(op(O), opjk(O)). Тогда перейти к (2).

  5.  Вызов операции

Когда операция op(O) выполняет глобальный шаг, т.е. посылает сообщение другому объекту, следующие шаги выполняются:

  •  DS(O):=DSL(O) DSI(O) DSR(O)
  •  Сообщение посылается получающему объекту вместе с параметрами сообщения и DS

  1.  Вызванная операция возвращается

Пусть результат глобального шага операции op(O) – в сообщении, вызывающем операцию opr(Or). Когда вызванная операция opr(Or) вернется, список зависимостей DS(Or) также вернется (вместе с результатом выполнения метода).

Тогда производятся следующие шаги:

  •  К списку DSR(O) добавляется DS(Or)
  •  Строится граф зависимостей и проверяется на наличие циклов, содержащих транзакцию Tr(op(O)), если такой цикл есть, Abort_Processing

  1.  Когда операция завершается
    Следующие шаги выполняются, когда
    op(O) заканчивает выполнение:
  •  Строится DS(O). Можно не включать в него зависимости соответствий к DSI(Oi). DS возвращается в Oi вместе с результатом операции op(O).
  1.  Когда достигнута точка останова
    Группировка и описание точек разрыва позволяет прерывать порядок операций. Это означает, что некоторые пункты зависимостей из локального списка зависимостей могут быть удалены, когда операция достигает точки разрыва. Когда операция op(O) достигает точки разрыва bk, производятся следующие шаги:
  •  Из определенной пользователем спецификации точки разрыва определяется уровень точки разрыва l
  •  Из группировки и спецификаций точек разрыва, пусть Opb = { Opk1(O), Opk1(O), … ,Opkm(O)} будет множеством операций, которые могут прервать op в bk.
  •  Удалить каждую зависимость в DSL(O), которая влечет за собой Tr(op(O)) и Tr(opkr(O)), где opkr(O)Opb.

  1.  Когда точка проверки достигнута
    Идея установки точек проверки
     используется для ограничения длины отката (rollback), который необходим, когда операция обрывается (aborted). В этом протоколе такие обрывы операций иногда необходимы, так как происходит некорректное выполнение. Поскольку известной заранее информации об объектах, к которым операции имеют доступ, недостаточно, это ведет к некорректному прерыванию операций.
    Когда точка проверки достигнута, будущие обрывы в этой или любой другой операции не требуют отката за эту точку.
    Когда операция
    op(O) достигает точки проверки ck, производятся следующие шаги:
  •  Строится DS(O). Пусть DepSet(Tr(op(O)),O)={Tj| <Tr(op(O)), Tj>DS} будет множеством пользовательских транзакций, которые конфликтуют с op(O) и предшествуют ей (и, следовательно, Tr(op(O)) на O.
  •  j: TjDepSet(Tr(op(O)),O) если или Tj имеет состояние «Никогда не активно» на O, или opk(O) (такая, что Trk(op(O))=Tj) есть в точке проверки, идти к следующему шагу, иначе блокировать до удовлетворения этого условия.
    Состояние
    Tr(op(O)) изменяется в «Блокировано для точки проверки».
  •  Сообщение точки проверки посылается каждому объекту Or, который получает сообщение от глобального шага op(O) вызвать opr(Or). Изменяется состояние Tr(op(O)) на «В точке проверки».

  1.  Объект получает сообщение точки проверки.
    Когда объект
    O получает сообщение точки проверки для операции op(O) из операции opi(Oi), производятся следующие шаги:
  •  Удаление каждой зависимости от DS(O), которая связана с Tr(op(O))
  •  Изменение состояния Tr(op(O)) в «Завершено»
  •  Сообщение точки проверки посылается каждому объекту Or, который получает сообщение от глобального шага op(O) вызвать opr(Or)

Abort_Processing

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

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

Abort_Processing вводится на особых объектах.

  1.  Цикл определения и обрыва
    В идеале обрыв должен быть произведен сразу как тоько некорректность выполняемой операции замечена. В протоколе множество зависимостей
    DS(O) объекта O помогает этому. Наличие циклов в связанном графе зависимостей DG(O), означает существование некорректно выполненяющихся операций. Другими словами, ациклический граф зависимостей может получить цикл только тогда, когда добавлено новое ребро, т.е. новая зависимость может быть добавлена в DS одним из следующих способов: добавлением зависимости в DSL(O), DSI(O) или DSR(O).

Рассмотрим две операции: opi(O) и opj(O) с Tr(opi(O))=Ti и Tr(opj(O))=Tj. Пусть выполнение шага opi(O) (который конфлитует и следует за шагом opj(O)) приводит к добавлению зависимости <Ti, Tj> к DS(O), которая дает цикл в DG(O). Это означает, что перед выполнением этого шага, DG содержал путь от Tj к Ti. Добавление новой зависимости привело к образованию цикла. (Цикл может включать другие транзакции, в дополнение к Ti и Tj.) Поскольку существование этого цикла означает некорректное прерывание выполнения операции, необходимо прервать не менее одной транзакции и разорвать цикл. Если opj(O) еще выполняется на O, можно прервать ее и, таким образом, зависимость <Ti, Tj> не будет добавлена.

Прерывание opj(O) приводит к прерыванию операций, которые могли быть выполнены на других объектах после глобального шага opj(O).

Однако, если opj(O) уже завершена на O, необходимо отменить результат opj(O) (в этом и всех других объектах, которые доступны глобальным шагам opj(O)). Таким образом, сообщение об обрыве должно быть послано всем этим объектам.

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

  1.  Получение запросов отказа (обрыва)

Когда объект O получает запрос отказа для особенной операции opj(O), производятся следующие шаги:

Если opj(O) выполняется на O

  •  Обрыв opj(O)
  •  Отмена эффектов шагов opj(O)
  •  Посылка сообщения обрыва всем объектам, которые получили сообщение от O как результат глобального шага opj(O)

Если opj(O) завершила выполнение на O

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

Для каждой операции opi(O), которая конфликтует с opi(O) на O и следует за ней

  •  Послать запрос обрыва в O (себя) для обрыва opj(O)




1. Введение Согласно логике сначала необходимо определить понятия о которых пойдет речь в данной работе
2. го сечения 108 м4 сопротивления 106 м3 прочности стали соединения ЗС
3. В процессе своей работы в любой прикладной области пользователю необходимо общаться с компьютерами и под
4. Основы ATL-маркетинга
5. Челябинский государственный университет ФГБОУ ВПО ЧелГУ Факультет управления Кафедра Менеджм
6. Інструкція -методична карта практичного заняття Юридична відповідальність
7. тема внутренних тайн Сказание о Златовласке Камзол отпущения Модуль 4
8. Философские подходы в прикладной физике лазеров
9. Тема- Д.Н. Мамин Сибиряк Сказка про храброго зайца длинные уши косые глаза короткий хвост
10. Биостратиграфия
11. Тема 11 Підприємство в системі ринкових відносин
12. Языки и методы программирования ~ 1 1 курс 1 семестр Этапы решения задачи
13. тема гражданского права как отрасли права Гражданское право в системе отраслей права Гражданское право к
14. 1Определение и функции микропроцессора
15. Отраслевые академии наук Российская академия архитектуры и строительных наук Российская академ
16. Можно предложить несколько рабочих операций в рамках которых это становится очевидным
17. . Теоретические основы развития музыкальных способностей [3] Глава 2.
18. Мы с вами не имеем возможности обсуждать всю философскую и психологическую сложность понятия пространс
19. Основы психологии
20. Архитектурные особенности усадьбы Суханово