Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем

Подождите немного. Документ загружается.

151

мы можем получить ситуацию, показанную на рисунке 5.1. (Стрелка от

философа к палочке означает, что философ хочет взять эту палочку,

стрелка в обратном направлении – что эту палочку этот философ уже

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

взять палочку слева. Ни один из философов не может ни есть, ни думать.

Эта ситуация и называется тупиком (deadlock).

Если же мы установим, что философ должен взять обе палочки сразу,

то может возникнуть ситуация, показанная на рисунке 5.2. Философ Чжуан

хочет взять палочки, но обнаруживает, что его правая палочка занята

философом Мо. Чжуан ожидает. Тем временем философ Мэн берет свои

палочки и начинает есть. Мо есть заканчивает, но Чжуан не может начать

есть, так как теперь занята его левая палочка. Если Мо и Мэн едят

попеременно, то Чжуан попадает в положение, которое называется

голоданием (starvation) или бесконечным откладыванием.

Рисунок 5.2 Обедающие философы. Бесконечное откладывание

152

Переходя от философов к вычислительным системам, мы можем

проиллюстрировать тупик таким примером. Процесс A использует

магнитную ленту, но для завершения ему нужен еще и принтер. В это

время процесс B удерживает за собой принтер, но ему нужна еще

магнитная лента. Процессы A и B блокируют друг друга, то есть находятся

в тупике. В системах с множественными ресурсами и с высоким уровнем

мультипрограммирования тупиковые ситуации могут быть и не столь

очевидными. Тупики могут быть локальными и глобальными. Так, если в

приведенном выше примере уровень мультипрограммирования выше 2, то

процессы A и B находятся в локальном тупике, другие процессы, которым

не требуются ресурсы, занятые процессами A и B, могут выполняться.

Философы же на рисунке 5.1 находятся в глобальном тупике.

Бесконечное откладывание – ситуация даже более общая,

свойственная управлению любыми ресурсами, а не только монопольными.

Так, при планировании процессорного времени по статическим

приоритетам низкоприоритетный процесс может откладываться до

бесконечности, если в систему постоянно поступают процессы с более

высокими приоритетами.

Тупик представляет собой ситуацию более опасную, чем

бесконечное откладывание: процессы, попавшие в тупик, удерживают при

этом системные ресурсы. Даже если тупик не глобальный, система

продолжает работать с уменьшенным объемом ресурсов, следовательно, с

пониженной производительностью. Бесконечное же откладывание одного

или нескольких процессов может и не повлиять на среднюю пропускную

способность системы, но, конечно же, влияет на показатели

справедливости обслуживания.

5.3. Тупики: предупреждение, обнаружение, развязка

153

Борьба с тупиками включает в себя три задачи:

• предупреждение тупиков – какую стратегию распределения

ресурсов выбрать, чтобы тупики не возникали вообще?

• обнаружение тупиков – если не удалось применить стратегию,

предупреждающую тупики, то как обнаружить возникший тупик?

• развязка тупиков – если тупик обнаружен, то как от него

избавиться?

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

двумя полюсами – от самых либеральных до самых консервативных. Чем

либеральнее стратегия, тем "охотнее" ОС удовлетворяет запросы на

ресурсы. Но за слишком либеральную стратегию приходится

расплачиваться возможностью возникновения тупика. Консервативные

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

и развязки при применении таких стратегий не ставятся, но плата за это –

частые отказы в выделении ресурсов, следовательно, снижение уровня

мультипрограммирования, а следовательно, – и снижение пропускной

способности. Ниже мы будем рассматривать стратегии предотвращения,

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

• последовательное выделение;

• залповое выделение;

• иерархическое выделение;

• выделение по предварительным заявкам.

Последовательное выделение

Любыми ресурсами может одновременно пользоваться только один

процесс. Если процесс A из предыдущего примера получил ресурс-

принтер, то процессу B будет отказано даже в выделении ресурса-ленты.

Очевидно, что такая стратегия делает тупики совершенно невозможными.

154

Очевидно также, что некоторые процессы будут при этом простаивать

совершенно неоправданно. Так, например, будет приостановлен некий

процесс C, которому принтер и не нужен, а нужна только лента. Поскольку

в число распределяемых ресурсов входят устройства ввода-вывода, а

работают они медленно (например, печать на принтере), простой может

затянуться. Эта стратегия неоправданно снижает уровень

мультипрограммирования и неэффективно использует ресурсы (они тоже

простаивают) и может применяться только в таких ОС, в которых и

расчетный уровень мультипрограммирования невысок.

Залповое выделение

Процесс должен запрашивать / освобождать все используемые им

ресурсы сразу. Эта стратегия позволяет параллельно выполняться

процессам, использующим непересекающиеся подмножества ресурсов.

(Процесс C работает с лентой, процесс D – с принтером.) Тупики по-

прежнему невозможны, однако неоправданное удерживание ресурсов

продолжается. Так, если процессу в ходе выполнения нужны ресурсы R1 и

R2, причем ресурс R1 он использует все время своего выполнения t1, а

ресурс R2 требуется ему только на время t2<<t1, то процесс вынужден

удерживать за собой и ресурс R2 в течение всего времени t1.

В рамках залповой стратегии возможны два варианта: выделять все

ресурсы при создании процесса и освобождать при его завершении или же

позволить процессу запрашивать/освобождать ресурсы несколько раз в

ходе своего выполнения (но обязательно все "залпом"). Очевидно, что

второй вариант более либеральный, так как он позволяет уменьшить

интервал времени удерживания ресурсов и разнести использование разных

ресурсов по разным "залпам". Интересны различия в API для этих двух

вариантов. В первом случае требования на ресурсы могут быть вообще

вынесены за пределы программного кода процесса и задаваться во

155

внешних описателях процесса (например, в языке управления заданиями).

Во втором случае системный вызов getResource является обязательным,

причем обязательно должна быть обеспечена возможность запроса в одном

вызове ресурсов разных классов и выделение всех запрошенных ресурсов

одной непрерываемой операцией.

Иерархическое выделение

Все классы ресурсов разбиваются по уровням с номерами от 1 до N,

каждый уровень содержит только один класс. Процесс имеет право

запрашивать ресурсы только из классов с более высокими номерами, чем у

тех, которыми он уже владеет. Эта стратегия также предотвращает

возникновение тупиков. В каждый момент времени в системе один или

несколько процессов имеют класс закрепленных за ними ресурсов выше,

чем у других. Эти процессы, обладающие ресурсами высокого уровня,

могут беспрепятственно выполняться и завершиться без блокировки.

Следовательно, в каждый момент времени имеется хотя бы один

способный к выполнению процесс. Если не будут поступать новые

процессы, то все процессы, уже имеющиеся в системе, в конце концов

завершатся – тупик отсутствует. Хотя в иерархической стратегии процесс

ограничен в последовательности запросов и возможна ситуация, в которой

он должен удерживать за собой ресурс более длительное время, чем это

действительно необходимо, эта стратегия позволяет достичь неплохой

эффективности, особенно при правильном распределении ресурсов по

уровням. Целесообразно более высокие уровни назначать более

дефицитным и более дорогостоящим ресурсам; как правило, и

использование таких ресурсов является более скоротечным.

Иерархическую стратегию применяет, например, OS/390 применительно к

некоторым системным структурам данных.

156

Иерархическая стратегия является самой либеральной из стратегий,

предотвращающих возникновение тупиков без дополнительной

информации. Более либеральные стратегии предотвращения требуют

предварительного знания о характеристиках процессов.

Предварительные заявки и алгоритм банкира

Эта стратегия названа так потому, что действия ОС напоминают

действия банкира, выдающего ссуды клиентам, именно на таком примере

эта стратегия была рассмотрена в первоисточнике [11]. Применение этой

стратегии требует, чтобы процесс передал ОС "предварительную заявку"

(advanced claim) и в ней указал максимальный объем ресурсов, который

ему понадобится. В ходе выполнения процесс может в произвольном

порядке запрашивать / освобождать ресурсы, не выходя, однако, за

пределы заявленного объема. Ситуация в системе называется реализуемой

при следующих условиях:

• ни одна заявка не превышает общего числа ресурсов в системе;

• ни один процесс не требует большего числа ресурсов, чем им

заявлено;

• суммарное число уже распределенных всем процессов ресурсов не

превосходит общего числа ресурсов в системе.

Ситуация называется безопасной, если процессы можно выстроить в

такую последовательность, при которой:

• первый процесс может нормально завершиться, даже если он

полностью выберет ресурсы по своей заявке;

• второй процесс может нормально завершиться, даже если он

полностью выберет ресурсы по своей заявке, при условии, что

завершится первый процесс и освободит удерживаемые им

ресурсы;

157

• i-й процесс может нормально завершиться, даже если он

полностью выберет ресурсы по своей заявке, при условии, что

завершится i-1-й процесс и освободит удерживаемые им

ресурсы.

В противном случае ситуация называется опасной.

Если ситуация безопасна, то при отсутствии новых процессов все

уже имеющиеся процессы могут нормально завершиться, выбрав ресурсы

в соответствии со своими заявками – тупик невозможен.

Пример представлен на рисунке 5.3. Пусть у ОС имеется всего 12

ресурсов одного класса и на текущий момент выполняются три процесса –

P1, P2 и P3, их заявки составляют 12, 4 и 8 ресурсов соответственно. На

текущий момент времени процессу P1 выделено 4 ресурса, процессу P2 –

2, процессу P3 – 4 (см. рисунок 5.3.а). В резерве ОС остаются, таким

образом, 2 ресурса. Ситуация рисунка 5.2.а является безопасной. ОС может

выделить оставшиеся два ресурса процессу P2 и этот процесс, полностью

получив по своей заявке, может завершиться, тогда системный резерв

увеличится до 4 ресурсов. Этот резерв ОС отдаст процессу P3, он,

завершившись, передаст в резерв ОС 8 ресурсов, которых будет

достаточно для удовлетворения заявки процесса P1. Ситуация станет

опасной, если ОС выделит ресурс какому-либо другому процессу, кроме

P2 (см. рисунок 5.3.б). В этой ситуации ОС за счет своего резерва не может

полностью удовлетворить ни одну заявку.

а) безопасная

