Тупик — ситуация, когда процесс ожидает какого-то события, которое никогда не произойдет.
Условия возникновения тупиков
Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.
- Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.
- Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.
- Условие неперераспределяемости (No preemption). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
- Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.
Обычно тупик моделируется циклом в графе, состоящем из узлов двух видов: прямоугольников — процессов и эллипсов — ресурсов. Стрелки, направленные от ресурса к процессу, показывают, что ресурс выделен данному процессу. Стрелки, направленные от процесса к ресурсу, означают, что процесс запрашивает данный ресурс.
Пример графа:
[Процесс P1] --> [Ресурс R1]
[Ресурс R1] --> [Процесс P2]
[Процесс P2] --> [Ресурс R2]
[Ресурс R2] --> [Процесс P1]Основные направления борьбы с тупиками
Методы предотвращения взаимоблокировок ориентированы главным образом на нарушение первых трех условий путем введения ряда ограничений на поведение процессов и способы распределения ресурсов. Методы обнаружения и устранения менее консервативны и сводятся к поиску и разрыву цикла ожидания ресурсов.
Основные направления борьбы с тупиками:
- Игнорирование проблемы в целом
- Предотвращение тупиков
- Обнаружение тупиков
- Восстановление после тупиков
Игнорирование проблемы тупиков
Простейший подход — не замечать проблему тупиков. Для того чтобы принять такое решение, необходимо оценить ущерб производительности системы. Проектировщики обычно не желают жертвовать производительностью системы или удобством пользователей для внедрения сложных и дорогостоящих средств борьбы с тупиками.
Заполнение всех записей таблицы процессов может привести к тому, что очередной запрос на создание процесса может быть отклонен. При неблагоприятном стечении обстоятельств несколько процессов могут выдать такой запрос одновременно и оказаться в тупике.
Подход большинства популярных ОС (Unix, Windows и др.) состоит в том, чтобы игнорировать данную проблему в предположении, что маловероятный случайный тупик предпочтительнее, чем правила, заставляющие пользователей ограничивать число процессов и открытых файлов.
Способы предотвращения тупиков путем тщательного распределения ресурсов. Алгоритм банкира
Наиболее известен алгоритм банкира, предложенный Дейкстрой, который базируется на так называемых безопасных или надежных состояниях (safe state). Безопасное состояние — это такое состояние, для которого имеется по крайней мере одна последовательность событий, которая не приведет к взаимоблокировке.
Суть алгоритма состоит в следующем:
- Предположим, что у системы в наличии n устройств, например лент.
- ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n.
- Пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени.
- Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течение конечного времени.
- В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.
Рассмотрим пример надежного состояния для системы с 3 пользователями и 11 устройствами, где 9 устройств задействовано, а 2 имеется в резерве. Пусть текущая ситуация такова:
Пользователь 1: макс. потребность = 6, выделено = 3
Пользователь 2: макс. потребность = 5, выделено = 4
Пользователь 3: макс. потребность = 4, выделено = 2Последующие действия системы могут быть таковы. Вначале удовлетворить запросы третьего пользователя, затем дождаться, когда он закончит работу и освободит свои три устройства. Затем можно обслужить первого и второго пользователей. То есть система удовлетворяет только те запросы, которые оставляют ее в надежном состоянии, и отклоняет остальные.
Термин «ненадежное состояние» не предполагает, что обязательно возникнут тупики. Он лишь говорит о том, что в случае неблагоприятной последовательности событий система может зайти в тупик.
Данный алгоритм обладает тем достоинством, что при его использовании нет необходимости в перераспределении ресурсов и откате процессов назад. Однако использование этого метода требует выполнения ряда условий:
- Число пользователей и число ресурсов фиксировано.
- Число работающих пользователей должно оставаться постоянным.
- Алгоритм требует, чтобы клиенты гарантированно возвращали ресурсы.
- Должны быть заранее указаны максимальные требования процессов к ресурсам. Чаще всего данная информация отсутствует.
Наличие таких жестких и зачастую неприемлемых требований может склонить разработчиков к выбору других решений проблемы взаимоблокировки.
Предотвращение тупиков за счет нарушения условий возникновения тупиков
Нарушение условия взаимоисключения
В качестве примера рассмотрим принтер. Известно, что пытаться осуществлять вывод на принтер могут несколько процессов.
Во избежание хаоса организуют промежуточное формирование всех выходных данных процесса на диске, то есть разделяемом устройстве. Лишь один системный процесс, называемый сервисом или демоном принтера, отвечающий за вывод документов на печать по мере освобождения принтера, реально с ним взаимодействует. Эта схема называется спулингом (spooling). Таким образом, принтер становится разделяемым устройством, и тупик для него устранен.
К сожалению, не для всех устройств и не для всех данных можно организовать спулинг. Неприятным побочным следствием такой модели может быть потенциальная тупиковая ситуация из-за конкуренции за дисковое пространство для буфера спулинга.
Нарушение условия ожидания дополнительных ресурсов
Условия ожидания ресурсов можно избежать, потребовав выполнения стратегии двухфазного захвата:
- В первой фазе процесс должен запрашивать все необходимые ему ресурсы сразу. До тех пор пока они не предоставлены, процесс не может продолжать выполнение.
- Если в первой фазе некоторые ресурсы, которые были нужны данному процессу, уже заняты другими процессами, он освобождает все ресурсы, которые были ему выделены, и пытается повторить первую фазу.
Таким образом, один из способов — заставить все процессы затребовать нужные им ресурсы перед выполнением («все или ничего»). Если система в состоянии выделить процессу все необходимое, он может работать до завершения. Если хотя бы один из ресурсов занят, процесс будет ждать.
Данное решение применяется в пакетных мэйнфреймах (mainframe), которые требуют от пользователей перечислить все необходимые его программе ресурсы. Другим примером может служить механизм двухфазной локализации записей в СУБД. Однако в целом подобный подход не слишком привлекателен и приводит к неэффективному использованию компьютера.
Нарушение принципа отсутствия перераспределения
Если бы можно было отбирать ресурсы у удерживающих их процессов до завершения этих процессов, то удалось бы добиться невыполнения третьего условия возникновения тупиков. Перечислим минусы данного подхода:
- Отбирать у процессов можно только те ресурсы, состояние которых легко сохранить, а позже восстановить, например состояние процессора.
- Если процесс в течение некоторого времени использует определенные ресурсы, а затем освобождает эти ресурсы, он может потерять результаты работы, проделанной до настоящего момента.
Следствием данной схемы может быть дискриминация отдельных процессов, у которых постоянно отбирают ресурсы. Также это может быть дорогостоящим.
Нарушение условия кругового ожидания
Один из способов — упорядочить ресурсы. Например, можно присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке их возрастания. Тогда круговое ожидание возникнуть не может.
Один из немногих примеров упорядочивания ресурсов — создание иерархии спин-блокировок в Windows 2000. Спин-блокировка — простейший способ синхронизации. Спин-блокировка может быть захвачена и освобождена процессом. Классическая тупиковая ситуация возникает, когда процесс P1 захватывает спин-блокировку S1 и претендует на спин-блокировку S2, а процесс P2 захватывает спин-блокировку S2 и хочет дополнительно захватить спин-блокировку S1. Чтобы этого избежать, все спин-блокировки помещаются в упорядоченный список. Захват может осуществляться только в порядке, указанном в списке.
Другой способ — действовать в соответствии с правилом, согласно которому каждый процесс может иметь только один ресурс в каждый момент времени. Если нужен второй ресурс — освободи первый. Очевидно, что для многих процессов это неприемлемо.
Таким образом, технология предотвращения циклического ожидания, как правило, неэффективна и может без необходимости закрывать доступ к ресурсам.
Обнаружение тупиков
Для обнаружения и выявления вовлеченных процессов производится проверка наличия циклического ожидания в случаях, когда выполнены первые три условия возникновения тупика.
Рассмотрим модельную ситуацию:
- Процесс P1 ожидает ресурс R1.
- Процесс P2 удерживает ресурс R2 и ожидает ресурс R1.
- Процесс P3 удерживает ресурс R1 и ожидает ресурс R3.
- Процесс P4 ожидает ресурс R2.
- Процесс P5 удерживает ресурс R3 и ожидает ресурс R2.
Для выяснения, является ли данная ситуация тупиковой, можно сконструировать граф ресурсов. Из рисунка видно, что имеется цикл, моделирующий условие кругового ожидания, и что процессы P2, P3, P5, а может быть, и другие находятся в тупиковой ситуации.
Граф:
P1 -> R1
R2 -> P2
P2 -> R1
R1 -> P3
P3 -> R3
R3 -> P5
P5 -> R2
P4 -> R2Визуально легко обнаружить наличие тупика, но нужны также формальные алгоритмы, реализуемые на компьютере.
Восстановление после тупиков
Обнаружив тупик, можно вывести из него систему, нарушив одно из условий существования тупика. При этом, возможно, несколько процессов частично или полностью потеряют результаты проделанной работы.
Сложность восстановления обусловлена рядом факторов:
- В большинстве систем нет достаточно эффективных средств, чтобы приостановить процесс, вывести его из системы и возобновить впоследствии с того места, где он был остановлен.
- Если даже такие средства есть, то их использование требует затрат и внимания оператора.
Самый простой и наиболее распространенный способ устранить тупик — завершить выполнение одного или более процессов, чтобы впоследствии использовать его ресурсы. Тогда в случае удачи остальные процессы смогут выполняться. Если это не помогает, можно ликвидировать еще несколько процессов.
После каждой ликвидации должен запускаться алгоритм обнаружения тупика.
Идемпотентные процессы — процессы, которые могут быть возвращены к началу без ущерба (например, компиляция).
С другой стороны, процесс, который изменяет содержимое базы данных, не всегда может быть корректно запущен повторно.
В некоторых случаях можно временно забрать ресурс у текущего владельца и передать его другому процессу. Подобное восстановление часто затруднительно, если не невозможно.
В некоторых системах возможен откат по контрольным точкам.
Когда тупик обнаружен, видно, какие ресурсы вовлечены в цикл кругового ожидания. Чтобы осуществить восстановление, процесс, который владеет таким ресурсом, должен быть отброшен к моменту времени, предшествующему его запросу на этот ресурс.