Взаимоблокировка. Причины возникновения. Классификация алгоритмов борьбы с взаимоблокировкой

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

Ресурсы:

· выгружаемые («безболезненно» забрать у владеющего им процесса);

· невыгружаемые (нельзя забрать, не уничтожив результаты вычислений).

Условия взаимоблокировки:

1. Условие взаимного исключения.

Каждый ресурс отдан или одному процессу, или свободен.

2. Условие удержания и ожидания.

Процессы могут удерживать ресурсы и запрашивать новые.

3. Условие отсутствия принудительной выгрузки ресурса.

У процесса нельзя забрать ранее полученные ресурсы. Он должен сам их освободить.

4. Условие циклического ожидания.

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

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

Выход из взаимоблокировки:

· восстановление при помощи принудительной выгрузки ресурса;

· восстановление через откат;

· восстановление путем уничтожения процессов.

Избежание взаимоблокировок.

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

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

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

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

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

Сети.