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

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

Три вектора, изображенные справа от матриц, показывают соответственно существующие ресурсы (вектор Е), занятые ресурсы (вектор Р) и доступные ресурсы (вектор А).

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


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

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

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

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

3. Повторяем шаги 1 и 2 до тех пор, пока либо все процессы будут помечены как завершенные (в этом случае исходное состояние было безопасным), либо не останется процессов, чьи запросы могут быть удовлетворены (в этом случае система не была в безопасном состоянии).

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

Теперь вернемся к примеру, показанному на рис. 6.10. Текущее состояние безопасно. Предположим, что процесс В теперь сделал запрос на принтер. Этот запрос может быть удовлетворен, поскольку получающееся в результате состояние по-прежнему безопасно (процесс Б может завершить свою работу, затем это же могут сделать процесс А или процесс Е, а затем и все остальные).

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

Дейкстра впервые опубликовал алгоритм банкира в 1965 году. С тех пор практически каждая книга по операционным системам дает его подробное описание. Различным аспектам этого алгоритма было посвящено бесчисленное количество статей. К сожалению, мало у кого из авторов хватило смелости показать, что хотя алгоритм замечателен в теории, на практике он по существу бесполезен, поскольку нечасто можно определить заранее, каковы будут максимальные потребности процессов в ресурсах. Кроме того, количество процессов не фиксированно, оно динамически изменяется по мере входа пользователей в систему и выхода их из нее. И более того, ресурсы, считавшиеся доступными, могут внезапно пропасть (накопитель на магнитной ленте может сломаться). Таким образом, на практике лишь немногие системы, если таковые вообще имеются, используют алгоритм банкира для уклонения от взаимоблокировок. Но в некоторых системах для предотвращения взаимных блокировок используются эвристические правила, подобные алгоритму банкира. Например, сети могут дросселировать трафик, когда использование буфера превысит, скажем, 70 %, при оценке, что оставшихся 30 % будет достаточно для завершения обслуживания текущих пользователей и возвращения их ресурсов.

6.6.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

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

  1. КАК БАНКИР ИСПОЛЬЗУЕТ ПОДСОЗНАНИЕ
  2. Очерк 2: Джейн «Иметь полномочия, свободу и ресурсы для того, чтобы делать важные дела»
  3. Статья 540. Выполнение обязательства, в котором принимают участие несколько кредиторов или несколько должников
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ
  6. АЛГОРИТМ УДАЧИ
  7. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  8. Алгоритм исцеления:
  9. Алгоритм избавления от боли
  10. Алгоритм обработки результатов.
  11. 2. Специфика и алгоритмы работы с источниками.
  12. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  13. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  14. Статья 1111. Типовой лицензионный договор
  15. Таблица типов
  16. 4. Ресурсы (resources)
  17. 13.4. Типовые следственные ситуации