Индекс
НазадОглавлениеВперед


Глава 5
Монопольно используемые ресурсы

5.1. Свойства ресурсов и их представление

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

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

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

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

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

Из определений ОС (как с точки зрения разработчика, так и с точки зрения пользователя), которые мы дали в первой главе, однозначно следует, что процесс ни в коем случае не может самостоятельно завладеть ресурсом - а только через посредство ОС. Для предоставления процессам такой возможности в составе API ОС должны быть системные вызовы типа:

    resourceHandle = getResource(class, number [,action] );
    releaseResource(resourceHandle);

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

Второй вызов открепляет от процесса ранее выделенный ему ресурс. Возможно, форма выделения/освобождения ресурса напомнила вам знакомые операции открытия / закрытия файла - и недаром. Поскольку файлы также являются ресурсами, операции open/close являются частными случаями операций getResource/releaseResource. Как правило, в реальных API ОС нет общих операций выделения/освобождения ресурсов, но для каждого ресурса имеется своя пара операций, отличающаяся от других названием и, возможно, составом параметров.

Третий, необязательный параметр операции getResource задает действия ОС в ситуации, когда выделить ресурс невозможно (не все ОС предоставляют процессам возможности такого выбора). Во-первых (и это действие обычно выполняется по умолчанию), ОС может заблокировать процесс, выдавший запрос, до освобождения требуемого ресурса. Во-вторых, ОС может не блокировать процесс, а вернуть ему отказ - сразу или после некоторой временной выдержки (timeout), в этом случае "умный" процесс может пока заняться другой работой, которую он может выполнить и без этого ресурса, а позже повторить запрос. Как ОС должна реагировать на запрос, который вообще не может быть выполнен (требуемого объема ресурсов просто нет в системе)? По нашему убеждению, такой запрос должен приводить к аварийному завершению выдавшего его процесса. Но если ОС допускает динамическую реконфигурацию ресурсов, то запрос может быть поставлен в очередь в ожидании момента, когда ресурс будет введен в систему. Такие нереализуемые запросы могут составлять серьезную неприятность в работе ОС, так как ресурс может никогда и не быть введен. Для избежания таких запросов целесообразно иметь в составе API вызов, возвращающий общее число ресурсов данного класса. Наконец, при невозможности удовлетворить запрос ОС может потребовать от процесса освободить уже имеющиеся в его распоряжении ресурсы. Если такая возможность имеется, то она может быть очень полезна для развязки тупиков (см. ниже).

Для каждого класса ресурсов ОС должна поддерживать дескриптор класса, в который должны входить:

Для каждой единицы ресурса имеется запись в таблице единиц, содержащая, как минимум, индикатор занятости ресурса и идентификатор процесса, которому ресурс распределен (если он не свободен).

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

Информация о ресурсах, выделенных процессу, хранится также в блоке контекста процесса.

5.2. Обедающие философы

Классической уже стала неформальная постановка задачи распределения ресурсов, носящая название "проблемы обедающих философов" и показанная на Рисунке 5.1.


Рис.5.1. Обедающие философы. Тупик

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

Если мы установим, что каждый философ должен взять одну палочку и не выпускать ее из рук до тех пор, пока не возьмет вторую палочку, то мы можем получить ситуацию, показанную на Рис.5.1. (стрелка от философа к палочке означает, что философ хочет взять эту палочку, стрелка в обратном направлении - что эту палочку этот философ уже взял.) Каждый из философов взял палочку справа от себя, но не может взять палочку слева. Ни один из философов не может ни есть, ни думать. Эта ситуация и называется тупиком (deadlock).

Если же мы установим, что философ должен взять обе палочки сразу, то может возникнуть ситуация, показанная на Рис.5.2. Философ Чжуан хочет взять палочки, но обнаруживает, что его правая палочка занята философом Мо. Чжуан ожидает. Тем временем философ Мэн берет свои палочки и начинает есть. Мо есть заканчивает, но Чжуан не может начать есть, так как теперь занята его левая палочка. Если Мо и Мэн едят попеременно, то Чжуан попадает в положение, которое называется голоданием (starvation) или бесконечным откладыванием.


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

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

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

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

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

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

