ЗАНЯТИЕ 24. «ВЗАИМОБЛОКИРОВКА»

В компьютерных системах множество ресурсов, которые одновременно могут использоваться только одним процессом. Стоит лишь вспомнить принтеры, накопители на магнитной ленте для резервного копирования данных компаний и элементы во внут¬ренних системных таблицах. Если два процесса одновременно вы¬водят информацию на принтер, то получается полная тарабарщина. Если два процесса будут использовать один и тот же элемент таб¬лицы файловой системы, то эта система непременно будет повре¬ждена. Поэтому все операционные системы способны временно предоставлять процессу исключительные права доступа к конкрет¬ным ресурсам.
При работе многих приложений процессу нужен исключи¬тельный доступ не к одному, а сразу к нескольким ресурсам. Пред¬положим, к примеру, что каждый из двух процессов захотел запи¬сать отсканированный документ на Blu-ray-диск (многослойный DVD диск большой емкости). Процесс A запрашивает разрешение на использование сканера и получает его. Процесс B запрограмми¬рован по-другому: сначала он запрашивает разрешение на исполь¬зование пишущего привода Blu-ray-дисков и также получает это разрешение. Теперь A запрашивает разрешение на использование пишущего привода Blu-ray-дисков, но запрос отклоняется до тех пор, пока это устройство не будет освобождено процессом B. К со-жалению, вместо того чтобы освободить привод, B запрашивает разрешение на использование сканера. И в этот момент оба про¬цесса оказываются заблокированными навсегда. Такая ситуация называется тупиковой ситуацией (тупиком), или взаимоблокиров-кой (deadlock).
Взаимоблокировки могут случаться и между машинами. К примеру, многие офисы оборудованы локальной сетью, к которой подключено множество компьютеров. Довольно часто такие устройства, как сканеры, пишущие приводы Blu-ray-дисков и DVD, принтеры и приводы накопителей на магнитной ленте, подключены к сети в качестве ресурсов общего пользования, доступных любому пользователю на любой машине. Если эти устройства могут быть дистанционно зарезервированы (например, с домашнего компью¬тера пользователя), то может возникнуть взаимоблокировка, похо¬жая на только что рассмотренную. При более сложных обстоятель¬ствах во взаимоблокировку могут быть вовлечены три, четыре и более устройств и пользователей.
Взаимоблокировки могут возникать и при массе других об¬стоятельств. К примеру, в системах управления базами данных, во избежание попадания в состояние состязания программе может по¬надобиться блокировка нескольких используемых ею записей. Если процесс A блокирует запись R1, а процесс B блокирует запись R2, а затем каждый процесс пытается заблокировать запись другого про¬цесса, то получается та же взаимоблокировка. Таким образом, вза¬имоблокировки могут появляться при работе как с аппаратными, так и с программными ресурсами.

21.1 Ресурсы

Основная часть взаимоблокировок связана с ресурсами, к которым некоторым процессам были предоставлены исключитель¬ные права доступа. К их числу относятся устройства, записи дан¬ных, файлы и т. д. Чтобы придать рассмотрению взаимоблокировок как можно более универсальный характер, мы будем называть объ¬екты, к которым предоставляется доступ, ресурсами. Ресурсами могут быть аппаратные устройства (например, привод Blu-ray-дис¬ков) или какая-то часть информации (например, запись базы дан¬ных). Обычно у компьютера может быть множество ресурсов, ко¬торые могут быть предоставлены процессу. Некоторые ресурсы могут быть доступны в нескольких идентичных экземплярах, например три привода Blu-ray-дисков. Когда доступны несколько копий ресурса, то для удовлетворения любого запроса на ресурс может быть использован один из них. Короче говоря, под ресурсом понимается все, что должно предоставляться, использоваться и че¬рез некоторое время высвобождаться, поскольку в один и тот же момент времени может использоватьс только одним процессом.

Выгружаемые и невыгружаемые ресурсы

Ресурсы бывают двух видов: выгружаемые и невыгружае¬мые. К выгружаемым относятся такие ресурсы, которые могут быть безболезненно отобраны у процесса, который ими обладает. При¬мером такого ресурса может послужить память. Рассмотрим си¬стему, имеющую 1 Гбайт пользовательской памяти, один принтер и два процесса по 1 Гбайт, каждый из которых хочет что-то вывести на печать. Процесс A запрашивает и получает принтер, а затем начинает вычислять значение, предназначенное для вывода на пе¬чать. Но до завершения вычисления истекает выделенный ему квант времени, и он выгружается на диск.
Теперь запускается процесс B, безуспешно, как оказыва¬ется, пытаясь завладеть принтером. Потенциально возникает ситуа¬ция взаимоблокировки, поскольку у процесса A есть принтер, а у процесса B — память и ни один из них не может продолжить свою работу без ресурса, удерживаемого другим процессом.
К счастью, есть возможность отобрать память у процесса B, выгрузив этот процесс на диск, и загрузить оттуда процесс A. Те¬перь A может возобновить свою работу, выполнить распечатку и высвободить принтер. И никакой взаимоблокировки не возникнет.
А вот невыгружаемый ресурс нельзя отобрать у его теку¬щего владельца, не вызвав потенциально сбоя в вычислениях. Если у процесса, который уже приступил к записи на Blu-ray-диск, вне¬запно отобрать пишущий привод и отдать его другому процессу, это приведет к порче Blu-ray-диска. Пишущие приводы Blu-ray-дисков нельзя отобрать в произвольный момент.
Выгружаемость ресурса зависит от контекста. На стандарт¬ном персональном компьютере память является выгружаемым ре¬сурсом, поскольку страницы всегда могут быть выгружены на диск, чтобы нужный объем свободной памяти был восстановлен. А на смартфоне, не поддерживающем свопинг (способ организацтт па¬мяти) или страничную организацию памяти, простой выгрузкой взаимоблокировки из-за дефицита памяти избежать не удастся.
Ресурсы бывают двух видов: выгружаемые и невыгружае¬мые. К выгружаемым относятся такие ресурсы, которые могут быть безболезненно отобраны у процесса, который ими обладает. При¬мером такого ресурса может послужить память. Рассмотрим си¬стему, имеющую 1 Гбайт пользовательской памяти, один принтер и два процесса по 1 Гбайт, каждый из которых хочет что-то вывести на печать. Процесс A запрашивает и получает принтер, а затем начинает вычислять значение, предназначенное для вывода на пе¬чать. Но до завершения вычисления истекает выделенный ему квант времени, и он выгружается на диск.
Теперь запускается процесс B, безуспешно, как оказыва¬ется, пытаясь завладеть принтером. Потенциально возникает ситуа¬ция взаимоблокировки, поскольку у процесса A есть принтер, а у процесса B — память и ни один из них не может продолжить свою работу без ресурса, удерживаемого другим процессом.
К счастью, есть возможность отобрать память у процесса B, выгрузив этот процесс на диск, и загрузить оттуда процесс A. Те¬перь A может возобновить свою работу, выполнить распечатку и высвободить принтер. И никакой взаимоблокировки не возникнет.
А вот невыгружаемый ресурс нельзя отобрать у его теку¬щего владельца, не вызвав потенциально сбоя в вычислениях. Если у процесса, который уже приступил к записи на Blu-ray-диск, вне¬запно отобрать пишущий привод и отдать его другому процессу, это приведет к порче Blu-ray-диска. Пишущие приводы Blu-ray-дисков нельзя отобрать в произвольный момент.
Выгружаемость ресурса зависит от контекста. На стандарт¬ном персональном компьютере память является выгружаемым ре¬сурсом, поскольку страницы всегда могут быть выгружены на диск, чтобы нужный объем свободной памяти был восстановлен. А на смартфоне, не поддерживающем свопинг или страничную органи¬зацию памяти, простой выгрузкой взаимоблокировки из-за дефи¬цита памяти избежать не удастся.
Как правило, во взаимоблокировках фигурируют невыгру¬жаемые ресурсы. Обычно потенциальные взаимоблокировки с уча¬стием выгружаемых ресурсов могут быть устранены путем пере¬распределения ресурсов от одного процесса к другому. Поэтому наше внимание будет сконцентрировано на невыгружаемых ресур¬сах.
В наиболее общем виде при использовании ресурса проис¬ходит следующая последовательность событий:

