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

Алгоритм планирования, позволяющий избегать взаимоблокировок, был разработан Дейкстрой фу^^а, 1965) и известен как алгоритм банкира. Он представляет собой расширение алгоритма обнаружения взаимоблокировок, представленного в разделе «Обнаружение взаимоблокировки при использовании одного ресурса каждого типа».
Модель алгоритма основана на примере банкира маленького городка, имеющего дело с группой клиентов, которым он выдал ряд кредитов. (Много лет назад банки не давали кредиты, пока не убеждались в том, что они могут быть возвращены.) Алгоритм проверяет, ведет ли выполнение каждого запроса к небезопасному состоянию. Если да, то запрос отклоняется. Если удовлетворение запроса к ресурсу приводит к безопасному состоянию, ресурс предоставляется процессу. На рис. 6.9, а показаны четыре клиента: А, В, С и Б, каждый из которых получил определенное количество единиц кредита (например, 1 единица равна 1000 долларов). Банкир знает, что не всем клиентам тотчас же понадобится максимальная сумма их кредита, поэтому для обслуживания их потребностей он зарезервировал только 10 единиц, а не все 22, которые нужны клиентам. (Чтобы провести аналогию с компьютерной системой, будем считать, что клиенты — это процессы, единицы — накопители на магнитной ленте, а банкир — операционная система.)

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

Рис.

6.9. Состояния распределения ресурсов: а — безопасное; б — безопасное; в —небезопасное

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

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

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

6.5.4.

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

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

  1. То, что очевидно для одного поколения, всегда было открытием для предыдущего.
  2. Тест для одного человека
  3. То, что хорошо для одного, не всегда хорошо для другого.
  4. 1. Создание видимости одного преступления для сокрытия другого
  5. КАК БАНКИР ИСПОЛЬЗУЕТ ПОДСОЗНАНИЕ
  6. Очерк 2: Джейн «Иметь полномочия, свободу и ресурсы для того, чтобы делать важные дела»
  7. § 24 Замена одного требования другим противоположным (компенсация). – Основания сей замены и законные для нее условия. – Однородность требований. – Отношение их по количеству. – Действие несостоятельности на замену. – Требования несоизмеримые. – Необязательность замены.
  8. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  9. АЛГОРИТМ
  10. АЛГОРИТМ УДАЧИ