Возможные стратегии распределения ресурсов располагаются между двумя полюсами - от самых либеральных до самых консервативных. Чем либеральнее стратегия, тем "охотнее" ОС удовлетворяет запросы на ресурсы. Но за слишком либеральную стратегию приходится расплачиваться возможностью возникновения тупика. Консервативные стратегии делают тупики невозможными в принципе, задачи обнаружения и развязки при применении таких стратегий не ставятся, но плата за это - частые отказы в выделении ресурсов, следовательно, снижение уровня мультипрограммирования, а следовательно, - и снижение пропускной способности. Ниже мы будем рассматривать стратегии предотвращения, двигаясь от консервативного полюса к либеральному в таком порядке:

Последовательное выделение.
Любыми ресурсами может одновременно пользоваться только один процесс. Если процесс A из предыдущего примера получил ресурс-принтер, то процессу B будет отказано даже в выделении ресурса-ленты. Очевидно, что такая стратегия делает тупики совершенно невозможными. Очевидно также, что некоторые процессы будут при этом простаивать совершенно неоправданно. Так, например, будет приостановлен некий процесс C, которому принтер и не нужен, а нужна только лента. Поскольку в число распределяемых ресурсов входят устройства ввода-вывода, а работают они медленно (пример - та же печать на принтере), простой может затянуться. Эта стратегия неоправданно снижает уровень мультипрограммирования и неэффективно использует ресурсы (они тоже простаивают), и может применяться только в таких ОС, в которых и расчетный уровень мультипрограммирования невысок.

Залповое выделение.
Процесс должен запрашивать/освобождать все используемые им ресурсы сразу. Эта стратегия позволяет параллельно выполняться процессам, использующим непересекающиеся подмножества ресурсов. (Процесс C работает с лентой, процесс D - с принтером.) Тупики по-прежнему невозможны, однако неоправданное удерживание ресурсов продолжается. Так, если процессу в ходе выполнения нужны ресурсы R1 и R2, причем ресурс R1 он использует все время своего выполнения t1, а ресурс R2 требуется ему только на время t2<<t1, то процесс вынужден удерживать за собой и ресурс R2 в течение всего времени t1.

В рамках залповой стратегии возможны два варианта: выделять все ресурсы при создании процесса и освобождать при его завершении или же позволить процессу запрашивать/освобождать ресурсы несколько раз в ходе своего выполнения (но обязательно все "залпом"). Очевидно, что второй вариант более либеральный, так как он позволяет уменьшить интервал времени удерживания ресурсов и разнести использование разных ресурсов по разным "залпам". Интересны различия в API для этих двух вариантов. В первом случае требования на ресурсы могут быть вообще вынесены за пределы программного кода процесса и задаваться во внешних описателях процесса (например, в языке управления заданиями). Во втором случае системный вызов getResource является обязательным, причем обязательно должна быть обеспечена возможность запроса в одном вызове ресурсов разных классов и выделение всех запрошенных ресурсов одной непрерываемой операцией.

Иерархическое выделение.
Все классы ресурсов разбиваются по уровням с номерами от 1 до N, каждый уровень содержит только один класс. Процесс имеет право запрашивать ресурсы только из классов с более высокими номерами, чем у тех, которыми он уже владеет. Эта стратегия также предотвращает возникновение тупиков. В каждый момент времени в системе один или несколько процессов имеют класс закрепленных за ними ресурсов выше, чем у других. Эти процессы, обладающие ресурсами высокого уровня, могут беспрепятственно выполняться и завершиться без блокировки. Следовательно, в каждый момент времени имеется хотя бы один способный к выполнению процесс. Если не будут поступать новые процессы, то все процессы, уже имеющиеся в системе, в конце концов завершатся - тупик отсутствует. Хотя в иерархической стратегии процесс ограничен в последовательности запросов и возможна ситуация, в которой он должен удерживать за собой ресурс более длительное время, чем это действительно необходимо, эта стратегия позволяет достичь неплохой эффективности, особенно при правильном распределении ресурсов по уровням. Целесообразно более высокие уровни назначать более дефицитным и более дорогостоящим ресурсам; как правило, и использование таких ресурсов является более скоротечным. Иерархическую стратегию применяет, например, OS/390 применительно к некоторым системным структурам данных.

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

