Устранение тупиковых ситуаций
Единственным способом выхода из тупиковой ситуации (deadlock) является снятие блокировки одним из потоков. Это означает прерывание или отказ от транзакции. Система может либо предупреждать захваты либо допускать их, но затем соответствующим образом обрабатывать. Оказалось, что стандартные протоколы работы с базами данных достаточно редко приводят к образованию захватов, поэтому было признано целесообразным допускать появление захватов при условии, что разработаны механизмы их обнаружения. Особую проблему составляет обнаружение захватов в распределенных базах данных, так как нет простого способа, с помощью которого один узел сети может узнать, какие блокировки наложены в данный момент другим узлом.
Два технических приема используются для обнаружения тупиковой ситуации. Первый – это установка таймера перед совершением транзакции. Если время для ее совершения вышло, то транзакция прерывается, блокировка снимается, что дает возможность другому потоку или процессу закончить свою операцию. Это решение очень просто реализовать, но его недостатком является то, что врожденно медленные транзакции могут потерять шанс быть выполненными.
Другим методом является создание специальной структуры данных, которая моделирует граф ожиданий (waits-for graph) – бинарное отношение ожидания между транзакциями. Узлами графа являются транзакции, а дугами – факты ожидания. Так, например, дуга (i, j) (из узла i в узел j) существует, если транзакция i ожидает освобождения блокировки, наложенной транзакцией j. Очевидно, что тупиковой ситуации в этой модели соответствует цикл. Отметьте, что" длина цикла (количество его дуг) может быть более двух.
Алгоритмы обнаружения циклов в графах давно разработаны. Графы обычно хранятся в виде динамических списков, то есть каждый узел хранит список блокировок – указателей на транзакции, которые ему мешают. Сам список обычно защищен семафором. С целью экономии времени процессора детектор циклов включается лишь при необходимости или периодически. Цикл считается обнаруженным, если в списке транзакций, которые тормозят данную, присутствует транзакция, в списке которой есть указатель на исходную. Эту фразу, вероятно, придется прочесть несколько раз.
Отметим, что библиотека классов MFC поддерживает механизмы синхронизации, но детали их реализации скрыты от разработчика. Тем не менее он может использовать их, не заботясь о деталях реализации. Главным требованием при этом, как и при работе с любыми другими объектами классов MFC, является соблюдение протокола, описанного в интерфейсе класса.
К сожалению, время, отведенное для написания книги, закончилось и мне не удастся привести и описать примеры приложений, иллюстрирующих использование синхронизирующих объектов ядра Windows, хотя такие примеры разработаны и достаточно давно используются в вышеупомянутом учебном центре.