Распределенная обработка данных. Найханова Л.В. - 54 стр.

          Транзакция А                     Время                    Транзакция В
                -                             |                           -
                -                             |                           -
        Блокировка р1 без                    t1                           -
         взаимного                            |                           -
             доступа                          |                           -
                -                            t2                   Блокировка р2 без
                -                             |                    взаимного
                -                             |                        доступа
        Блокировка р2 без                    t3                           -
         взаимного                            |                           -
             доступа                          |                           -
            Ожидание                         t4                   Блокировка р1 без
            Ожидание                          |                взаимного доступа
            Ожидание                          |                       Ожидание
            Ожидание                         ↓                        Ожидание
            Ожидание
                            Рис. 5.10. Пример тупиковой ситуации
     Тупиковая ситуация возникает тогда, когда две или более транзакции одновременно
находятся в состоянии ожидания, причем для продолжения работы каждая из транзакций
ожидает прекращения выполнения другой транзакции. На рис. 5.10 показана тупиковая
ситуация, включающая две транзакции, однако в принципе возможны тупиковые
ситуации с участием трех, четырех и более транзакций. Однако эксперименты с системой
System R показали, что на практике никогда не встречаются тупиковые ситуации с
участием более чем двух транзакций.
     Желательно, чтобы при возникновении тупиковой ситуации система могла обна-
ружить ее и найти из нее выход. Для обнаружения тупиковой ситуации следует обна-
ружить цикл в диаграмме состояний ожидания, т.е. в перечне “транзакций, которые
ожидают окончания выполнения других транзакций”. Поиск выхода из тупиковой си-
туации состоит в выборе одной из заблокированных транзакций в качестве жертвы и
отмене ее выполнения. Таким образом, с нее снимается блокировка, а выполнение другой
транзакции может быть возобновлено.
     На практике не все системы в состоянии обнаружить тупиковую ситуацию.
Например, в некоторых из них используется хронометраж выполнения транзакций, и
сообщение о возникновении тупиковой ситуации поступает, если транзакция не
выполняется за некоторое предписанное заранее время.
     Рассмотрим различные методы разрешения тупиковых ситуаций.
Способность к упорядочению
     В предыдущих разделах были описаны некоторые основы, необходимые для объяс-
нения ключевого понятия “способность к упорядочению”, которое является обще-
принятым критерием правильности управления параллельной обработкой кортежей.
Точнее говоря, чередующееся выполнение заданного множества транзакций будет
верным, если оно упорядочено, т.е. при его выполнении будет получен такой же
результат, как и при последовательном выполнении тех же транзакций. Обосновать это
утверждение помогут следующие замечания:
     1. Отдельные транзакции считаются верными, если при их выполнении база данных
        переходит из одного непротиворечивого состояния в другое непротиворечивое со-

54