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

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

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

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

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

В заданном расписании S, охватывающем транзакции T₁ и T₂, T₁ предшествует T₂, если существуют действия A₁ транзакции T₁ и A₂ транзакции T₂, удовлетворяющие условиям:

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

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

Пример

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

S: r₁;w₂;w₁;w₃;

Чтение r₁ транзакции T₁ Выполняется раньше записи w₂ транзакции T₂. Следовательно, T₁ предшествует T₂. Аналогично, T₂ предшествует T₃.

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

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

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

S: r₁;w₂;r₂;w₁;w₃;

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