Предварительные заявки и алгоритм банкира.
Эта стратегия названа так потому, что действия ОС напоминают действия банкира, выдающего ссуды клиентам, именно на таком примере эта стратегия была рассмотрена в первоисточнике [7]. Применение этой стратегии требует, чтобы процесс передал ОС "предварительную заявку" (advanced claim) и в ней указал максимальный объем ресурсов, который ему понадобится. В ходе выполнения процесс может в произвольном порядке запрашивать/освобождать ресурсы, не выходя, однако, за пределы заявленного объема. Ситуация в системе называется реализуемой, если

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

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

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

Пример представлен на Рисунке 5.3.: пусть у ОС имеется всего 12 ресурсов одного класса и на текущий момент выполняются три процесса - P1, P2 и P3, их заявки составляют 12, 4 и 8 ресурсов соответственно. На текущий момент времени процессу P1 выделено 4 ресурса, процессу P2 - 2, процессу P3 - 4 - Рис.5.3.а. В резерве ОС остаются, таким образом, 2 ресурса. Ситуация Рис.5.3.а является безопасной. ОС может выделить оставшиеся два ресурса процессу P2, и этот процесс, полностью получив по своей заявке, может завершится, тогда системный резерв увеличится до 4 ресурсов. Этот резерв ОС отдаст процессу P3, он, завершившись, передаст в резерв ОС 8 ресурсов, которых будет достаточно для удовлетворения заявки процесса P1. Ситуация станет опасной, если ОС выделит ресурс какому-либо другому процессу, кроме P2 - см.Рис.5.3.б. В этой ситуации ОС за счет своего резерва не может полностью удовлетворить ни одну заявку.



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


б) опасная
Рис.5.3. Анализ ситуации

Стратегия алгоритма банкира состоит в том, что запрос на ресурс удовлетворяется только в том случае, если выделение его не сделает ситуацию опасной. Алгоритмическая реализация проверки ситуации на безопасность состоит в "проигрывании" на списке процессов приведенного выше определения безопасной ситуации:

  1. Создать список, элементами которого являются процессы с их ресурсами и заявками.
  2. Если список пуст, - установить флаг безопасной ситуации и перейти к п. 7.
  3. Найти в списке процесс, заявка которого может быть удовлетворена из системного резерва.
  4. Если такой процесс не найден, - установить флаг опасной ситуации и перейти к п.7.
  5. Удалить найденный процесс из списка и передать те ресурсы, которыми он обладал в системный резерв.
  6. Перейти к п.2.
  7. Закончить проверку.

Алгоритм Габермана.
Другая алгоритмическая реализация стратегии с предварительными заявками известна как алгоритм Габермана. Этот алгоритм иллюстрируется следующим программным листингом:

    /* Алгоритм Габермана */
    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.

На Рисунке 5.4 показана работа алгоритма Габермана для ситуации, рассмотренной нами в примере выше. В графе "Событие" таблицы на рисунке указывается идентификатор процесса, которому выделяется единица ресурса; остальная часть каждой строки представляет состояние массива S после этого выделения. Строка "итог" показывает состояние на момент, когда ресурсы распределены так, как показано на Рис.5.3.а. (Убедитесь сами, что на конечное состояние массива S не влияет последовательность, в которой ресурсы выделялись.) Три нижние строки, в которых идентификатору процесса предшествует символ '*', показывают состояние массива S для альтернативных вариантов - выделения еще одного ресурс процессу P1 или P2, или P3. Видно, что только процесс P2 может получать ресурсы, не переводя систему в опасное состояние.


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

К сожалению, простая реализация алгоритма Габермана возможна только для одного класса ресурсов. При наличии в системе нескольких классов безопасность во всех классах по отдельности не гарантирует безопасности всей системы в целом. Так в примере про процессы A и B, использующие принтер и ленту, ситуация является безопасной как по классу принтеров, так и по классу лент, но в комплексе она является тупиковой. Алгоритм "проигрывания ситуации", требует значительного объема вычислений, но обеспечивает комплексный анализ безопасности.

