Алгоритм Банкира в Operaтинговая система [Пример]
Натаниэль Брукс
⚡ Умное резюме
Банковский алгоритм — это метод предотвращения взаимоблокировок, который проверяет, обеспечивает ли распределение ресурсов безопасное состояние системы. Названный в честь банковского дела, он удовлетворяет запрос только в том случае, если остается достаточно ресурсов для удовлетворения всех процессов.
Что такое алгоритм банкира?
Алгоритм Банкира используется преимущественно в банковской системе для предотвращения тупик. Это поможет вам определить, будет ли предоставлен кредит или нет.
Этот алгоритм используется для проверки безопасного моделирования распределения для определения максимальной суммы, доступной для всех ресурсов. Он также проверяет все возможные действия, прежде чем определить, следует ли продолжать распределение или нет.
Например, в конкретном банке насчитывается X владельцев счетов, а общая сумма денег на их счетах составляет G.
Когда банк обрабатывает автокредит, программная система выполняет следующие действия:tracЭто сумма кредита, предоставленного на покупку автомобиля, из общей суммы денежных средств (G + фиксированный депозит + схема ежемесячного дохода + золото и т. д.), имеющихся у банка.
Автокредит предоставляется только в том случае, если остаток средств превышает G, поэтому все владельцы счетов могут снять G в любое время.
Обозначения алгоритма банкира
Вот некоторые важные обозначения, используемые в алгоритме банкира:
- X: Указывает общее количество процессов в системе.
- Y: указывает общее количество ресурсов, присутствующих в системе.
Доступны
[1:Y] указывает, сколько экземпляров каждого типа ресурса доступно.
Max
[1:X, 1:Y]: Выражает максимальное количество ресурсов типа j, которые может запросить процесс i.
распределение
[1:X, 1:Y]: Указывает ресурсы типа j, выделенные в данный момент процессу i.
Необходимость
Показывает, сколько дополнительных ресурсов каждого типа процессу i еще необходимо для выполнения своей задачи.
Пример алгоритма Банкира
Предположим, что у нас есть следующие ресурсы:
- 5 флэш-накопителей
- 2 принтеров
- 4 сканера
- 3 жестких диска
Здесь мы создали вектор, представляющий общее количество ресурсов: Доступно = (5, 2, 4, 3).
Предположим, что имеется четыре процесса. Доступные ресурсы уже распределены в соответствии с приведенной ниже матричной таблицей.
| Имя процесса | Пен Диски | Принтер | Сканер | жесткий диск |
|---|---|---|---|---|
| P | 2 | 0 | 1 | 1 |
| Q | 0 | 1 | 0 | 0 |
| R | 1 | 0 | 1 | 1 |
| S | 1 | 1 | 0 | 1 |
| Всего | 4 | 2 | 2 | 3 |
Здесь выделенные ресурсы представляют собой сумму ресурсов этих столбцов:
Выделено = (4, 2, 2, 3).
Мы также создаем матрицу для отображения количества каждого ресурса, необходимого для всех процессов. Эта матрица называется Необходимость = (3, 0, 2, 2).
| Имя процесса | Пен Диски | Принтер | Сканер | жесткий диск |
|---|---|---|---|---|
| P | 1 | 1 | 0 | 0 |
| Q | 0 | 1 | 1 | 2 |
| R | 2 | 1 | 0 | 0 |
| S | 0 | 0 | 1 | 0 |
Доступный вектор будет следующим:
Доступно = Доступно – Выделено
= (5, 2, 4, 3) – (4, 2, 2, 3)
= (1, 0, 2, 0)
Алгоритм запроса ресурсов
Алгоритм запроса ресурсов позволяет представить поведение системы, когда конкретный процесс запрашивает ресурсы.
Давайте разберемся в этом, следуя приведенным ниже шагам:
Шаг 1) Когда общее количество запрошенных экземпляров всех ресурсов станет меньше, чем позволяет процесс, переходите к шагу 2.
Шаг 2) Если количество запрошенных экземпляров каждого типа ресурсов меньше, чем количество доступных ресурсов каждого типа, процесс переходит к следующему шагу. В противном случае процесс приостанавливается из-за нехватки ресурсов.
Шаг 3) Ресурсы выделяются, как показано в приведенном ниже псевдокоде.
Available = Available – Request (y) Allocation(x) = Allocation(x) + Request(x) Need(x) = Need(x) - Request(x)
Этот заключительный шаг выполняется потому, что система должна исходить из предположения, что ресурсы выделены, поэтому после выделения остается меньше доступных ресурсов.
Характеристики алгоритма Банкира
Вот важные характеристики алгоритма банкира:
- Поддерживает множество ресурсов, удовлетворяющих требованиям как минимум одного клиента.
- Всякий раз, когда процесс получает все свои ресурсы, ему необходимо вернуть их в течение ограниченного периода времени.
- Когда процесс запрашивает ресурс, ему может потребоваться подождать.
- Система располагает ограниченным количеством ресурсов.
- Это расширенная функция для максимального распределения ресурсов.
Недостаток алгоритма Банкера
Вот минусы и недостатки использования банковского алгоритма:
- Это не позволяет процессу изменять свои максимальные потребности во время обработки.
- Это позволяет удовлетворять все запросы в ограниченные сроки, но один год является фиксированным периодом для этого.
- Все процессы должны заранее знать и указывать свои максимальные потребности в ресурсах.
