Условия возникновения тупиков

Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.

1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.

3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.

Для образования тупика необходимым и достаточным является выполнение всех четырех условий.

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

Основные направления борьбы с тупиками

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

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

· Игнорирование проблемы в целом

· Предотвращение тупиков

· Обнаружение тупиков

· Восстановление после тупиков

Игнорирование проблемы тупиков

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

Любая ОС, имеющая в ядре ряд массивов фиксированной размерности, потенциально страдает от тупиков, даже если они не обнаружены. Таблица открытых файлов, таблица процессов, фактически каждая таблица являются ограниченными ресурсами. Заполнение всех записей таблицы процессов может привести к тому, что очередной запрос на создание процесса может быть отклонен. При неблагоприятном стечении обстоятельств несколько процессов могут выдать такой запрос одновременно и оказаться в тупике. Следует ли отказываться от вызова CreateProcess, чтобы решить эту проблему?

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

Вопрос 24.

В 1971 г. Коффман, Элфик и Шошани сформулировали следующие четыре условия для возникновения тупиков.

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

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (которые при этом обычно удерживаются другими процессами).

3. Условие неперераспределяемости (No preemtion). Ресурс, данный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам цепи.

Для тупика необходимо выполнение всех четырех условий.

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

Вопрос 25.

Основные направления борьбы с тупиками:

1. Игнорирование проблемы в целом;

2. Предотвращение тупиков;

3. Обнаружение тупиков;

4. Восстановление после тупиков.

1. Игнорирование проблемы тупиков.

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

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

2. Предотвращение тупиков.

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

Алгоритм банкира – тщательное распределение ресурсов.

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

Надежное состояние – это такое состояние, для которого имеется, по крайней мере, одна последовательность событий, которая не приведет к взаимоблокировке.

Модель алгоритма основана на действиях банкира, который, имея капитал, выдает кредиты:

1. Предположим, что у системы в наличии n устройств, например, лент.

2. ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n.

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

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

5. В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.

Примером надежного состояния для системы с тремя пользователями и одиннадцатью устройствами, где 9 устройств задействовано, а 2 в резерве:

Пусть текущая ситуация такова:

Пользователь	Максимальная потребность в ресурсах	Выделенные ресурсы
Первый
Второй
Третий

 

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

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

Условия:

Число пользователей и число ресурсов фиксировано;

Число работающих пользователей должно оставаться постоянным;

Алгоритм требует, чтобы клиенты гарантированно возвращали ресурсы.

Должны быть заранее указаны максимальные требования процессов в ресурсах (чаще всего эта информация отсутствует).

Вопрос 26.

Алгоритм банкира

 

Вопрос 27.

Иерархия памяти компьютера

 

Вопрос 28.

Алгоритм банкира