Интернет магазин китайских планшетных компьютеров



Компьютеры - Граф предшествования

22 января 2011





Граф предшествования, понятие теории графов.

Граф предшествования для последовательности событий S состоит из

  • узла для каждой подтвержденной транзакции в S
  • стрелки из Ti в Tj если транзакция Ti предшествует или конфликтует с одной из Tj.

В заданном расписании S, охватывающем транзакции T1 и T2, T1 предшествует T2, если существуют действия A1 транзакции T1 и A2 транзакции T2, удовлетворяющие условиям:

  • A1 выполняется раньше A2
  • A1 и A2 адресуют один и тот же элемент данных
  • Хотя бы одно из действий A1 и A2 связано с операцией записи

Граф предшествования позволяет наглядно показать, является ли расписание условно-последовательным.

Пример

Time T1 T2 T3
1 read
2 write
3 Commit
4 write
5 Commit
6 write
7 Commit

Рассмотрим данный пример. Расписание для него будет иметь следующий вид:

S: r1;w2;w1;w3;

Чтение r1 транзакции T1 Выполняется раньше записи w2 транзакции T2. Следовательно, T1 предшествует T2. Аналогично, T2 предшествует T3.

Для этого расписания граф предшествования будет таким:


Graf pred 1.jpg


Как видно, граф не содержит циклов, следовательно расписание является условно-последовательным с учетом конфликтов.

Рассмотрим теперь другой пример.

Time T1 T2 T3
1 read
2 write
3 read
4 Commit
5 write
6 Commit
7 write
8 Commit

S: r1;w2;r2;w1;w3;

T1 предшествует T2, вместе с тем, T2 предшествует T1. Очевидно, граф будет содержать цикл, и это показывает, что данное расписание не является условно-последовательным.

Graf pred 2.jpg




Просмотров: 521


<<< Граф ожидания