Глава_3 (Методическое пособие по Операционным системам)

118

Глава 3

_{Взаимоблокировка}

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

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

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

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

мы также окажемся в тупике. Таким образом, взаимоблокировки появляются при работе как с аппаратными, так и с программными ресурсами.

В этой главе мы рассмотрим тупиковые ситуации более подробно, увидим, как они возникают, и изучим некоторые способы, позволяющие предупредить тупико­вые ситуации или избежать их. Хотя информация о тупиках представлена в контек­сте операционной системы, они также могут встретиться в системах баз данных и во множестве других ситуаций, поэтому этот материал на самом деле применим к широкому ряду систем, работающих с несколькими процессами. О взаимобло­кировках было написано много книг и статей. Библиографии по теме дважды пуб­ликовались в Operating Systems Review и к ним следует обращаться за справочной информацией. Несмотря на то что эти библиографии написаны давно, большая часть работ по взаимоблокировкам была проделана до 1980 года, поэто­му данные книги полезны до сих пор.

Ресурсы

Система может зайти в тупик, когда процессам предоставляются исключительные права доступа к устройствам, файлам и т. д. Чтобы максимально обобщить рассказ о взаимоблокировках, мы будем называть объекты предоставления доступа ресур­сами. Ресурсом может быть аппаратное устройство (например, накопитель на маг­нитной ленте) или часть информации (например, закрытая запись в базе данных). В компьютере существует масса различных ресурсов, к которым могут происхо­дить обращения. Кроме того, в системе может оказаться несколько идентичных экземпляров какого-либо ресурса, например три накопителя на магнитных лентах. Если в системе есть несколько экземпляров ресурса, то в ответ на обращение к нему может предоставляться любая из доступных копий. Короче говоря, ресурс — это все то, что может использоваться только одним процессом в любой момент времени.

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

Ресурсы бывают двух типов: выгружаемые и невыгружаемые. Выгружаемый ресурс можно безболезненно забирать у владеющего им процесса. Образцом такого ресур­са является память. Рассмотрим, например, систему с пользовательской памятью размером 32 Мбайт, одним принтером и двумя процессами по 32 Мбайт, каждый из которых хочет что-то напечатать. Процесс А запрашивает и получает принтер, затем начинает вычислять данные для печати. Еще не закончив расчеты, он пре­вышает свой квант времени и выгружается на диск в область подкачки.

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

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

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

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

1. Запрос ресурса.

2. Использование ресурса.

3. Возврат ресурса.

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

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

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

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

Для некоторых видов ресурсов, таких как записи в базе данных, управление ис­пользованием ресурсов зависит от самих пользовательских процессов. Один из способов, делающих возможным пользовательское управление, заключается в при­соединении семафора к каждому из ресурсов. Все семафоры в исходном состоянии равны 1. С тем же успехом можно использовать мьютексы. Три шага, перечислен­ные выше, выполняются следующим образом: сначала для запроса ресурса исполь-

зуется вызов down, примененный к семафору, затем программа использует ресурс и, наконец, используется вызов up для его освобождения. Эти шаги представлены в листинге 3.1, а.

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

typedef int semaphore; typedef int semaphore;

semaphore resource_l; semaphore resource_l;

semaphore resource_2;

void process_A(void) { void process_A(void) {

down(&resource_l): down(&resource_l):

use_resource_l(): down(&resource_2);

up(&resource_l); use_both_resources():

} up(&resource_2);

up(&resource_l); }

а б

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

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

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

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

Другая ситуация представлена в листинге 3.2, б. Может случиться так, что один из процессов получит оба ресурса и эффективно блокирует другой процесс до за­вершения своей работы. Однако также может произойти и то, что процесс А займет ресурс 1, а процесс В получит ресурс 2. Теперь, когда они попытаются запросить еще по одному ресурсу, каждый из них будет заблокирован. Ни один из двух про­цессов не сможет когда-либо заработать снова. Это ситуация взаимоблокировки.

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

Листинг 3.2. Код, не приводящий к тупику (а); код с потенциальной взаимоблокировкой (б)

typedef int semaphore; typedef int semaphore:

semaphore resource_l; semaphore resource_l;

semaphore resource_2; semaphore resource_2;

void process_A(void) { void process_A(void) {

down(&resource_l); down(&resource_1);

down(&resource_2); down(&resource_2);

use_both_resources(); use_both_resources();

up(&resource_2); up(&resource_2):

up(&resource_l); up(&resource l);

} }

void process_B(void) { void process_B(void) {

down(&resource_l); down(&resource_2);

down(&resource_2); down(&resource_l);

use_both_resources(); use_both_resources();

up(&resource_2); up(&resource_l);

up(&resource_l); up(&resource_2);

а б

Введение

Взаимоблокировки или тупиковые ситуации формально можно определить так:

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

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

Условия взаимоблокировки

Коффман (Coffman) и другие исследователи доказали, что для возникнове­ния ситуации взаимоблокировки должны выполняться четыре условия:

1. Условие взаимного исключения. Каждый ресурс в данный момент или от­дан ровно одному процессу, или доступен.

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

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

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

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

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

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