Добавлен: 29.10.2018
Просмотров: 48196
Скачиваний: 190
6.6. Предотвращение взаимоблокировки
511
Если демон запрограммирован на начало печати еще до того, как все выходные данные
попали в очередь на печать, принтер может простоять впустую, если выводящий дан-
ные процесс решит подождать несколько часов после первого пакета выходных данных.
Поэтому демоны обычно программируются так, чтобы начинать печать, только если
доступен полный файл выходных данных. Но само по себе это решение может привести
к взаимоблокировке. Что получится, если каждый из двух процессов заполнит по по-
ловине доступного пространства, выделенного на диске под очередь на печать своими
выходными данными, и ни один из них не сформирует свои полные выходные данные?
В таком случае мы получим два процесса, завершивших формирование только части,
но не всего объема своих выходных данных, и не имеющих возможности продолжить
свою работу. Ни один из процессов не сможет когда-либо завершиться, и мы получим
взаимоблокировку, связанную с выводом данных на диск.
И все же здесь проглядывается намек на идею, которая довольно часто применяется
на практике. Следует избегать выделения ресурса, если в нем нет насущной потреб-
ности, и постараться, чтобы как можно меньше процессов могло фактически требовать
получения этого ресурса.
6.6.2. Атака условия удержания и ожидания
Второе из условий, сформулированных Коффманом (Coffman et al., 1971), выглядит
несколько более обещающим. Если можно будет помешать процессам, удерживающим
ресурсы, войти в фазу ожидания дополнительных ресурсов, то можно будет исключить
и взаимоблокировку. Один из способов достижения этой цели заключается в том, чтобы
заставить все процессы запрашивать все свои ресурсы до начала выполнения своей
работы. Если все доступно, то процессу будет выделено все, что ему требуется, и он
сможет доработать до завершения. Если один или несколько ресурсов заняты, ничего
не будет выделяться и процесс будет просто ждать.
Проблема, непосредственно связанная с этим подходом, состоит в том, что многие
процессы не знают, сколько ресурсов им понадобится, пока не начнут работу. Фак-
тически если бы они об этом знали, то можно было бы использовать и алгоритм
банкира. Вторая проблема состоит в том, что при таком подходе ресурсы не будут
использоваться оптимально. Возьмем, к примеру, процесс, считывающий данные
с входной ленты, анализирующий их в течение часа, а затем записывающий выход-
ную ленту, да еще и выводящий результаты на плоттер. Если все ресурсы должны
быть запрошены заранее, то процессор на целый час займет выходной накопитель
на магнитной ленте и плоттер.
И все-таки некоторые пакетные системы на универсальных машинах требуют, чтобы
пользователи перечисляли все ресурсы в первой строке каждого задания. Затем система
немедленно заранее распределяет все ресурсы и удерживает их до тех пор, пока они
станут не нужны заданию (или в простейшем случае, пока выполнение задания не будет
завершено). Несмотря на то что этот метод обременяет программиста и расточительно
расходует ресурсы, он предотвращает возникновение взаимоблокировок.
Слегка отличающийся метод нарушения условия удержания и ожидания заключается
в требовании от процесса, запрашивающего ресурс, вначале временно высвободить все
ресурсы, удерживаемые им на данный момент. Затем этот процесс пытается заполучить
сразу все, что ему требуется.
512
Глава 6. Взаимоблокировка
6.6.3. Атака условия невыгружаемости
Возможна также атака и третьего условия (невыгружаемости). Если процессу выделен
принтер и он распечатал лишь половину своих выходных данных, то принудительно
отобрать у него принтер по причине недоступности запрошенного плоттера в лучшем
случае будет слишком затруднительно, а в худшем — просто невозможно. Тем не
менее, чтобы избежать подобной ситуации, некоторые ресурсы могут быть виртуа-
лизированы. Сохранение очереди на печать на диске и предоставление возможности
доступа к реальному принтеру только демону принтера исключает возникновение
взаимоблокировок с участием принтера, хотя и создает одну из таких потенциальных
возможностей в отношении дискового пространства. Но при наличии дисков большой
емкости исчерпание дискового пространства становится маловероятным.
Однако не все ресурсы могут быть виртуализированы подобным образом. К примеру,
чтобы записи в базах данных или в таблицах внутри операционной системы могли ис-
пользоваться, они должны быть заблокированы, и здесь закладывается потенциальная
вероятность взаимоблокировки.
6.6.4. Атака условия циклического ожидания
Осталось только одно условие. Циклическое ожидание можно устранить несколькими
способами. Один из них заключается в простом выполнении правила, которое гласит,
что процессу в любой момент времени дано право только на один ресурс. Если нужен
второй ресурс, процесс обязан освободить первый. Но подобное ограничение непри-
емлемо для процесса, копирующего огромный файл с магнитной ленты на принтер.
Другой способ, позволяющий избежать циклического ожидания, заключается в под-
держке общей нумерации всех ресурсов (рис. 6.11, а). Теперь действует следующее
правило: процессы могут запрашивать ресурс, когда только пожелают, но все запросы
должны быть сделаны в порядке нумерации ресурсов. Процесс может запросить сна-
чала принтер, затем накопитель на магнитной ленте, но не может сначала потребовать
плоттер, а затем принтер.
Если придерживаться этого правила, то у графа распределения ресурсов никогда не
будет циклов. Посмотрим, почему это имеет место в случае двух процессов, показанных
на рис. 6.11, б. Взаимоблокировка может произойти, только если процесс A запросит
ресурс j, а процесс B запросит ресурс i. Предположим, что ресурсы i и j относятся к раз-
ным типам, тогда они будут иметь и разные номера. Если i > j, то процессу A не разре-
шается запрашивать ресурс j, потому что его номер меньше, чем номер уже имеющегося
у него ресурса. Если же i < j, то процесс B не может запрашивать ресурс i, потому что
его номер меньше номера уже удерживаемого этим процессом ресурса. Так или иначе,
взаимоблокировка невозможна.
При работе более чем с двумя процессами сохраняется та же самая логика. В любой
момент времени один из предоставленных ресурсов будет иметь наивысший номер.
Процесс, использующий этот ресурс, никогда не запросит тот ресурс, который уже
распределен. Он или закончит свою работу, или, в худшем случае, запросит ресурс
с еще большим номером, а все такие ресурсы доступны. В итоге процесс завершит
работу и высвободит свои ресурсы. К этому времени какой-нибудь другой процесс
будет удерживать ресурс с самым большим номером и тоже сможет завершить свою
работу. Короче говоря, существует сценарий, по которому все процессы завершают
свою работу, поэтому никаких взаимоблокировок и не возникает.
6.7. Другие вопросы
513
Рис. 6.11. а — пронумерованные ресурсы; б — граф ресурсов
При незначительном изменении этого алгоритма исключается требование приоб-
ретения ресурсов в строго возрастающем порядке и просто требуется, чтобы ни один
процесс не запрашивал ресурс с меньшим номером, чем номер того ресурса, который
он уже удерживает. Если процесс сначала запрашивает ресурсы 9 и 10, а затем вы-
свобождает их обоих, то это во всех отношениях равнозначно новому началу работы,
поэтому теперь уже незачем запрещать ему запрос ресурса 1.
Хотя порядковая нумерация ресурсов исключает проблему взаимоблокировок, может
не представиться возможности подобрать порядок, удовлетворяющий абсолютно всех.
Когда ресурсы включают в себя элементы таблицы процессов, дисковое пространство
очереди печати, заблокированные записи базы данных и другие абстрактные ресурсы,
количество потенциальных ресурсов и различных применений может быть настолько
большим, что не сможет работать никакое упорядочение.
Различные методы предупреждения взаимоблокировок сведены в табл. 6.1.
Таблица 6.1. Методы предупреждения взаимоблокировок
Условие
Метод
Взаимное исключение
Организация очереди на диске
Удержание и ожидание
Изначальный запрос всех ресурсов
Невыгружаемость
Отобрать ресурсы
Циклическое ожидание
Провести порядковую нумерацию ресурсов
6.7. Другие вопросы
В этом разделе будет рассмотрен ряд разнообразных вопросов, имеющих отношение
к взаимоблокировкам (тупиковым ситуациям), среди которых двухфазное блокиро-
вание, взаимоблокировка, не связанная с ресурсами, а также зависание.
6.7.1. Двухфазное блокирование
Хотя и уклонение от взаимоблокировок, и предупреждение их возникновения в общем
случае оказались не слишком перспективными средствами, для определенных при-
ложений известно множество превосходных алгоритмов специального назначения.
К примеру, во многих системах управления базами данных часто встречающимися
операциями являются запросы на блокирование нескольких записей с последующим
обновлением всех заблокированных записей. Когда одновременно запущено несколько
процессов, существует реальная опасность возникновения взаимоблокировок.
514
Глава 6. Взаимоблокировка
Часто используемый при этом подход называется двухфазным блокированием. В пер-
вой фазе процесс пытается заблокировать по одной все необходимые ему записи. Если
все проходит успешно, он приступает ко второй фазе, осуществляя свои обновления
и снимая блокировку. При этом в первой фазе не проводится никакой реальной работы.
Если в первой фазе встретятся некоторые необходимые записи, которые уже заблоки-
рованы, процесс просто снимает все свои блокировки и начинает первую фазу заново.
В определенном смысле этот подход аналогичен предварительному запросу необходи-
мых ресурсов или, по крайней мере, запросу до того, как произойдет нечто необратимое.
В некоторых версиях двухфазного блокирования, если заблокированная запись обнару-
жилась во время первой фазы, никакого снятия блокировок и перезапуска первой фазы
с начала не происходит. Эти версии подвержены возникновению взаимоблокировок.
Но эта стратегия в общем виде неприменима. К примеру, в системах реального времени
и системах управления процессами остановка процесса на полпути только из-за недо-
ступности ресурса и его повторный запуск с самого начала просто недопустимы. Нельзя
также перезапускать процесс, если он считал с сети или запустил в сеть сообщение,
обновил файлы и сделал что-нибудь еще, что не может быть безопасно повторено еще
раз. Алгоритм работает только в том случае, когда программист очень тщательно все
подготовил таким образом, что программу можно остановить в любой точке первой
фазы и запустить заново. Многие программы не могут быть структурированы таким
образом.
6.7.2. Взаимные блокировки при обмене данными
До сих пор вся наша работа сосредотачивалась на взаимоблокировках, связанных с ис-
пользованием ресурсов. Один процесс нуждается в том, чем обладает другой процесс,
и должен ждать, пока тот не высвободит то, что он удерживает. Иногда в качестве
ресурсов выступают аппаратные или программные объекты, к примеру приводы Blu-
ray-дисков или записи базы данных, а иногда они имеют более абстрактную форму.
Ресурсная взаимоблокировка является проблемой синхронизации соперничества.
Независимые процессы завершат обслуживание, если их выполнение не будет чере-
доваться с соперничающими процессами. Процесс блокирует ресурсы с целью предот-
вращения их непоследовательного состояния, вызываемого чередующимся доступом
к ресурсам. В листинге 6.2 показана ресурсная взаимоблокировка, где в качестве
ресурсов выступают семафоры. Это намного более абстрактное понятие, чем привод
Blu-ray-дисков, но в этом примере каждый процесс успешно получает ресурс (один
из семафоров) и попадает во взаимоблокировку, пытаясь получить еще один ресурс
(другой семафор). Эта ситуация представляет собой классическую взаимоблокировку,
связанную с использованием ресурсов.
Как уже упоминалось в начале главы, хотя ресурсные взаимоблокировки и являются
наиболее распространенным видом, но они не единственные в своем роде. Другая раз-
новидность взаимоблокировок может проявиться в системах обмена данными (напри-
мер, сетях), в которых один и более процессов связываются путем обмена сообщения-
ми. Общая договоренность предполагает, что процесс A отправляет сообщение-запрос
процессу B, а затем блокируется до тех пор, пока B не пошлет назад ответное сообще-
ние. Предположим, что сообщение-запрос где-то затерялось. Процесс A заблокирован
в ожидании ответа. Процесс B заблокирован в ожидании запроса на какие-либо его
действия. В результате возникает взаимоблокировка.
6.7. Другие вопросы
515
Но это не является классической взаимоблокировкой, связанной с ресурсами. Про-
цесс A не обладает какими-то ресурсами, которые нужны процессу B, и наоборот.
Фактически никаких ресурсов здесь нет и в помине. Но тем не менее это взаимобло-
кировка, соответствующая формальному определению, поскольку есть группа из двух
процессов, каждый из которых заблокирован, ожидая события, причиной которого
может быть только другой процесс. Подобную ситуацию назвали коммуникационной
взаимоблокировкой
, чтобы отличить ее от более распространенной ресурсной взаимо-
блокировки. Коммуникационная взаимоблокировка является аномальным вариантом
синхронизации совместных действий. Процесс в этом типе взаимной блокировки не
может завершить обслуживание, если выполняется независимо от других процессов.
Коммуникационные взаимоблокировки не могут быть предотвращены за счет упо-
рядочения ресурсов (за неимением таковых) или обойдены за счет тщательного
планирования (поскольку здесь нет моментов, когда запрос может быть отложен).
К счастью, существует другая технология, которая обычно может быть применена для
прекращения коммуникационной взаимоблокировки, — истечение времени ожидания.
В большинстве сетевых систем обмена данными, как только послано сообщение, на
которое ожидается ответ, тут же запускается таймер. Если выставленное в таймере
время истечет до поступления ответа, отправитель сообщения предположит, что со-
общение затерялось, и пошлет его снова (и снова, и снова, если нужно). Таким образом
взаимоблокировка будет предотвращена. Иначе говоря, истечение времени ожидания
служит эвристическим средством обнаружения взаимных блокировок и позволяет
восстановить нормальную работу системы.
Разумеется, если исходное сообщение не было утрачено, а ответ просто задержался,
намеченный получатель может получить сообщение два или более раз, возможно,
с нежелательными последствиями. Представьте себе систему электронного банкинга,
в которой сообщение содержит команду на производство платежа. Вполне понятно,
что это сообщение не должно быть повторено (и исполнено) несколько раз только
потому, что сеть работает медленно или время ожидания выбрано слишком коротким.
Разработка правил обмена данными, называемых протоколом и применяемых, чтобы
все проходило должным образом, — дело нелегкое и лежит за пределами рассматри-
ваемой в этой книге тематики.
Читатели, заинтересовавшиеся сетевыми протоколами, могут обратиться к другой
книге автора — «Computer Networks»
1
(Tanenbaum and Wetherall, 2010). Не все взаимо-
блокировки, случающиеся в системах обмена данными или в сетях, относятся к комму-
никационным. Здесь могут встречаться и ресурсные взаимоблокировки. Рассмотрим,
к примеру, сеть, показанную на рис. 6.12. Здесь изображен весьма упрощенный взгляд
на Интернет. Согласно рисунку, Интернет состоит из двух видов компьютеров: хостов
и маршрутизаторов. Хост (host) — это пользовательский компьютер, либо чей-то до-
машний планшетный или персональный компьютер, либо компьютер в компании, либо
корпоративный сервер. Хосты работают на людей. Маршрутизатор (роутер, router)
является специализированным коммуникационным компьютером, перемещающим
пакеты с данными от источника к приемнику. Каждый хост подключен к одному или
нескольким маршрутизаторам по DSL-каналу, телевизионному кабелю, локальной
сети, обычной телефонной линии, беспроводной сети, оптическому кабелю либо по
чему-нибудь еще.
1
Таненбаум Э. Компьютерные сети. 4-е изд. — СПб.: Питер, 2010.