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

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

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

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

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

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