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

 

 

 

 

 

 

 

 

 

рис. 1 - Наиболее эффективные средства обеспечения ИБ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ГЛАВА3.РЕАЛИЗАЦИЯ АЛГОРИТМА БАНКИРА

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

Алгоритм банкира для безопасного распределения ресурсов операционной

системы (без тупиков) был представлен Э. Дейкстрой и впервые был реализован в

операционной системе 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 минус суммарное число устройств, отведённых различным пользователям.

Алгоритм банкира, который был предложен Дейкстрой, говорит о том, что

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

которое может со временем может привести к тупику.

3.2. Примеры надёжного и ненадёжного состояния

3.2.1 Пример надежного состояния

Представим, что   система имеет двенадцать одинаковых лентопротяжных

устройств, причем эти накопители распределяются между тремя пользователями,

как показано в таблице 1.

Таблица 1 – надёжное состояние

	Текущее количество выделенных устройств		Максимальная потребность
Пользователь (1)	1		4
Пользователь (2)	4		6
Пользователь (3)	5		8
Резерв		2

 

 

Это состояние является «надежным», поскольку при этом состоянии все три

пользователя закончат работу. Отметим, что в текущий момент пользователь (2)

имеет четыре выделенных ему устройства и со временем потребуется ещё больше, максимум шесть, т. е. два дополнительных устройства. В наличии у системы находится двенадцать устройств, из которых десять в реальном времени в работе, а два остальных — в резерве. Если два остальных резервных устройства, которые имеются в наличии, выделить пользователю (2), удовлетворяя тем самым максимальную потребность этого пользователя, то он может продолжать свою работу пока не завершится. После того как он завершился пользователь (2) освободит все шесть своих устройств так, что система сможет отдать их пользователю (1), а также пользователю (3). Пользователь (1) имеет одно устройство и со временем ему понадобится еще три. У пользователя (3) — пять устройств и со временем ему понадобится еще три. Если пользователь (2) возвращает шесть накопителей, то три из них можно отдать пользователю (1), который получает таким образом возможность для завершения  работы и затем

отдать четыре накопителя системе. После всего система может отдать три накопителя пользователю (3), который тем самым также получает возможность закончить работу. Таким образом, основной показатель надежного состояния – это присутствие последовательности действий, позволяющей всем пользователям

вовремя закончить работу.

3.2.2 Пример ненадежного состояния

Представим, что   двенадцать лентопротяжных устройств, распределены в

системе, согласно состоянию таблицы 2

Таблица 2 – ненадёжное состояние

	Текущее количество выделенных устройств		Максимальная потребность
Пользователь (1)	8		10
Пользователь (2)	2		5
Пользователь (3)	1		3
Резерв		1

 

 

Здесь из двенадцати  устройств системы одиннадцать в реальный момент

находятся в работе и только одно остается в резерве. В такой ситуации несмотря от того, какой из пользователей запросит данное резервное устройство, мы не сможем дать гарантию, что все три пользователя смогут закончить работу. И на самом деле, представим, что пользователь (1) запрашивает и получает последнее из оставшихся устройств. При этом случае возникновения тупиковой ситуации может возникнуть в трех случаях, когда каждому из трех процессов нужно запросить хотя бы одно дополнительное устройство, не возвратив определённое

количество устройств в общий пул ресурсов. Здесь надо отметить, что определение «ненадежное состояние» не предполагает, что в настоящий момент существует или в какое-то время может обязательно возникнуть тупиковая ситуация.

3.2.3 Пример перехода из надежного состояния в ненадежное

Если   известно, что   данное   состояние   надежно,   это не значит, что все

остальные состояния также будут надежными. Механизм распределения ресурсов должен точно анализировать все запросы на выделение ресурсов, прежде чем он их удовлетворит. представим, например, случай, когда система находится в текущем состоянии, показанном как таблица 3. Предположим теперь, что пользователь (3) запрашивает дополнительный ресурс. Если система удовлетворит этот запрос, то она перейдёт в новое состояние, показанное в таблице 4. Состояние в таблице 4 не должно привести к тупиковой ситуации. Если, конечно, состояние в таблице 3 было надежным, то состояние в таблице 4 сразу же станет ненадежным.

