(повтор необходимых и достаточных условий (4 условия с прошлой лекции))

Решение проблемы - создание в системе условия, при которых возникновение тупиков в принципе невозможно (недопущение, устанение условия возникновения тупика (см. прошлую лекцию)).

Алгоритм Банкира (или он же Алгоритм Дейкстры) - обход тупиков: тупики в принципе возможны, но менеджер ресурсов выполняет определенные действия, в результате которых тупик не допускается.

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

Необходимо выполнить n! проверок.

В текущий момент времени можно считать, что кол-во процессов в системе фиксированное (система знает количество запущенных процессов). Количество ресурсов фиксированное.

Для повторно используемых ресурсов характерно постоянное кол-во единиц этих ресурсов в системе. Выход из строя ресурсов является аварийной ситуацией в системе.

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

Из-за огромных затрат на выполнение алгоритма банкира, он имеет теоретическое значение.

12:37

P1, ..., PN - N процессов

Количество ресурсов = а

Вектор b = (b1, ..., bN) - максимальный запрос ресурсов каждого процесса (заявка)

Каждый процесс делает заявку claim, где указывает свои максимальные потребности в каждом из ресурсов - такая заявка может быть реализована в виде вектора

// текущее распределение c (c1, ..., cN) - показывает общее выделение ресурсов для процессов (сколько единиц ресурса выделено каждому процессу) => Речь идёт только об одном ресурсе.

говорят, что состояние ресурсов реализуемо (ресурсы могут быть выделены) если выполняются:

1. 
2. c <= b
3. 

Число свободных ресурсов в текущий момент времени t определяется, как

4. r(t) >= 0 (ну оно вообще следует из условия 3, но она выделила)

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

Реализуемое состояние, которое описывается (a, b, c) является безопасным, если существует такая последовательность процессов S, что

(*)

Условие (*) показывает, что запрос i-ого процесса на j-й ресурс P_ij не должен превышать сумму свободных ресурсов и сумму ресурсов, которые будут освобождены процессами, которые предшествуют i-ому процессу в последовательности процессов.

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

Важно: существует ли вообще возможность проанализировать состояние системы? Необходимо иметь информацию о количестве процессов, заявках, количестве ресурса (свободных единиц ресурса).

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

Если состояние ресурсов безопасное и частичная последовательность S процессов удовлетворяет условию (*), то она может быть продлена. Если все процессы до k-ого могут завершить, то можно продлить на k + 1-й процесс и тд.

Это предварительное необходимое условие: анализ.

31:00

// пустая последовательность удовлетворяет (*)

1. S = 0

   // далее пробуем расширить S так, чтобы после добавления процесса k, S продолжила удовлетворять (*)

2. Добавление в S процесса Pk

   может быть неудачным:

   1. все процессы уже в S -- состояние безопасное.
   2. ни одно добавление не удовлетворяет (*) -- состояние небезопасное.

S -- частичная последовательность  
S* -- дополение к S  
T -- набор процессов для добавления в S  
R -- число свободных единиц ресурсов  

S = 0;
T = S*;
// пока есть кандидаты
while (T <> 0)
{
    Candidate = T[1];
    T = T - {T[1]};      // ушел из кандидатов
    if (B[Candidate] - C[Candidate]) <= R + SUM(S, C) // SUM см. ниже
    {
        S = S U {Candidate};
        T = S*;
    }
}
SAFE = (S* = 0); // количество кандидатов стало равным 0,
// определяем состояние системы как безопасное

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

Очевидно, что это строгая последовательность действий и данный алгоритм может быть упрощен благодаря следующим утверждениям:

Если безопасное состояние модифицировано путем назначения дополнительных ресурсов процессу $P_k$ и некоторая последовательность S, которая может быть частичной, содержит процесс $P_k$ и удовлетворяет условию (*), то это новое состояние так же безопасно.

48:30

// N - число процессов
// a - максимальное число ресурсов в системе
// b - вектор макс запросов ресурса
// c - вектор текущего распределения

N = 5;
a = 10;
b = (5, 8, 7, 6, 9);
с = (2, 3, 1, 1, 3) // в сумме 10 == a
// вып усл \sum c_i <= a

