Взаимное блокирование (deadlock1) можно определить как постоянное блокирование множества процессов, которые либо конкурируют в борьбе за системные ресурсы, либо сообщаются один с другим. В отличие от других проблем, возникающих в процессе управления параллельными вычислениями, данная проблема в общем случае эффективного решения не имеет.
Все взаимоблокировки предполагают наличие конфликта в борьбе за ресурсы между двумя или несколькими процессами. Наиболее ярким примером может служить транспортная взаимоблокировка. На рис. 6.1 показана ситуация, когда четыре автомобиля должны примерно одновременно пересечь перекресток. Четыре квадранта перекрестка представляют собой ресурсы, которые требуются процессам. В частности, для успешного пересечения перекрестка всеми четырьмя автомобилями необходимые ресурсы выглядят следующим образом:
автомобилю, движущемуся на север, нужны квадранты 1 и 2;
автомобилю, движущемуся на запад, нужны квадранты 2 и 3;
автомобилю, движущемуся на юг, нужны квадранты 3 и 4;
автомобилю, движущемуся на восток, нужны квадранты 4 и 1.
Обычное правило пересечения перекрестка состоит в том, что автомобиль должен уступить дорогу движущемуся справа. Это правило работает, когда перекресток пересекают два или три автомобиля. Например, если на перекрестке встретятся автомобили, движущиеся на север и на запад, то автомобиль, движущийся на север, уступит дорогу автомобилю, движущемуся на запад. Но если перекресток пересекают одновременно четыре автомобиля, каждый из которых согласно правилу воздержится от въезда на перекресток, возникнет взаимоблокировка. Она возникнет и в том случае, если все четыре машины проигнорируют правило и осторожно въедут на перекресток, поскольку при этом каждый автомобиль захватит один ресурс (один квадрант) и останется на вечной стоянке в ожидании, когда другой автомобиль освободит следующий требующийся для пересечения перекрестка квадрант. Итак, мы опять получили взаимоблокировку.
1 Дословно — "мертвые объятия". В русскоязычной литературе встречаются термины "тупик", "клинч", однако наиболее полно отражает суть происходящего именно термин "взаимоблокировка". — Прим. перев.
а) Возможна взаимоблокировка б) Взаимоблокировка
Рис. 6.1. Пример взаимоблокировки
Рассмотрим теперь картину взаимоблокировки с участием процессов и системных ресурсов. На рис. 6.2 показано выполнение двух процессов, конкурирующих в борьбе за два ресурса. Каждый из процессов требует исключительного владения обоими ресурсами на некоторое время. Процессы Р и Q имеют общий вид:
Process P Process Q
• •
• •
Get A Get В
• •
Get В Get A
• •
• •
Release A Release В
• •
Release В Release A
На рис. 6.2 ось x представляет выполнение процесса P, а ось у — выполнение процесса Q. Таким образом, совместное выполнение двух процессов можно представить в виде пути из начала координат в северо-восточном направлении. В однопроцессорной системе в каждый момент времени может выполняться только один процесс, так что путь состоит из чередующихся горизонтальных и вертикальных отрезков, причем горизонтальные отрезки представляют работу процесса Р, а вертикальные — процесса Q.
Рис. 6.2. Пример взаимоблокировки [ВАСО98]
На рис. 6.2 показаны шесть различных путей выполнения процессов.
- Q получает ресурс В, затем — ресурс А, затем освобождает ресурсы В и А. Когда процесс Р продолжает выполнение, он может получить оба ресурса.
- Q получает ресурс В, а затем — ресурс А. Процесс Р начинает работу и блокируется при запросе ресурса A. Q освобождает ресурсы В и А. Когда процесс Р продолжает выполнение, он может получить оба ресурса.
- Q получает ресурс В, затем Р получает ресурс А. Взаимоблокировка неизбежна, поскольку выполнение Q заблокируется при запросе ресурса А, а выполнение процесса Р — при запросе ресурса В.
- Р получает ресурс А, затем Q получает ресурс В. Взаимоблокировка неизбежна, поскольку выполнение Q заблокируется при запросе ресурса А, а выполнение процесса Р — при запросе ресурса В.
- Р получает ресурс А, а затем — ресурс В. Процесс Q начинает работу и блокируется при запросе ресурса В. Р освобождает ресурсы А и В. Когда процесс Q продолжает выполнение, он может получить оба ресурса.
- Р получает ресурс А, затем — ресурс В, затем освобождает ресурсы А и В. Когда процесс Q продолжает выполнение, он может получить оба ресурса.
Произойдет взаимоблокировка или нет, зависит как от динамики выполнения процессов, так и от подробностей построения приложения. Предположим, например, что процесс Р не требует получения обоих ресурсов одновременно и имеет следующий вид:
Process P
.
Get A
.
Release A
.
Get В
.
Release В
Эта ситуация изображена на рис. 6.3. Немного поразмыслив, вы можете убедиться, что независимо от того, каким образом два процесса выполняются друг относительно друга, взаимоблокировка невозможна.
Повторно используемые ресурсы
Ресурсы можно разделить на две основные категории: повторно используемые (reusable) и расходуемые (consumable). Повторно используемые ресурсы могут безопасно использоваться одновременно только одним процессом и при этом не истощаться. Процесс получает ресурс, который позже освобождает для повторного использования другими процессами. Примерами повторно используемых ресурсов могут служить процессор, каналы ввода-вывода, основная и вторичная память, периферийные устройства, а также структуры данных — такие, как файлы, базы данных и семафоры.
Рис. 6.3. Пример отсутствия взаимоблокировки [ВАСО98]
В качестве примера взаимоблокировки с повторно используемым ресурсе рассмотрим два процесса, которые конкурируют за исключительный доступ дисковому файлу D и стримеру Т. Программа выполняет показанные на рис. 6. операции. Взаимоблокировка осуществляется в том случае, когда каждый процесс захватывает один ресурс и запрашивает другой. Например, взаимоблокировка произойдет при следующем чередовании двух процессов: PoPiQoQiP2Q2. Может показаться, что это ошибка программиста, не имеющая отношения к разработчику операционной системы. Однако, как мы знаем, разработка программ для параллельных вычислений — весьма сложная задача, и выявление источника взаимоблокировки в сложной программе — дело очень непростое. Одна и стратегий при работе с такими взаимоблокировками состоит в наложении си- cтемных ограничений на порядок запроса ресурсов.
Процесс Р Процесс Q
Шаг Действие Шаг Действие
Рис. 6.4. Пример конкуренции двух процессов в борьбе за повторно используемый ресурс
Другим примером взаимоблокировки с повторно используемыми ресурсами могут быть запросы к основной памяти. Предположим, что для распределения доступно 200 Кбайт памяти, и выполняется такая последовательность запросов:
Если оба процесса дойдут да своего второго запроса, возникнет взаимоблокировка. Если количество требуемой памяти заранее неизвестно, работать с таким типом взаимоблокировок на уровне системных ограничений (в том числе и операционной системы) очень сложно. Наилучший способ справиться с этой конкретной проблемой заключается в использовании виртуальной памяти, о которой рассказывается в главе 8, "Виртуальная память".
Расходуемые ресурсы
Расходуемыми являются те ресурсы, которые могут быть созданы (произведены) и уничтожены (потреблены). Обычно ограничений на количество расходуемых ресурсов определенного типа нет. Незаблокированный процесс-производитель может выпустить любое количество таких ресурсов; когда процесс запрашивает некоторый ресурс, последний прекращает свое существование. Примерами расходуемых ресурсов могут служить прерывания, сигналы, сообщения и информация в буферах ввода-вывода.
В качестве примера взаимоблокировки с расходуемыми ресурсами рассмотрим следующую пару процессов, где каждый из процессов пытается получить сообщение от другого процесса, а затем отправить сообщение своему визави.
Взаимоблокировка осуществляется, если операция Receive является блокирующей (т.е. получающий процесс блокируется до тех пор, пока сообщение не будет получено). И вновь причиной взаимоблокировки является ошибка при разработке программы. Такие ошибки обычно довольно таинственны и трудноуловимы. Кроме того, может оказаться, что взаимоблокировку вызывает только достаточно редкая комбинация событий, и тогда до того, как ошибка проявит себя, программа может побывать в эксплуатации многие годы.
Единой эффективной стратегии для работы со всеми типами взаимоблокировок нет. Позже мы изучим различные подходы к решению проблемы, но сначала рассмотрим условия возникновения взаимоблокировок.
Условия возникновения взаимоблокировок
Для того чтобы взаимоблокировка стала возможной, требуется наличие трех условий.
- Взаимные исключения. Одновременно использовать ресурс может только
один процесс.
Удержание и ожидание. Процесс может удерживать выделенные ресурсы во
время ожидания других ресурсов.
Отсутствие перераспределения. Ресурс не может быть принудительно ото
бран у удерживающего его процесса.
Эти условия выполняются довольно часто. Например, взаимоисключения необходимы для гарантии согласованности результатов и целостности базы данных. Аналогично, невозможно произвольное применение перераспределения, в особенности при работе с данными, когда требуется обеспечить механизм отката.
Кроме перечисленных трех условий для реального осуществления взаимоблокировки требуется выполнение четвертого условия.
4. Циклическое ожидание. Существует замкнутая цепь процессов, каждый из
которых удерживает как минимум один ресурс, необходимый процессу,
следующему в цепи после данного (см. рис. 6.5).
Рис. 6.5. Циклическое ожидание
Первые три условия являются необходимыми, но не достаточными для осуществления взаимоблокировки. Четвертое условие в действительности представляет собой потенциальное следствие первых трех — т.е. при наличии первых трех условий может осуществиться такая последовательность событий, которая приведет к неразрешимому циклическому ожиданию (что, по сути, и является определением взаимоблокировки). Неразрешимость циклического ожидания из условия 4 обеспечивается выполнением предыдущих трех условий. Таким образом, совокупность четырех перечисленных выше условии является необходимым и достаточным условием взаимоблокировки.2
