В многопроцессорной системе тупиковая ситуация — это нежелательная ситуация, которая возникает в среде общих ресурсов, где процесс бесконечно ожидает ресурс, который удерживается другим процессом.
Например, предположим набор транзакций {T 0 , T 1 , T 2 , …, T n }. T 0 нужен ресурс X, чтобы завершить свою задачу. Ресурс X удерживается T 1 , а T 1 ожидает ресурс Y, который удерживается T 2 . T 2 ожидает ресурс Z, который удерживается T 0 . Таким образом, все процессы ждут друг друга, чтобы освободить ресурсы. В этой ситуации ни один из процессов не может завершить свою задачу. Эта ситуация известна как тупик.
Тупики не полезны для системы. В случае, если система застревает в тупике, транзакции, вовлеченные в тупик, либо откатываются, либо перезапускаются.
Предотвращение тупиковой ситуации
Чтобы предотвратить любую тупиковую ситуацию в системе, СУБД настойчиво проверяет все операции, в которых собираются выполнить транзакции. СУБД проверяет операции и анализирует, могут ли они создать тупиковую ситуацию. Если он обнаруживает, что может возникнуть ситуация взаимоблокировки, эта транзакция никогда не будет разрешена для выполнения.
Существуют схемы предотвращения взаимоблокировок, в которых используется механизм упорядочения временных меток транзакций для предопределения ситуации взаимоблокировки.
Схема ожидания
В этой схеме, если транзакция запрашивает блокировку ресурса (элемента данных), который уже удерживается с конфликтующей блокировкой другой транзакцией, то может возникнуть одна из двух возможностей:
-
Если TS (T i ) <TS (T j ) — то есть T i , который запрашивает конфликтующую блокировку, старше, чем T j — тогда T i разрешается ждать, пока элемент данных станет доступным.
-
Если TS (T i )> TS (t j ) — то есть T i моложе, чем T j — тогда T i умирает. T i перезапускается позже со случайной задержкой, но с той же отметкой времени.
Если TS (T i ) <TS (T j ) — то есть T i , который запрашивает конфликтующую блокировку, старше, чем T j — тогда T i разрешается ждать, пока элемент данных станет доступным.
Если TS (T i )> TS (t j ) — то есть T i моложе, чем T j — тогда T i умирает. T i перезапускается позже со случайной задержкой, но с той же отметкой времени.
Эта схема позволяет старшей транзакции ждать, но убивает младшую.
Схема ожидания
В этой схеме, если транзакция запрашивает блокировку ресурса (элемента данных), который уже удерживается с конфликтующей блокировкой какой-либо другой транзакцией, может возникнуть одна из двух возможностей:
-
Если TS (T i ) <TS (T j ), то T i заставляет T j откатываться — то есть T i ранит T j . T j перезапускается позже со случайной задержкой, но с той же временной меткой.
-
Если TS (T i )> TS (T j ), то T i вынужден ждать, пока ресурс не станет доступен.
Если TS (T i ) <TS (T j ), то T i заставляет T j откатываться — то есть T i ранит T j . T j перезапускается позже со случайной задержкой, но с той же временной меткой.
Если TS (T i )> TS (T j ), то T i вынужден ждать, пока ресурс не станет доступен.
Эта схема позволяет младшей транзакции ждать; но когда более старая транзакция запрашивает элемент, принадлежащий более молодой, более старая транзакция вынуждает более молодую транзакцию прервать и отпустить элемент.
В обоих случаях транзакция, поступающая в систему на более позднем этапе, прерывается.
Предотвращение тупиков
Отмена транзакции не всегда практический подход. Вместо этого можно заранее использовать механизмы предотвращения тупиковой ситуации для обнаружения любой тупиковой ситуации. Такие методы, как «график ожидания», доступны, но они подходят только для тех систем, где транзакции имеют малый вес и имеют меньшее количество экземпляров ресурса. В громоздкой системе методы предотвращения тупиковых ситуаций могут хорошо работать.
График ожидания
Это простой метод, доступный для отслеживания возможных ситуаций тупика. Для каждой транзакции, входящей в систему, создается узел. Когда транзакция T i запрашивает блокировку элемента, скажем, X, которая удерживается какой-либо другой транзакцией T j , создается направленный край от T i до T j . Если T j освобождает элемент X, грань между ними отбрасывается, и T i блокирует элемент данных.
Система поддерживает этот график ожидания для каждой транзакции, ожидающей некоторые элементы данных, удерживаемые другими. Система постоянно проверяет, есть ли цикл на графике.
Здесь мы можем использовать любой из следующих двух подходов:
Во-первых, не допускайте никаких запросов на элемент, который уже заблокирован другой транзакцией. Это не всегда выполнимо и может вызвать голод, когда транзакция бесконечно ожидает элемент данных и никогда не сможет его получить.
Второй вариант — откатить одну из транзакций. Не всегда выполнимо откатить младшую транзакцию, поскольку она может быть важнее старой. С помощью некоторого относительного алгоритма выбирается транзакция, которая должна быть прервана. Эта транзакция называется жертвой, а процесс — выбором жертвы .