Отметим, что алгоритм банкира, хотя и является значительно более либеральным, чем все рассмотренные выше, тоже не обеспечивает оптимального уровня мультипрограммирования. Опасная ситуация еще не является тупиковой. Так, ситуация, представленная на Рис.5.3.б, еще может разрядиться, если процесс P1 освободит хотя бы один из удерживаемых им ресурсов. ОС же в оценке ситуации исходит из прогноза о наихудшем развитии ситуации - предположения о том, что процессы будут только запрашивать ресурсы, а не освобождать их.

Возможны и стратегии, обеспечивающие еще более либеральную политику, но они требуют большей предварительной информации о процессе и, как правило, - большего объема вычислений при реализации стратегии. Например, нетрудно представить себе, что если ОС заранее знает, в какой последовательности процесс будет запрашивать/освобождать ресурсы, то она может обеспечить более эффективное управление ими. Но часто ли такая последовательность может быть известна заранее? Среди авторов [8, 20, 27 и др.] нет даже единодушного мнения о том, реально ли требовать от процесса предварительной заявки. На наш взгляд, однако, такое требование в большинстве случаев реально выполнимо: для пакетных процессов потребность в ресурсах бывает известна заранее, интерактивные же процессы в многопользовательских системах запускаются только зарегистрированными пользователями, указанный при регистрации пользователя доступный ему объем ресурсов может считаться такой заявкой.

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

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

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

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

Пусть в системе имеется 11 ресурсов одного класса, как представлено на Рисунке 5.5. Процесс P1 уже имеет 2 ресурса и запрашивает еще 2, процесс P2 уже имеет 3 и запрашивает еще 5, процесс P3 имеет 4 и запрашивает еще 4. Системный резерв - 2 ресурса. В зависимости от того, какие у процессов максимальные заявки (нам это неизвестно), ситуация может быть расценена как опасная или безопасная, но она определенно не является тупиковой. Процесс P1 может получить требуемые ресурсы, если он после этого закончится, то может быть удовлетворен запрос процесса P3, а после его завершения - процесса P2. Но если мы выделим еще хотя бы один ресурс процессу P3, ситуация станет тупиковой.



а) нетупиковая.

a)
б) тупиковая.
Рис.5.5. Анализ ситуации

При исследовании проблемы тупиков удобно представлять систему в виде графа. Пример такого графа показан на Рисунке 5.6.


Рис.5.6. Граф ресурсов и процессов

Графы такого рода содержат вершины двух типов - процессы (показаны окружностями) и классы ресурсов (показаны прямоугольниками), в последних указывается число ресурсов в классе. Дуги графа могут соединять только разнотипные вершины. Направленность дуг означает: от ресурса к процессу - ресурс выделен данному процессу, от процесса к ресурсу - процесс запрашивает ресурс. Признаком тупика является наличие в графе петли - такого пути, который начинается и заканчивается в одной вершине и из которого нет выхода. Так, на Рис. 5.5 представлена тупиковая ситуация: следование по графу любыми возможными путями заставит нас проходить одни и те же вершины. Если же мы уберем дугу, ведущую от процесса P3 к ресурсу R2, то появится выход из петли в вершину P3. Обнаружение тупика сводится к попытке редукции (сокращения) графа. Из графа удаляются те вершины-процессы, которые не имеют запросов или запросы которых могут быть удовлетворены. При этом сокращаются также и все дуги, связанные с этими вершинами. За счет освободившихся ресурсов появляется возможность сократить новые вершины-процессы и т.д. Если в графе нет петель, то после многократных сокращений нам удастся сократить все вершины-процессы.

Как часто следует выполнять проверку тупика? Обратим внимание на то, что если конструктор ОС отказывается от предупреждения тупиков, то он делает это в значительной степени из нежелания загружать систему значительным объемом вычислений по анализу безопасности при каждом запросе. Обнаружение тупика выполняется сходным образом с анализом безопасной ситуации и требует такого же объема вычислений, следовательно, желательно выполнять его как можно реже. Единственным событием, которое может перевести систему из нетупикового состояния в тупиковое, является поступление запроса, который не может быть удовлетворен. Следовательно, попытку обнаружения тупика надо производить только по этому событию, никак не чаще. В некоторых реализациях ОС применяет еще более ленивую политику. Неудовлетворенный запрос может привести к тупику, но может и не привести. "Ленивая" ОС не спешит выполнять проверку даже при поступлении такого запроса, а выжидает некоторое время: может быть "все само собой уладится" - и в большинстве случаев именно так и случается. И только, если запрос остается неудовлетворенным в течение определенного времени, ОС принимается за поиск тупика. Размер временной выдержки может определяться скоростными характеристиками запрашиваемого ресурса.

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

