Модель конфликтов транзакций. Граф предшествования

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

Для проверки упорядоченности графиков используется граф предшествования (граф упорядоченности).

Определение. Для графика выполнения множества транзакций S = {A, B} граф предшествования представляет собой ориентированный граф G = (V, E), состоящий из множества вершин V – определяющих выполняемые транзакции и множества ориентированных ребер или дуг E – формируемых следующим образом:

1. Создается вершина, соответствующая каждой транзакции.

2. Создается дуга A → B, если транзакция B считывает значение элемента данных, записанного транзакцией A.

3. Создается дуга A → B, если транзакция B записывает значение в элемент данных, после того, как он был считан транзакцией A.

4. Создается дуга A → B, если транзакция B записывает значение в элемент данных, после того, как он был записан транзакцией A.

Если в графе предшествования, соответствующем чередующемуся графику S, существует дуга A ® B, то в любом последовательном графике S¢, транзакция A должна предшествовать транзакции B.

Если граф предшествования содержит цикл, то соответствующий ему график является не упорядочиваемым.

Например. Построим граф предшествования для примера графика демонстрирующего проблему потери обновления (см. график выше).