1. Запрос ресурса.
2. Использование ресурса.
3. Высвобождение ресурса.
   Если во время запроса ресурс недоступен, запрашивающий процесс вынужден перейти к ожиданию. В некоторых операцион¬ных системах при отказе в выделении запрошенного ресурса про¬цесс автоматически блокируется, а когда ресурс становится досту-пен — возобновляется. В других системах отказ в выделении за¬прашиваемого ресурса сопровождается кодом ошибки, и принятие решения о том, что следует делать, немного подождать или попы¬таться снова получить ресурс, возлагается на вызывающий процесс.
   Процесс, чей запрос на выделение ресурса был только что отклонен, обычно входит в короткий цикл: запрос ресурса, затем приостановка, — после чего повторяет попытку. Хотя этот процесс не заблокирован, но по всем показателям он является фактически заблокированным, поскольку не может выполнять никакой полез¬ной работы. При дальнейшем рассмотрении вопроса мы будем предполагать, что при отказе в выделении запрошенного ресурса процесс впадает в спячку.
   Особенности запроса ресурса существенно зависят от ис¬пользуемой системы. В некоторых системах для запроса предостав¬ляется системный вызов request, позволяющий процессам запросить ресурс в явном виде. В других системах единственными ресурсами, о которых знает операционная система, являются специальные файлы, которые в конкретный момент времени могут быть открыты только одним процессом. Они открываются с использованием обычного вызова open. Если файл уже используется, вызывающий процесс блокируется до тех пор, пока файл не будет закрыт теку¬щим владельцем.

Получение ресурса

Для некоторых видов ресурсов, таких как записи в базе дан¬ных, управление использованием ресурсов зависит от самих поль¬зовательских процессов, а не от системы. Один из способов, позво¬ляющих ввести пользовательское управление ресурсами, заключа-ется в присоединении семафора (Тип переменной. Значение сема¬фора может быть равно 0, что будет свидетельствовать об отсут¬ствии сохраненных активизаций, или иметь какое-нибудь положи¬тельное значение, если ожидается не менее одной активизации). к каждому из ресурсов.
Все эти семафоры получают исходное значение, равное 1. С таким же успехом могут использоваться и мьютексы. Перечислен¬ные ранее три этапа затем воплощаются в применение к семафору вызова down для получения ресурса, использование ресурса и, в завершение, применение вызова up при высвобождении ресурса. Эти этапы показаны в листинге 3, а.

Листинг 3. Использование семафоров для защиты: а — одного ресурса; б — двух  ресурсов

typedef int semaphore; semaphore resource_1;  void process_A(void) {      down(&resource_1);      use_resource_1( );      up(&resource_1); }   а

typedef int semaphore; semaphore resource_1; semaphore resource_2; void process_A(void) {      down(&resource_1);      down(&resource_2);      use_both_resources( );      up(&resource_2);      up(&resource_1); } б

Иногда процессы нуждаются в двух и более ресурсах. Их можно получать последовательно, как показано в листинге 3, б. Если требуется больше двух ресурсов, их запрашивают непосред­ственно один за другим.

Пока все идет хорошо. Пока речь идет только об одном процессе, все работает нормально. Конечно, когда используется только один процесс, нет нужды в формальном получении ресур­сов, поскольку нет соперничества за обладание ими.

Теперь рассмотрим ситуацию с двумя процессами — A и B — и двумя ресурсами. В листинге 4 показаны два сценария: а — оба процесса запрашивают ресурсы в одном и том же порядке; б — запрашивают ресурсы в разном порядке. Разница может показаться несущественной, но это не так.

Листинг 4. Код: а — не вызывающий взаимоблокировки; б — в котором кроется потенциальная возможность взаимоблокировки

typedef int semaphore; semaphore resource_1; semaphore resource_2; void process_A(void) {      down(&resource_1);      down(&resource_2);      use_both_resources( );      up(&resource_2);      up(&resource_1); }   void process_B(void) {     down(&resource_1);     down(&resource_2);     use_both_resources( );     up(&resource_2);     up(&resource_1); }	semaphore resource_1; semaphore resource_2; void process_A(void) {      down(&resource_1);      down(&resource_2);      use_both_resources( );      up(&resource_2);      up(&resource_1); }   void process_B(void){     down(&resource_2);     down(&resource_1);     use_both_resources( );     up(&resource_1);     up(&resource_2); }
a	б

В листинге 4, а один из процессов запрашивает первый ре­сурс раньше, чем это делает второй процесс. Затем этот же процесс успешно получает второй ресурс и выполняет свою работу. Если второй процесс попытается получить ресурс 1 до его высвобожде­ния, то он будет просто заблокирован до тех пор, пока ресурс не станет доступен.

В листинге 4, б показана другая ситуация. Может случиться, что один из процессов получит оба ресурса и надежно заблокирует другой процесс до тех пор, пока не сделает свою работу. Но может случиться и так, что процесс A получит ресурс 1, а процесс B полу­чит ресурс 2. Каждый из них теперь будет заблокирован при по­пытке получения второго ресурса. Ни один из процессов не возоб­новит свою работу. Плохо то, что возникнет ситуация взаимобло­кировки.

Здесь мы видим, что происходит из-за небольшой разницы в стиле программирования: в зависимости от того, какой из ресурсов будет получен первым, программа либо работает, либо дает труд­ноопределимый сбой. Поскольку взаимоблокировки могут возни­кать столь просто, для борьбы с ними были проведены обширные исследования.

21.2 Введение во взаимоблокировки

Взаимоблокировкам можно дать следующее формальное определение.

Взаимоблокировка в группе процессов возникает в том случае, если каждый процесс из этой группы ожидает события, наступление которого зависит исключительно от другого про­цесса из этой же группы.

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

В большинстве случаев событием, наступления которого ожидает каждый процесс, является высвобождение какого-либо ресурса, которым на данный момент владеет другой участник группы. Иными словами, каждый процесс из группы, попавшей в ситуацию взаимоблокировки, ожидает ресурса, которым обладает другой процесс из этой же группы. Ни один из процессов не может работать, ни один из них не может высвободить какой-либо ресурс, и ни один из них не может возобновить свою работу. Количество процессов и количество и вид удерживаемых и запрашиваемых ре­сурсов не имеет значения. Этот результат сохраняется для любого типа ресурсов, включая аппаратные и программные ресурсы. Этот вид взаимоблокировки называется ресурсной взаимоблокировкой. Наверное, это самый распространенный, но далеко не единствен­ный вид.

Условия возникновения ресурсных взаимоблокировок

Коффман (Coffman et al., 1971) показал, что для возникно¬вения ресурсных взаимоблокировок должны выполняться четыре условия:

1. Условие взаимного исключения. Каждый ресурс либо выде¬лен в данный момент только одному процессу, либо досту¬пен.
2. Условие удержания и ожидания. Процессы, удерживающие в данный момент ранее выделенные им ресурсы, могут запра¬шивать новые ресурсы.
3. Условие невыгружаемости. Ранее выделенные ресурсы не мо¬гут быть принудительно отобраны у процесса. Они должны быть явным образом высвобождены тем процессом, который их удерживает.
4. Условие циклического ожидания. Должна существовать коль¬цевая последовательность из двух и более процессов, каждый из которых ожидает высвобождения ресурса, удерживаемого следующим членом последовательности.
   Для возникновения ресурсной взаимоблокировки должны соблюдаться все четыре условия. Если одно из них не соблюдается, ресурсная взаимоблокировка невозможна.
   Следует заметить, что каждое условие относится к той по¬литике, которой придерживается или не придерживается система. Может ли данный ресурс быть выделен одновременно более чем одному процессу? Может ли процесс удерживать ресурс и запра-шивать другой ресурс? Может ли ресурс быть отобран? Может ли получиться циклическое ожидание? Чуть позже мы увидим, как взаимоблокировке может противостоять попытка устранения неко¬торых из этих условий.

Моделирование взаимоблокировок

