Модель повторно используемых ресурсов Холта.
Описание модели повторно используемых ресурсов
Модель повторно используемых ресурсов Холта была разработана для исследования параллельных процессов и, в частности, проблемы тупиков. Согласно этой модели система представляется как набор (множество) процессов и набор ресурсов, причем каждый из ресурсов состоит из фиксированного числа единиц. Любой процесс может изменять состояние системы с помощью запроса, получения или освобождения единицы ресурса.
В графической форме процессы и ресурсы представляются квадратами и кружками соответственно. Каждый кружок содержит некоторое количество маркеров (фишек) в соответствии с существующим количеством единиц этого ресурса. Дуга, указывающая из «процесса» на «ресурс», означает запрос одной единицы этого ресурса. Дуга, указывающая из «ресурса» на «процесс», представляет выделение ресурса процессу. Поскольку каждая единица любого ресурса типа SR может быть выделена одновременно не более чем одному процессу, то число дуг, исходящих из ресурса к различным процессам, не может превышать общего числа единиц этого ресурса. Такая модель называется графом повторно используемых ресурсов.
Пример 5.5. Одно из состояний системы из трех процессов с ресурсами типа SR представлено на рисунке 5.6.
Пусть процесс Р1 запрашивает две единицы ресурса R1 и одну единицу ресурса R2. Процессу Р2 принадлежат две единицы ресурса R1 и одна единица ресурса R3 и ему нужна одна единица R2. Процессу Р3 требуется по одной единице ресурсов R2 и R3. Предположим, что процесс Р1 получил запрошенную им единицу R2. Если принято правило, по которому процесс должен получить все запрошенные им ресурсы, прежде чем освободить хотя бы один из них, то удовлетворение запроса Р1 приведет к тупиковой ситуации: Р1 не сможет продолжиться до тех пор, пока Р2 не освободит единицу ресурса R1, а процесс Р2 не сможет продолжиться до тех пор, пока Р1 не освободит единицу R2; Р3 будет ждать освобождения R2 и R3, которое никогда не произойдет. Причиной этого дедлока являются неупорядоченные попытки процессов войти в критический интервал, связанный с выделением соответствующей единицы ресурса.
Рисунок 5.6 - Пример модели Холта для системы из трех процессов