Вектор Available

Вектор Available — это концепция в теории вычислительных систем и операционных системах, обозначающая механизм, используемый для управления доступом к ресурсам и синхронизации процессов. В наиболее общем виде вектор Available представляет собой упорядоченный набор (массив) чисел, характеризующий текущее количество доступных экземпляров каждого типа ресурса в системе. Данная концепция является ключевым элементом алгоритмов предотвращения взаимоблокировок (deadlock avoidance), в частности алгоритма банкира (Banker’s algorithm), предложенного Эдсгером Дейкстрой.

Определение и назначение

В контексте операционных систем ресурсы делятся на типы (например, центральные процессоры, оперативная память, устройства ввода-вывода, файлы). Для каждого типа ресурса может существовать несколько идентичных экземпляров. Вектор Available фиксирует, сколько экземпляров каждого типа ресурса в данный момент свободно и может быть выделено процессам. Формально вектор Available — это массив длины \( m \), где \( m \) — количество типов ресурсов. Каждый элемент \( Available[j] \) равен количеству доступных экземпляров ресурса типа \( j \).

Основное назначение вектора Available — служить входными данными для алгоритмов, оценивающих, находится ли система в безопасном состоянии. Безопасным называется такое состояние, при котором существует последовательность выполнения процессов, позволяющая всем процессам завершиться без возникновения взаимоблокировки. Вектор Available динамически изменяется по мере выделения и освобождения ресурсов процессами.

История и происхождение

Концепция вектора Available была введена в рамках алгоритма банкира, который впервые был описан Эдсгером Дейкстрой в 1965 году в его работе «Cooperating sequential processes». Алгоритм был назван в честь банковской системы, где банк (операционная система) должен решить, можно ли выдать кредит (выделить ресурсы) клиенту (процессу), не рискуя обанкротиться (не допустить взаимоблокировки). Вектор Available в этой аналогии соответствует количеству наличных денег, которые банк имеет в данный момент.

Алгоритм банкира и его компоненты, включая вектор Available, стали классическим примером в учебных курсах по операционным системам. Однако на практике, в современных операционных системах (Windows, Linux, macOS) алгоритм банкира в чистом виде не применяется из-за сложности и накладных расходов. Вместо этого используются более простые методы предотвращения взаимоблокировок, такие как упорядочивание ресурсов или использование тайм-аутов. Тем не менее, концепция вектора Available остаётся важной теоретической моделью.

Компоненты алгоритма банкира

Алгоритм банкира оперирует несколькими структурами данных, среди которых вектор Available является одной из основных. В полном наборе также присутствуют:

• Максимальная потребность (Max) — матрица \( n \times m \), где \( n \) — количество процессов. Каждый элемент \( Max[i][j] \) показывает максимальное количество экземпляров ресурса типа \( j \), которое может запросить процесс \( i \).
• Выделенные ресурсы (Allocation) — матрица \( n \times m \), где \( Allocation[i][j] \) — количество экземпляров ресурса типа \( j \), уже выделенных процессу \( i \).
• Оставшаяся потребность (Need) — матрица \( n \times m \), рассчитываемая как \( Need[i][j] = Max[i][j] - Allocation[i][j] \). Она показывает, сколько ещё экземпляров каждого ресурса необходимо процессу для завершения.

Вектор Available в этом наборе является одномерным массивом, который обновляется после каждого выделения или освобождения ресурсов. Формула обновления: \( Available[j] = Available[j] - Allocation[i][j] \) при выделении и \( Available[j] = Available[j] + Allocation[i][j] \) при освобождении.

Применение в алгоритме проверки безопасного состояния

Алгоритм проверки, находится ли система в безопасном состоянии, использует вектор Available следующим образом:

1. Инициализация: Создаётся временный вектор \( Work = Available \) и массив \( Finish \) размером \( n \), где \( Finish[i] = false \) для всех процессов.
2. Поиск процесса: Ищется процесс \( i \), для которого \( Finish[i] = false \) и \( Need[i][j] \leq Work[j] \) для всех \( j \). Если такой процесс найден, то предполагается, что он завершится, и его ресурсы освобождаются: \( Work[j] = Work[j] + Allocation[i][j] \), а \( Finish[i] = true \).
3. Повторение: Шаг 2 повторяется до тех пор, пока либо все процессы не будут помечены как завершённые (\( Finish[i] = true \) для всех \( i \)), либо не останется ни одного процесса, удовлетворяющего условию.
4. Результат: Если все \( Finish[i] = true \), то состояние безопасно. В противном случае — небезопасно, и выделение ресурсов, которое привело к этому состоянию, должно быть отклонено.

Вектор Available играет здесь роль начального запаса ресурсов, который постепенно пополняется по мере гипотетического завершения процессов.

Пример работы

Рассмотрим систему с двумя типами ресурсов (R1 и R2) и тремя процессами (P1, P2, P3). Пусть вектор Available = [3, 2] (3 экземпляра R1 и 2 экземпляра R2 доступны). Матрицы Allocation и Max заданы:

• Allocation: P1 = [1, 0], P2 = [0, 1], P3 = [1, 1]
• Max: P1 = [2, 1], P2 = [1, 2], P3 = [2, 2]

Тогда Need = Max - Allocation:

• P1: [1, 1]
• P2: [1, 1]
• P3: [1, 1]

Алгоритм проверки:

• Work = [3, 2]. Ищем процесс с Need ≤ Work. Все три процесса удовлетворяют условию. Выбираем, например, P1. Work = [3+1, 2+0] = [4, 2]. Finish[1] = true.
• Work = [4, 2]. Ищем следующий. P2: Need = [1, 1] ≤ [4, 2]. Work = [4+0, 2+1] = [4, 3]. Finish[2] = true.
• Work = [4, 3]. P3: Need = [1, 1] ≤ [4, 3]. Work = [4+1, 3+1] = [5, 4]. Finish[3] = true.

Все Finish = true, состояние безопасно. Если бы вектор Available был меньше, например [0, 1], то ни один процесс не мог бы быть удовлетворён, и система оказалась бы в небезопасном состоянии.

Критика и ограничения

Несмотря на теоретическую элегантность, использование вектора Available в алгоритме банкира имеет ряд недостатков:

• Высокая вычислительная сложность: Алгоритм проверки безопасного состояния имеет сложность \( O(n^2 \cdot m) \), что может быть неприемлемо для систем с большим количеством процессов и ресурсов.
• Необходимость априорного знания: Для работы требуется, чтобы каждый процесс заранее объявил свою максимальную потребность в ресурсах (Max), что на практике часто невозможно или нецелесообразно.
• Статичность: Вектор Available и связанные с ним структуры данных не учитывают динамическое изменение потребностей процессов во время выполнения.
• Неприменимость в реальных ОС: Из-за указанных ограничений алгоритм банкира и его компоненты, включая вектор Available, в основном используются в образовательных целях и симуляторах, а не в промышленных операционных системах.

Интересные факты

• Концепция вектора Available является частным случаем более общего понятия «вектора состояния ресурсов» в теории распределённых систем.
• В некоторых реализациях алгоритма банкира вектор Available может быть многомерным, если ресурсы имеют сложную иерархическую структуру.
• Алгоритм банкира, включая вектор Available, был реализован в экспериментальной операционной системе THE (Technische Hogeschool Eindhoven), разработанной Дейкстрой.

Источники

• Dijkstra, E. W. (1965). «Cooperating sequential processes». Technological University Eindhoven.
• Silberschatz, A., Galvin, P. B., Gagne, G. (2018). «Operating System Concepts», 10th Edition. Wiley.
• Tanenbaum, A. S., Bos, H. (2015). «Modern Operating Systems», 4th Edition. Pearson.
• Stallings, W. (2017). «Operating Systems: Internals and Design Principles», 9th Edition. Pearson.