158

б) опасная

Рисунок 5.3 Анализ ситуации

Стратегия алгоритма банкира состоит в том, что запрос на ресурс

удовлетворяется только в том случае, если выделение его не сделает

ситуацию опасной. Алгоритмическая реализация проверки ситуации на

безопасность состоит в "проигрывании" на списке процессов приведенного

выше определения безопасной ситуации:

1. Создать список, элементами которого являются процессы с их

ресурсами и заявками.

2. Если список пуст, установить флаг безопасной ситуации и

перейти к п. 7.

3. Найти в списке процесс, заявка которого может быть

удовлетворена из системного резерва.

4. Если такой процесс не найден – установить флаг опасной

ситуации и перейти к п.7.

5. Удалить найденный процесс из списка и передать те ресурсы,

которыми он обладал в системный резерв.

6. Перейти к п.2.

7. Закончить проверку.

Алгоритм Габермана

Другая алгоритмическая реализация стратегии с предварительными

заявками известна как алгоритм Габермана. Этот алгоритм

иллюстрируется следующим программным кодом на языке C:

159

/* Алгоритм Габермана */

static int S[r];

/* Начальные установки */

void HabervanInit(void) {

int i;

for (i=0; i<r; S[i++]=0);

}

/* Выделение ресурса */

int HabermanGet(int claim, int hold) {

int i;

for (i=0; i<claim-hold; i++)

if (!S[i]) return -1; /* отказ */

for (i=0; i<claim-hold; S[i++]--);

return 0; /* подтверждение */

}

