bigpo.ru
добавить свой файл
1
Лекция 9.

Взаимная блокировка


Ресурс – это любой объект, который может запрашиваться и ожидаться процессом. Ресурс состоит из …

Есть две группы ресурсов:

  • Повторно-используемые ( не истощаются при использовании, обычно не возникают и не уничтожаются)

  • Расходуемые

Процесс, память, УВВ, файлы.


Пример 1. Повторно блокируемые ресурсы. Пусть есть два ресурса – А и В, процесс запрашивает сначала ресурс А, затем ресурс В. Когда подойдет очередь второго ресурса, произойдет взаимоблокировка. Может показаться, что данная ситуация является ошибкой программиста, но она имеет место в разработке ОС.


Пример 2. Пусть емкость оперативной памяти - 200 килобайт, загружены два процесса. Первый процесс запрашивает сначала 80 килобайт, а затем 60, второй процесс запрашивает сначала 70, потом 80 килобайт. Если процессы будут работать параллельно, то возникнут проблемы с распределением памяти.


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


Рассмотрим пример блокировки с расходуемыми ресурсами, который встречаются довольно часто. Есть два процесса, которые собираются обмениваться ресурсами, используя функции send и receive для получения и отправки сообщения:





Понятно, что если оба процесса одновременно получат сообщение, то они заблокируются оба навечно. Не существует надежного метода их обнаружения.


Запишем условия взаимных блокировок, их всего 4, первых 3 являются необходимыми:

  • ^ Взаимное исключение

Общий ресурс может использоваться одновременно только одним процессом

  • Удержание и ожидание

Процесс может удерживать выделенные ресурсы, во время ожидания других ресурсов.

  • Отсутствие перераспределения

Ресурс не может быть принудительно отобран у удерживающего его процесса

  • ^ Циклическое ожидание

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

Существует два режима доступа к ресурсу:

  • монопольный

  • разделяемый

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

^

Моделирование взаимоблокировок с помощью ресурсного графа.


Объявим два множества:





Ресурсный граф – это направленный двудольный граф с непересекающимся множеством ресурсов.

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

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


- дуга запроса, стрелка направлена от процесса к ресурсу, то есть процесс запрашивает одну единицу ресурса.

Наоборот, дуга от ресурса к процессу - дуга назначения, значит процессу выделена одна единица ресурса.

- дуга от расходуемого ресурса – дуга производителя. Обозначает, что процесс является производителем ресурса.

То есть с помощью ресурсного графа можно наглядно увидеть возможность взаимной блокировки.


Пример: есть два процесса и два ресурса:



Рассмотрим данные на этой картинке:

Р2 – производитель ресурса R2.


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





Рассмотрим использование данных графов:

Есть три процесса – A, B, C , и три ресурса – R, S , T


A

B

C

Запрос R

Запрос S

Запрос T

Запрос S

Запрос T

Запрос R

Освобождение R

Освобождение S

Освобождение T

Освобождение S

Освобождение T

Освобождение R


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

A запросил R

B запросил S

C запросил T

A запросил S

B запросил T

С запросил R





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


^

Четыре стратегии обработки взаимоблокировок.


  1. Пренебрежение взаимоблокировками

  2. Обнаружение и устранение – блокировке позволяют произойти, и предпринимают какие – либо действия для ее ликвидации

  3. Обход взаимоблокировок с помощью аккуратного распределения ресурсов

  4. Предотвращение взаимоблокировок с помощью предотвращения одного из четырех условий взаимоблокировок


Рассмотрим их более подробно.

    1. ^ Пренебрежение взаимоблокировками

Итак , самый распространенный вид в ОС разного плана, например в Windows. Политика данных действий такова – зачем тратить много ресурсов и времени на нахождение взаимоблокировок, если их можно просто игнорировать, но это уменьшает надежность работы ОС.


    1. ^ Обнаружение и устранение – блокировке позволяют произойти, и предпринимают какие – либо действия для ее ликвидации

2.1 Один ресурс каждого типа

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

2.2 Несколько ресурсов каждого типа

n – число процессов

m – число классов ресурсов

- количество единиц ресурса каждого типа

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

- вектор ресурсов, которые доступны в данный момент, он меняется во время работы

- матрица текущего распределения

- количество единиц , выделенных процессу.

- матрица текущего распределения ресурсов

Существующие ресурсы -

Доступные ресурсы -

Наш алгоритм будет ставить над процессами отметку, и после завершения алгоритма, какой-либо процесс остался без отметок, значит процесс находится в тупиковой ситуации. Алгоритм состоит из следующих пунктов:

  1. Ищем строку , для которой ( мы ищем процесс, все запросы которого могут быть удовлетворены при данных доступных ресурсах)

  2. Если такой процесс найден, маркируем его и прибавляем строку матрицы С к вектору А, и возвращаемся к шагу один.

  3. Если таких процессов не существует, работа алгоритма заканчивается.

Пример данного алгоритма:





, вычисляется путем вычитания из вектора А , суммы столбцов матрицы С.



Применяем наш алгоритм:

  1. Процесс 3 (он может быть завершен; помечаем его как завершенный и его строчку в матрице С прибавляем к матрице А). Тогда вектор А равен . Смотрим, чья строчка меньше вектора А.

  2. Процесс 2 завершается; маркируем его и прибавляем его строчку к вектору А

  3. Может быть завершен процесс 1; таким образом, в системе нет взаимоблокировок.

Когда нужно искать возникновение взаимоблокировок? Теоретически, когда запрашивается очередной ресурс, но это очень сложно. Когда обнаруживается блокировка, система должна вывести их из этого состояния. Существуют несколько способов:

  1. принудительно выгрузить ресурс для одного из процессов

  2. делать откаты при помощи контрольных точек

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


3. Избежание взаимоблокировок с помощью аккуратного распределения ресурсов. Это «алгоритм банкира».

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


Ранее мы считали, что процесс одновременно запрашивает все ресурсы. На самом деле, ресурсы запрашиваются поочередно. Рассмотрим такой пример: два процесса и два ресурса:




Можно изобразить поведение процессов на плоскости:





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