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

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

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

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

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

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

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

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

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

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

3.3.2. Понятие взаимной блокировки

Определение взаимоблокировки формально можно озвучить так:

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

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

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

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

Коффман (Coffman et al.) [70] и другие исследователи доказали, что для возникновения ситуации взаимоблокировки должны выполняться четыре условия.

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

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

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

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

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

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

в [44] Холт (Holt) показал, как можно смоделировать четыре условия возникновения тупиков, используя направленные фафы. Графы имеют два вида узлов:

процессы, показанные кружочками, и ресурсы, нарисованные квадратиками. Ребро, направленное от узла ресурса (квадрат) к узлу процесса (круг), означает, что ресурс ранее был запрошен процессом, получен и в данный момент используется этим процессом. На рис. 3.5, а ресурс R в настоящее время отдан процессу А.

Ребро, направленное от процесса к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к этому ресурсу. На рис. 3.5, б процесс В ждет ресурс S. На рис. 3.5, в мы видим взаимоблокировку: процесс С ожидает ресурс Т, удерживаемый в настоящее время процессом D. Процесс D вовсе не намеревается освобождать ресурс Т, потому что он ждет ресурс и, используемый процессом С. Оба процесса будут ждать до бесконечности. Цикл в фафе означает наличие взаимоблокировки, циклично включающей процессы и ресурсы (предполагается, что в системе есть по одному ресурсу каждого вида). В этом примере циклом является последовательность C-T-D-U-C.

©

Рис. 3.5. Графы распределения ресурсов: а - ресурс занят; 6 - запрос ресурса;

в - взаимоблокировка

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

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

Теперь предположим, что процессы выполняют как расчеты, так и ввод/вывод, соответственно циклический алгоритм планирования является рациональ-