Билет 21 1. Взаимоблокировки процессов (тупики). Условия возникновения, методы и алгоритмы обнаружения тупиков

1. Страничная организация памяти. Многоуровневая организация виртуального адресного пространства. Пример схемы двухуровневой страничной организации.

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

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

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

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

Тупики также могут иметь место в ситуациях, не требующих выделенных ресурсов. Например, в системах управления базами данных процессы могут локализовывать записи, чтобы избежать гонок (см. главу "Синхронизация процессов"). В этом случае может получиться так, что один из процессов заблокировал записи, требуемые другому процессу и наоборот. Т.о. тупики могут иметь место, как на аппаратных, так и на программных ресурсах.

Условия возникновения тупиковых ситуаций

1. Взаимное исключение. Каждый ресурс в данный момент или отдан ровно одному процессу, или недоступен.

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

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

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

Стратегии борьбы с взаимоблокировками:

1. Пренебрежение проблемой в целом.

2. Обнаружение и устранение (восстановление).

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

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