Обход тупиков, алгоритм банкира. Обнаружение тупиков и восстановление системы.

Исключение условий (100%) возникновения тупика. Часто приводит к нерациональному расходованию ресурсов. Требуется исключение только одного из условий Хавендера. Оправдано в тех системах, где нужно 100% исключить вероятность возникновения. Недостаток: дорого.

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

Алгоритм банкира.

Банкир (ведет себя соответственно). Клиенты – процессы.

При удовлетворении запроса – ресурс выделяется, если система останется в надежном состоянии. Надежное состояние – если все процессы системы в течение конечного времени смогут завершить свою работу. Недостатки алгоритма: а) для каждого процесса, необходимо указать максимальное количество ресурсов, необходимых для выполнения (сообщается «банкиру» - ОС). При динамическом распределении ресурсов трудно оценить максимальные потребности пользователей. б) он требует, что бы число работающих пользователей оставалось постоянным. в) не слишком корректное использование конечного времени выполнения. г) алгоритм требует, чтобы клиенты гарантированно возвращали ресурсы. В реальных системах требуются гораздо более конкретные гарантии. ПРИМЕР 1: пусть всего имеется 12 ресурсов. В сумме по таблице выделено 1+4+5 = 10, значит 12 – 10 = 2 – резерв. Надежное состояние, так как потоку  2 можно отдать резерв, он завершится и освободит ресурсы, которые можно перераспределить между 1 и 3. В ненадежное состояние система перейдет, если первый поток запросит 2 ресурса и они ему будут выделены. ПРИМЕР 2: пусть всего имеется 12 ресурсов. В сумме по таблице выделено 8+2+1 = 11, значит 12 – 11 = 1 – резерв. Ненадежное состояние. 3) метод обнаружения и восстановления. Обнаружение тупика – установление факта входа процесса в тупиковую ситуацию (как правило, проверяется наличие фактов кругового ожидания) и определение потоков и ресурсов. Восстановление системы: 1) принудительное завершение тупика (то есть нарушение условия кругового ожидания). 2) использование контрольных точек, при которых тупика ещё не было (откат). 3) приостановка потока с временным освобождением ресурса. По возможности лучше убить тот процесс, который может быть без ущерба возвращен к началу (такие процессы называются идемпотентными), например, компиляция. Наиболее предпочтителен метод обнаружения и восстановления. В системах реального времени все методы сводятся к методу предотвращения тупиков. Выводы: В большинстве современных ОС используется комбинация методов: -              Предотвращения. -              Обхода. -              Обнаружения. При этом от процессов не требуется, какой либо дополнительной информации, а вся ответственность за тупики ложиться на ОС. Сегодня проблема тупиков стоит все острее т.к.:

1. Увеличивается количество одновременно выполняющихся процессов.
2. Ресурсы распределяются динамически (во время выполнения программы).
3. Увеличивается количество типов ресурсов (сейчас данные рассматриваются как ресурс).