Взаимоблокировки

Лекция 3

Для возникновения взаимоблокировки (тупика) в системе должно выполняться 4 условия:

1. Условие взаимного исключения – каждый ресурс в каждый момент времени отдан ровно одному процессу или доступен.

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

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

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

Взаимоблокировки моделируются при помощи направленных графов

Пример 1: Типичная простейшая ситуация

Пример 2:

A, B, C, D, E, F, G – процесс

R, S, T, V, W, N – ресурс

RàAàS -?

Анализ на наличие циклов

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

P = {P1, P2, …, Pn} n – число процессов

E = {E1, E2, …, Em} m – число классов ресурсов

А – вектор доступных ресурсов = {A1, A2, …, Am}

Aj≤ Ej j=(1,m)

С – матрица текущего распределения ресурсов = {c_ij i=(1,n) j=(1,m)}

c_ij - количество ресурсов j-ого класса, которое занимает процесс Pi.

R – матрица требуемых или запрашиваемых ресурсов = {r_ij i=(1,n) j=(1,m)}

r_ij - количество ресурсов j-ого класса, которое запрашивает процесс Pi.

Справедливо, m соотношений по ресурсам:

В исходном состоянии все процессы немаркированы (неотмечаны).

1. Ищется процесс Pi, для которого i-ая строка R меньше вектора А. 2…

2. Если такой процесс найден, он маркируется и i-ая строка C прибавляется к вектору А. 3…

3. Переход на шаг 1

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

Взаимоблокировки могут проверяться:

1. Когда запрашивается очередной ресурс (максимально рано обнаружение, но накладки по процессору)

2. Через определенные промежутки времени или при низкой загрузке процессора