Реализация алгоритма банкира

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

Алгоритм банкира для безопасного распределения ресурсов операционной системы (без тупиков) был представлен Э. Дейкстрой и впервые был реализован в операционной системе THE в конце 1960;х годов. Это название возникло из-за того, что поведение алгоритма похоже на стратегию банкира при проведении банковских операций. Алгоритма банкира имеет следующие принципы:

• · Каждый процесс должен точно выделить свои потребности в ресурсах по максимуму.
• · Когда процесс запрашивает ресурс, ему, скорее всего придется подождать (часто выделение ресурсов по запросу происходит очень долго).
• · процесс, получаемый требуемые ресурсы, должен вернуть их системе за определённый период времени.

Когда при описании алгоритма банкира мы будем говорить о ресурсах, мы подразумеваем ресурсы одного и того же типа, и всё же мы будем распространять этот алгоритм на пулы ресурсов нескольких различных типов. Рассмотрим, например, проблему распределения определённого количества t одинаковых лентопротяжных устройств. Операционная система должна обеспечить распределение нескольких фиксированных чисел t одинаковых лентопротяжных устройств между определённым числом пользователей. Все пользователи заранее указывает на максимальное число устройств, которые ему понадобятся во время выполнения своей программы на машине. Операционная система принимает запрос пользователя только лишь в том случае, если максимальная потребность этого пользователя в лентопротяжных устройствах не выше t. Пользователь может освобождать или занимать устройства по одному, а может и все сразу. Возможно, что порой надо будет ждать, чтобы выделили дополнительное устройство. Текущее число устройств, которое было выделено пользователю, никогда не может превышать указанную максимальную потребность этого пользователя. Если операционная система может удовлетворить его максимальную потребность пользователя в устройствах, то пользователь гарантирует, что вернёт эти устройства в течении определённого времени (т.е. когда закончить его использовать). Текущее состояние вычислительной машины можно назвать только тогда надежным, когда операционная система может обеспечить всем текущим пользователям завершение их заданий в течение конечного времени. Если этого не случилось то тогда такое состояние системы называется ненадежным.

Представим теперь, что работают К пользователей. Пусть l (i) предполагает текущее количество лентопротяжных устройств, отведённых i пользователю. Если, например, пользователю 5 выделены четыре устройства, то l (5)=4. Пусть т (i) — максимальная потребность пользователя i, так что если пользователь 3 имеет максимальную потребность в двух устройствах, то m (3)=2. Пусть c (t) — текущая потребность пользователя, которая равна его максимальной потребности минус текущее число отведённых ему ресурсов. Если, например, пользователь 7 имеет максимальную потребность в шести лентопротяжных устройствах, а текущее количество отведённых ему устройств составляет четыре, то мы получим:

с (7)=m (7) — 1(7)=6 — 4=2.

В составе операционной системы имеются t лентопротяжных устройств. Число устройств, остающихся для распределения, обозначим через v. Тогда v равно t минус суммарное число устройств, отведённых различным пользователям.

Алгоритм банкира, который был предложен Дейкстрой, говорит о том, что выделять лентопротяжные устройства пользователям можно лишь только в том случае, если после очередного выделения устройств состояние системы остается надежным. Надежное состояние — это состояние, при котором все пользователи со временем могут завершить свою работу Ненадежное состояние — это состояние, которое может со временем может привести к тупику.