Обнаружение тупиков

Недостатки алгоритма банкира

Распределение ресурсов согласно алгоритму банкира

Пример перехода из надежного состояния в ненадежное

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

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

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

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

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

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

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

Обнаружение тупика – установление факта, что возникла тупиковая ситуация, и определение процессов и ресурсов, вовлеченных в эту тупиковую ситуацию. Алгоритмы обнаружения тупиков, как правило, применяются в системах, где выполняются первые три необходимых условия возникновения тупиковой ситуации. Эти алгоритмы затем определяют, не создался ли режим кругового ожидания. Одним из способов обнаружения тупиков является редукция ориентированного графа распределения ресурсов и запросов. Редукция графа на конкретный процесс изображается исключением стрелок, идущих к этому процессу от резервов (т.е. ресурсов, выделенных данному процессу) и стрелок к ресурсам от этого процесса (т.е. текущих запросов данного процесса на выделение ресурсов). Если граф можно редуцировать на все процессы, значит тупиковой ситуации нет, а если этого сделать нельзя, то все “нередуцируемые” процессы образуют набор процессов, вовлеченных в тупиковую ситуацию.