Распознавание тупика требует дальнейшего восстановления

Восстановление можно интерпретировать как запрет постоянного пребывания в опасном состоянии. Существуют следующие методы восстановления:

· принудительный перезапуск системы, характеризующийся потерей информации обо всех процессах, существовавших до перезапуска;

· принудительное завершение процессов, находящихся в тупике;

· принудительное последовательное завершение процессов, находящихся в тупике с последующим вызовом алгоритма распознавания после каждого завершения до исчезновения тупика;

· перезапуск процессов, находящихся в тупике, с некоторой контрольной точки, то есть из состояния, предшествовавшего запросу на ресурс;

· перераспределение ресурсов с последующим последовательным перезапуском процессов, находящихся в тупике.

Основные издержки восстановления составляют потери времени на повторные вычисления, которые могут оказаться весьма существенными. К сожалению, в ряде случаев восстановление может стать невозможным: например, исходные данные, поступившие с каких-либо датчиков, могут уже измениться, а предыдущие значения – безвозвратно потеряны.

Контрольные вопросы: Проблемная ситуация Представим себе двух студентов, которым нужно поработать с одной и той же книгой, имеющейся в библиотеке в единственном экземпляре. Они одновременно пришли в библиотеку, но один из них сначала пошел в читальный зал и, заняв единственное свободное место, отправился в книжное хранилище, а другой — наоборот, начал с того, что получил книгу, а потом пошел в читальный зал искать место. В результате ни один из них не может выполнить работу, так как для этого им не хватает необходимого ресурса. Можно ли считать, что в данном случае произошла взаимная блокировка, или, другими словами, клинч? Ответ: Нет, в данном случае мы имеем дело не с клинчем, а с очередью. Действительно, студент, ожидающий в читальном зале, может быть «разблокирован» в результате освобождения какого-либо другого места в читальном зале, а затем он, выполнив свою работу и сдав книгу, «разблокирует» другого студента, ожидающего в книжном хранилище. Для того чтобы ситуация могла быть названа клинчем, следует дополнить задачу еще одним условием—в читальном зале имеется только одно рабочее место. . Вопросы для самоконтроля:

Какие вычислительные процессы называются параллельными и почему? Какие параллельные процессы называются независимыми, а какие – взаимодейтсвующими?
Объясните команду “проверка и установка”.
Что такое самфоры Дейкстры? Чем обеспечивается взаимное исключение при выполнении P- и V-примитивов?
Что такое mutex?
Изложите алгоритм решения задачи “поставщик-потребитель”.
Изложите алгоритм решения задачи “читатели-писатели”.
Что такое монитора Хоара?

Вопросы для самоконтроля:

Что такое тупиковое состояние? Перечислите условия, при которых возникает тупик.
Какие стратегии работы с тупиками вы знаете?
Какие графические средства используются для работы с тупиками?
Что собой представляет «предотвращение тупика»? Как его можно реализовать?
Что представляет собой «обход тупика»? Приведите алгоритм банкира Дейкстры.
Что такое «опасное состояние»? Приведите пример опасного состояния.
Изложите алгоритм обнаружения тупика по наличию замкнутой цепочки запросов.

Домашнее задание: Конспект лекций