Алгоритм Банкира

Оглавление

Введение        3

Глава 1. Информация об алгоритме        4

1. Алгоритм Банкира        4

1.1. Преимущество алгоритма банкира        7

1.2. Недостатки алгоритма банкира        7

2. Аналогичные алгоритмы        8

Глава 2. Применение алгоритма        11

1. Использования алгоритма Банкир        11

1.1. Структуры данных для алгоритма банкира        13

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

1.3. Алгоритм запроса ресурсов для процесса Pi – основная часть алгоритма банкира        15

1.4. Пример использования алгоритма банкира        15

2. Применение алгоритма Банкир        17

Заключение        20

Список литературы        21

Введение

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

Алгоритм банкира – алгоритм распределения ресурсов операционной системой, предоставляющий избежание тупиков. Его требование и принципы:

• возможны множественные экземпляры ресурсов;
• каждый процесс обязан заранее обозначить собственные максимальные потребности в ресурсах;
• при запросе ресурса вероятно ожидание процесса;
• после получения ресурсов процесс обязан возвратить их за ограниченный промежуток времени.

Основа алгоритма банкира – алгоритм запроса ресурсов для процесса. Он проводит проверку, не превысил ли процесс свои максимальные потребности (иначе – исключительная ситуация). Затем проверяется, не превышает ли требование существующих объемов доступных ресурсов, иначе – ожидание процессом их освобождения. В случае если все необходимые ресурсы с целью удовлетворения запроса существуют, алгоритм вычисляет новое состояние после удовлетворения запроса и проводит проверку его безопасность. В случае если новое состояние безопасно, запрос удовлетворяется. В случае если отсутствует, происходит возврат, и процесс ожидает освобождения необходимых ресурсов.

Глава 1. Информация об алгоритме

1. Алгоритм Банкира

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

К примеру, то что описанные алгоритмы, связанные термином «предотвращение взаимных блокировок», накладывают большие ограничения. В то же время алгоритмы, входящие в группу «избежание взаимных блокировок», требуются с целью собственной работы информации, которая не всегда существует.

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