Проблема тупиков

Приведенный пример позволяет проиллюстрировать проблему синхронизации, на­зываемую тупиками, дедлоками (deadlocks) или клинчами (clinch) и состоящую во вза­имных блокировках процессов (ряд процессов удерживает ресурсы, запрашиваемые другими процессами, и в то же время запрашивает ресурсы, удерживаемые другими).

Если переставить местами операции P(e) и P(b) в программе-писателе, то при не­котором стечении обстоятельств рассматриваемые два процесса могут заблокиро­вать друг друга.

Пусть процесс-писатель первым войдет в критическую секцию и обнаружит от­сутствие свободных буферов. Картина примет следующий вид.

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

В рассмотренном примере тупик был образован двумя процессами, но взаимно бло­кировать друг друга могут и большее число процессов.

Решение проблемы тупиков требует решения следующих задач:

· предотвращение тупиков,

· распознавание тупиков,

· восстановление системы после тупиков.

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

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

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

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

Из всего вышесказанного ясно, что использовать семафоры нужно очень осторож­но, так как одна незначительная ошибка может привести к останову системы (или по крайней мере нескольких процессов).

Для того, чтобы облегчить написание корректных программ, было предложено вы­сокоуровневое средство синхронизации, называемое монитором. Монитор - это на­бор процедур, переменных и структур данных. Процессы могут вызывать процедуры монитора, но не имеют доступа к внутренним данным монитора. Мониторы имеют важ­ное свойство, которое делает их полезными для достижения взаимного исключения: только один процесс может быть активным по отношению к монитору. Компилятор об­рабатывает вызовы процедур монитора особым образом. Обычно, когда процесс вы-зывает процедуру монитора, то первые несколько инструкций этой процедуры прове­ряют, не активен ли какой-либо другой процесс по отношению к этому монитору. Если да, то вызывающий процесс приостанавливается, пока другой процесс не освободит монитор. Таким образом, исключение входа нескольких процессов в монитор реализу­ется не программистом, а компилятором, что делает ошибки менее вероятными.