Обнаружение взаимоблокировки при наличии нескольких ресурсов каждого типа

Рассмотрим систему.

m - число классов ресурсов (например: принтеры это один класс)

n - количество процессов

P(n) - процессы

E - вектор существующих ресурсов

E(i) - количество ресурсов класса i

A - вектор доступных (свободных) ресурсов

A(i) - количество доступных ресурсов класса i

С - матрица текущего распределения (какому процессу, какие ресурсы принадлежат)

R - матрица запросов (какой процесс, какой ресурс запросил)

C(ij) - количество экземпляров ресурса j, которое занимает процесс P(i).

R(ij) - количество экземпляров ресурса j, которое хочет получить процесс P(i).

Общее количество ресурсов равно сумме занятых и свободных ресурсов

Рассмотрим алгоритм поиска тупиков.

Алгоритм поиска тупиков при наличии нескольких ресурсов каждого типа

Если остаются не маркированные процессы, значит, есть тупик.

Рассмотрим работу алгоритма на реальном примере.

Используем алгоритм:

1. Третий процесс может получить желаемые ресурсы, т.к. R (2 1 0 0) = A (2 1 0 0)

2. Третий процесс освобождает ресурсы. Прибавляем их к A. А = (2 1 0 0) + (0 1 2 0) =(2 2 2 0). Маркируем процесс.

3. Может выполняться процесс 2. По окончании А=(4 2 2 1).

4. Теперь может работать первый процесс.

Тупиков не обнаружено.

Если рассмотреть пример, когда второму процессу требуются ресурсы (1 0 3 0), то два процесса окажутся в тупике.

Когда можно искать тупики:

o Когда запрашивается очередной ресурс (очень загружает систему)

o Через какой то промежуток времени (в интерактивных системах пользователь это ощутит)

o Когда загрузка процессора слишком велика

Выход из взаимоблокировки

Восстановление при помощи принудительной выгрузки ресурса

Как правило, требует ручного вмешательства (например: принтер).

Восстановление через откат

Состояние процессов записывается в контрольных точках, и в случае тупика можно сделать откат процесса на более раннее состояние, после чего он продолжит работу снова с этой точки.

С принтером опять будут проблемы.

Восстановление путем уничтожения процесса

Самый простой способ.

Но с принтером опять будут проблемы.

В реальных системах они не годятся.

Динамическое избежание взаимоблокировок

В этом способе ОС должна знать, является ли предоставление ресурса безопасным или нет.

Траектории ресурсов

Рассмотрим модель из двух процессов и двух ресурсов.

А1 - запрос принтера процессом А

А2 - запрос плоттера процессом А

А3 - освобождение принтера процессом А

А4 - освобождение плоттера процессом А

В1 - запрос плоттера процессом В

В2 - запрос принтера процессом В

В3 - освобождение плоттера процессом В

В4 - освобождение принтера процессом В

Динамическое избежание взаимоблокировок

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

Чтобы избежать тупика, процессам надо обойти прямоугольник, охватывающий всю заштрихованную область.

Безопасные и небезопасные состояния

В безопасном состоянии система может гарантировать, что все процессы закончат свою работу.

Рассмотрим систему.

10 экземпляров ресурса

3 процесса

Процесс А занял 3 экземпляра, но ему необходимо 9.

В этой ситуации можно спланировать так, сначала запустить процесс В, потом С и потом А.

Процессы заканчивают работу без тупиковой ситуации.

Рассмотрим другую ситуацию.

Процесс А занял 4 экземпляра.

Возникает небезопасное состояние.

В принципе, процесс А может в какой то момент ресурс освободить и тупика не возникнет.

Видно, что в этом случае не стоило давать ресурс процессу А.

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

" Банкира", потому что аналогия такая, клиенты-процессы, кредиты-ресурсы.

Рассмотрим систему:

Банкир может дать 10 кредитов (ресурсы).

К нему попеременно обращаются 4-ре клиента.

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

1. Банкиру поступает запрос от клиента на получение кредита

2. Банкир проверяет, приводит ли этот запрос к небезопасному состоянию.

3. Банкир в зависимости от этого дает или отказывает в кредите.

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

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться:

Популярное:

1. A. обеспечение выполнения расписания движения, корректировка движения в случае необходимости, оказание техпомощи ПС на линии, принятие мер в случае ДТП и др.
2. A. эксплуатируемые вручную или с применением ручного труда; без применения ручного труда (механические, автоматические и др.).
3. B. Специфика восприятия выразительных средств театра
4. Extended Primitives-расширенные примитивы
5. I ) При нейтральной оси в полке.
6. I. ДВА ТИПА ЭКОНОМИЧЕСКОЙ ТЕОРИИ
7. I. Заполнение фрагмента «Талон приема»
8. I. Общие сведения о воспитательном мероприятии
9. I. Прием и отправление поездов
10. I. Принятие нормативных актов органами государства.
11. I. ЭКГ при нарушениях ритма сердца (аритмиях)
12. I. Этические принципы психолога