Бесконечные ожидания и тупики.
Проблема
бесконечного ожидания может возникнуть
в любой обстановке, предусматривающей
параллельное исполнение процессов.
Пусть транзакция
проводит работу с элементом
,
и доступ к элементу
заблокирован этой транзакцией;
находится в состоянии ожидания; транзакция
также
запрашивает блокировку
,
и этот запрос исполняется раньше, чем
запрос
.
Далее, в то время, когда блокировку
установила транзакция
,
ее запрашивает
,
чьё требование удовлетворяется после
разблокирования
транзакцией
и т.д. Не исключено, что транзакция
будет пребывать в состоянии бесконечного
ожидания.
Простой способ избежать этого: регистрировать все запросы и удовлетворять их в порядке очерёдности.
Вторая, более серьёзная проблема – тупики.
Пример: : 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, называется тупиком.
Подход к решению этой проблемы:
Потребовать, чтобы каждая транзакция единовременно запрашивала все нужные ей блокировки. Система либо полностью удовлетворяет такой запрос, либо не предоставляет вообще никаких блокировок и заставляет данную транзакцию ждать, если один или более требуемых элементов заблокирован до транзакции. Это устраняет тупик из примера.
Вводится произвольное линейное упорядочивание элементов и все транзакции должны запрашивать блокировки в этом порядке. Это гарантирует установление очередности между транзакциями. Для транзакции, заблокировавшей некоторый элемент, гарантируется возможность заблокировать и все следующие за ним элементы.
Совсем иной способ борьбы с тупиками – ничего не предпринимать для их предотвращения, а периодически проверять запросы на блокировки и выявлять: не возникла ли тупиковая ситуация. Облегчает проведение такой проверки алгоритм построения графа, вершины которого обозначают транзакции, а ориентированная дуга
,
что транзакция
ожидает выполнения своего запроса на
блокирование элемента, заблокированного
в данный момент транзакцией
.
Возникновение тупика определяет наличие
в построенном указанным способом графе
цикла. Если цикла нет, то не существует
и тупиков.
В случае обнаружения тупика нужно произвести снятие всех блокировок (рестарт) хотя бы для одной из попавших в него транзакций (удалить дугу) или сделать откат транзакции (удалить вершину).