Операционные системы. Управление ресурсами


Тупики: предупреждение, обнаружение, развязка - часть 5


Другая алгоритмическая реализация стратегии с предварительными заявками известна как алгоритм Габермана. Этот алгоритм иллюстрируется следующим программным листингом:

/* Алгоритм Габермана */ static int S[r]; /* Начальные установки */ void HabervanInit(void) { int i; for (i=0; i<r; S[i++]=0); } /* Выделение ресурса */ int HabermanGet(int claim, int hold) { int i; for (i=0; i<claim-hold; i++) if (!S[i]) return -1; /* отказ */ for (i=0; i<claim-hold; S[i++]--); return 0; /* подтверждение */ } /* Освобождение ресурса */ void HabermanRelease(int claim, int hold) { int i; for (i=0; i<=claim-hold; S[i++]++); }

Если в системе имеется r ресурсов одного класса, то ОС создает массив S из r целых чисел. В ходе начальных установок в массив записывается убывающая последовательность чисел от r до 1. Если процесс, имеющий заявку на claim ресурсов и уже получивший hold ресурсов, запрашивает еще один ресурс, то (функция HabervanGet) все элементы массива S с номерами от 0 до claim-hold-1 включительно уменьшаются на 1. Индикатором опасного состояния является отрицательное значение любого элемента массива S.

На Рисунке 5.4 показана работа алгоритма Габермана для ситуации, рассмотренной нами в примере выше. В графе "Событие" таблицы на рисунке указывается идентификатор процесса, которому выделяется единица ресурса; остальная часть каждой строки представляет состояние массива S после этого выделения. Строка "итог" показывает состояние на момент, когда ресурсы распределены так, как показано на Рис.5.3.а. (Убедитесь сами, что на конечное состояние массива S не влияет последовательность, в которой ресурсы выделялись.) Три нижние строки, в которых идентификатору процесса предшествует символ '*', показывают состояние массива S для альтернативных вариантов - выделения еще одного ресурс процессу P1 или P2, или P3. Видно, что только процесс P2 может получать ресурсы, не переводя систему в опасное состояние.


Рис.5.4. Алгоритм Габермана

К сожалению, простая реализация алгоритма Габермана возможна только для одного класса ресурсов.


Начало  Назад  Вперед



Книжный магазин