Таблица 3 – переход из надежного в ненадёжное состояние(1 часть)

	Текущее количество выделенных устройств		Максимальная потребность
Пользователь (1)	1		4
Пользователь (2)	4		6
Пользователь (3)	5		8
Резерв		2

 

Таблица 3 – переход из надежного в ненадёжное состояние(2 часть)

	Текущее количество выделенных устройств		Максимальная потребность
Пользователь (1)	1		4
Пользователь (2)	4		6
Пользователь (3)	6		8
Резерв		1

 

 

Состояние показанное в таблице 4 характеризует  систему, в   которой   нет гарантии успешного завершения всех процессов пользователей. Здесь в резерве останется только один ресурс, а на самом деле  в наличии должно быть как минимум два ресурса, чтобы либо пользователь (2), либо пользователь (3) могли завершить свою работу нормально, возвратить занимаемые ими ресурсы в систему и позволить оставшимся пользователям закончить работу.

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

Пусть в системе имеется n процессов и m типов ресурсов. Вектор Available

длины m содержит информацию о доступных ресурсах. Если Avaliable[j] = k, то в

системе в настоящем времени присутствует k единиц ресурса j. Матрица Max (n *

m) показывает максимальные потребности процессов в ресурсах. Если Max [i, j] = k, то процесс i может запросить, самое большее, k единиц ресурса j. Матрица Allocation (n * m) показывает фактическую отдачу системой ресурсов. Если Allocation [i, j] = k, то процессу i в настоящем времени выделено системой k единиц ресурса j. Матрица Need (n * m) показывает оставшиеся потребности процессов в ресурсах. Если Need [i, j] = k, то процессу i могут понадобиться еще k

единиц ресурса j для завершения работы. Имеет место следующее соотношение

между элементами матриц: Need [i, j] = Max [i, j] – Allocation [i, j].

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

В разделе структуры данных для алгоритма банкира, представлен алгоритм

проверки состояния системы на то, является ли алгоритм безопасным. Введем целочисленный вектор Work (длины m ) и булевский вектор Finish (длины n ). Вектор Work показывает пробные выделения ресурсов. Вектор Finish показывает данные о завершённости процессов при текущем состоянии системы.

Алгоритм безопасности.

Шаг 1. Инициализация.

Work = Available

Finish [i] = false для i = 1, …, n.

Здесь и в дальнейшем все присваивания и сравнения, в которых принимают участие векторы или матрицы, производится поэлементно.

Шаг 2. Найдём i, при значениях:

Finish [i] = false

Need [i] <= Work

Если такого i не существует, то тогда переходим к шагу 4.

Шаг 3.

Work = Work + Allocation [i]

Finish [i] = true

Переходим к шагу 2.

Шаг 4. Если Finish[i] = true для всех i = 1, …, n, то система в безопасном состоянии.

Необходимые пояснения к алгоритму:

• Алгоритм выполняет безопасную последовательность номеров процессов i,

если она есть. На каждом шаге, после нахождения очередного элемента последовательности, алгоритм моделирует освобождение i - м процессом ресурсов после того как его завершил.

• На шаге 1 присваивание векторов происходит поэлементно.
• На шаге 2, Need - матрица потребностей ( n * m ); Need[i] - строка матрицы,

представляющая вектор потребностей (длины m ) процесса i. Сравнение происходит поэлементно, и в результате считается верным, если соотношение сделано для всех элементов векторов. Проверяемое условие означает, что потребности процесса i с найденным номером могут быть выполнены немедленно, и процесс их получает и завершиться.

• На шаге 3, Allocation [i]   -  строка матрицы Allocation ,которая обозначает

текущие ресурсы, выделенные процессу i. С помощью вектора Work моделируется освобождение ресурсов i - м процессом, после этого процессу присваивается признак завершенности.

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

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

Для    основного   алгоритма  введем   вектор Requesti (длины m) – вектор

 запросов для процесса Pi . Если Requesti [j] = k, то процесс Pi запрашивает k экземпляров ресурса Rj.

Шаг 1. Если Requesti <= Need[i], переходим к шагу 2. Иначе надо сгенерировать исключительную ситуацию.

Шаг 2. Если Requesti <= Available, переходим к шагу 3. Иначе процесс будет ждать, так как данный ресурс недоступен.