Бесконечные ожидания и тупики.

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

Простой способ избежать этого: регистрировать все запросы и удовлетворять их в порядке очерёдности.

Вторая, более серьёзная проблема – тупики.

Пример: : READ A

: READ A

: READ A

…

– возможно бесконечное ожидание.

: LOCK A : LOCK B

LOCK B LOCK A

UNLOCK A UNLOCK B

UNLOCK B UNLOCK A

Транзакция запрашивает блокировку и её запрос удовлетворяется. Точно так же удовлетворяется запрос транзакции на блокировку . Затем запрашивает блокировку и ждет, т.к. он заблокирован транзакцией . Аналогично запрашивает блокировку и должна ждать, пока разблокирует . Таким образом, ни одна транзакция не может продолжаться; каждая из них ожидает, пока другая разблокирует требуемый для нее элемент. Поэтому и будут ждать бесконечно долго.

Ситуация, в которой каждая транзакция из множества S, содержащего не менее 2-х транзакций, ожидает, когда ей будет предоставлена возможность заблокировать элемент, заблокированный в данный момент времени какой-нибудь иной транзакцией из данного множества S, называется тупиком.

Подход к решению этой проблемы:

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

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

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

В случае обнаружения тупика нужно произвести снятие всех блокировок (рестарт) хотя бы для одной из попавших в него транзакций (удалить дугу) или сделать откат транзакции (удалить вершину).

Протоколы и расписание.

Каждая транзакция состоит из элементарных шагов (блокировка, чтение записи и т.д.).

Расписанием совокупности транзакций называется порядок, в котором выполняются элементарные шаги этих транзакций. Шаги любой транзакции должны появляться в расписании в порядке их вхождения в программу, прогоном которой является эта транзакция.

Расписание считается последовательным, если все шаги каждой транзакции выполняются последовательно; сериализуемым, если результат его реализации всегда эквивалентен результату некоторого последовательного расписания.

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

 

 

Простая модель транзакции.

Изучим простейшую модель транзакции, которая позволяет говорить о сериализуемости. В этой модели транзакция рассматривается как последовательность операторов блокирования и разблокирования. Каждый блокированный элемент впоследствии должен быть разблокирован. Будем считать, что при между шагом LOCK A и UNLOCK A транзакция осуществляет изменение значения .

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

Пример: : LOCK A A B C

: LOCK B …

: LOCK C …

: UNLOCK B

: LOCK B

: UNLOCK A

: LOCK A

: UNLOCK C

: UNLOCK A

: LOCK A

: LOCK C

: UNLOCK B

: UNLOCK C

: UNLOCK A