2.3. Проблема тупика

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

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

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

Особенно большое значение решение проблемы тупика приобретает в системах реального времени, в вычислительных сетях.

Таким образом, проблема тупика - глобальная системная проблема, в рамках которой решаются следующие задачи:

• предотвращение тупиков;

• обход тупиков;

• распознавание тупиков;

• вывод системы из тупика и восстановление ее работоспособности.

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

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

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

Прогнозирование поведения системы при решении задачи обхода тупика основано на тех же методах, что и решение задачи распознавания тупика.

Если оказалось, что система все-таки попала в тупик, то необходимо уметь распознать эту ситуацию. Цель задачи распознавания тупика - установить сам факт возникновения тупиковой ситуации и определить объекты системы (процессы и ресурсы), вовлеченные в нее, то есть определить причины, приведшие к тупику.

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

2.3.1. Определение тупика

Более точное определение тупика требует использования математической модели ВС.

Определим систему как пару

 = {  ,  },

где  = {S₁ , S₂ , ...} - множество состояний системы,  = { p₁ , p₂ , ...} - множество процессов, протекающих в системе.

В системе, которая определяется таким образом, процесс p_i   представляет собой частичную функцию, отображающую состояния системы в непустые подмножества ее же состояний:

p_{i :}   {  }.

Процесс p_i может быть определен не для всех состояний.

Если p_i определен на состоянии S_l, то p_i(S_l) - область его значений, то есть процесс p_i может изменить состояние системы из S_l в состояние S_k  p_i(S_l ). Для перевода системы из состояния S_l в состояние S_k процесс должен выполнить некоторую операцию. Для обозначения перевода процессом p_i системы  из состояния S_l в состояние S_k введем обозначение

p_i

S_l  S_k.

Состояние системы может измениться только при выполнении процессом одной из следующих операций:

• запрос на ресурс;

• приобретение ресурса;

• освобождение ресурса.

Введем еще одно обозначение: нотация

_*

S_l  S_n

означает

(a) S_l = S_n или

p_i

(b)  p_i : S_l  S_n или

p_{i *}

(c)  S_k &  p_i : (S_l  S_k) & (S_k  S_n).

То есть система может быть переведена из состояния S_l в состояние S_n посредством h операций (h  0), которые могут быть выполнены m различными процессами (m  0).

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

Процесс p_i заблокирован в состоянии S_l, если не существует ни одного такого состояния S_k , что

p_i

S_l  S_k .

То есть заблокированный процесс не может выполнить никакой операции по изменению состояния системы.

Процесс p_i находится в тупике в состоянии S_l, если для любого состояния S_k, такого что

_*

S_l  S_k

процесс p_i будет заблокирован в этом состоянии. То есть процесс находится в тупике в состоянии S_l, если он заблокирован в этом состоянии и останется заблокированным в любом другом состоянии S_k, в которое система может перейти из этого состояния S_l при выполнении любых операций любыми другими процессами (процесс останется заблокированным, как бы ни изменялось состояние системы в будущем).

Состояние S_l называется тупиковым, если существует процесс p_i, находящийся в тупике в этом состоянии.

Состояние S_l называется безопасным, если любое состояние S_k, такое что

_*

S_l  S_k,

не будет состоянием тупика.

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

Рассмотрим пример системы, в которой есть как тупиковое, так и безопасное состояние. Пусть  = {S₁, S₂, S₃, S₄, S₅} - множество состояний системы,  = {p₁, p₂} - множество выполняющихся в ней процессов (рис.2.9).

p₁ p₂

p₂ p₁

S ₁ S₂ p₁ S₃ S₄ p₁ S₅

Р ис.2.9. Пример системы с тупиковым и безопасным состоянием

Состояние S₁ является состоянием тупика. Состояния S₄ и S₅ являются безопасными состояниями. Состояния S₂ и S₃ не являются безопасными состояниями, но не являются и тупиковыми.