Холт (Holt, 1972) показал, как эти четыре условия могут быть смоделированы с использованием направленных графов. У графов имеется два вида узлов: процессы, показанные окружно¬стями, и ресурсы, показанные квадратами. Направленное ребро, которое следует от узла ресурса (квадрата) к узлу процесса (окруж¬ности), означает, что этот ресурс был ранее запрошен, получен и на данный момент удерживается этим процессом. На рис. 74, а ресурс R в данное время выделен процессу A.
Направленное ребро, идущее от процесса к ресурсу, озна¬чает, что процесс в данное время заблокирован в ожидании высво¬бождения этого ресурса. На рис. 74, б процесс B ожидает высво¬бождения ресурса S. На рис. 74, в мы наблюдаем взаимоблоки¬ровку: процесс C ожидает высвобождения ресурса T, который в данный момент удерживается процессом D. Процесс D не собира¬ется высвобождать ресурс T, поскольку он ожидает высвобождения ресурса U, удерживаемого процессом C. Оба процесса находятся в состоянии вечного ожидания. Циклическая структура графа озна¬чает, что мы имеем дело с взаимоблокировкой, включившей про¬цессы и ресурсы в цикл (предполагается, что в системе есть только один ресурс каждого типа). В данном примере получился следую¬щий цикл: C–T–D–U–C.

Рассмотрим пример того, как могут быть использованы графы ресурсов. Представим, что есть три процесса, A, B и C, и три ресурса, R, S и T. Последовательности действий по запросу и высвобождению ресурсов, осуществляемые этими тремя процессами, показаны на рис. 75, а–в. Операционная система может в любое время запустить любой незаблокированный процесс, то есть она может принять решение запустить процесс A и дождаться, пока он не завершит всю свою работу, затем запустить процесс B и довести его работу до завершения и, наконец, запустить процесс C.
Такой порядок не приводит к взаимоблокировкам (поскольку отсутствует борьба за овладение ресурсами), но в нем нет и никакой параллельной работы. Кроме действий по запросу и высвобождению ресурсов процессы занимаются еще и вычислениями, и вводом-выводом данных. Когда процессы запускаются последовательно, отсутствует возможность использования центрального процессора одним процессом, в то время когда другой процесс ожидает завершения операции ввода-вывода. Поэтому строго последовательное выполнение процессов может быть не оптимальным решением. В то же время, если ни один из процессов не выполняет никаких операций ввода-вывода, алгоритм, при котором кратчайшее задание выполняется первым, более привлекателен, чем циклический алгоритм, поэтому при определенных условиях последовательный запуск всех процессов может быть наилучшим решением.
Теперь предположим, что процессы занимаются как вводом-выводом, так и вычислениями, поэтому наиболее разумным алгоритмом планирования их работы является циклический алгоритм. Запросы ресурсов могут происходить в том порядке, который показан на рис. 75, г. Если эти шесть запросов выполняются именно в этом порядке, им соответствую шесть результирующих ресурсных графов, показанных на рис. 75, д–к. После выдачи запроса 4 процесс A, как показано на рис. 75, з, блокируется в ожидании ресурса S. На следующих двух этапах процессы B и C также блокируются, что в итоге приводит к зацикливанию и возникновению взаимоблокировки, показанной на рис. 75, к.

Но как уже ранее упоминалось, от операционной системы не требовалось запускать процессы в каком-то определенном по¬рядке. В частности, если удовлетворение конкретного запроса мо¬жет привести к взаимоблокировке, операционная система может просто приостановить процесс, не удовлетворяя его запрос (то есть просто не планируя работу процесса) до тех пор, пока это не будет безопасно. На рис. 75, если операционная система знает о грядущей взаимоблокировке, она может приостановить процесс B, вместо того чтобы выделить ему ресурс S. Запуская только процессы A и C, мы получим такую последовательность действий по запросу и высвобождению ресурсов, которая показана на рис. 75, л, а не ту, которая показана на рис. 75, г. Эта последовательность отобража¬ется ресурсным графом, показанным на рис. 75, м–с, и не приводит к взаимоблокировке.
По окончании этапа, показанного на рис. 75, с, процессу B может быть выделен ресурс S, поскольку процесс A завершил свою работу, а процесс C имеет все необходимое. Даже если B заблоки¬руется при запросе ресурса T, взаимоблокировки не возникнет. Процесс B просто будет ждать, пока процесс C не завершит свою работу.
Нужно понять, что ресурсные графы являются инструмен¬том, позволяющим понять, приводит ли данная последовательность запросов/возвратов ресурсов к взаимоблокировке. Мы всего лишь шаг за шагом осуществляем запросы и возвраты ресурсов и после каждого шага проверяем граф на наличие каких-либо циклов. Если образуется цикл, значит, возникла взаимоблокировка, а если нет, значит, нет и взаимоблокировки. Хотя здесь рассматривался граф ресурсов, составленный для случая использования по одному ре¬сурсу каждого типа, ресурсные графы могут быть применены также для обработки нескольких ресурсов одного и того же типа (Holt, 1972).
Чаще всего для борьбы с взаимными блокировками исполь¬зуются четыре стратегии:

1. Игнорирование проблемы. Может быть, если вы про¬игнорируете ее, она проиг норирует вас.
2. Обнаружение и восстановление. Дайте взаимоблокиров¬кам проявить себя, обнаружьте их и выполните необходимые дей¬ствия.
3. Динамическое уклонение от них за счет тщательного рас¬пределения ресурсов.
4. Предотвращение за счет структурного подавления одного из четырех условий, необходимых для их возникновения.

21.3. Страусиный алгоритм

Самым простым подходом к решению проблемы является «страусиный алгоритм»: спрячьте голову в песок и сделайте вид, что проблема отсутствует1. Люди реагируют на эту стратегию по-разному. Математики считают ее неприемлемой и говорят, что вза-имоблокировки следует предотвращать любой ценой. Инженеры спрашивают, как часто ожидается возникновение проблемы, как часто система дает сбой по другим причинам и насколько серьезны последствия взаимоблокировки. Если взаимоблокировка возникает в среднем один раз в пять лет, а система раз в неделю сбоит из-за технических отказов и дефектов операционной системы, большин¬ство инженеров не захотят платить за избавление от взаимоблоки¬ровок существенным снижением производительности или удобства использования.
Чтобы усилить контраст между этими двумя позициями, рассмотрим операционную систему, которая блокирует вызываю¬щий процесс, когда системный вызов open, относящийся к такому физическому устройству, как привод Blu-ray-диска или принтер, не может быть выполнен из-за занятости устройства. Обычно именно драйвер устройства решает, какое действие и при каких обстоя¬тельствах предпринять. Две вполне очевидные возможности — это блокировка или возвращение кода ошибки. Если одному процессу удастся «открыть» привод Blu-ray-дисков, а другому посчастли¬вится «открыть» принтер, а затем каждый процесс попытается «от¬крыть» еще и другой ресурс и его попытка будет заблокирована, возникнет взаимоблокировка. Лишь немногие современные си¬стемы в состоянии обнаружить подобную ситуацию.

21.4. Обнаружение взаимоблокировок и восстановление работоспособности

Вторая по счету — технология обнаружения и восстановле¬ния. При ее использовании система не пытается предотвращать взаимоблокировки. Она позволяет им произойти, пытается обнару¬жить момент их возникновения, а затем предпринимает некоторые действия по восстановлению работоспособности.
Обнаружение взаимоблокировки при использовании одного ресурса каждого типа

Начнем с самого простого случая, когда используется только один ресурс каждого типа. У системы может быть один ска¬нер, один пишущий привод Blu-ray-дисков, один плоттер и один накопитель на магнитной ленте, но только по одному экземпляру каждого класса ресурсов. Иными словами, мы временно исключаем системы, имеющие два принтера. Они будут рассмотрены позже с использованием другого метода.
Для такой системы можно построить ресурсный граф (рис. 74). Если этот граф содержит один и более циклов, значит, мы имеем дело с взаимоблокировкой. Любой процесс, являющийся частью цикла, заблокирован намертво. Если циклов нет, значит, система не находится в состоянии взаимоблокировки.
В качестве примера более сложной системы по сравнению с ранее рассмотренными, возьмем систему с семью процессами от A до G и шестью ресурсами от R до W. Каждый ресурс находится в состоянии текущей занятости, и на каждый ресурс в данный мо¬мент поступил запрос:

1. Процесс A удерживает R и хочет получить S.
2. Процесс B не удерживает никаких ресурсов, но хочет полу¬чить T.
3. Процесс C не удерживает никаких ресурсов, но хочет полу¬чить S.
4. Процесс D удерживает U и хочет получить S и T.
5. Процесс E удерживает T и хочет получить V.
6. Процесс F удерживает W и хочет получить S.
7. Процесс G удерживает V и хочет получить U.
   Возникает следующий вопрос: «Находится ли эта система в состоянии взаимоблокировки, и если находится, то какие процессы вовлечены в это состояние?»
   Чтобы ответить на этот вопрос, можно построить граф ре¬сурсов (рис. 75, а). Этот граф содержит один цикл, который можно обнаружить визуально. Этот цикл показан на рис. 75, б. Из цикла видно, что процессы D, E и G вовлечены во взаимоблокировку. Процессы A, C и F не находятся в состоянии взаимоблокировки, поскольку ресурс S может быть выделен любому из них, который затем закончит свою работу и вернет ресурс. Затем оставшиеся два процесса смогут взять его по очереди и также завершить свою ра¬боту. (Заметьте, чтобы сделать этот пример немного интереснее, мы позволили процессам, а именно процессу D, запрашивать одно¬временно два ресурса.)

Хотя визуально выделить взаимоблокировку из простого графа относительно нетрудно, для использования в настоящих си¬стемах нужен формальный алгоритм обнаружения взаимоблокиро¬вок. Известно множество алгоритмов для обнаружения циклов в направленных графах. Далее будет приведен простой алгоритм, проверяющий граф и прекращающий свою работу либо при обна¬ружении цикла, либо при обнаружении отсутствия циклов. В нем используется одна динамическая структура данных, L, представля-ющая собой список узлов, а также список ребер. В процессе работы алгоритма ребра будут помечаться для обозначения того, что они уже были проверены, чтобы предотвратить повторные проверки.
Действие алгоритма основано на выполнении следующих шагов:

1. Для каждого узла N, имеющегося в графе, выполняются следующие пять шагов, использующих узел N в качестве началь¬ного.
2. Инициализируется (очищается) список L, а со всех ребер снимаются пометки.
3. Текущий узел добавляется к концу списка L, и прово¬дится проверка, не появится ли этот узел в списке L дважды. Если это произойдет, значит, граф содержит цикл (отображенный в списке L), и алгоритм прекращает работу.
4. Для заданного узла определяется, нет ли каких-нибудь отходящих от него непомеченных ребер. Если такие ребра есть, осуществляется переход к шагу 5, если их нет, осуществляется пе¬реход к шагу 6.
5. Произвольно выбирается и помечается непомеченное от¬ходящее от узла ребро. Затем по нему осуществляется переход к новому текущему узлу, и алгоритм возвращается к шагу 3.
6. Если этот узел является первоначальным узлом, значит, граф не содержит никаких циклов, и алгоритм завершает свою ра¬боту. В противном случае алгоритм зашел в тупик. Этот узел уда¬ляется, и алгоритм возвращается к предыдущему узлу, то есть к тому узлу, который был текущим перед только что удаленным уз¬лом. Данный узел делается текущим, и осуществляется переход к шагу 3.
   Этот алгоритм берет поочередно каждый узел в качестве корневого в надежде, что из этого получится дерево, и выполняет в дереве поиск в глубину. Если в процессе обхода алгоритм возвра¬щается к уже встречавшемуся узлу, значит, он нашел цикл. Если алгоритм обходит все ребра из какого-нибудь заданного узла, то он возвращается к предыдущему узлу. Если он возвращается к корне¬вому узлу и не может идти дальше, то подграф, доступный из те¬кущего узла, не содержит циклов. Если данное свойство сохраня¬ется для всех узлов, значит, полный граф не содержит циклов, а система не находится в состоянии взаимоблокировки.
   Чтобы увидеть на практике работу этого алгоритма, вос¬пользуемся графом, изображенным на рис. 75, а. Порядок обра¬ботки узлов произвольный, поэтому будем исследовать их слева направо и сверху вниз, выбрав при первом запуске алгоритма начальный узел R, затем последовательно выбирая узлы A, B, C, S, D, T, E, F и т. д. Если мы обнаружим цикл, алгоритм прекратит свою работу.
   Начинаем с узла R и инициализируем L как пустой список. Затем добавляем узел R в список, переходим к единственно воз¬можному узлу A и также добавляем его к списку L, получая L = [R, A]. Из узла A следуем к узлу S, получая L = [R, A, S]. Узел S не имеет отходящих от него ребер, следовательно, это тупик, который заставляет нас вернуться к узлу A. Так как у узла A также нет не¬маркированных отходящих от него ребер, мы возвращаемся к узлу R, завершая таким образом его исследование.
   Теперь перезапускаем алгоритм, начиная его работу с узла A и предварительно вернув список L в исходное состояние. Этот поиск также быстро остановится, поэтому начнем снова с узла B. Из узла B проследуем по отходящим ребрам до тех пор, пока не доберемся до узла D; к этому моменту список будет иметь следую¬щий вид: L = [B, T, E, V, G, U, D]. Теперь нужно сделать произ¬вольный выбор. Если выбрать узел S, мы попадаем в тупик и воз¬вращаемся к узлу D. Во второй раз выбираем узел T и обновляем список L до вида [B, T, E, V, G, U, D, T], где обнаруживаем цикл и останавливаем работу алгоритма.
   Этот алгоритм еще далек от оптимального. Более удачный алгоритм показан в работе Эвена (Even, 1979). Тем не менее приве¬денный пример доказывает само существование алгоритма для об¬наружения взаимоблокировки.

Обнаружение взаимоблокировки при использовании нескольких ресурсов каждого типа

Когда в системе существует несколько экземпляров каких-нибудь ресурсов, для обнаружения взаимоблокировки необходим другой подход. Сейчас будет представлен алгоритм, основанный на использовании матриц и предназначенный для обнаружения взаи-моблокировки при работе n процессов, от P1 до Pn. Пусть m — это число классов ресурсов, Е1 — количество ресурсов класса 1, Е2 — количество ресурсов класса 2, а в общем Ei — количество ресурсов класса i (где 1 ≤ i ≤ m). E — это вектор существующих ресурсов. Он передает общее количество имеющихся в наличии экземпляров каждого ресурса. Например, если класс 1 представляет собой нако¬пители на магнитных лентах, то E1 = 2 означает, что в системе есть два таких накопителя.
В любой момент времени какие-то ресурсы могут быть вы¬делены и недоступны. Пусть A будет вектором доступных ресур¬сов, где Ai дает количество экземпляров ресурса i, доступных на данный момент (то есть не выделенных). Если оба накопителя на магнитной ленте уже выделены, A1 будет равно 0.
Теперь нам нужны два массива: C — матрица текущего рас¬пределения и R — матрица запросов. i-я строка в матрице C гово¬рит о том, сколько экземпляров каждого класса ресурсов в данный момент удерживает процесс Pi. Таким образом, Cij — это количе¬ство экземпляров ресурса j, которое удерживается процессом i. По аналогии с этим Rij — это количество экземпляров ресурса j, кото¬рое хочет получить процесс Pi. Все четыре структуры данных пока¬заны на рис. 76.

Для этих четырех структур данных сохраняется одно важ­ное соотношение. А именно — каждый ресурс является либо выде­ленным, либо доступным. Это наблюдение означает, что

Иными словами, если сложить все уже выделенные экзем¬пляры ресурса j и к ним прибавить все еще доступные экземпляры, в результате получится количество существующих экземпляров ресурса этого класса.
Алгоритм обнаружения взаимоблокировок основан на срав¬нении векторов. Определим, что для двух векторов A и B сооотно¬шение A ≤ B означает, что каждый элемент вектора A меньше или равен соответствующему элементу вектора B. Математически это можно записать так: A ≤ B тогда и только тогда, когда Ai ≤ Bi для 1 ≤ i ≤ m.
Каждый процесс изначально объявляется немаркирован¬ным. По мере работы процессы будут помечаться, показывая, что они способны завершить свою работу и не участвуют во взаимо¬блокировке. Когда алгоритм завершает свою работу, любой непо-меченный процесс считается участвующим во взаимоблокировке. При работе этого алгоритма предполагается наихудший из возмож¬ных сценариев развития событий: все процессы удерживают все полученные ресурсы до тех пор, пока не закончат свою работу.
Теперь алгоритм обнаружения взаимного исключения можно изложить в следующей последовательности:

