Распределенная взаимоблокировка. Методы предотвращения взаимоблокировок

Распределенная взаимоблокировка. Виды распределенных взаимоблокировок.

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

Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.

Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память).

Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер).

Проблема взаимоблокировок процессов возникает при борьбе за невыгружаемый ресурсы.

Условия необходимые для взаимоблокировки:

1. Условие взаимного исключения - в какой-то момент времени, ресурс занят только одним процессом или свободен.

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

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

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

Четыре стратегии избегания взаимоблокировок:

1. Пренебрежением проблемой в целом (вдруг пронесет).

2. Обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется).

3. Динамическое избежание тупиков.

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

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

Р1 ждет сообщений от Р4 и Р2

Имеет место недоступность буферов сообщений.

При наличии буфера возникает 2 вида блокировки:

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

2) Косвенная блокировка – если образуется замкнутый цикл узлов передачи, на каждом из которых очередь сообщений передаваемых на соседний узел предназначена для передачи на узел следующий за соседним (надо использовать структурный буферный пул)

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

Дата добавления: 2014-01-20