Алгоритм Габермана

Алгоритм Дейкстры.

Идея заключается в том, что:

Вводится понятие надежного состояния (это состояние, находясь в котором система не зависнет даже при самых неблагоприятных прогнозах).

Переход осуществляется из одного надежного состояния в другое.

Исходные данные для планирования – матрица ресурсов, процессов и т.д.

Каждый раз, когда запрашивается ресурс, то анализируется ситуация при каждом запросе процесса ресурсов; если выделение этого ресурса приводит к другим НС, то ресурс выделяется, в противном случае – нет.

Пример:

проц	рес	Макс. число рес.
P1
P2
P3

Свободно 2 ресурса. Какому процессу их отдать? – второму, т.к. он поработает и отдаст их системе, т.е. здесь имеет место НС.

Достоинства:

+ гибкий алгоритм;

+ позволяет теоретически показать, что процессы сходятся (если хватает ресурсов); если число ресурсов равно хотя бы максимальному числу необходимых ресурсов какого-либо из процессов, то можно продолжить выполнение хотя бы последовательно (в отсутствии многозадачности).

Недостатки:

- алгоритм работает для конкретного числа процессов;

- если число процессов n, то число ресурсов = n!

Это – графический режим.

			Вершины – процессы Дуги - ресурсы
		Суть метода заключается в предоставлении ресурса до тех пор, пока не образуется цикл в графе (из рисунка видно, что 3-ий ресурс не предоставляется первому процессу)

Достоинства:

1) нет ограничений на количество процессов;

2) сложность проверки на наличие цикла в графе.

Дата добавления: 2013-12-13