1. Поиск непомеченного процесса, Pi, для которого i-я строка матрицы R меньше или равна A.
2. Если такой процесс найден, прибавление к A i-й строки мат¬рицы C, установка метки на процесс и возвращение к шагу 1.
3. Если такого процесса нет, алгоритм завершает работу.
   По окончании работы алгоритма все непомеченные про¬цессы, если таковые имеются, считаются участвующими во взаи¬моблокировке.
   На первом шаге алгоритм ищет процесс, который может до¬работать до конца. Такой процесс характеризуется тем, что все его запросы на ресурсы могут быть удовлетворены за счет текущих доступных ресурсов. Тогда выбранный процесс доработает до конца, после чего вернет все удерживаемые им ресурсы в фонд до¬ступных ресурсов. Затем этот процесс помечается завершенным. Если в итоге окажется, что все процессы могут доработать до конца, значит, ни один из них не участвует во взаимоблокировке. Если часть процессов никогда не сможет доработать до конца, зна¬чит, они находятся в состоянии взаимоблокировки. Хотя алгоритм не является детерминированным (поскольку он может запускать процессы в любом возможном порядке), результат всегда одинаков.
   Рассмотрим пример работы алгоритма обнаружения взаи¬моблокировок, показанный на рис. 77. Здесь изображены три про¬цесса и четыре класса ресурсов, которые мы произвольно обозна¬чили как накопители на магнитной ленте, плоттеры, сканер и при¬вод Blu-ray-дисков. Процесс 1 удерживает один сканер. Процесс 2 удерживает два ленточных привода и один привод Blu-ray-дисков. Процесс 3 удерживает плоттер и два сканера. Каждый процесс нуждается в дополнительных ресурсах, что отображено в матрице R.

Во время работы алгоритма обнаружения взаимоблокировок осуществляется поиск процесса, чей запрос на ресурс может быть удовлетворен. Требования первого процесса удовлетворить невоз¬можно из-за отсутствия доступного привода Blu-ray-дисков. Запрос второго процесса также нельзя удовлетворить, так как нет свобод¬ного сканера. К счастью, можно удовлетворить запрос третьего процесса, поэтому третий процесс запускается и в конечном итоге высвобождает все удерживавшиеся им ресурсы, в результате чего получается:
A = (2 2 2 0)
Теперь может быть запущен процесс 2, высвобождающий удерживающиеся им ресурсы, в результате чего получается:
A = (4 2 2 1)
и может быть запущен оставшийся процесс. При этом взаимобло¬кировки в системе не возникает.
Рассмотрим незначительное изменение ситуации, показан¬ной на рис. 77. Предположим, что процесс 3 нуждается в приводе Blu-ray-дисков, а также в двух ленточных накопителях и плоттере. Ни один из этих запросов не может быть удовлетворен, поэтому вся система в конечном итоге войдет в состояние взаимоблокировки. Даже если мы дадим процессу 3 два его ленточных накопителя и один плоттер, система войдет в состояние взаимоблокировки при запросе привода Blu-ray-дисков.
Теперь, когда мы знаем, как можно обнаружить взаимобло¬кировку (по крайней мере, при заранее известных статических за¬просах на выделение ресурсов), возникает вопрос, когда именно нужно приступать к их поиску. Можно, конечно, проводить про¬верку при выдаче каждого запроса на выделение ресурса. Тем са¬мым будет обеспечено их обнаружение на самой ранней стадии, но это слишком обременительно для центрального процессора. Есть альтернативная стратегия, предусматривающая проверку каждые k минут или, может быть, только в том случае, когда степень загру¬женности процессора снижается относительно какого-то порога. Оценка загруженности процессора имеет определенный смысл, по¬скольку при участии во взаимоблокировке достаточного количества процессов работоспособными останутся лишь несколько процессов и центральный процессор будет часто простаивать.

Выход из взаимоблокировки

Предположим, что наш алгоритм обнаружения взаимобло¬кировки успешно отработал и обнаружил такую блокировку. Что же дальше? Нужны какие-то методы выхода из нее, позволяющие системе восстановить работоспособность. В этом разделе будут рассмотрены различные способы выхода из взаимоблокировки. Но ни один из них не обладает какой-то исключительной привлека¬тельностью.

Восстановление за счет приоритетного овладения ресурсом

Иногда можно временно отобрать ресурс у его текущего владельца и передать его другому процессу. В большинстве случаев для этого может понадобиться вмешательство оператора, особенно в операционных системах пакетной обработки, запускаемых на универсальных машинах.
К примеру, чтобы отобрать лазерный принтер у владельца, оператор может сложить все уже отпечатанные листы в стопку. За¬тем процесс может быть приостановлен (помечен как неработоспо¬собный). После этого принтер может быть выделен другому про¬цессу. Когда этот процесс завершит свою работу, стопка отпеча¬танных листов бумаги может быть помещена обратно в приемный лоток принтера и работа исходного процесса может быть возобнов¬лена.
Возможность отобрать ресурс у процесса, позволить ис¬пользовать его другому процессу, а затем вернуть его без извеще¬ния процесса во многом зависит от природы этого ресурса. Восста¬новление этим способом зачастую затруднено или вовсе невоз¬можно. Выбор процесса для приостановки обусловлен тем, какой именно процесс обладает тем ресурсом, который у него можно легко отобрать.

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

Если разработчики системы и операторы вычислительной машины знают о том, что есть вероятность возникновения взаимо¬блокировки, они могут организовать периодическое создание про¬цессами контрольных точек. Это означает, что состояние процесса записывается в файл, что позволит осуществить его последующий перезапуск. Контрольные точки содержат не только образ памяти, но и состояние ресурсов, то есть информацию о том, какие ресурсы в данный момент выделены процессу. Для большей эффективности новая контрольная точка должна записываться не поверх старой, а в новый файл, чтобы во время выполнения процесса собралась це¬лая последовательность контрольных точек.
При обнаружении взаимоблокировки несложно определить, какие ресурсы нужны. Чтобы выйти из взаимоблокировки, процесс, владеющий необходимым ресурсом, откатывается назад к точке, предшествующей получению данного ресурса, для чего он запуска¬ется из одной из своих контрольных точек. Вся работа, выполнен¬ная после этой контрольной точки, теряется (например, должна быть выброшена вся отпечатанная после этой контрольной точки выходная информация, поскольку она будет отпечатана снова). Фактически процесс возвращается к предшествующему моменту, когда он еще не обладал тем ресурсом, который теперь выделен одному из участвующих во взаимоблокировке процессов. Если пе¬резапущенный процесс пытается опять получить ресурс, ему при¬ходится ждать, пока тот не станет доступен.

Восстановление путем уничтожения процессов

Самым грубым, но и самым простым способом прервать взаимоблокировку является уничтожение одного или нескольких процессов. Можно уничтожить процесс, находящийся в цикле вза¬имоблокировки. Если повезет, то другие процессы смогут продол¬жить свою работу. Если это не поможет, то все можно повторить, пока цикл не будет разорван.
В качестве альтернативы можно выбрать жертвой процесс, не находящийся в цикле, чтобы он высвободил удерживаемые им ресурсы. При этом подходе уничтожаемый процесс выбирается с особой тщательностью, потому что он должен удерживать ресурсы, необходимые некоторым процессам в цикле. Например, один про¬цесс может удерживать принтер и требовать плоттер, а другой, наоборот, удерживать плоттер и запрашивать принтер. Оба они находятся в состоянии взаимоблокировки. Третий процесс может удерживать другой такой же принтер и другой такой же плоттер и успешно работать. Уничтожение третьего процесса приведет к вы¬свобождению этих ресурсов и разрушит взаимоблокировку первых двух процессов.
По возможности лучше убить процесс, который может быть безболезненно перезапущен с самого начала. К примеру, компиля¬ция всегда может быть перезапущена, поскольку все, что она де¬лает, — это читает входной файл и создает объектный файл. Если процесс компиляции будет уничтожен на полпути, то первый за¬пуск не повлияет на второй.
А вот процесс, обновляющий базу данных, не всегда можно будет безопасно запустить во второй раз. Если процесс прибавляет единицу к какой-нибудь записи таблицы базы данных, то его пер¬воначальный запуск, уничтожение, а затем повторный запуск при-ведут к неверному результату, поскольку к полю будет прибавлена двойка.

21.5 Уклонение от взаимоблокировок

При рассмотрении темы обнаружения взаимоблокировок мы предположили, что когда процесс запрашивает ресурсы, он про¬сит их все сразу (матрица R на рис. 76). Но в большинстве систем ресурсы запрашиваются по одному. Система должна уметь прини¬мать решение, представляет выделение ресурса опасность или нет, и выделять его только в том случае, если это безопасно. В связи с этим возникает вопрос: существует ли алгоритм, который помог бы избежать взаимоблокировки, каждый раз делая правильный выбор? Ответом будет да, но при определенных условиях взаимоблоки¬ровки можно избежать, но только если заранее будет доступна вполне определенная информация.