// Данное состояние безопасное? (оно реализуемое?)

/// ====================== условия ======================
    1. для любого k: bk <=a
    2. c <= b
    3. \sum_i^N c_i <= a
    4. r(t) = a - \sum_i^N c_i >= 0
/// ====================== условия ======================

// (1) и (3)
2 + 3 + 1 + 1 + 3 = 10 -> (1) - (3) удововлетворяются -> реализуемое 

S = 0;
T = S*: {1, 2, 3, 4, 5}
candidate = 1;
    T = {2, 3, 4, 5}
    b1 - c1 = 5 - 2 = 3 <= 0 -> нет
candidate = 2;
    T = {3, 4, 5}
    b2 - c2 = 8 - 3 = 5 <= 0 -> нет
candidate = 3;
    T = {4, 5}
    b3 - c3 = 7 - 1 = 6 <= 0 -> нет 
candidate = 4;
    T = {5}
    b4 - c4 = 6 - 1 = 5 <= 0 -> нет
candidate = 5;
    T = 0
    b5 - c5 = 9 - 3 = 6 <= 0 -> нет
------------------------------------------
T = 0, S* != 0
-> состояние является небезопасным

N=5, a=10
b = (5, 8, 7, 6, 9)
с = (1, 1, 1, 1, 2) // в сумме 6 == a - 4
// 4 свобод ед ресурса

2 + 3 + 1 + 1 + 3 = 6 -> 10 - 6 = 4 (свобод единицы ресурса)

S = 0;
T = S*: {1, 2, 3, 4, 5}

candidate = 1;
    T = {2, 3, 4, 5}
    b1 - c1 = 5 - 1 = 4 <= 4 + 0 -> да 
// только 4 свободные единицы ресурса,
// процесс 1 может завершиться и вернет системе единицу ресурса
    
candidate = 2;
    T = {3, 4, 5}
    b2 - c2 = 8 - 1 = 7 <= 4 + 1 -> нет
// даже если 1й процесс вернет системе единицу ресурса,
// в сумме это не удовлетворит потребность второго процесса

candidate = 3;
    T = {4, 5}
    b3 - c3 = 7 - 1 = 6 <= 4 + 1 -> нет 
// второй процесс не может завершиться, только первый - но в сумме этого недостаточно,
// чтобы удовлетворить потребность третьего процесса 

candidate = 4;
    T = {5}
    b4 - c4 = 6 - 1 = 5 <= 4 + 1 -> да
// ему понадобится 5 единиц ресурса, условие выполняется -
// 4й процесс может успешно завершиться: он вернет системе единицу ресурса -
// станет 6 свободных единиц
 
// опять проходим последовательность, начиная со второго процесса

b2 - c2 = 8 - 1 = 7 <= 4 + 1 + 1 -> нет
// не сможет успешно завершиться

b3 - c3 = 7 - 1 = 6 <= 4 + 1 + 1 -> да
// может успешно завершиться
    
S = {1, 4} U {3} = {1, 4, 3}

T = {2, 5}
candidate = 2
b2 - c2 = 8 - 1 = 7 <= 4 + 1 + 1 + 1-> да
// завершится и вернет 1

T = {5}
candidate = 5
b5 - c5 = 9 - 2 = 7 <= 4 + 1 + 1 + 1 + 1 -> да
----------------------------------------------------
S = {1, 4, 3, 2, 5}
T = 0
S* = 0 -> SAFE

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

Все рассуждения полезны в развитии подобных подходов, в частности, в 3 методе: обнаружение тупиков. В данной задаче мы работаем с векторами (задача крайне упрощена, рассматривается только 1 ресурс). Очевидно, если рассматривать систему с N ресурсами - возникает матрица. Для каждого типа ресурса будет вектор распределения, а уже эти вектора можно объединить только в матрицу.

Самый демократичный способ. Ресурсы распределяются по мере надобности. Вообще, система может быть динамической (то есть может меняться количество процессов/ресурсов?), но все вычисления выполняются для фиксированных матриц (списков), чтобы получить текущий результат. Обнаружение тупиков выполняется с помощью двудольного графа, который может быть представлен в виде матрицы.

