• Вести информацию о текущем распределении элементов данных для транзакций.
• Предоставить алгоритм, позволяющий определить, вошла ли система в состояние тупика.
• Восстановление из тупика, когда алгоритм обнаружения определяет, что тупик существует.
Обнаружение тупика
Простой способ обнаружить состояние тупика — с помощью графика ожидания. Этот граф строится и поддерживается системой. В графе ожидания создается один узел для каждой транзакции, которая выполняется в данный момент. Всякий раз, когда транзакция Ti ожидает блокировки элемента X, который в данный момент заблокирован транзакцией Tj, в графе ожидания создается направленное ребро (Ti-> Tj). Когда Tj снимает блокировку с элементов, которые Ti ожидал, направленный край удаляется из графика ожидания. У нас есть состояние тупика, если и только если у графика ожидания есть цикл. Тогда каждая транзакция, участвующая в цикле, считается заблокированной. Чтобы обнаружить взаимоблокировки, система должна поддерживать график ожидания и периодически вызывать алгоритм, который ищет цикл в графике.
Чтобы проиллюстрировать эти концепции, рассмотрим следующий график ожидания на рисунке. Вот:
Транзакция T25 ожидает транзакции T26 и T27.
Транзакции T27 ожидают транзакции T26.
Транзакция T26 ожидает транзакции T28.
Этот график ожидания не имеет цикла, поэтому нет состояния тупика.
Предположим теперь, что транзакция T28 запрашивает элемент, удерживаемый T27. Затем ребро T28 ————> T27 добавляется к графику ожидания, что приводит к новому состоянию системы, как показано на рисунке.
На этот раз график содержит цикл.
T26 ——> T28 ——-> T27 ————> T26
Это означает, что транзакции T26, T27 и T28 все заблокированы.
Вызов алгоритма обнаружения тупиковой ситуации
Вызов алгоритма обнаружения взаимоблокировки зависит от двух факторов:
• Как часто возникает тупик?
• Сколько транзакций будет затронуто тупиком?
Если часто возникают взаимоблокировки, то алгоритм обнаружения должен вызываться чаще, чем обычно. Элементы данных, выделенные для заблокированных транзакций, будут недоступны для других транзакций до тех пор, пока не будет устранена тупиковая ситуация. В худшем случае мы будем вызывать алгоритм обнаружения каждый раз, когда запрос на распределение не может быть удовлетворен немедленно.
Восстановление из тупика
Когда алгоритм обнаружения определяет, что существует тупик, система должна восстановиться из тупика. Наиболее распространенным решением является откат одной или нескольких транзакций для выхода из тупика. Выбор транзакции для отмены называется «Выбор жертвы».
Выбор жертвы тупика
В приведенном ниже графике ожидания транзакции T26, T28 и T27 заблокированы. Чтобы устранить взаимоблокировку, необходимо откатить одну из транзакций из этих трех.
Мы должны откатить те транзакции, которые повлекут за собой минимальные затраты. При обнаружении тупика можно выбрать, какую транзакцию отменить, используя следующие критерии:
• транзакция с наименьшим количеством блокировок
• транзакция, которая выполнила наименьшую работу
• Транзакция, наиболее удаленная от завершения
отмена
Как только мы решили, что конкретная транзакция должна быть откатана, мы должны определить, насколько далеко откатить эту транзакцию. Самое простое решение — полный откат; Прервите транзакцию и перезапустите ее. Однако более эффективно откатить транзакцию только настолько, насколько это необходимо для выхода из тупика. Но этот метод требует, чтобы система поддерживала дополнительную информацию о состоянии всей работающей системы.
Проблема Голодания
В системе, где выбор жертв основывается главным образом на факторах стоимости, может случиться так, что одна и та же транзакция всегда выбирается в качестве жертвы. В результате эта транзакция, которая никогда не завершается, может быть выбрана в качестве жертвы только (маленькое) конечное число раз. Наиболее распространенным решением является включение количества откатов в фактор стоимости.
Обнаружение против Предотвращения
В схемах, основанных на предотвращении, механизм прерывания используется преимущественно во избежание взаимоблокировок. С другой стороны, в схемах, основанных на обнаружении, транзакции в цикле взаимоблокировки удерживают блокировки, которые препятствуют выполнению других транзакций. Положение системы уменьшается в случае обнаружения, поскольку многие транзакции могут быть заблокированы, ожидая получения блокировок, удерживаемых в настоящее время заблокированными транзакциями.
Это фундаментальный компромисс между этими подходами предотвращения и обнаружения к тупикам: потеря работы из-за упреждающих прерываний и потеря работы из-за заблокированных транзакций в цикле тупика. Мы можем увеличить частоту проверки циклов взаимоблокировки и тем самым уменьшить объем работы, потерянной из-за заблокированных транзакций, но это влечет за собой соответствующее увеличение стоимости механизма обнаружения взаимоблокировок.
Обнаружение взаимоблокировки предпочтительно, если разные транзакции редко обращаются к одним и тем же элементам одновременно. Это может произойти, если транзакции короткие, и каждая транзакция блокирует только несколько элементов или если загрузка транзакции незначительна.
С другой стороны, если транзакции длинные и каждая транзакция использует много элементов, или если нагрузка транзакции достаточно велика, может быть выгодно использовать схему предотвращения тупиковых ситуаций.
По материалам compshop.kz.