Двухфазная локализация

Родственные проблемы

Нарушение условия кругового ожидания

Нарушение принципа неперераспределяемости.

В соответствии со вторым принципом Хавендера можно отбирать ресурсы у удерживающих их процессов до завершения этих процессов. Если бы это было всегда возможно, то можно было бы добиться невыполнения третьего условия возникновения тупиков. С проблемой отнятия ресурсов у удерживающих их процессов мы сталкивались в 7.7.1. Если процесс в течение некоторого времени использует определенные ресурсы, а затем освобождает эти ресурсы, он теряет всю работу, проделанную до настоящего момента. Весь вопрос в цене данного решения, которая может быть слишком высокой, если подобная ситуация возникает часто.

Другим недостатком данной схемы может быть дискриминация отдельных процессов, у которых постоянно отбирают ресурсы.

Осталось одно условие. Циклического ожидания можно избежать несколькими путями.

Один из них действовать в соответствии с правилом, согласно которому каждый процесс может иметь только один ресурс в каждый момент времени. Если нужен второй ресурс - освободи первый. Очевидно, что для многих процессов это не приемлемо, например, для тех, которые распечатывают большие файлы с ленты на принтер.

Другой способ - присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке возрастания номеров. Тогда круговое ожидание возникнуть не может.

Небольшой вариацией этого алгоритма будет нумерация в возрастающем порядке не ресурсов, а запросов процесса. После последнего запроса и освобождения всех ресурсов можно разрешить процессу опять осуществит первый запрос.

Очевидно, что невозможно найти порядок, который удовлетворит всех.

Хотя в общем случае рассмотренные способы предотвращения тупиков не кажутся перспективными, для отдельных специфичных приложений подобные алгоритмы широко используются. Например, во многих СУБД часто требуется локализация нескольких записей, и затем изменение всех локализованных записей. Когда несколько процессов работают с базой данных, есть реальная опасность тупика. Типичный в подобных ситуациях подход - двухфазная локализация. В первой фазе процесс пытается локализовать все записи, которые ему нужны за один раз. Если это ему удалось, то он переходит ко второй фазе, выполняя изменения и освобождая записи. В первой фазе не делается реальной работы.

Если в первой фазе некоторые записи, которые ему нужны, уже локализованы, процесс освобождает все, что он локализовал и пытается повторить первую фазу. В известном смысле этот подход напоминает требование захвата всех ресурсов заранее. Естественно, что это срабатывает только в тщательно организованных программах, которые могут быть приостановлены в течение первой фазы и рестартованы впоследствии. Далеко не все программы укладываются в эту схему.

Дата добавления: 2014-12-16