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

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

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

Тупики не ресурсного типа

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

Голод (starvation)

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

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

Заключение.

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

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

Считается, что в будущих системах тупики станут более критичным фактором, так как системы будущего:

• будут в большей степени ориентированы на параллельную работу
• будет преимущественно реализовываться динамическое распределение ресурсов
• растет тенденция рассматривать данные как ресурс, в связи с чем количество ресурсов возрастет.

Более подробно данная тема рассмотрена в [9,12,22 и др.]