Траектории ресурса

Основные алгоритмы уклонения от взаимоблокировок ос¬нованы на концепции безопасных состояний. Перед тем как дать описание алгоритмов, нужно сделать небольшое отступление, чтобы рассмотреть концепцию безопасности в графическом, про¬стом для понимания виде. Хотя графический подход не перево¬дится непосредственно в пригодный к использованию алгоритм, он дает неплохое интуитивное понимание существа вопроса.
На рис. 78 представлена модель для системы с двумя про¬цессами и двумя ресурсами, например принтером и плоттером. На горизонтальной оси отображены номера команд, выполняемых процессом A. На вертикальной оси отображены номера команд, выполняемых процессом B. В команде I1 процесс A запрашивает принтер, в команде I2 он запрашивает плоттер. Принтер и плоттер высвобождаются командами I3 и I4 соответственно. Процессу B нужны плоттер с команды I5 по команду I7 и принтер с команды I6 по команду I8.
Каждая точка на графике представляет совместное состоя¬ние двух процессов. Изначально система находится в точке p, когда ни один процесс еще не выполнил ни одной инструкции. Если пла¬нировщик запустит процесс A первым, мы попадем в точку q, в ко¬торой процесс A выполнил какое-то количество команд, а процесс B еще ничего не сделал. В точке q траектория становится верти¬кальной, показывая, что планировщик решил запустить в работу процесс B. При наличии одного процессора все отрезки траектории могут быть только вертикальными или горизонтальными, но не диагональными. Кроме того, движение всегда происходит в север¬ном или восточном направлении (вверх и вправо) и никогда не происходит в южном или западном (вниз и влево), поскольку про¬цессы не могут работать, возвращаясь в прошлое.

Когда процесс A пересекает прямую I1 на пути из r в s, он запрашивает, а затем получает в свое распоряжение принтер. Когда процесс B достигает точки t, он запрашивает плоттер.
Особый интерес представляют заштрихованные области. Область со штриховкой из верхнего левого угла в правый нижний представляет промежуток времени, когда оба процесса удерживают принтер. Правило взаимного исключения делает попадание в эту область невозможным. Аналогично этому область, имеющая дру¬гую штриховку, представляет промежуток времени, когда оба про¬цесса удерживают плоттер, и попадание в эту область также невоз¬можно.
Если система войдет в прямоугольник, ограниченный по бокам прямыми I1 и I2, а сверху и снизу прямыми I5 и I6, то она в конце концов доберется до пересечения линий I2 и I6 и возникнет взаимоблокировка. В этот момент процесс A запрашивает плоттер, а процесс B запрашивает принтер, но оба ресурса будут уже выде¬лены. Получается, что небезопасным является весь прямоугольник и в него входить нельзя. В точке t единственным безопасным дей¬ствием будет работа процесса до тех пор, пока он не дойдет до ко¬манды I4. После нее для того, чтобы добраться до точки u, подой¬дет любая траектория.
Важный для понимания момент заключается в том, что в точке t процесс B запрашивает ресурс. Система должна принять решение, предоставлять его или нет. Если ресурс предоставляется, система попадает в небезопасную область и со временем входит в состояние взаимоблокировки. Чтобы предупредить взаимоблоки¬ровку, нужно приостановить процесс B до тех пор, пока процесс A не запросит и не высвободит плоттер.

Безопасное и небезопасное состояние

При дальнейшем рассмотрении алгоритмов уклонения от взаимоблокировок используется информация, представленная на рис. 76. В любой заданный момент времени существует текущее состояние, содержащее E, A, C и R. Состояние считается безопас¬ным, если существует какой-то порядок планирования, при котором каждый процесс может доработать до конца, даже если все про¬цессы внезапно и срочно запросят максимальное количество ресур¬сов. Это положение проще всего проиллюстрировать с помощью примера, в котором используется один ресурс. На рис. 79, а пока¬зано состояние, в котором процесс A удерживает 3 экземпляра ре¬сурса, но в конечном счете может затребовать 9 экземпляров. Про¬цесс B в этот момент удерживает 2 экземпляра, но позже может затребовать в общей сложности еще 4. Процесс C также удерживает 2 экземпляра, но может затребовать еще 5. В системе есть всего 10 экземпляров данного ресурса, 7 из которых уже распределены, а 3 пока свободны.

Состояние на рис. 79, а является безопасным, потому что существует такая последовательность предоставления ресурсов, которая позволяет завершиться всем процессам. А именно — планировщик может просто запустить в работу только процесс B на то время, пока он запросит и получит 2 дополнительных экземпляра ресурса, что приведет к состоянию, изображенному на рис. 79, б. Когда процесс B завершит свою работу, мы получим состояние, показанное на рис. 79, в. Затем планировщик может запустить процесс C, что со временем приведет нас к ситуации, показанной на рис. 79, г. По завершении работы процесса C мы получим ситуацию, показанную на рис. 79, д. Теперь процесс A наконец-то может получить необходимые ему 6 экземпляров ресурса и также успешно завершить свою работу. Таким образом, состояние, показанное на рис. 79, а, является безопасным, поскольку система может избежать взаимоблокировки с помощью тщательного планирования процессов.

Теперь предположим, что исходное состояние системы показано на рис. 80, а, но в данный момент процесс A запрашивает и получает еще один ресурс и система переходит в состояние, показанное на рис. 80, б. Сможем ли мы найти последовательность, которая гарантирует безопасную работу системы? Давайте попробуем. Планировщик может дать поработать процессу B до того момента, пока он не запросит все свои ресурсы (рис. 80, в).

В итоге процесс B успешно завершается, и мы получаем ситуацию, показанную на рис. 80, г. В этом месте мы застряли: в системе осталось только 4 свободных экземпляра ресурса, а каждому из активных процессов необходимо по 5 экземпляров. И не существует последовательности действий, гарантирующей успешное завершение всех процессов. Следовательно, решение о предоставлении ресурса, которое перевело систему из состояния, показанного на рис. 80, а, в состояние, показанное на рис. 80, б, из безопасного в небезопасное состояние. Если из состояния, показанного на рис. 80, б, запустить процесс A или C, то ни один из них не заработает. Возвращаясь назад, нужно сказать, что запрос процесса A не должен был удовлетворяться.
Следует отметить, что небезопасное состояние само по себе не является состоянием взаимоблокировки. Начиная с состояния, показанного на рис. 80, б, система может поработать некоторое время. Фактически может даже успешно завершиться работа одного из процессов. Кроме того, процесс A может высвободить один ресурс еще до запроса дополнительного ресурса, позволяя успешно завершить работу процессу C, а системе в целом избежать взаимоблокировки. Таким образом, разница между безопасным и небезопасным состоянием заключается в том, что в безопасном состоянии система может гарантировать, что все процессы закончат свою работу, а в небезопасном состоянии такой гарантии дать нельзя.

Алгоритм банкира для одного ресурса

Алгоритм планирования, позволяющий избегать взаимо¬блокировок, был разработан Дейкстрой (Dijkstra, 1965) и известен как алгоритм банкира. Он представляет собой расширение алго¬ритма обнаружения взаимоблокировок, представленного в разделе «Обнаружение взаимоблокировки при использовании одного ре¬сурса каждого типа». Модель алгоритма основана на примере бан¬кира маленького городка, имеющего дело с группой клиентов, ко¬торым он выдал ряд кредитов. (Много лет назад банки не давали кредиты, пока не убеждались в том, что они могут быть возвра¬щены.) Алгоритм проверяет, ведет ли выполнение каждого запроса к небезопасному состоянию. Если да, то запрос отклоняется. Если удовлетворение запроса к ресурсу приводит к безопасному состоя¬нию, ресурс предоставляется процессу. На рис. 81, а показаны че¬тыре клиента: A, B, C и D, каждый из которых получил определен¬ное количество единиц кредита (например, 1 единица равна 1000 долларов). Банкир знает, что не всем клиентам тотчас же понадо¬бится максимальная сумма их кредита, поэтому для обслуживания их потребностей он зарезервировал только 10 единиц, а не все 22, которые нужны клиентам. (Чтобы провести аналогию с компью¬терной системой, будем считать, что клиенты — это процессы, единицы — накопители на магнитной ленте, а банкир — операци¬онная система.)
Клиенты занимаются своими делами, время от времени за¬прашивая ссуды (то есть запрашивая ресурсы). В какой-то опреде¬ленный момент возникает ситуация, показанная на рис. 81, б. Это состояние не представляет опасности, поскольку при оставшихся двух единицах банкир может отложить выполнение любых запро¬сов, за исключением запроса клиента C, позволяя C завершить свои дела и высвободить все четыре своих ресурса. Имея в своем распо¬ряжении четыре единицы ресурса, банкир может позволить полу¬чить необходимые единицы либо D, либо B и т. д.