/* Освобождение ресурса */

void HabermanRelease(int claim, int hold) {

int i;

for (i=0; i<=claim-hold; S[i++]++);

}

Если в системе имеется r ресурсов одного класса, то ОС создает

массив S из r целых чисел. В ходе начальных установок в массив

записывается убывающая последовательность чисел от r до 1. Если

процесс, имеющий заявку на claim ресурсов и уже получивший hold

ресурсов, запрашивает еще один ресурс, то (функция HabervanGet) все

элементы массива S с номерами от 0 до claim-hold-1 включительно

уменьшаются на 1. Индикатором опасного состояния является

отрицательное значение любого элемента массива S.

160

На рисунке 5.4 показана работа алгоритма Габермана для ситуации,

рассмотренной нами в примере выше. В графе "Событие" таблицы на

рисунке 5.4 указывается идентификатор процесса, которому выделяется

единица ресурса; остальная часть каждой строки представляет состояние

массива S после этого выделения. Строка с пустой графой "Событие"

показывает исходное состояние массива S, строка "итог" – состояние на

момент, когда ресурсы распределены так, как показано на рисунке 5.3.а.

(Убедитесь сами, что на конечное состояние массива S не влияет

последовательность, в которой ресурсы выделялись.) Три нижние строки, в

которых идентификатору процесса предшествует символ '*', показывают

состояние массива S для альтернативных вариантов – выделения еще

одного ресурса процессу P1 или P2, или P3. Видно, что только процесс P2

может получать ресурсы, не переводя систему в опасное состояние.

Рисунок 5.4 Алгоритм Габермана

К сожалению, простая реализация алгоритма Габермана возможна

только для одного класса ресурсов. При наличии в системе нескольких

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

безопасности всей системы в целом. Так, в примере про процессы A и B,

использующие принтер и ленту, ситуация является безопасной как по