Взаимоблокировки (тупики)

Коффман и другие исследователи доказали, что для возникновения тупиковой ситуации должны выполняться четыре условия [37].

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

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

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

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

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

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

Рассмотрим методы обнаружения взаимоблокировок.

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

Например, пусть система из семи процессов (A, B, C, D, E, F, G) и шести ресурсов (R, S, T, V,W, U) в некоторый момент соответствует следующему списку [17].

1. Процесс A занимает ресурс R и хочет получить ресурс S.

Вопрос: заблокирована ли эта система, и если да, то какие процессы в этом участвуют?

Чтобы ответить на этот вопрос, нужно составить граф ресурсов и процессов (рис. 5.14).

Рис. 5.14. Граф ресурсов и процессов

Этот граф содержит цикл, указывающий, что процессы D, E, G заблокированы (зрительно легко видно). Однако в этом случае в операционной системе необходима реализация формального алгоритма, выявляющего тупики.

Рассмотрим возможность обнаружения взаимоблокировок при наличии нескольких ресурсов каждого типа. Пусть имеется множество процессов P={P₁, P₂,... P_n}, всего n процессов, и множество ресурсов E={E₁, E₂,... E_m}, где m – число классов ресурсов. В любой момент времени некоторые из ресурсов могут быть заняты и, соответственно, недоступны. Пусть А – вектор доступных ресурсов A={A₁, A2,... A_m}. Очевидно, что A_j<= E_j, j = 1, 2, …, m.

Введем в рассмотрение две матрицы:

C={c_i,j| i = 1, 2,…, n; j = 1, 2, …, m} – матрица текущего распределения ресурсов, где c_i,j – количество ресурсов j-ого класса, которые занимает процессP_i ;

R={r_i,j| i = 1, 2,…, n; j = 1,2, …, m} – матрица требуемых (запрашиваемых) ресурсов, r_i,j – количество ресурсов j-ого класса, которые хочет получить процесс P_i.

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

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

Алгоритм обнаружения тупиков состоит из следующих шагов.

1. Отыскивается процесс P_i, для которого i-я строка матрицы R меньше вектора A, т.е. R_i <= A, или r_j,I <Aj, j=1, 2, …, m.
2. Если такой процесс найден, это означает, что он может завершиться, а следовательно – освободить занятые ресурсы. Найденный процесс маркируется, и далее прибавляется i-я строка матрицы С к вектору А, т.е. A_j = A_j + c_i,j , j=1, 2, …, m. Возвращаемся к шагу 1.
3. Если таких процессов не существует, работа алгоритма заканчивается. Немаркированные процессы попадают в тупик.

Когда нужно искать возникновение тупиков? Можно, конечно, проверять систему каждый раз, когда запрашивается очередной ресурс, это позволит обнаружить тупик максимально рано, но приведет к большим издержкам процессорного времени. Поэтому период проверки нужно выбрать: например, каждые К (сколько – нужно определить!) минут или когда процессор слабо загружен.

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

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

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

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

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