Рассмотрим, что получится, если запрос от B одной допол¬нительной единицы будет удовлетворен в ситуации, показанной на рис. 81, б. Мы получим небезопасную ситуацию, показанную на рис. 81, в. Если все клиенты внезапно запросят максимальные ссуды, банкир не сможет удовлетворить никого из них и мы полу¬чим взаимоблокировку. Небезопасное состояние необязательно приводит к взаимоблокировке, поскольку клиенту может и не по-надобиться максимальная сумма кредита, но банкир не может рас¬считывать на это.
Алгоритм банкира рассматривает каждый запрос по мере поступления и проверяет, приведет ли его удовлетворение к без¬опасному состоянию. Если да, то запрос удовлетворяется, в про¬тивном случае запрос откладывается до лучших времен. Чтобы по-нять, является ли состояние безопасным, банкир проверяет, может ли он предоставить достаточно ресурсов для удовлетворения запро¬сов какого-нибудь клиента. Если да, то эти ссуды считаются воз¬вращенными, после чего проверяется следующий ближайший к пределу займа клиент и т. д. Если в конечном счете все ссуды могут быть погашены, состояние является безопасным и исходный запрос можно удовлетворить.

Алгоритм банкира для нескольких типов ресурсов

Алгоритм банкира может быть распространен на работу с несколькими ресурсами. На рис. 82 показано, как он работает. Здесь изображены две матрицы. Левая матрица показывает, сколько экземпляров каждого ресурса в данный момент выделено каждому из пяти процессов. Правая показывает, сколько экземпляров ресур¬сов все еще необходимо каждому процессу для завершения его ра¬боты. На рис. 77 эти матрицы назывались C и R. Как и в случае с ресурсом одного типа, процессы перед выполнением своей работы должны сообщить об общих потребностях в ресурсах, чтобы си¬стема в любой момент могла вычислить правую матрицу.

Три вектора, изображенные справа от матриц, показывают соответственно существующие ресурсы (вектор E), занятые ре¬сурсы (вектор P) и доступные ресурсы (вектор A). Судя по значе¬нию вектора E, в системе имеется шесть накопителей на магнитной ленте, три плоттера, четыре принтера и два привода Blu-ray-дисков. Из них заняты в данный момент пять накопителей, три плоттера, два принтера и два привода Blu-ray-дисков. Этот факт можно уста¬новить путем сложения значений четырех столбцов, соответству¬ющих ресурсам, в левой матрице. Вектор доступных ресурсов — это разница между количеством присутствующих в системе ресур¬сов и количеством ресурсов, используемых в настоящее время.
Теперь может быть изложен алгоритм проверки состояния на безопасность.

1. Ищем в матрице R строку, соответствующую процессу, чьи неудовлетворенные потребности в ресурсах меньше или равны вектору A. Если такой строки не существует, то система в конце концов войдет в состояние взаимоблокировки, поскольку ни один процесс не сможет доработать до успешного завершения (предпо¬лагается, что процессы удерживают все ресурсы, пока не завершат свою работу).
2. Допускаем, что процесс, чья строка была выбрана, за¬прашивает все необходимые ему ресурсы (возможность чего гаран¬тируется) и завершает свою работу. Отмечаем этот процесс как за¬вершенный и прибавляем все его ресурсы к вектору A.
3. Повторяем шаги 1 и 2 до тех пор, пока либо все процессы будут помечены как завершенные (в этом случае исходное состоя¬ние было безопасным), либо не останется процессов, чьи запросы могут быть удовлетворены (в этом случае система не была в без-опасном состоянии).
   Если на шаге 1 подходят для выбора несколько процессов, то неважно, который из них будет выбран: фонд доступных ресур¬сов либо увеличивается, либо в худшем случае остается таким же.
   Теперь вернемся к примеру, показанному на рис. 82. Теку¬щее состояние безопасно. Предположим, что процесс B теперь сде¬лал запрос на принтер. Этот запрос может быть удовлетворен, по¬скольку получающееся в результате состояние по-прежнему без¬опасно (процесс D может завершить свою работу, затем это же мо¬гут сделать процесс A или процесс E, а затем и все остальные).
   Представим теперь, что после выделения процессу B одного из двух оставшихся принтеров E затребует последний принтер. Удовлетворение этого запроса уменьшит значение вектора доступ¬ных ресурсов до (1 0 0 0), что приведет к взаимоблокировке. Со-вершенно ясно, что запрос процесса E должен быть на некоторое время отклонен.
   Дейкстра впервые опубликовал алгоритм банкира в 1965 году. С тех пор практически каждая книга по операционным систе¬мам дает его подробное описание. Различным аспектам этого алго¬ритма было посвящено бесчисленное количество статей. К сожале¬нию, мало у кого из авторов хватило смелости показать, что хотя алгоритм замечателен в теории, на практике он по существу беспо¬лезен, поскольку нечасто можно определить заранее, каковы будут максимальные потребности процессов в ресурсах. Кроме того, ко¬личество процессов не фиксированно, оно динамически изменяется по мере входа пользователей в систему и выхода их из нее. И более того, ресурсы, считавшиеся доступными, могут внезапно пропасть (накопитель на магнитной ленте может сломаться). Таким образом, на практике лишь немногие системы, если таковые вообще име¬ются, используют алгоритм банкира для уклонения от взаимобло¬кировок. Но в некоторых системах для предотвращения взаимных блокировок используются эвристические правила, подобные алго¬ритму банкира. Например, сети могут дросселировать трафик, ко¬гда использование буфера превысит, скажем, 70 %, при оценке, что оставшихся 30 % будет достаточно для завершения обслуживания текущих пользователей и возвращения их ресурсов.

21.6 Предотвращение взаимоблокировки

Как все-таки можно избежать взаимоблокировок в реальных системах? Ведь мы уже убедились в том, что уклониться от них по сути невозможно, поскольку для этого требуется информация о бу¬дущих запросах, о которых ничего не известно. Чтобы ответить на этот вопрос, вернемся назад к четырем условиям, сформулирован¬ным Коффманом и его коллегами (Koffman at al., 1971), и посмот¬рим, смогут ли они дать нам ключ к решению проблемы. Если мы сможем гарантировать, что хотя бы одно из этих условий никогда не будет выполнено, то взаимоблокировки станут структурно не¬возможными (Havender, 1968).

Атака условия взаимного исключения

Сначала предпримем атаку на условие взаимного исключе¬ния. Если в системе нет ресурсов, отданных в единоличное пользо¬вание одному процессу, мы никогда не попадем в ситуацию взаи¬моблокировки. Данные проще всего сделать доступными только для чтения, чтобы процессы могли их использовать одновременно. Но также понятно, что если позволить двум процессам одновре¬менно печатать данные на принтере, то это приведет к хаосу. За счет использования очереди на печать (спулинга) выдавать свои выходные данные могут сразу несколько процессов. В этой модели единственным процессом, который фактически запрашивает физи¬ческий принтер, является демон (Демон — служебная программа в некоторых операционных системах (преимущественно основанных на UNIX), работающая в фоновом режиме без непосредственного взаимодействия с пользователем.) принтера. Так как демон не за¬прашивает никакие другие ресурсы, взаимоблокировки, связанные с принтером, можно исключить.
Если демон запрограммирован на начало печати еще до того, как все выходные данные попали в очередь на печать, принтер может простоять впустую, если выводящий данные процесс решит подождать несколько часов после первого пакета выходных дан¬ных. Поэтому демоны обычно программируются так, чтобы начи¬нать печать, только если доступен полный файл выходных данных. Но само по себе это решение может привести к взаимоблокировке. Что получится, если каждый из двух процессов заполнит по поло¬вине доступного пространства, выделенного на диске под очередь на печать своими выходными данными, и ни один из них не сфор¬мирует свои полные выходные данные? В таком случае мы полу¬чим два процесса, завершивших формирование только части, но не всего объема своих выходных данных, и не имеющих возможности продолжить свою работу. Ни один из процессов не сможет когда-либо завершиться, и мы получим взаимоблокировку, связанную с выводом данных на диск.
И все же здесь проглядывается намек на идею, которая до¬вольно часто применяется на практике. Следует избегать выделе¬ния ресурса, если в нем нет насущной потребности, и постараться, чтобы как можно меньше процессов могло фактически требовать получения этого ресурса.

