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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. Репликация данных. Согласование реплик. Варианты внесения изменений в реплицированные данные.

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

2 варианта внесения изменений в реплицированных данных:

3. Слабая согласованность – изменение внесенное в одну из реплик немедленно становится видно клиенту. Далее это изменение распространяется на другие реплики. Данные реплик остаются несогласованными.

4. Строгая согласованность – изменение становится доступным клиенту только после его распространения на все реплики.

Существует несколько способов согласования реплик:

1) Чтение любой – запись во все (Read-Any –Write All). Недостаток: в момент записи некоторые серверы не работоспособны.

2) Запись в доступные (Available-Copies). Недостаток: возможность появления несогласованных копий

3) Кворум (Quorum). Пусть имеется n реплик. Изменения записываются в w реплик. Клиент при чтении файла обязательно обращается к r репликам. Утверждается что если w+r > n, то среди любых произвольно выбранных r реплик всегда найдется хотя бы одна из w реплик, в которую были записаны последние обновления. Пример: n=8, r=2, w=8. При r=1, w=n получаем “чтение любой-запись во все”