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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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