Желательно, чтобы "пострадавший" процесс был снова запущен, причем, возможно даже, с повышенным приоритетом. Но всякий ли процесс можно прервать на середине, а потом запустить сначала? Представьте себе процесс-программу, которая должна начислить взносы на 10 банковских счетов. Эта программа принудительно завершается в тот момент, когда она успела обработать только 5 счетов. Если при перезапуске программа начнет выполняться с начала, она повторно начислит взносы на первые 5 счетов. ОС не может знать, приведет ли перезапуск процесса к нежелательным последствиям, поэтому решение о повторном запуске обычно перекладывается на пользователя.

5.4. Бесконечное откладывание

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

Единственной дисциплиной, которая гарантирует, что все процессы в очереди будут в конце концов обслужены, является FCFS. Другие методы базируются на приоритетах - внешних или вычисляемых на основании размера запроса или/и безопасности ситуации. Очередь может быть упорядочена по возрастанию размера запроса, и при освобождении ресурсов последние могут отдаваться по запросу "самого подходящего" размера. Очередь может быть упорядочена в порядке возрастания опасности выделения ресурсов, и освободившийся ресурс может отдаваться тому процессу, запрос которого самый безопасный. При упорядочении очереди, процесс, выдавший самый большой или самый опасный запрос, может надолго в ней застрять, то есть, попасть в ситуацию бесконечного откладывания. С другой стороны, применение FCFS в чистом виде может привести к снижению уровня мультипрограммирования, к опасному состоянию и даже к тупику - если процесс со слишком большим запросом окажется первым в очереди. Отчасти это противоречие может быть сглажено, если мы допустим частичное выделение ресурсов: запрос, стоящий в очереди первым получает столько ресурсов, сколько ему можно выделить, сохраняя ситуацию безопасной, остальные - отдаются следующему в очереди процессу.

Поскольку тупиковая ситуация более опасна, чем бесконечное откладывание, ОС все же отдает предпочтение критериям безопасности, следовательно, заведомо предотвратить бесконечное откладывание невозможно. Бесконечное откладывание процесса устанавливается по времени его пребывания в очереди: если процесс пребывает в очереди дольше некоторого установленного времени, то считается, что он ожидает бесконечно. В зависимости от политики ОС в отношении справедливости обслуживания и от характеристик процесса (если они известны) допустимое время ожидания может устанавливаться большим или меньшим. Если же бесконечное откладывание установлено, то для его ликвидации ОС приостанавливает выдачу ресурсов новым процессам, пока не будет обслужен отложенный процесс.

Проблема тупиков до некоторой степени теряет актуальность в современных ОС, так как они имеют тенденцию к уменьшению количества неразделяемых ресурсов. Одним из способов сделать неразделяемое устройство разделяемым является буферизация, которую мы рассмотрим в следующей главе. Системные структуры данных разделяются с использованием средств взаимного исключения доступа, которым будет посвящена глава 8. Эта проблема, однако, становится все более актуальной для современных СУБД, которые обеспечивают одновременный доступ к ресурсам-данным для тысяч и десятков тысяч пользователей.

Контрольные вопросы

  1. Приведите примеры ресурсов: разделяемых и монопольно используемых, непрерывных и дискретных, потребляемых и повторно используемых.
  2. Какую информацию о ресурсах должна хранить ОС?
  3. Почему иерархическое выделение ресурсов является весьма популярным во многих ОС?
  4. В чем состоят ограничения на возможность применения алгоритма банкира?
  5. В чем сходство безопасной и беступиковой ситуаций? В чем их различия?
  6. В какие моменты ОС должна проводить действия по обнаружению тупика?
  7. Какие соображения могут влиять на выбор процесса-жертвы при ликвидации тупика?
  8. В чем достоинство дисциплины обслуживания FCFS для очередей к монопольно используемым ресурсам?

НазадОглавлениеВперед
Индекс