Глава 7. Тупики
Предыдущая глава | Программа курса | Следующая глава
В предыдущих главах рассмотрены способы синхронизации процессов, которые позволяют процессам успешно кооперироваться. Однако если средствами синхронизации пользоваться неосторожно, то могут возникнуть непредвиденные затруднения. Предположим, что несколько процессов конкурируют за обладание конечным числом ресурсов. Если запрашиваемый процессом ресурс недоступен, процесс переходит в состояние ожидания. В случае если требуемый ресурс удерживается другим ожидающим процессом, то первый процесс не сможет сменить свое состояние. Такая ситуация называется тупиком. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, дедлока (deadlock) или клинча, если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация или зависание системы является следствием того, что один или более процессов находятся в состоянии тупика.
Рассмотрим пример. Предположим, что два процесса осуществляют вывод с ленты на принтер. Один из них успел монополизировать ленту и претендует на принтер, а другой наоборот. После этого оба процесса оказываются заблокированными в ожидании второго ресурса (см. рис. 7.1)
Рис. 7.1. Пример тупиковой ситуации.
Тупики также могут иметь место в ситуациях, не требующих выделенных ресурсов. Например, в системах управления базами данных процессы могут локализовывать записи, чтобы избежать гонок (см. главу "Синхронизация процессов"). В этом случае может получиться так, что один из процессов заблокировал записи, требуемые другому процессу и наоборот. Т.о. тупики могут иметь место, как на аппаратных, так и на программных ресурсах.
Другой пример возникновение тупика в системах спулинга. Режим спулинга ввод-вывод с буферизацией информации, предназначенной для печати, на диске и организации очереди на печать часто применяется для повышения производительности системы. Программа, осуществляющая вывод на печать должна полностью сформировать свои выходные данные в промежуточном файле, после чего начинается реальная распечатка. В итоге, несколько заданий может оказаться в тупиковой ситуации, если предусмотренная емкость буфера для промежуточных файлов будет заполнена до того, как одно из заданий закончит свою работу. Возможные решения: увеличить размер буфера, или не принимать дополнительные задания, если файл спулинга близок к какому то порогу насыщения, например, заполнен на 75%.
Определение. Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое только другой процесс данного множества может вызвать. Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другого члена множества и, следовательно, все процессы будут спать вместе. Обычно событие, которого ждет процесс в тупиковой ситуации - освобождение ресурса.
Далее в тексте данной главы будут обсуждаться вопросы, обнаружения, предотвращения, обхода тупиков и восстановления после тупиков. Рассматривается также тесно связанная проблема бесконечного откладывания, которое может происходить из-за дискриминационной политики планировщика ресурсов. Во многих случаях цена борьбы с тупиками, которую приходится платить высока. Тем не менее, для ряда систем, например для систем реального времени, нет иного выхода.
Уже говорилось, что одна из основных функций ОС осуществлять распределение ресурсов между процессами, то есть быть менеджером ресурсов.
Как устройства, так и данные могут являться ресурсами.
Некоторые виды ресурсов допускают разделение между процессами, то есть являются разделяемыми устройствами. Например, память, процессор, диски коллективно используются процессами. Другие - нет, то есть являются выделенными, например, лентопротяжное устройство. Чаще всего тупики связаны с выделенными ресурсами, то есть тупики возникают, когда процессу дается эксклюзивный доступ к устройствам, файлам и другим ресурсам.
Последовательность событий, требуемых для использования ресурса такова:
запросить (request) ресурс,
использовать (use) ресурс,
освободить (release) ресурс.
Если ресурса нет в наличии, когда он требуется, то процесс вынужден ждать. В некоторых ОС процесс автоматически блокируется, когда получает отказ на запрос к ресурсу и просыпается, когда ресурс оказывается в наличии. В других системах отказ сопровождается возвратом ошибки и уже задача вызывающего процесса решить: подождать немного и попытаться осуществить запрос вновь.
В наших дальнейших рассуждениях мы будем предполагать, что когда запрос отклонен, процесс переходит в состояние ожидания.
Природа запроса сильно зависит от ОС. В некоторых системах имеется системный вызов request для прямого запроса на ресурс. В других - единственные ресурсы, о которых ОС знает - специальные файлы, которые только один процесс имеет право открывать за раз. Это делается обычным вызовом open. Если файл уже используется, вызывающий процесс блокируется, пока ресурс не освободится.
7.3 Условия возникновения тупиков
В 1971 г. Коффман, Элфик и Шошани сформулировали следующие четыре условия для возникновения тупиков.
1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются.
2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (которые при этом обычно удерживаются другими процессами).
3. Условие неперераспределяемости (No preemtion). Ресурс, данный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам цепи.
Для тупика необходимо выполнение всех четырех условий.
Обычно тупик моделируется прямым графом, наподобие того, что изображен на рис. 7.1, состоящим из узлов двух видов: прямоугольников процессов и эллипсов ресурсов. Стрелки, направленные от ресурса к процессу, показывают, что ресурс выделен данному процессу.
7.4 Основные направления борьбы с тупиками.
В связи с проблемой тупиков были выполнено много интересных исследований в области информатики и операционных систем.
Основные направления борьбы с тупиками:
Игнорировать данную проблему
Обнаружение тупиков
Восстановление после тупиков
Предотвращение тупиков за счет тщательного выделения ресурсов или нарушения одного из условий возникновения тупиков.
Простейший подход - игнорировать проблему тупиков. Различные люди реагируют на подобную стратегию по-разному. Математики находят ее неприемлемой и утверждают, что тупики должны быть предотвращены любой ценой. Инженеры задают вопрос: как часто возникает данная проблема и как часто система виснет по другим причинам? Если тупик встречается раз в пять лет, но аварийный останов системы из-за отказов оборудования, ошибок компиляторов или ОС происходит раз в месяц, большинство инженеров не пожелают пожертвовать производительностью или удобством, чтобы ликвидировать тупик.
Например, ОС Unix, имеющая в ядре ряд массивов фиксированной размерности, потенциально страдает от тупиков, даже если они не обнаружены. Например, суммарное число процессов в системе определяется размерностью таблицы процессов. Если таблица заполнена, вероятность этого ничтожна, но такое может произойти, то для программы, которая делает вызов fork, резонно подождать некоторое время и попытаться осуществить этот вызов вновь. Следует ли отказываться от вызова fork, чтобы решить эту проблему?
Максимальное число открытых файлов аналогичным образом ограничено размером таблицы индексных узлов. С ними может произойти аналогичная ситуация. Пространство выгрузки на диске - другой лимитируемый ресурс. Фактически любая таблица в ОС - конечный ресурс.
Подход Unix состоит в том, чтобы игнорировать данную проблему в предположении, что большинство пользователей предпочтут случайный тупик нелепым правилам заставляющих их иметь один процесс, один открытый файл и т.п. ... Таким образом, мы сталкиваемся с нежелательным выбором между строгостью и удобством. Трудно найти общее, устраивающее всех решение.
Обнаружение тупика это установление факта, что возникла тупиковая ситуация и определение процессов и ресурсов, вовлеченных в эту ситуацию. Как правило, алгоритмы обнаружения применяются, когда выполнены первые три необходимых условия возникновения тупиковой ситуации. Затем проверяется наличие режима кругового ожидания. При этом активно используются уже упоминавшиеся графы распределения ресурсов.
Рассмотрим модельную ситуацию [12]:
Вопрос состоит в том, является ли данная ситуация тупиковой, и если да, то какие процессы в ней участвуют.
Рис. 7.2 (а) Граф ресурсов. (б) Цикл, извлеченный из графа (a).
Для ответа на этот вопрос можно сконструировать граф ресурсов, как показано на рис. 7.2. Из рисунка видно, что имеется цикл, моделирующий условие кругового ожидания, и процессы D,E,G в тупиковой ситуации
Визуально легко обнаружить наличие тупика, но нужны также формальные алгоритмы, реализуемые на компьютере.
Один из таких алгоритмов описан в [12], там же можно найти ссылки на другие алгоритмы.
Существуют и другие способы обнаружения тупиков, применимые также в ситуациях, когда имеется несколько ресурсов каждого типа. Так в [22] описан способ, называемый редукцией графа распределения ресурсов, а в [12] матричный алгоритм.
7.7 Восстановление после тупиков
Предположим, что алгоритм обнаружения справился со своей задачей и обнаружил тупик. Что дальше. Один из путей - восстановиться и заставить систему работать дальше. В данной секции мы обсудим различные способы восстановления после тупиков.
Систему, оказавшуюся в тупике, можно вывести из него, нарушив одно из условий его существования. При этом возможно несколько процессов частично или полностью потеряют результаты проделанной работы.
Сложность восстановления обусловлена рядом факторов.
в большинстве систем нет достаточно эффективных средств для приостановки процесса, вывода его из системы и возобновления впоследствии;
если даже такие средства есть, то их использование требует затрат и внимания оператора;
восстановление после серьезного тупика может потребовать много работы.
7.7.1 Восстановление при помощи перераспределения ресурсов
Один из способов восстановления - принудительный вывод некоторого процесса из системы для последующего использования его ресурсов. Для определения того, какой процесс выводить из системы зачастую требуются усилия оператора. В некоторых случаях может оказаться возможным временно забрать ресурс у его текущего владельца и передать его другому процессу.
Например, чтобы отобрать лазерный принтер у процесса, который осуществляет вывод на него, оператор может собрать уже напечатанные бумаги и сложить их в стопку. Затем процесс может быть приостановлен и принтер передан другому процессу. После окончания его работы бумага может быть возвращена в принтер и первый процесс возобновляется. Возможность забрать ресурс у процесса, дать его другому процессу и затем вернуть его назад без нанесения ущерба сильно зависит от природы ресурса. Подобное восстановление часто трудно, если не невозможно.
7.7.2 Восстановление через откат назад
Это, по всей вероятности, самый эффективный способ приостановки и возобновления.
В ряде систем реализованы средства рестарта с контрольной точки (сохранение состояния системы в какой-то момент времени). Там где эти средства не предусмотрены, их должны организовать разработчики прикладных программ. Если проектировщики системы знают, что тупик вероятен, они могут периодически организовывать для процессов контрольные точки.
Когда тупик обнаружен, видно какие ресурсы вовлечены в цикл кругового ожидания. Чтобы осуществить восстановление, процесс, который владеет таким ресурсам, должен быть отброшен к моменту времени, предшествующему его запросу на этот ресурс.
7.7.3 Восстановление через ликвидацию одного из процессов
Грубый, но простейший способ устранить тупик - убить один или более процессов. Например, убить процесс, который в цикле. Тогда при удаче остальные процессы смогут выполняться. Если это не помогает, то можно ликвидировать еще один процесс.
По возможности лучше убить тот процесс, который может быть без ущерба возвращен к началу (такие процессы называются идемпотентными), например, компиляция. С другой стороны процесс, который изменяет содержимое базы данных, не всегда может быть корректно запущен повторно.
7.8 Способы предотвращения тупиков путем тщательного распределения ресурсов.
При предотвращении тупиков целью является обеспечение условий, исключающих возможность возникновения тупиковых ситуаций.
Система, предоставляя ресурс в распоряжение процесса, должна принять решение, безопасно это или нет. Возникает вопрос: есть ли такой алгоритм, который помогает всегда избегать тупиков и делать правильный выбор. Ответ - да, мы можем избегать тупиков, но только, если определенная информация известна заранее. В данной секции мы рассмотрим пути предотвращения тупиков за счет тщательного распределения ресурсов.
Один из алгоритмов предотвращения тупиков базируется на концепции безопасных состояний.
7.8.1 Предотвращение тупиков и алгоритм банкира.
Можно избежать тупиковой ситуации, если рациональным образом использовать ресурсы, придерживаясь
определенных правил. Наиболее известен среди алгоритмов такого рода - алгоритм банкира, предложенный Дейкстрой. Он, как бы имитирует действия банкира, который, располагая определенным источником капитала, принимает ссуды и выдает платежи.
Предположим, что у системы в наличии n устройств, например лент. Суть алгоритма состоит в следующем.
ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n.
Пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени.
Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течение конечного времени.
В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.
Рассмотрим пример надежного состояния для системы с тремя пользователями и 12-ю устройствами, где 10 устройств задействовано, а 2 имеется в наличии. Пусть текущая ситуация такова:
|
Текущее количество |
Максимальная потребность |
|
|
Первый пользователь |
1 |
4 |
|
Второй пользователь |
4 |
6 |
|
Третий пользователь |
5 |
8 |
Данное состояние надежно. Последующие действия системы могут быть таковы. Вначале удовлетворить запросы второго пользователя, затем дождаться, когда он выполнит свою работу и освободит свои 6 устройств. Затем можно обслужить остальных пользователей. То есть, система удовлетворяет только те запросы, которые оставляют ее в надежном состоянии и отклоняет остальные.
Термин ненадежное состояние не предполагает, что обязательно возникнут тупики. Он лишь говорит о том, что в случае неблагоприятной последовательности событий система может зайти в тупик.
7.8.2 Недостатки алгоритма банкира
У алгоритма банкира имеются серьезные недостатки, из-за которых разработчик может выбрать другой подход для решения проблемы тупиков:
Алгоритм банкира исходит из фиксированного количества ресурсов.
Он требует, чтобы число работающих пользователей оставалось постоянным
Данный алгоритм требует, чтобы распределитель гарантированно удовлетворял запросы за конечный период времени. Очевидно, что для реальных систем нужны более конкретные гарантии.
Алгоритм требует, чтобы клиенты гарантированно возвращали ресурсы. Опять таки в реальных системах требуются, гораздо более конкретные гарантии.
Требуется, чтобы пользователи заранее указали свои максимальные потребности в ресурсах. При динамическом распределении ресурсов трудно оценить максимальные потребности пользователей.
В следующей секции рассмотрены другие способы предотвращения тупиков.
7.9 Предотвращение тупиков за счет нарушения условий возникновения тупиков.
Как же может реальная система избежать тупиков, если отсутствует информация о будущих запросах? Для ответа на этот вопрос вернемся к четырем условиям раздела 7.3. Если мы сможем организовать работу системы так, что, по крайней мере, одно из этих условий не удовлетворено, тупик не возможен.
7.9.1 Нарушение условия взаимоисключения
Если в системе отсутствуют выделенные ресурсы, тупиков не будет. Тем не менее, ясно, что обобществление, например, принтера, то есть, разрешение двум процессам писать на один принтер в одно и то же время приведет к хаосу. За счет организации спулинга одновременная печать для нескольких процессов становится возможной. В этой модели единственный процесс, реально взаимодействующий с принтером - демон принтера. Таким образом, тупик для принтера устранен.
К сожалению, не для всех устройств может быть организован спулинг (таблица процессов плохо поддается спулингу). Неприятным побочным следствием может быть потенциальная тупиковая ситуация из-за конкуренции за дисковое пространство для спул-буфера. Тем не менее, в той или иной форме эта идея применяется часто.
7.9.2 Hарушение условия ожидания дополнительных ресурсов
Хавендер в 1968 г. предложил следующую стратегию.
Каждый процесс должен запрашивать все требуемые ему ресурсы сразу, причем не может начать выполняться до тех пор, пока все они не будут ему предоставлены.
Если же процесс, удерживает определенные ресурсы и получает отказ в выделении ему дополнительных ресурсов, то он должен освободить свои первоначальные ресурсы и, при необходимости, запросить их снова вместе с дополнительными.
Таким образом, один из способов - заставить все процессы затребовать все свои ресурсы перед выполнением (все или ничего). Если система в состоянии выделить процессу все необходимое, он может работать до завершения. Если хотя бы один из ресурсов занят, процесс будет ждать.
Подобный подход не слишком привлекателен и приводит к снижению эффективности работы компьютера. Редко бывает, что все запрашиваемые устройства необходимы программе одновременно. Можно, конечно, разделить программу на несколько шагов и выделять ресурсы отдельно для каждого шага программы, но основная проблема как раз в том, что многие процессы не знают, сколько ресурсов им понадобится до начала вычислений. Если такая информация есть, то можно воспользоваться алгоритмом банкира. Тем не менее, некоторые пакетные мэйнфреймы требуют от пользователей перечислить все необходимые его программе ресурсы.
7.9.3 Нарушение принципа неперераспределяемости.
В соответствии со вторым принципом Хавендера можно отбирать ресурсы у удерживающих их процессов до завершения этих процессов. Если бы это было всегда возможно, то можно было бы добиться невыполнения третьего условия возникновения тупиков. С проблемой отнятия ресурсов у удерживающих их процессов мы сталкивались в 7.7.1. Если процесс в течение некоторого времени использует определенные ресурсы, а затем освобождает эти ресурсы, он теряет всю работу, проделанную до настоящего момента. Весь вопрос в цене данного решения, которая может быть слишком высокой, если подобная ситуация возникает часто.
Другим недостатком данной схемы может быть дискриминация отдельных процессов, у которых постоянно отбирают ресурсы.
7.9.4 Нарушение условия кругового ожидания
Осталось одно условие. Циклического ожидания можно избежать несколькими путями.
Один из них действовать в соответствии с правилом, согласно которому каждый процесс может иметь только один ресурс в каждый момент времени. Если нужен второй ресурс - освободи первый. Очевидно, что для многих процессов это не приемлемо, например, для тех, которые распечатывают большие файлы с ленты на принтер.
Другой способ - присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке возрастания номеров. Тогда круговое ожидание возникнуть не может.
Небольшой вариацией этого алгоритма будет нумерация в возрастающем порядке не ресурсов, а запросов процесса. После последнего запроса и освобождения всех ресурсов можно разрешить процессу опять осуществит первый запрос.
Очевидно, что невозможно найти порядок, который удовлетворит всех.
Хотя в общем случае рассмотренные способы предотвращения тупиков не кажутся перспективными, для отдельных специфичных приложений подобные алгоритмы широко используются. Например, во многих СУБД часто требуется локализация нескольких записей, и затем изменение всех локализованных записей. Когда несколько процессов работают с базой данных, есть реальная опасность тупика. Типичный в подобных ситуациях подход - двухфазная локализация. В первой фазе процесс пытается локализовать все записи, которые ему нужны за один раз. Если это ему удалось, то он переходит ко второй фазе, выполняя изменения и освобождая записи. В первой фазе не делается реальной работы.
Если в первой фазе некоторые записи, которые ему нужны, уже локализованы, процесс освобождает все, что он локализовал и пытается повторить первую фазу. В известном смысле этот подход напоминает требование захвата всех ресурсов заранее. Естественно, что это срабатывает только в тщательно организованных программах, которые могут быть приостановлены в течение первой фазы и рестартованы впоследствии. Далеко не все программы укладываются в эту схему.
7.10.2 Тупики не ресурсного типа
До сих пор все наше внимание было сконцентрировано на ресурсных тупиках. Есть и другие тупиковые ситуации, например, когда один из процессов ждет чего-то от другого. Это часто случается при некорректном использовании семафоров, когда один из процессов забывает открыть семафор для другого процесса.
Близкая к тупикам проблема - голод. В динамических системах постоянно происходят запросы процессов к ресурсам. Естественно, что должна быть реализована некоторая политика для принятия решения относительно того, кто получит ресурсы и когда. Эта политика может быть дискриминационной по отношению к некоторым процессам, хотя формально они и не в тупике.
Например, несколько процессов конкурируют за принтер, и система выделяет его по принципу - первым печатать файл наименьшего размера. Этот подход увеличивает число счастливых пользователей принтера и кажется удовлетворительным. Однако пользователь с большим файлом оказывается в состоянии бесконечного ожидания (тупике). В данном случае голода можно избежать путем применения иной политики, например, FCFS (первый пришедший обслуживается первым).
Возникновение тупиков является потенциальной проблемой любой операционной системы. Они возникают, когда имеется группа процессов, каждый из которых пытается иметь эксклюзивный доступ к некоторым ресурсам и претендует на ресурсы, принадлежащие другому процессу. В итоге все они оказываются в состоянии бесконечного ожидания.
С тупиками можно бороться, можно их обнаруживать, избегать и восстанавливать систему после тупиков. Однако цена подобных действий высока и соответствующие усилия должны предприниматься только в системах, где игнорирование тупиковых ситуаций приводит к катастрофическим последствиям.
Считается, что в будущих системах тупики станут более критичным фактором, так как системы будущего:
будут в большей степени ориентированы на параллельную работу
будет преимущественно реализовываться динамическое распределение ресурсов
растет тенденция рассматривать данные как ресурс, в связи с чем количество ресурсов возрастет.
Более подробно данная тема рассмотрена в [9,12,22 и др.]