Атака условия удержания и ожидания

Второе из условий, сформулированных Коффманом (Coffman et al., 1971), выглядит несколько более обещающим. Если можно будет помешать процессам, удерживающим ресурсы, войти в фазу ожидания дополнительных ресурсов, то можно будет ис¬ключить и взаимоблокировку. Один из способов достижения этой цели заключается в том, чтобы заставить все процессы запрашивать все свои ресурсы до начала выполнения своей работы. Если все до¬ступно, то процессу будет выделено все, что ему требуется, и он сможет доработать до завершения. Если один или несколько ресур¬сов заняты, ничего не будет выделяться и процесс будет просто ждать.
Проблема, непосредственно связанная с этим подходом, со¬стоит в том, что многие процессы не знают, сколько ресурсов им понадобится, пока не начнут работу. Фактически если бы они об этом знали, то можно было бы использовать и алгоритм банкира. Вторая проблема состоит в том, что при таком подходе ресурсы не будут использоваться оптимально. Возьмем, к примеру, процесс, считывающий данные с входной ленты, анализирующий их в тече¬ние часа, а затем записывающий выходную ленту, да еще и выво-дящий результаты на плоттер. Если все ресурсы должны быть за¬прошены заранее, то процессор на целый час займет выходной накопитель на магнитной ленте и плоттер.
И все-таки некоторые пакетные системы на универсальных машинах требуют, чтобы пользователи перечисляли все ресурсы в первой строке каждого задания. Затем система немедленно заранее распределяет все ресурсы и удерживает их до тех пор, пока они станут не нужны заданию (или в простейшем случае, пока выпол¬нение задания не будет завершено). Несмотря на то что этот метод обременяет программиста и расточительно расходует ресурсы, он предотвращает возникновение взаимоблокировок.
Слегка отличающийся метод нарушения условия удержания и ожидания заключается в требовании от процесса, запрашиваю¬щего ресурс, вначале временно высвободить все ресурсы, удержи¬ваемые им на данный момент. Затем этот процесс пытается заполу¬чить сразу все, что ему требуется.

Атака условия невыгружаемости

Возможна также атака и третьего условия (невыгружаемо¬сти). Если процессу выделен принтер и он распечатал лишь поло¬вину своих выходных данных, то принудительно отобрать у него принтер по причине недоступности запрошенного плоттера в луч¬шем случае будет слишком затруднительно, а в худшем — просто невозможно. Тем не менее, чтобы избежать подобной ситуации, некоторые ресурсы могут быть виртуализированы. Сохранение очереди на печать на диске и предоставление возможности доступа к реальному принтеру только демону принтера исключает возник¬новение взаимоблокировок с участием принтера, хотя и создает одну из таких потенциальных возможностей в отношении диско¬вого пространства. Но при наличии дисков большой емкости ис¬черпание дискового пространства становится маловероятным.
Однако не все ресурсы могут быть виртуализированы по¬добным образом. К примеру, чтобы записи в базах данных или в таблицах внутри операционной системы могли использоваться, они должны быть заблокированы, и здесь закладывается потенциальная вероятность взаимоблокировки.

Атака условия циклического ожидания

Осталось только одно условие. Циклическое ожидание можно устранить несколькими способами. Один из них заключа¬ется в простом выполнении правила, которое гласит, что процессу в любой момент времени дано право только на один ресурс. Если нужен второй ресурс, процесс обязан освободить первый. Но по¬добное ограничение неприемлемо для процесса, копирующего огромный файл с магнитной ленты на принтер.
Другой способ, позволяющий избежать циклического ожи¬дания, заключается в поддержке общей нумерации всех ресурсов (рис. 83, а). Теперь действует следующее правило: процессы могут запрашивать ресурс, когда только пожелают, но все запросы должны быть сделаны в порядке нумерации ресурсов. Процесс мо¬жет запросить сначала принтер, затем накопитель на магнитной ленте, но не может сначала потребовать плоттер, а затем принтер.
Если придерживаться этого правила, то у графа распределе¬ния ресурсов никогда не будет циклов. Посмотрим, почему это имеет место в случае двух процессов, показанных на рис. 83, б. Взаимоблокировка может произойти, только если процесс A запро¬сит ресурс j, а процесс B запросит ресурс i. Предположим, что ре¬сурсы i и j относятся к разным типам, тогда они будут иметь и раз¬ные номера. Если i > j, то процессу A не разрешается запрашивать ресурс j, потому что его номер меньше, чем номер уже имеющегося у него ресурса. Если же i < j, то процесс B не может запрашивать ресурс i, потому что его номер меньше номера уже удерживаемого этим процессом ресурса. Так или иначе, взаимоблокировка невоз¬можна.
При работе более чем с двумя процессами сохраняется та же самая логика. В любой момент времени один из предоставлен¬ных ресурсов будет иметь наивысший номер. Процесс, использую¬щий этот ресурс, никогда не запросит тот ресурс, который уже рас¬пределен. Он или закончит свою работу, или, в худшем случае, за¬просит ресурс с еще большим номером, а все такие ресурсы до¬ступны. В итоге процесс завершит работу и высвободит свои ре¬сурсы. К этому времени какой-нибудь другой процесс будет удер¬живать ресурс с самым большим номером и тоже сможет завершить свою работу. Короче говоря, существует сценарий, по которому все процессы завершают свою работу, поэтому никаких взаимоблоки¬ровок и не возникает.

При незначительном изменении этого алгоритма исключается требование приобретения ресурсов в строго возрастающем порядке и просто требуется, чтобы ни один процесс не запрашивал ресурс с меньшим номером, чем номер того ресурса, который он уже удерживает. Если процесс сначала запрашивает ресурсы 9 и 10, а затем высвобождает их обоих, то это во всех отношениях равнозначно новому началу работы, поэтому теперь уже незачем запрещать ему запрос ресурса 1.
Хотя порядковая нумерация ресурсов исключает проблему взаимоблокировок, может не представиться возможности подобрать порядок, удовлетворяющий абсолютно всех. Когда ресурсы включают в себя элементы таблицы процессов, дисковое пространство очереди печати, заблокированные записи базы данных и другие абстрактные ресурсы, количество потенциальных ресурсов и различных применений может быть настолько большим, что не сможет работать никакое упорядочение.
Различные методы предупреждения взаимоблокировок сведены в табл. 10.

Таблица 10. Методы предупреждения взаимоблокировок

Условие	Метод
Взаимное исключение	Организация очереди на диске
Удержание и ожидание	Изначальный запрос всех ресурсов
Невыгружаемость	Отобрать ресурсы
Циклическое ожидание	Провести порядковую нумерацию ресурсов

21.7  Зависание

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

В качестве примера рассмотрим распределение принтера. Представим себе, что система использует некий алгоритм, гаранти­рующий, что распределение принтера не приводит к взаимоблоки­ровкам. Теперь предположим, что несколько процессов разом захо­тели получить принтер в свое распоряжение. И кто его получит?

Один из возможных алгоритмов предусматривает передачу принтера тому процессу, у которого самый маленький файл для вывода на печать (предположим, что подобная информация до­ступна). Такой подход до максимума увеличивает число счастли­вых клиентов и представляется вполне справедливым. А теперь по­смотрим, что получится на работающей системе, где у одного про­цесса есть для вывода на печать огромный файл. Как только прин­тер освободится в очередной раз, система осмотрится и выберет процесс с самым коротким файлом. Если поток процессов с корот­кими файлами не иссякает, процесс с огромным файлом не получит принтер никогда. Он просто намертво зависнет (будет отложен навсегда, даже если не будет заблокирован).

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

Стоит заметить, что некоторые не различают зависание и взаимоблокировку, поскольку в обоих случаях нет движения впе­ред. Другие же чувствуют фундаментальную разницу, поскольку процесс можно легко запрограммировать на то, чтобы попытаться сделать что-нибудь n раз, и если все попытки провалятся, попы­таться сделать что-нибудь другое. А заблокированный процесс та­кого шанса не имеет.