Действительно, в теории тупиков вводится понятие двудольного (в оригинале "бихроматического") направленного графа. Систему можно описать таким графом. Почему? - потому что имеется 2 подмножества вершин графа: процессы и ресурсы. Эти подмножества не пересекаются (имеют разные свойства).

Пример простейшего графа тупика (P - процессы, R - ресурсы; этот же пример был в начале этой темы):

Стрелка от ресурса к процессу - приобретение или получение.

Стрелка от процесса к ресурсу - запрос.

Дуги могут быть записаны:

• Приобретение - (r, p) (типа от ресурса процессу)
• Запрос - (p, r) (наоборот)

На рисунке:

• r1 - 3 единицы
• r2 - 2 единицы

Требуется определить, является ли ситуация тупиковой или нет.

p1 запросил 2 единицы r1 и получил их. p2 запросил 1 единицу r2 и получил её. p1 дополнительно запрашивает еще 1 единицу r2, а p2 - еще 1 единицу r1. У системы есть необходимое количество ресурсов, чтобы удовлетворить потребности и процесса p1, и процесса p2 в единицах ресурсов (ситуация на картинке ниже)

Теперь p2 получил единицу ресурса r1 и ему требуется еще 1 единица ресурса r1. Кроме единицы ресурса r1 ему требуется единица ресурса r2.

Видно, что процесс p1 может завершиться. Значит процесс p1 может стать изолированной вершиной (может освободить занимаемые им ресурсы и эти ресурсы будут возвращены системе).

Когда p1 завершится, запросы p2 могут быть удовлетворены (следовательно и он сможет завершиться) и как итог обе вершины p1, p2 станут изолированы. Такой редукцией определяется, что система не находится в тупике (вершины процессов стали изолированы).

Ситуация может быть небезопасной и тогда никакого освобождения ресурсов быть не может. Пример графа - ниже.

1. Граф является полностью сокращаемым, если существует такая последовательность сокращений, которая устраняет все дуги. Если граф нельзя полностью сократить, то анализируемое состояние является тупиком (доказательства есть в книге Логическое программирование ОС, мы не рассматриваем)

   В последнем примере, например, видно, что не хватает свободных единиц ресурса.

2. Цикл в графе повторно используемых ресурсов является необходимым условием тупика (Тупик существует, если существует цикл (или как по-другому говорят: замкнутая цепь запросов))

3. Если состояние системы S не является состоянием тупика и S -[i]-> T (i должно быть над стрелочкой, Марк Даун не умеет так; обозначает переход из состояния S в состояние T), то в случае, если операция процесса pi есть запрос и в T pi находится в тупике, состояние T является состоянием тупика (проще: возникновение тупика в системе возможно только в результате запроса)

Очевидно, что двудольный граф может быть описан 2 матрицами (или 2 связными списками). Матричное представление более удобно представлять, поэтому мы будем работать с ним.

Матрица текущего распределения: B = {r, p}

- количество ресурса i выделенного j-ому процессу.

Матрица запросов: A = {p, r}

- запрос i-ого процесса на j-ый ресурс.

Есть прямой алгоритм (метод прямого обнаружения): последовательно рассматриваются запросы каждого процесса и определяется, может ли этот запрос быть удовлетворен. Последовательный просмотр матрицы запросов. В процессе просмотра определяется возможно сокращение соответствующей дуги или невозможно (если возможно - сокращается). Те процессы, которые останутся в этих матрицах после всех возможных сокращений будут находится в тупике. Очевидно, что для реализации нужно выполнить (m процессов, n ресурсов) - (mn)^2 проверок.

(более эффективный)

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

Вектор свободных единиц ресурсов: F = { ..., f_j, ... } f_j - количество свободных единиц j-ого ресурса.

В результате можно получить следующее выражение:

, где k_j - общее количество единиц j-ого ресурса.

Пусть имеется 2 вектора: C и D.

Тогда:

В результате, если i-ый процесс запрашивает j-ый ресурс и при этом строка запроса этого процесса меньше или равна вектора F, то такой запрос может быть удовлетворен (и могут быть выполнены соотвествующие сокращения; то есть такой процесс может продолжить выполнение и завершиться, то есть дуги, выходящие из этого процесса могут быть сокращены)